Namespaces
Variants

Iterator library

From cppreference.net
C++
Iterator library
Iterator concepts
Iterator primitives
Algorithm concepts and utilities
Indirect callable concepts
Common algorithm requirements
(C++20)
(C++20)
(C++20)
Utilities
(C++20)
Iterator adaptors
Range access
(C++11) (C++14)
(C++14) (C++14)
(C++11) (C++14)
(C++14) (C++14)
(C++17) (C++20)
(C++17)
(C++17)

Iteratoren sind eine Verallgemeinerung von Pointern , die es einem C++-Programm ermöglichen, mit verschiedenen Datenstrukturen (zum Beispiel Containern und Ranges (seit C++20) ) auf einheitliche Weise zu arbeiten. Die Iterator-Bibliothek bietet Definitionen für Iteratoren sowie Iterator-Traits, Adapter und Utility-Funktionen.

Da Iteratoren eine Abstraktion von Zeigern sind, sind ihre Semantiken eine Verallgemeinerung der meisten Semantiken von Zeigern in C++. Dies stellt sicher, dass jede Funktionsvorlage , die Iteratoren akzeptiert, ebenso gut mit regulären Zeigern funktioniert.

Inhaltsverzeichnis

Iteratorkategorien

Es gibt fünf (bis C++17) sechs (seit C++17) Arten von Iteratoren: LegacyInputIterator , LegacyOutputIterator , LegacyForwardIterator , LegacyBidirectionalIterator , LegacyRandomAccessIterator , und LegacyContiguousIterator (seit C++17) . (Siehe auch LegacyIterator für die grundlegendste Art von Iterator.)

Anstatt durch spezifische Typen definiert zu werden, wird jede Kategorie von Iteratoren durch die Operationen definiert, die auf ihnen ausgeführt werden können. Diese Definition bedeutet, dass jeder Typ, der die notwendigen Operationen unterstützt, als Iterator verwendet werden kann – zum Beispiel unterstützt ein Zeiger alle Operationen, die für einen LegacyRandomAccessIterator erforderlich sind, daher kann ein Zeiger überall verwendet werden, wo ein LegacyRandomAccessIterator erwartet wird.

Alle Iteratorkategorien (außer LegacyOutputIterator ) können in eine Hierarchie eingeordnet werden, wobei leistungsfähigere Iteratorkategorien (z.B. LegacyRandomAccessIterator ) die Operationen weniger leistungsfähiger Kategorien (z.B. LegacyInputIterator ) unterstützen. Wenn ein Iterator in eine dieser Kategorien fällt und zusätzlich die Anforderungen von LegacyOutputIterator erfüllt, dann wird er als veränderbarer Iterator bezeichnet und unterstützt sowohl Eingabe als auch Ausgabe. Nicht-veränderbare Iteratoren werden als konstante Iteratoren bezeichnet.

Iteratoren werden als constexpr -Iteratoren bezeichnet, wenn alle Operationen, die zur Erfüllung der Iterator-Kategorienanforderungen bereitgestellt werden, constexpr-Funktionen sind.

(since C++20)
Iteratorkategorie Operationen und Speicheranforderungen
Schreiben Lesen Inkrementieren Dekrementieren Direktzugriff
(Random Access) 		Kontinuierliche
Speicherung
ohne
Mehrfach-
durchläufe 		mit
Mehrfach-
durchläufen
LegacyIterator Erforderlich
LegacyOutputIterator Erforderlich Erforderlich
LegacyInputIterator
(veränderlich, falls Schreiboperation unterstützt) 		Erforderlich Erforderlich
LegacyForwardIterator
(erfüllt ebenfalls LegacyInputIterator ) 		Erforderlich Erforderlich Erforderlich
LegacyBidirectionalIterator
(erfüllt ebenfalls LegacyForwardIterator ) 		Erforderlich Erforderlich Erforderlich Erforderlich
LegacyRandomAccessIterator
(erfüllt ebenfalls LegacyBidirectionalIterator ) 		Erforderlich Erforderlich Erforderlich Erforderlich Erforderlich
LegacyContiguousIterator [1]
(erfüllt ebenfalls LegacyRandomAccessIterator ) 		Erforderlich Erforderlich Erforderlich Erforderlich Erforderlich Erforderlich
  1. ↑ LegacyContiguousIterator wurde erst in C++17 formal spezifiziert, aber die Iteratoren von std::vector , std::basic_string , std::array und std::valarray sowie Zeiger auf C-Arrays wurden in Pre-C++17-Code oft als separate Kategorie behandelt.

