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)

Les itérateurs sont une généralisation des pointeurs qui permettent à un programme C++ de travailler avec différentes structures de données (par exemple, conteneurs et ranges (depuis C++20) ) de manière uniforme. La bibliothèque d'itérateurs fournit des définitions pour les itérateurs, ainsi que des traits d'itérateurs, des adaptateurs et des fonctions utilitaires.

Puisque les itérateurs sont une abstraction des pointeurs, leur sémantique est une généralisation de la plupart de la sémantique des pointeurs en C++. Cela garantit que chaque function template qui prend des itérateurs fonctionne aussi bien avec des pointeurs classiques.

Table des matières

Catégories d'itérateurs

Il existe cinq (jusqu'au C++17) six (depuis C++17) types d'itérateurs : LegacyInputIterator , LegacyOutputIterator , LegacyForwardIterator , LegacyBidirectionalIterator , LegacyRandomAccessIterator , et LegacyContiguousIterator (depuis C++17) . (Voir aussi LegacyIterator pour le type d'itérateur le plus basique.)

Plutôt que d'être définis par des types spécifiques, chaque catégorie d'itérateur est définie par les opérations qui peuvent être effectuées sur celui-ci. Cette définition signifie que tout type qui supporte les opérations nécessaires peut être utilisé comme itérateur -- par exemple, un pointeur supporte toutes les opérations requises par LegacyRandomAccessIterator , donc un pointeur peut être utilisé partout où un LegacyRandomAccessIterator est attendu.

Toutes les catégories d'itérateurs (à l'exception de LegacyOutputIterator ) peuvent être organisées en une hiérarchie, où les catégories d'itérateurs plus puissantes (par exemple LegacyRandomAccessIterator ) prennent en charge les opérations des catégories moins puissantes (par exemple LegacyInputIterator ). Si un itérateur appartient à l'une de ces catégories et satisfait également aux exigences de LegacyOutputIterator , alors il est appelé itérateur mutable et prend en charge à la fois l'entrée et la sortie. Les itérateurs non mutables sont appelés itérateurs constants .

Les itérateurs sont appelés constexpr itérateurs si toutes les opérations fournies pour satisfaire les exigences de catégorie d'itérateur sont des fonctions constexpr .

(depuis C++20)
Catégorie d'itérateur Opérations et exigences de stockage
écriture lecture incrémentation décrémentation accès
aléatoire 		stockage
contigu
sans
passages
multiples 		avec
passages
multiples
LegacyIterator Requis
LegacyOutputIterator Requis Requis
LegacyInputIterator
(mutable s'il supporte l'opération d'écriture) 		Requis Requis
LegacyForwardIterator
(satisfait aussi LegacyInputIterator ) 		Requis Requis Requis
LegacyBidirectionalIterator
(satisfait aussi LegacyForwardIterator ) 		Requis Requis Requis Requis
LegacyRandomAccessIterator
(satisfait aussi LegacyBidirectionalIterator ) 		Requis Requis Requis Requis Requis
LegacyContiguousIterator [1]
(satisfait aussi LegacyRandomAccessIterator ) 		Requis Requis Requis Requis Requis Requis
  1. ↑ LegacyContiguousIterator a été formellement spécifié uniquement dans C++17, mais les itérateurs de std::vector , std::basic_string , std::array , et std::valarray , ainsi que les pointeurs vers les tableaux C sont souvent traités comme une catégorie distincte dans le code pré-C++17.

Note : Un type supportant les opérations requises dans une ligne du tableau ci-dessus n'appartient pas nécessairement à la catégorie correspondante, consultez la page de la catégorie pour la liste complète des exigences.

Définitions

Types et possibilité d'écriture

Un itérateur d'entrée i supporte l'expression * i , produisant une valeur d'un certain type d'objet T , appelé le type de valeur de l'itérateur.

Un itérateur de sortie i possède un ensemble non vide de types qui sont écrivables (jusqu'en C++20) indirectly_writable (depuis C++20) vers l'itérateur ; pour chaque type T de cet ensemble, l'expression * i = o est valide où o est une valeur de type T .

Pour chaque type d'itérateur X pour lequel l'égalité est définie (jusqu'à C++20) , il existe un type entier (jusqu'à C++20) entier-like (depuis C++20) signé correspondant appelé le type de différence de l'itérateur.

Déréférenceabilité et validité

Tout comme un pointeur classique vers un array garantit qu'il existe une valeur de pointeur pointant après le dernier élément du tableau, de même pour tout type d'itérateur, il existe une valeur d'itérateur qui pointe après le dernier élément d'une séquence correspondante. Une telle valeur est appelée une valeur past-the-end .

Les valeurs d'un itérateur i pour lesquelles l'expression * i est définie sont appelées déréférençables . La bibliothèque standard ne suppose jamais que les valeurs au-delà de la fin sont déréférençables.

Les itérateurs peuvent également avoir des valeurs singulières qui ne sont associées à aucune séquence. Les résultats de la plupart des expressions sont indéfinis pour les valeurs singulières ; les seules exceptions sont

  • l'assignation d'une valeur non singulière à un itérateur qui détient une valeur singulière,
  • la destruction d'un itérateur qui détient une valeur singulière, et,
  • pour les itérateurs qui satisfont aux exigences DefaultConstructible , l'utilisation d'un itérateur initialisé par valeur comme source d'une opération de copie ou de déplacement (depuis C++11) .

Dans ces cas, la valeur singulière est écrasée de la même manière que toute autre valeur. Les valeurs déréférençables sont toujours non singulières.

Un itérateur invalide est un itérateur qui peut être singulier.

Plages

La plupart des modèles algorithmiques de la bibliothèque standard qui opèrent sur des structures de données possèdent des interfaces utilisant des plages.

Un itérateur j est dit accessible depuis un itérateur i si et seulement s'il existe une séquence finie d'applications de l'expression ++ i qui rend i == j . Si j est accessible depuis i , ils se réfèrent aux éléments de la même séquence.

Une plage est une paire d'itérateurs qui désignent le début et la fin du calcul. Une plage [ i , i ) est une plage vide ; en général, une plage [ i , j ) se réfère aux éléments de la structure de données commençant par l'élément pointé par i et allant jusqu'à mais n'incluant pas l'élément pointé par j .

La plage [ i , j ) est valide si et seulement si j est accessible depuis i .

(jusqu'à C++20)

Un range peut être désigné par soit

  • [ i , s ) , avec un itérateur i et un sentinel s qui désignent le début et la fin du calcul ( i et s peuvent avoir des types différents), ou
  • i + [ ​ 0 ​ , n ) , avec un itérateur i et un compteur n qui désignent le début et le nombre d'éléments auxquels le calcul doit être appliqué.
Range itérateur-sentinel

Un itérateur et un sentinel désignant un range sont comparables. [ i , s ) est vide si i == s ; sinon, [ i , s ) fait référence aux éléments dans la structure de données commençant par l'élément pointé par i et jusqu'à mais non inclus l'élément, s'il existe, pointé par le premier itérateur j tel que j == s .

Un sentinel s est dit accessible depuis un itérateur i si et seulement s'il existe une séquence finie d'applications de l'expression ++ i qui rend i == s .

Si s est accessible depuis i , [ i , s ) désigne un range valide .

Range compté

Un range compté i + [ ​ 0 ​ , n ) est vide si n == 0 ; sinon, i + [ ​ 0 ​ , n ) fait référence aux n éléments dans la structure de données commençant par l'élément pointé par i et jusqu'à mais non inclus l'élément, s'il existe, pointé par le résultat de n applications de ++ i .

Un range compté i + [ ​ 0 ​ , n ) est valide si et seulement si

  • n == 0 ; ou
  • toutes les conditions suivantes sont satisfaites :
    • n est positif,
    • i est déréférençable, et
    • ++ i + [ ​ 0 ​ , -- n ) est valide.
(depuis C++20)

Le résultat de l'application de fonctions de la bibliothèque standard à des plages non valides n'est pas défini.

Concepts d'itérateur (depuis C++20)

Un nouveau système d'itérateurs basé sur des concepts qui diffèrent des itérateurs C++17. Bien que la taxonomie fondamentale reste similaire, les exigences pour les catégories individuelles d'itérateurs sont quelque peu différentes.

Défini dans l'espace de noms std
(C++20)
spécifie qu'un type est indirectement lisible en appliquant l'opérateur *
(concept)
(C++20)
spécifie qu'une valeur peut être écrite dans l'objet référencé par un itérateur
(concept)
(C++20)
spécifie qu'un type semiregular peut être incrémenté avec les opérateurs de pré-incrémentation et post-incrémentation
(concept)
(C++20)
spécifie que l'opération d'incrémentation sur un type weakly_incrementable préserve l'égalité et que le type est equality_comparable
(concept)
(C++20) (C++20)
spécifie qu'un type se comporte comme un type entier (signé)
( concept d'exposition uniquement* )
(C++20)
spécifie que les objets d'un type peuvent être incrémentés et déréférencés
(concept)
(C++20)
spécifie qu'un type est un sentinelle pour un type input_or_output_iterator
(concept)
(C++20)
spécifie que l'opérateur - peut être appliqué à un itérateur et un sentinelle pour calculer leur différence en temps constant
(concept)
(C++20)
spécifie qu'un type est un itérateur d'entrée, c'est-à-dire que ses valeurs référencées peuvent être lues et qu'il peut être pré-incrémenté et post-incrémenté
(concept)
(C++20)
spécifie qu'un type est un itérateur de sortie pour un type de valeur donné, c'est-à-dire que les valeurs de ce type peuvent y être écrites et qu'il peut être pré-incrémenté et post-incrémenté
(concept)
(C++20)
spécifie qu'un input_iterator est un itérateur avant, prenant en charge la comparaison d'égalité et le multi-passage
(concept)
(C++20)
spécifie qu'un forward_iterator est un itérateur bidirectionnel, prenant en charge le déplacement vers l'arrière
(concept)
(C++20)
spécifie qu'un bidirectional_iterator est un itérateur à accès aléatoire, prenant en charge l'avancement en temps constant et l'indexation
(concept)
(C++20)
spécifie qu'un random_access_iterator est un itérateur contigu, référençant des éléments contigus en mémoire
(concept)

Types associés aux itérateurs (depuis C++20)

Défini dans l'espace de noms std
(C++20)
calcule le type de différence d'un type weakly_incrementable
(modèle de classe)
(C++20)
calcule le type de valeur d'un type indirectly_readable
(modèle de classe)
(C++20) (C++20) (C++23) (C++20) (C++20) (C++20)
calcule les types associés d'un itérateur
(modèle d'alias)

Primitives d'itérateur

fournit une interface uniforme pour les propriétés d'un itérateur
(modèle de classe)
(C++20)
types de classes vides utilisés pour indiquer les catégories d'itérateurs
(classe)
(obsolète en C++17)
classe de base pour faciliter la définition des types requis pour les itérateurs simples
(modèle de classe)

Points de personnalisation des itérateurs (depuis C++20)

Défini dans l'espace de noms std::ranges
(C++20)
convertit le résultat du déréférencement d'un objet en son type de référence rvalue associé
(objet point de personnalisation)
(C++20)
échange les valeurs référencées par deux objets déréférençables
(objet point de personnalisation)

Concepts et utilitaires d'algorithmes (depuis C++20)

Un ensemble de concepts et de modèles utilitaires associés conçus pour faciliter la contrainte des opérations algorithmiques courantes.

Défini dans l'en-tête <iterator>
Défini dans l'espace de noms std
Concepts d'appel indirect
(C++20) (C++20)
spécifie qu'un type appelable peut être invoqué avec le résultat du déréférencement d'un indirectly_readable type
(concept)
(C++20)
spécifie qu'un type appelable, lorsqu'il est invoqué avec le résultat du déréférencement d'un indirectly_readable type, satisfait predicate
(concept)
(C++20)
spécifie qu'un type appelable, lorsqu'il est invoqué avec le résultat du déréférencement de deux indirectly_readable types, satisfait predicate
(concept)
(C++20)
spécifie qu'un type appelable, lorsqu'il est invoqué avec le résultat du déréférencement de deux indirectly_readable types, satisfait equivalence_relation
(concept)
(C++20)
spécifie qu'un type appelable, lorsqu'il est invoqué avec le résultat du déréférencement de deux indirectly_readable types, satisfait strict_weak_order
(concept)
Exigences communes des algorithmes
(C++20)
spécifie que les valeurs peuvent être déplacées d'un indirectly_readable vers un indirectly_writable type
(concept)
(C++20)
spécifie que les valeurs peuvent être déplacées d'un indirectly_readable vers un indirectly_writable et que le déplacement peut être effectué via un objet intermédiaire
(concept)
(C++20)
spécifie que les valeurs peuvent être copiées d'un indirectly_readable type vers un indirectly_writable type
(concept)
(C++20)
spécifie que les valeurs peuvent être copiées d'un indirectly_readable type vers un indirectly_writable type et que la copie peut être effectuée via un objet intermédiaire
(concept)
(C++20)
spécifie que les valeurs référencées par deux indirectly_readable types peuvent être échangées
(concept)
(C++20)
spécifie que les valeurs référencées par deux indirectly_readable types peuvent être comparées
(concept)
(C++20)
spécifie les exigences communes des algorithmes qui réorganisent les éléments sur place
(concept)
(C++20)
spécifie les exigences des algorithmes qui fusionnent des séquences triées en une séquence de sortie en copiant les éléments
(concept)
(C++20)
spécifie les exigences communes des algorithmes qui réorganisent les séquences en séquences ordonnées
(concept)
Utilitaires
(C++20)
calcule le résultat de l'invocation d'un objet appelable sur le résultat du déréférencement d'un ensemble de indirectly_readable types
(alias de modèle)
(C++20)
template d'aide pour spécifier les contraintes sur les algorithmes qui acceptent des projections
(alias template)
(C++26)
calcule le type de valeur d'un indirectly_readable par projection
(alias de modèle)

Adaptateurs d'itérateurs

adaptateur d'itérateur pour le parcours en ordre inverse
(modèle de classe)
(C++14)
crée un std::reverse_iterator dont le type est déduit de l'argument
(modèle de fonction)
adaptateur d'itérateur pour l'insertion à la fin d'un conteneur
(modèle de classe)
crée un std::back_insert_iterator dont le type est déduit de l'argument
(modèle de fonction)
adaptateur d'itérateur pour l'insertion au début d'un conteneur
(modèle de classe)
crée un std::front_insert_iterator dont le type est déduit de l'argument
(modèle de fonction)
adaptateur d'itérateur pour l'insertion dans un conteneur
(modèle de classe)
crée un std::insert_iterator dont le type est déduit de l'argument
(modèle de fonction)
(C++23)
adaptateur d'itérateur qui convertit un itérateur en itérateur constant
(modèle de classe)
(C++23)
calcule un type d'itérateur constant pour un type donné
(modèle d'alias)
(C++23)
calcule un type sentinelle à utiliser avec les itérateurs constants
(modèle d'alias)
(C++23)
crée un std::const_iterator dont le type est déduit de l'argument
(modèle de fonction)
(C++23)
crée un std::const_sentinel dont le type est déduit de l'argument
(modèle de fonction)
(C++11)
adaptateur d'itérateur qui se déréférence en une valeur rvalue
(modèle de classe)
(C++20)
adaptateur de sentinelle pour std::move_iterator
(modèle de classe)
(C++11)
crée un std::move_iterator dont le type est déduit de l'argument
(modèle de fonction)
(C++20)
adapte un type d'itérateur et son sentinelle en un type d'itérateur commun
(modèle de classe)
(C++20)
sentinelle par défaut pour utilisation avec les itérateurs qui connaissent la limite de leur plage
(classe)
(C++20)
adaptateur d'itérateur qui suit la distance jusqu'à la fin de la plage
(modèle de classe)
(C++20)
sentinelle qui compare toujours inégale à tout type weakly_incrementable
(classe)

Itérateurs de flux

itérateur d'entrée qui lit depuis std::basic_istream
(modèle de classe)
itérateur de sortie qui écrit vers std::basic_ostream
(modèle de classe)
itérateur d'entrée qui lit depuis std::basic_streambuf
(modèle de classe)
itérateur de sortie qui écrit vers std::basic_streambuf
(modèle de classe)

Opérations sur les itérateurs

Défini dans l'en-tête <iterator>
avance un itérateur d'une distance donnée
(modèle de fonction)
retourne la distance entre deux itérateurs
(modèle de fonction)
(C++11)
incrémente un itérateur
(modèle de fonction)
(C++11)
décrémente un itérateur
(modèle de fonction)
(C++20)
avance un itérateur d'une distance donnée ou jusqu'à une limite donnée
(objet fonction algorithme)
(C++20)
retourne la distance entre un itérateur et un sentinelle, ou entre le début et la fin d'une plage
(objet fonction algorithme)
(C++20)
incrémente un itérateur d'une distance donnée ou jusqu'à une limite
(objet fonction algorithme)
(C++20)
décrémente un itérateur d'une distance donnée ou jusqu'à une limite
(objet fonction algorithme)

Accès aux plages (depuis C++11)

Ces modèles de fonctions non membres fournissent une interface générique pour les conteneurs, les tableaux bruts et std::initializer_list .

Défini dans l'en-tête <array>
Défini dans l'en-tête <deque>
Défini dans l'en-tête <flat_map>
Défini dans l'en-tête <flat_set>
Défini dans l'en-tête <forward_list>
Défini dans l'en-tête <inplace_vector>
Défini dans l'en-tête <iterator>
Défini dans l'en-tête <list>
Défini dans l'en-tête <map>
Défini dans l'en-tête <regex>
Défini dans l'en-tête <set>
Défini dans l'en-tête <span>
Défini dans l'en-tête <string>
Défini dans l'en-tête <string_view>
Défini dans l'en-tête <unordered_map>
Défini dans l'en-tête <unordered_set>
Défini dans l'en-tête <vector>
Défini dans l'espace de noms std
(C++11) (C++14)
retourne un itérateur vers le début d'un conteneur ou d'un tableau
(modèle de fonction)
(C++11) (C++14)
retourne un itérateur vers la fin d'un conteneur ou d'un tableau
(modèle de fonction)
(C++14)
retourne un itérateur inverse vers le début d'un conteneur ou d'un tableau
(modèle de fonction)
(C++14)
retourne un itérateur inverse de fin pour un conteneur ou un tableau
(modèle de fonction)
(C++17) (C++20)
retourne la taille d'un conteneur ou d'un tableau
(modèle de fonction)
(C++17)
vérifie si le conteneur est vide
(modèle de fonction)
(C++17)
obtient le pointeur vers le tableau sous-jacent
(modèle de fonction)

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR Applicable à Comportement publié Comportement corrigé
CWG 1181 C++98 les types tableau ne pouvaient pas être des types valeur ils le peuvent
LWG 208 C++98 les itérateurs past-the-end étaient toujours non singuliers ils peuvent être singuliers
LWG 278 C++98 la validité d'un itérateur n'était pas définie définie comme toujours non singulier
LWG 324 C++98 les itérateurs de sortie avaient des types valeur les itérateurs de sortie ont des types écrivables à la place
LWG 407 C++98 les itérateurs singuliers ne pouvaient pas être détruits autorisé
LWG 408
( N3066 ) 		C++98 les itérateurs singuliers ne pouvaient pas être copiés autorisé s'ils sont initialisés par valeur
LWG 1185
( N3066 ) 		C++98 LegacyForwardIterator , LegacyBidirectionalIterator
et LegacyRandomAccessIterator
satisfont toujours LegacyOutputIterator 		ils pourraient ne pas satisfaire LegacyOutputIterator
LWG 1210
( N3066 ) 		C++98 la définition de la singularité d'itérateur et
de l'accessibilité dépendait des conteneurs 		dépend des séquences à la place
LWG 3009 C++17 <string_view> ne fournissait pas les
modèles de fonction d'accès aux plages 		fournit ces modèles
LWG 3987 C++23 <flat_map> et <flat_set> ne
fournissaient pas les modèles de fonction d'accès aux plages 		fournissent ces modèles