Quelles sont les règles d'invalidation de l'itérateur pour les conteneurs C ++?

De préférence dans un format de liste récapitulative.

_{(Remarque: Ceci est censé être une entrée de la FAQ C ++ de Stack Overflow . Si vous voulez critiquer l'idée de fournir une FAQ sous cette forme, alors la publication sur la méta qui a commencé tout cela serait l'endroit pour le faire. Réponses à cette question est surveillée dans le salon de discussion C ++ , où l'idée de FAQ a commencé en premier, donc votre réponse est très susceptible d'être lue par ceux qui ont eu l'idée.)}

C ++ 17 (Toutes les références proviennent de la version finale du CPP17 - n4659 )

Insertion

Conteneurs de séquence

• vector: Les fonctions insert, emplace_back, emplace, push_backréaffectation des causes si la nouvelle taille est supérieure à l'ancienne capacité. La réallocation invalide toutes les références, pointeurs et itérateurs faisant référence aux éléments de la séquence. Si aucune réallocation ne se produit, tous les itérateurs et références avant le point d'insertion restent valides. [26.3.11.5/1]
  En ce qui concerne la reservefonction, la réallocation invalide toutes les références, pointeurs et itérateurs faisant référence aux éléments de la séquence. Aucune réallocation ne doit avoir lieu pendant les insertions qui se produisent après un appel à reserve()jusqu'au moment où une insertion rendrait la taille du vecteur supérieure à la valeur de capacity(). [26.3.11.3/6]

• deque: Une insertion au milieu du deque invalide tous les itérateurs et les références aux éléments du deque. Une insertion à l'une ou l'autre extrémité du deque invalide tous les itérateurs du deque, mais n'a aucun effet sur la validité des références aux éléments du deque. [26.3.8.4/1]

• list: N'affecte pas la validité des itérateurs et des références. Si une exception est levée, il n'y a aucun effet. [26.3.10.4/1].
  Le insert, emplace_front, emplace_back, emplace, push_front, les push_backfonctions sont couverts par cette règle.

• forward_list: Aucune des surcharges de insert_afterne doit affecter la validité des itérateurs et des références [26.3.9.5/1]

• array: En règle générale , les itérateurs d'un tableau ne sont jamais invalidés pendant toute la durée de vie du tableau. Il convient toutefois de noter que lors de l'échange, l'itérateur continuera de pointer vers le même élément du tableau et changera donc sa valeur.

Conteneurs associatifs

• All Associative Containers: Les insertet les emplacemembres ne doivent pas affecter la validité des itérateurs et des références au conteneur [26.2.6 / 9]

Conteneurs associatifs non ordonnés

• All Unordered Associative Containers: Le ressassement invalide les itérateurs, modifie l'ordre entre les éléments et modifie les éléments dans lesquels les compartiments apparaissent, mais n'invalide pas les pointeurs ou les références aux éléments. [26.2.7 / 9]
  Les insertet les emplacemembres ne doivent pas affecter la validité des références à des éléments de conteneurs, mais peut annuler tous les itérateurs au récipient. [26.2.7 / 14]
  Les insertet les emplacemembres ne doivent pas affecter la validité de itérateurs si (N+n) <= z * B, où Nest le nombre d'éléments dans le conteneur avant l'opération d'insertion, nest le nombre d'éléments insérés, Best le nombre de seau du conteneur, et zest facteur de charge maximale du conteneur. [26.2.7 / 15]

• All Unordered Associative Containers: Dans le cas d'une opération de fusion (par exemple, a.merge(a2)), les itérateurs faisant référence aux éléments transférés et tous les itérateurs faisant référence aseront invalidés, mais les itérateurs des éléments restants a2resteront valides. (Tableau 91 - Exigences relatives aux conteneurs associatifs non ordonnés)

Adaptateurs pour conteneurs

• stack: hérité du conteneur sous-jacent
• queue: hérité du conteneur sous-jacent
• priority_queue: hérité du conteneur sous-jacent

Effacement

Conteneurs de séquence

• vector: Les fonctions eraseet pop_backinvalident les itérateurs et les références au moment de l'effacement ou après. [26.3.11.5/3]

• deque: Une opération d'effacement qui efface le dernier élément d'un dequeinvalide uniquement l'itérateur passé la fin et tous les itérateurs et les références aux éléments effacés. Une opération d'effacement qui efface le premier élément d'un dequemais pas le dernier élément invalide uniquement les itérateurs et les références aux éléments effacés. Une opération d'effacement qui n'efface ni le premier élément ni le dernier élément d'un dequeinvalide l'itérateur passé la fin et tous les itérateurs et les références à tous les éléments du deque. [Remarque: pop_frontet pop_backsont des opérations d'effacement. —Fin note] [26.3.8.4/4]

• list: Invalide uniquement les itérateurs et les références aux éléments effacés. [26.3.10.4/3]. Cela s'applique à erase, pop_front, pop_back, clearfonctions.
  removeet remove_iffonctions membres: efface tous les éléments de la liste référencés par un itérateur de liste ipour lequel les conditions suivantes sont remplies: *i == value, pred(*i) != false. Invalide uniquement les itérateurs et les références aux éléments effacés [26.3.10.5/15].
  uniquefonction membre - Supprime tout sauf le premier élément de chaque groupe consécutif d'éléments égaux auquel l'itérateur fait référence idans la plage [first + 1, last)pour laquelle *i == *(i-1)(pour la version de unique sans argument) oupred(*i, *(i - 1))(pour la version de unique avec un argument de prédicat) est valable. Invalide uniquement les itérateurs et les références aux éléments effacés. [26.3.10.5/19]

• forward_list: erase_aftern'invalidera que les itérateurs et les références aux éléments effacés. [26.3.9.5/1].
  removeet remove_iffonctions membres - Supprime tous les éléments de la liste référencés par un itérateur de liste i pour lequel les conditions suivantes sont remplies : *i == value(pour remove()), pred(*i)est vrai (pour remove_if()). Invalide uniquement les itérateurs et les références aux éléments effacés. [26.3.9.6/12].
  uniquefonction membre - Efface tout sauf le premier élément de chaque groupe consécutif d'éléments égaux référencé par l'itérateur i dans la plage [premier + 1, dernier) pour lequel *i == *(i-1)(pour la version sans arguments) ou pred(*i, *(i - 1))(pour la version avec un prédicat argument) est valable. Invalide uniquement les itérateurs et les références aux éléments effacés. [26.3.9.6/16]

• All Sequence Containers: clearinvalide toutes les références, pointeurs et itérateurs faisant référence aux éléments de a et peut invalider l'itérateur passé la fin (Tableau 87 - Exigences du conteneur de séquence). Mais pour forward_list, clearn'invalide pas les itérateurs ultérieurs. [26.3.9.5/32]

• All Sequence Containers: assigninvalide toutes les références, pointeurs et itérateurs faisant référence aux éléments du conteneur. Pour vectoret deque, invalide également l'itérateur passé la fin. (Tableau 87 - Exigences relatives aux conteneurs de séquence)

Conteneurs associatifs

• All Associative Containers: Les erasemembres invalideront uniquement les itérateurs et les références aux éléments effacés [26.2.6 / 9]

• All Associative Containers: Les extractmembres invalident uniquement les itérateurs de l'élément supprimé; les pointeurs et les références à l'élément supprimé restent valides [26.2.6 / 10]

Adaptateurs pour conteneurs

• stack: hérité du conteneur sous-jacent
• queue: hérité du conteneur sous-jacent
• priority_queue: hérité du conteneur sous-jacent

Exigences générales relatives aux conteneurs concernant l'invalidation des itérateurs:

• Sauf indication contraire (explicitement ou en définissant une fonction en termes d'autres fonctions), l'invocation d'une fonction membre de conteneur ou le passage d'un conteneur comme argument à une fonction de bibliothèque ne doit pas invalider les itérateurs ou modifier les valeurs des objets dans ce conteneur. . [26.2.1 / 12]

• aucune swap()fonction n'invalide les références, pointeurs ou itérateurs faisant référence aux éléments des conteneurs échangés. [Remarque: l'itérateur end () ne fait référence à aucun élément, il peut donc être invalidé. —Fin note] [26.2.1 / (11.6)]

Comme exemples des exigences ci-dessus:

• transformalgorithme: les fonctions opet binary_opne doivent pas invalider les itérateurs ou les sous-plages, ni modifier les éléments des plages [28.6.4 / 1]

• accumulatealgorithme: dans la plage [premier, dernier], binary_opne doit ni modifier les éléments ni invalider les itérateurs ou les sous-plages [29.8.2 / 1]

• reducealgorithme: binary_op ne doit ni invalider les itérateurs ou les sous-plages, ni modifier les éléments de la plage [premier, dernier]. [29.8.3 / 5]

etc...

C ++ 03 (Source: règles d'invalidation d'itérateur (C ++ 03) )

Insertion

Conteneurs de séquence

• vector: tous les itérateurs et références avant le point d'insertion ne sont pas affectés, sauf si la nouvelle taille de conteneur est supérieure à la capacité précédente (auquel cas tous les itérateurs et références sont invalidés) [23.2.4.3/1]
• deque: tous les itérateurs et références sont invalidés, sauf si le membre inséré se trouve à une extrémité (avant ou arrière) de la deque (auquel cas tous les itérateurs sont invalidés, mais les références aux éléments ne sont pas affectées) [23.2.1.3/1]
• list: tous les itérateurs et références non affectés [23.2.2.3/1]

Conteneurs associatifs

• [multi]{set,map}: tous les itérateurs et références non affectés [23.1.2 / 8]

Adaptateurs pour conteneurs

• stack: hérité du conteneur sous-jacent
• queue: hérité du conteneur sous-jacent
• priority_queue: hérité du conteneur sous-jacent

Effacement

Conteneurs de séquence

• vector: chaque itérateur et référence après le point d'effacement est invalidé [23.2.4.3/3]
• deque: tous les itérateurs et références sont invalidés, sauf si les membres effacés se trouvent à une extrémité (avant ou arrière) de la deque (auquel cas seuls les itérateurs et les références aux membres effacés sont invalidés) [23.2.1.3/4]
• list: seuls les itérateurs et les références à l'élément effacé sont invalidés [23.2.2.3/3]

Conteneurs associatifs

• [multi]{set,map}: seuls les itérateurs et les références aux éléments effacés sont invalidés [23.1.2 / 8]

Adaptateurs pour conteneurs

• stack: hérité du conteneur sous-jacent
• queue: hérité du conteneur sous-jacent
• priority_queue: hérité du conteneur sous-jacent

Redimensionnement

• vector: selon insertion / effacement [23.2.4.2/6]
• deque: selon insertion / effacement [23.2.1.2/1]
• list: selon insertion / effacement [23.2.2.2/1]

Note 1

Sauf indication contraire (explicitement ou en définissant une fonction en termes d'autres fonctions), l'invocation d'une fonction membre de conteneur ou le passage d'un conteneur comme argument à une fonction de bibliothèque ne doit pas invalider les itérateurs ou modifier les valeurs des objets dans ce conteneur. . [23.1 / 11]

Note 2

Il n'est pas clair en C ++ 2003 si les itérateurs "fin" sont soumis aux règles ci-dessus ; vous devez de toute façon supposer qu'ils le sont (comme c'est le cas en pratique).

Note 3

Les règles d'invalidation des pointeurs sont les mêmes que les règles d'invalidation des références.

C ++ 11 (Source: règles d'invalidation d'itérateur (C ++ 0x) )

Insertion

Conteneurs de séquence

• vector: tous les itérateurs et références avant le point d'insertion ne sont pas affectés, sauf si la nouvelle taille de conteneur est supérieure à la capacité précédente (auquel cas tous les itérateurs et références sont invalidés) [23.3.6.5/1]
• deque: tous les itérateurs et références sont invalidés, sauf si le membre inséré se trouve à une extrémité (avant ou arrière) de la deque (auquel cas tous les itérateurs sont invalidés, mais les références aux éléments ne sont pas affectées) [23.3.3.4/1]
• list: tous les itérateurs et références non affectés [23.3.5.4/1]
• forward_list: tous les itérateurs et références non affectés (s'applique à insert_after) [23.3.4.5/1]
• array: (n / a)

Conteneurs associatifs

• [multi]{set,map}: tous les itérateurs et références non affectés [23.2.4 / 9]

Conteneurs associatifs non triés

• unordered_[multi]{set,map}: tous les itérateurs sont invalidés lors du ressassement, mais les références ne sont pas affectées [23.2.5 / 8]. Le ré-émaillage ne se produit pas si l'insertion ne fait pas dépasser la taille du conteneur z * Boù zest le facteur de charge maximum et Ble nombre actuel de godets. [23.2.5 / 14]

Adaptateurs pour conteneurs

• stack: hérité du conteneur sous-jacent
• queue: hérité du conteneur sous-jacent
• priority_queue: hérité du conteneur sous-jacent

Effacement

Conteneurs de séquence

• vector: chaque itérateur et référence au point d'effacement ou après est invalidé [23.3.6.5/3]
• deque: l'effacement du dernier élément invalide uniquement les itérateurs et les références aux éléments effacés et à l'itérateur passé la fin; l'effacement du premier élément invalide uniquement les itérateurs et les références aux éléments effacés; l'effacement de tout autre élément invalide tous les itérateurs et références (y compris l'itérateur passé la fin) [23.3.3.4/4]
• list: seuls les itérateurs et les références à l'élément effacé sont invalidés [23.3.5.4/3]
• forward_list: seuls les itérateurs et les références à l'élément effacé sont invalidés (s'applique à erase_after) [23.3.4.5/1]
• array: (n / a)

Conteneurs associatifs

• [multi]{set,map}: seuls les itérateurs et les références aux éléments effacés sont invalidés [23.2.4 / 9]

Conteneurs associatifs non ordonnés

• unordered_[multi]{set,map}: seuls les itérateurs et les références aux éléments effacés sont invalidés [23.2.5 / 13]

Adaptateurs pour conteneurs

• stack: hérité du conteneur sous-jacent
• queue: hérité du conteneur sous-jacent
• priority_queue: hérité du conteneur sous-jacent

Redimensionnement

• vector: selon insertion / effacement [23.3.6.5/12]
• deque: selon insertion / effacement [23.3.3.3/3]
• list: selon insertion / effacement [23.3.5.3/1]
• forward_list: selon insertion / effacement [23.3.4.5/25]
• array: (n / a)

Note 1

Sauf indication contraire (explicitement ou en définissant une fonction en termes d'autres fonctions), l'invocation d'une fonction membre de conteneur ou le passage d'un conteneur comme argument à une fonction de bibliothèque ne doit pas invalider les itérateurs ou modifier les valeurs des objets dans ce conteneur. . [23.2.1 / 11]

Note 2

aucune fonction swap () n'invalide les références, pointeurs ou itérateurs faisant référence aux éléments des conteneurs échangés. [Remarque: l' itérateur end () ne fait référence à aucun élément, il peut donc être invalidé . —Fin note] [23.2.1 / 10]

Note 3

Mis à part la mise en garde ci-dessus concernant swap(), il n'est pas clair si les itérateurs "finaux" sont soumis aux règles par conteneur énumérées ci-dessus ; vous devez de toute façon supposer qu'ils le sont.

Remarque 4

vectoret tous les conteneurs associatifs non ordonnés prennent en charge reserve(n)ce qui garantit qu'aucun redimensionnement automatique ne se produira au moins jusqu'à ce que la taille du conteneur atteigne n. Des précautions doivent être prises avec les conteneurs associatifs non ordonnés car une future proposition permettra la spécification d'un facteur de charge minimum, ce qui permettrait de ressasser insertaprès que suffisamment d' eraseopérations réduisent la taille du conteneur en dessous du minimum; la garantie doit être considérée comme potentiellement nulle après un erase.

Il est sans doute utile d' ajouter qu'un iterator insert de toute nature ( std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator) est garantie reste valable tant que toutes les insertions sont effectuées par ce iterator et aucun autre événement invalidant iterator indépendant se produit.

Par exemple, lorsque vous effectuez une série d'opérations d'insertion dans un std::vectoren utilisant, std::insert_iteratoril est fort possible que ces insertions déclenchent une réallocation de vecteur, ce qui invalidera tous les itérateurs qui "pointent" dans ce vecteur. Cependant, l'itérateur d'insertion en question est garanti pour rester valide, c'est-à-dire que vous pouvez continuer en toute sécurité la séquence d'insertions. Vous n'avez pas à vous soucier du déclenchement de la réallocation des vecteurs.

Ceci, encore une fois, ne s'applique qu'aux insertions effectuées via l'itérateur d'insertion lui-même. Si l'événement invalidant l'itérateur est déclenché par une action indépendante sur le conteneur, l'itérateur d'insertion est également invalidé conformément aux règles générales.

Par exemple, ce code

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

est garanti pour effectuer une séquence d'insertions valide dans le vecteur, même si le vecteur "décide" de se réallouer quelque part au milieu de ce processus. Iterator itdeviendra évidemment invalide, mais it_insrestera valide.

Étant donné que cette question attire autant de votes et devient une FAQ, je suppose qu'il serait préférable d'écrire une réponse distincte pour mentionner une différence significative entre C ++ 03 et C ++ 11 concernant l'impact de std::vectorl'opération d'insertion de sur le validité des itérateurs et des références par rapport à reserve()et capacity(), que la réponse la plus votée n'a pas remarquée.

C ++ 03:

La réallocation invalide toutes les références, pointeurs et itérateurs faisant référence aux éléments de la séquence. Il est garanti qu'aucune réallocation n'a lieu pendant les insertions qui se produisent après un appel à reserve () jusqu'au moment où une insertion rendrait la taille du vecteur supérieure à la taille spécifiée dans le dernier appel à reserve () .

C ++ 11:

La réallocation invalide toutes les références, pointeurs et itérateurs faisant référence aux éléments de la séquence. Il est garanti qu'aucune réallocation n'a lieu pendant les insertions qui se produisent après un appel à reserve () jusqu'au moment où une insertion rendrait la taille du vecteur supérieure à la valeur de capacity () .

Donc en C ++ 03, ce n'est pas " unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)" comme mentionné dans l'autre réponse, mais plutôt " greater than the size specified in the most recent call to reserve()". C'est une chose que C ++ 03 diffère de C ++ 11. En C ++ 03, une fois que an insert()fait en sorte que la taille du vecteur atteigne la valeur spécifiée dans l' reserve()appel précédent (qui pourrait bien être plus petite que le courant capacity()car a reserve()pourrait en résulter une plus grande capacity()que ce qui était demandé), toute suite insert()pourrait provoquer une réallocation et invalider tous les itérateurs et références. En C ++ 11, cela ne se produira pas et vous pouvez toujours faire confiance capacity()pour savoir avec certitude que la prochaine réaffectation n'aura pas lieu avant que la taille ne dépasse capacity().

En conclusion, si vous travaillez avec un vecteur C ++ 03 et que vous voulez vous assurer qu'aucune réallocation ne se produira lorsque vous effectuez l'insertion, c'est la valeur de l'argument que vous avez précédemment transmis reserve()que vous devez vérifier la taille, pas la valeur de retour d'un appel à capacity(), sinon vous risquez de vous surprendre d'une réallocation " prématurée ".

Voici un joli tableau récapitulatif de cppreference.com :

Ici, l' insertion fait référence à toute méthode qui ajoute un ou plusieurs éléments au conteneur et l' effacement fait référence à toute méthode qui supprime un ou plusieurs éléments du conteneur.