Hinweis: Ein Typ, der die erforderlichen Operationen in einer Zeile der obigen Tabelle unterstützt, fällt nicht notwendigerweise in die entsprechende Kategorie. Siehe die Kategorieseite für die vollständige Liste der Anforderungen.

Definitionen

Typen und Schreibbarkeit

Ein Eingabe-Iterator i unterstützt den Ausdruck * i , was zu einem Wert eines Objekttyps T führt, genannt der Werttyp des Iterators.

Ein Ausgabeiterator i hat eine nicht-leere Menge von Typen, die beschreibbar (bis C++20) indirectly_writable (seit C++20) für den Iterator sind; für jeden solchen Typ T ist der Ausdruck * i = o gültig, wobei o ein Wert vom Typ T ist.

Für jeden Iteratortyp X für den Gleichheit definiert ist (bis C++20) gibt es einen entsprechenden vorzeichenbehafteten Integer (bis C++20) integer-ähnlichen (seit C++20) Typ, der als Differenztyp des Iterators bezeichnet wird.

Dereferenzierbarkeit und Gültigkeit

Genau wie ein regulärer Zeiger auf ein array garantiert, dass es einen Zeigerwert gibt, der über das letzte Element des Arrays hinaus zeigt, so gibt es für jeden Iteratortyp einen Iteratorwert, der über das letzte Element einer entsprechenden Sequenz hinaus zeigt. Ein solcher Wert wird als past-the-end -Wert bezeichnet.

Werte eines Iterators i , für die der Ausdruck * i definiert ist, werden als dereferenzierbar bezeichnet. Die Standardbibliothek geht niemals davon aus, dass Endwerte dereferenzierbar sind.

Iteratoren können auch singuläre Werte haben, die keiner Sequenz zugeordnet sind. Die Ergebnisse der meisten Ausdrücke sind für singuläre Werte undefiniert; die einzigen Ausnahmen sind

  • die Zuweisung eines nicht-singulären Werts an einen Iterator, der einen singulären Wert hält,
  • die Zerstörung eines Iterators, der einen singulären Wert hält, und,
  • für Iteratoren, die die DefaultConstructible Anforderungen erfüllen, die Verwendung eines wertinitialisierten Iterators als Quelle einer Kopier- oder Verschiebeoperation (seit C++11) .

In diesen Fällen wird der singuläre Wert auf dieselbe Weise überschrieben wie jeder andere Wert. Dereferenzierbare Werte sind immer nicht-singulär.

Ein invalid Iterator ist ein Iterator, der singular sein kann.

Bereiche

Die meisten algorithmischen Templates der Standardbibliothek, die auf Datenstrukturen operieren, haben Schnittstellen, die Bereiche verwenden.

Ein Iterator j wird als erreichbar von einem Iterator i bezeichnet, genau dann wenn es eine endliche Folge von Anwendungen des Ausdrucks ++ i gibt, die i == j bewirkt. Wenn j von i erreichbar ist, beziehen sie sich auf Elemente derselben Sequenz.

Ein Bereich ist ein Paar von Iteratoren, die den Beginn und das Ende der Berechnung bezeichnen. Ein Bereich [ i , i ) ist ein leerer Bereich; im Allgemeinen bezieht sich ein Bereich [ i , j ) auf die Elemente in der Datenstruktur, beginnend mit dem durch i gezeigten Element bis zu, aber nicht einschließlich des durch j gezeigten Elements.

Ein Bereich [ i , j ) ist gültig genau dann wenn j von i erreichbar ist.

(bis C++20)

Ein Range kann entweder bezeichnet werden durch

  • [ i , s ) , mit einem Iterator i und einem Sentinel s , die den Anfang und das Ende der Berechnung bezeichnen ( i und s können unterschiedliche Typen haben), oder
  • i + [ ​ 0 ​ , n ) , mit einem Iterator i und einer Anzahl n , die den Anfang und die Anzahl der Elemente bezeichnen, auf die die Berechnung angewendet werden soll.
Iterator-Sentinel-Range

Ein Iterator und ein Sentinel, die einen Range bezeichnen, sind vergleichbar. [ i , s ) ist leer, wenn i == s ; andernfalls bezieht sich [ i , s ) auf die Elemente in der Datenstruktur, beginnend mit dem Element, auf das i zeigt, und bis zu, aber nicht einschließlich des Elements, auf das der erste Iterator j zeigt, für den j == s gilt.

Ein Sentinel s wird erreichbar von einem Iterator i genannt, genau dann wenn es eine endliche Folge von Anwendungen des Ausdrucks ++ i gibt, die i == s bewirkt.

Wenn s von i erreichbar ist, bezeichnet [ i , s ) einen gültigen Range.

Gezählter Range

Ein gezählter Range i + [ ​ 0 ​ , n ) ist leer, wenn n == 0 ; andernfalls bezieht sich i + [ ​ 0 ​ , n ) auf die n Elemente in der Datenstruktur, beginnend mit dem Element, auf das i zeigt, und bis zu, aber nicht einschließlich des Elements, auf das das Ergebnis von n Anwendungen von ++ i zeigt.

Ein gezählter Range i + [ ​ 0 ​ , n ) ist gültig genau dann wenn

  • n == 0 ; oder
  • alle der folgenden Bedingungen erfüllt sind:
    • n ist positiv,
    • i ist dereferenzierbar, und
    • ++ i + [ ​ 0 ​ , -- n ) ist gültig.
(seit C++20)

Das Ergebnis der Anwendung von Funktionen der Standardbibliothek auf ungültige Bereiche ist undefiniert.

Iterator-Konzepte (seit C++20)

Ein neues System von Iteratoren basierend auf Concepts , das sich von C++17-Iteratoren unterscheidet. Während die grundlegende Taxonomie ähnlich bleibt, sind die Anforderungen für einzelne Iteratorkategorien etwas anders.

Definiert im Namespace std
(C++20)
spezifiziert, dass ein Typ indirekt lesbar ist durch Anwendung des Operators *
(Konzept)
(C++20)
spezifiziert, dass ein Wert in das referenzierte Objekt eines Iterators geschrieben werden kann
(Konzept)
(C++20)
spezifiziert, dass ein semiregular Typ mit Prä- und Post-Inkrementoperatoren inkrementiert werden kann
(Konzept)
(C++20)
spezifiziert, dass die Inkrementoperation auf einem weakly_incrementable Typ gleichheitserhaltend ist und dass der Typ equality_comparable ist
(Konzept)
(C++20) (C++20)
spezifiziert, dass ein Typ sich wie ein (vorzeichenbehafteter) Ganzzahltyp verhält
( Nur zur Darstellung* )
(C++20)
spezifiziert, dass Objekte eines Typs inkrementiert und dereferenziert werden können
(Konzept)
(C++20)
spezifiziert, dass ein Typ ein Sentinel für einen input_or_output_iterator Typ ist
(Konzept)
(C++20)
spezifiziert, dass der - Operator auf einen Iterator und einen Sentinel angewendet werden kann, um ihre Differenz in konstanter Zeit zu berechnen
(Konzept)
(C++20)
spezifiziert, dass ein Typ ein Eingabeiterator ist, d.h. seine referenzierten Werte können gelesen werden und er kann sowohl prä- als auch post-inkrementiert werden
(Konzept)
(C++20)
spezifiziert, dass ein Typ ein Ausgabeiterator für einen gegebenen Werttyp ist, d.h. Werte dieses Typs können in ihn geschrieben werden und er kann sowohl prä- als auch post-inkrementiert werden
(Konzept)
(C++20)
spezifiziert, dass ein input_iterator ein Vorwärtsiterator ist, der Gleichheitsvergleich und Mehrfachdurchläufe unterstützt
(Konzept)
(C++20)
spezifiziert, dass ein forward_iterator ein Bidirektionaler Iterator ist, der Rückwärtsbewegung unterstützt
(Konzept)
(C++20)
spezifiziert, dass ein bidirectional_iterator ein Iterator mit wahlfreiem Zugriff ist, der Fortbewegung in konstanter Zeit und Indizierung unterstützt
(Konzept)
(C++20)
spezifiziert, dass ein random_access_iterator ein zusammenhängender Iterator ist, der auf Elemente verweist, die zusammenhängend im Speicher liegen
(Konzept)

Iterator-Assoziierte Typen (seit C++20)

Definiert im Namespace std
(C++20)
berechnet den Differenztyp eines weakly_incrementable Typs
(Klassentemplate)
(C++20)
berechnet den Werttyp eines indirectly_readable Typs
(Klassentemplate)
(C++20) (C++20) (C++23) (C++20) (C++20) (C++20)
berechnet die assoziierten Typen eines Iterators
(Alias-Template)

Iterator-Primitive

Bietet eine einheitliche Schnittstelle für die Eigenschaften eines Iterators
(Klassen-Template)
(C++20)
Leere Klassentypen zur Kennzeichnung von Iterator-Kategorien
(Klasse)
(veraltet in C++17)
Basisklasse zur Vereinfachung der Definition erforderlicher Typen für einfache Iteratoren
(Klassen-Template)

Iterator-Anpassungspunkte (seit C++20)

Definiert im Namespace std::ranges
(C++20)
konvertiert das Ergebnis der Dereferenzierung eines Objekts in seinen assoziierten Rvalue-Referenztyp
(Customization Point Object)
(C++20)
tauscht die von zwei dereferenzierbaren Objekten referenzierten Werte
(Customization Point Object)

Algorithmus-Konzepte und Hilfsmittel (seit C++20)

Eine Reihe von Konzepten und zugehörigen Utility-Templates, die dazu dienen, die Einschränkung allgemeiner Algorithmusoperationen zu erleichtern.

Definiert im Header <iterator>
Definiert im namespace std
Indirekte aufrufbare Konzepte
(C++20) (C++20)
spezifiziert, dass ein aufrufbarer Typ mit dem Ergebnis der Dereferenzierung eines indirectly_readable Typs aufgerufen werden kann
(Konzept)
(C++20)
Spezifiziert, dass ein aufrufbarer Typ, wenn er mit dem Ergebnis der Dereferenzierung eines indirectly_readable Typs aufgerufen wird, das predicate Konzept erfüllt
(Konzept)
(C++20)
spezifiziert, dass ein aufrufbarer Typ, wenn er mit dem Ergebnis der Dereferenzierung zweier indirectly_readable Typen aufgerufen wird, das Konzept predicate erfüllt
(Konzept)
(C++20)
spezifiziert, dass ein aufrufbarer Typ, wenn er mit dem Ergebnis der Dereferenzierung zweier indirectly_readable Typen aufgerufen wird, equivalence_relation erfüllt
(Konzept)
(C++20)
spezifiziert, dass ein aufrufbarer Typ, wenn er mit dem Ergebnis der Dereferenzierung zweier indirectly_readable Typen aufgerufen wird, strict_weak_order erfüllt
(Konzept)
Allgemeine Algorithmusanforderungen
(C++20)
spezifiziert, dass Werte von einem indirectly_readable Typ zu einem indirectly_writable Typ verschoben werden können
(Konzept)
(C++20)
spezifiziert, dass Werte von einem indirectly_readable Typ zu einem indirectly_writable Typ verschoben werden können und dass die Verschiebung über ein Zwischenobjekt erfolgen kann
(Konzept)
(C++20)
spezifiziert, dass Werte von einem indirectly_readable Typ zu einem indirectly_writable Typ kopiert werden können
(Konzept)
(C++20)
spezifiziert, dass Werte von einem indirectly_readable Typ zu einem indirectly_writable Typ kopiert werden können und dass die Kopie über ein Zwischenobjekt ausgeführt werden kann
(Konzept)
(C++20)
spezifiziert, dass die Werte, auf die von zwei indirectly_readable Typen referenziert wird, ausgetauscht werden können
(Konzept)
(C++20)
spezifiziert, dass die von zwei indirectly_readable Typen referenzierten Werte verglichen werden können
(Konzept)
(C++20)
spezifiziert die allgemeinen Anforderungen von Algorithmen, die Elemente direkt umordnen
(Konzept)
(C++20)
spezifiziert die Anforderungen von Algorithmen, die sortierte Sequenzen durch Kopieren von Elementen in eine Ausgabesequenz zusammenführen
(Konzept)
(C++20)
spezifiziert die allgemeinen Anforderungen von Algorithmen, die Sequenzen in geordnete Sequenzen umwandeln
(Konzept)
Utilities
(C++20)
berechnet das Ergebnis des Aufrufs eines aufrufbaren Objekts auf das Ergebnis der Dereferenzierung einiger indirectly_readable Typen
(Alias-Template)
(C++20)
Hilfs-Template zur Spezifikation der Constraints für Algorithmen, die Projektionen akzeptieren
(Alias-Template)
(C++26)
berechnet den Werttyp eines indirectly_readable Typs durch Projektion
(Alias-Template)

Iterator-Adapter

Iterator-Adapter für die Traversierung in umgekehrter Reihenfolge
(Klassentemplate)
(C++14)
erstellt einen std::reverse_iterator mit vom Argument abgeleitetem Typ
(Funktionstemplate)
Iterator-Adapter für das Einfügen am Ende eines Containers
(Klassen-Template)
erstellt einen std::back_insert_iterator vom vom Argument abgeleiteten Typ
(Funktions-Template)
Iterator-Adapter für das Einfügen am Anfang eines Containers
(Klassentemplate)
erstellt einen std::front_insert_iterator vom vom Argument abgeleiteten Typ
(Funktions-Template)
Iterator-Adapter für das Einfügen in einen Container
(Klassentemplate)
erstellt einen std::insert_iterator vom aus dem Argument abgeleiteten Typ
(Funktionsschablone)
(C++23)
Iterator-Adapter, der einen Iterator in einen konstanten Iterator umwandelt
(Klassentemplate)
(C++23)
berechnet einen konstanten Iteratortyp für einen gegebenen Typ
(Alias-Template)
(C++23)
berechnet einen Sentinel-Typ zur Verwendung mit konstanten Iteratoren
(Alias-Template)
(C++23)
erstellt einen std::const_iterator vom aus dem Argument abgeleiteten Typ
(Funktions-Template)
(C++23)
erstellt einen std::const_sentinel mit vom Argument abgeleitetem Typ
(Funktionsschablone)
(C++11)
Iterator-Adapter, der zu einem Rvalue dereferenziert
(Klassentemplate)
(C++20)
Sentinel-Adapter für std::move_iterator
(Klassentemplate)
(C++11)
erstellt einen std::move_iterator mit vom Argument abgeleitetem Typ
(Funktions-Template)
(C++20)
passt einen Iteratortyp und seinen Sentinel an einen gemeinsamen Iteratortyp an
(Klassentemplate)
(C++20)
Standardsentinel zur Verwendung mit Iteratoren, die die Grenze ihres Bereichs kennen
(Klasse)
(C++20)
Iterator-Adapter, der den Abstand zum Ende des Bereichs verfolgt
(Klassentemplate)
(C++20)
Sentinel, der stets ungleich mit jedem weakly_incrementable Typ verglichen wird
(Klasse)

Stream-Iteratoren

Eingabe-Iterator, der aus std::basic_istream liest
(Klassentemplate)
Ausgabe-Iterator, der in std::basic_ostream schreibt
(Klassentemplate)
Eingabe-Iterator, der aus std::basic_streambuf liest
(Klassentemplate)
Ausgabe-Iterator, der in std::basic_streambuf schreibt
(Klassentemplate)

Iterator-Operationen

Definiert im Header <iterator>
bewegt einen Iterator um eine gegebene Distanz
(Funktions-Template)
gibt die Distanz zwischen zwei Iteratoren zurück
(Funktions-Template)
(C++11)
erhöht einen Iterator
(Funktions-Template)
(C++11)
verringert einen Iterator
(Funktions-Template)
(C++20)
bewegt einen Iterator um eine gegebene Distanz oder zu einer gegebenen Grenze
(Algorithmus-Funktionsobjekt)
(C++20)
gibt die Distanz zwischen einem Iterator und einem Sentinel zurück, oder zwischen Anfang und Ende eines Bereichs
(Algorithmus-Funktionsobjekt)
(C++20)
erhöht einen Iterator um eine gegebene Distanz oder zu einer Grenze
(Algorithmus-Funktionsobjekt)
(C++20)
verringert einen Iterator um eine gegebene Distanz oder zu einer Grenze
(Algorithmus-Funktionsobjekt)

Bereichszugriff (since C++11)

Diese nicht-elemente Funktionstemplates bieten eine generische Schnittstelle für Container, einfache Arrays und std::initializer_list .

Definiert in Header <array>
Definiert in Header <deque>
Definiert in Header <flat_map>
Definiert in Header <flat_set>
Definiert in Header <forward_list>
Definiert in Header <inplace_vector>
Definiert in Header <iterator>
Definiert in Header <list>
Definiert in Header <map>
Definiert in Header <regex>
Definiert in Header <set>
Definiert in Header <span>
Definiert in Header <string>
Definiert in Header <string_view>
Definiert in Header <unordered_map>
Definiert in Header <unordered_set>
Definiert in Header <vector>
Definiert in Namespace std
(C++11) (C++14)
gibt einen Iterator zum Anfang eines Containers oder Arrays zurück
(Funktions-Template)
(C++11) (C++14)
gibt einen Iterator zum Ende eines Containers oder Arrays zurück
(Funktions-Template)
(C++14)
gibt einen Reverse-Iterator zum Anfang eines Containers oder Arrays zurück
(Funktions-Template)
(C++14)
gibt einen Reverse-End-Iterator für einen Container oder ein Array zurück
(Funktions-Template)
(C++17) (C++20)
gibt die Größe eines Containers oder Arrays zurück
(Funktions-Template)
(C++17)
prüft, ob der Container leer ist
(Funktions-Template)
(C++17)
erhält den Zeiger auf das zugrundeliegende Array
(Funktions-Template)

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR Angewendet auf Verhalten wie veröffentlicht Korrektes Verhalten
CWG 1181 C++98 Array-Typen konnten keine Werttypen sein sie können
LWG 208 C++98 Past-the-end-Iteratoren waren immer nicht-singulär sie können singulär sein
LWG 278 C++98 Die Gültigkeit eines Iterators war nicht definiert als immer nicht-singulär definiert
LWG 324 C++98 Output-Iteratoren hatten Werttypen Output-Iteratoren haben stattdessen beschreibbare Typen
LWG 407 C++98 Singuläre Iteratoren konnten nicht zerstört werden erlaubt
LWG 408
( N3066 ) 		C++98 Singuläre Iteratoren konnten nicht kopiert werden erlaubt wenn sie wertinitialisiert sind
LWG 1185
( N3066 ) 		C++98 LegacyForwardIterator , LegacyBidirectionalIterator
und LegacyRandomAccessIterator
erfüllen immer LegacyOutputIterator 		sie erfüllen möglicherweise nicht LegacyOutputIterator
LWG 1210
( N3066 ) 		C++98 Die Definition von Iterator-Singularität und
Erreichbarkeit hing von Containern ab 		hängt stattdessen von Sequenzen ab
LWG 3009 C++17 <string_view> stellte die
Range-Zugriffsfunktionsvorlagen nicht bereit 		stellt diese Vorlagen bereit
LWG 3987 C++23 <flat_map> und <flat_set> stellten
die Range-Zugriffsfunktionsvorlagen nicht bereit 		stellen diese Vorlagen bereit