Question Règles d'invalidation de l'itérateur


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.

(Note: Ceci est censé être une entrée pour FAQ C ++ de Stack Overflow. Si vous voulez critiquer l'idée de fournir une FAQ dans ce formulaire, alors l'affichage sur meta qui a commencé tout cela serait l'endroit pour le faire. Les réponses à cette question sont suivies dans le Chatroom C ++, où l'idée de FAQ a commencé en premier lieu, ainsi votre réponse est très susceptible d'être lue par ceux qui ont eu l'idée.)


434
2018-06-22 10:01


origine


Réponses:


C ++ 03 (La source: Règles d'invalidation d'itérateurs (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 du conteneur est supérieure à la capacité précédente (auquel cas tous les itérateurs et les références sont invalidés) [23.2.4.3/1]
  • deque: tous les itérateurs et références sont invalidés, à moins que le membre inséré ne soit à l'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 de conteneur

  • 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 sont à la fin (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 de conteneur

  • 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 insert / erase [23.2.4.2/6]
  • deque: selon insert / erase [23.2.1.2/1]
  • list: selon insertion / effacement [23.2.2.2/1]

Note 1

Sauf indication contraire (non plus   explicitement ou en définissant une fonction   en termes d'autres fonctions), invoquant   une fonction de membre de conteneur ou de passage   un conteneur en tant qu'argument une   la fonction de bibliothèque n'invalidera pas   itérateurs à, ou changer les valeurs de,   objets dans ce conteneur.   [23.1 / 11]

Note 2

Il n'est pas clair dans C ++ 2003 si les itérateurs "fin" sont soumis aux règles ci-dessus; vous devez supposer, de toute façon, 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.


382
2018-06-22 10:01



C ++ 11 (La source: Règles d'invalidation de l'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 du 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, à moins que le membre inséré ne soit à l'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 ressuage ne se produit pas si l'insertion n'entraîne pas un dépassement de la taille du récipient z * B où z est le facteur de charge maximale et B le nombre actuel de godets. [23.2.5 / 14]

Adaptateurs de conteneur

  • 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 à ou après le point d'effacement est invalidé [23.3.6.5/3]
  • deque: effacer le dernier élément invalide uniquement les itérateurs et les références aux éléments effacés et à l'itérateur passé; 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 précédent) [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 de conteneur

  • 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 (non plus   explicitement ou en définissant une fonction   en termes d'autres fonctions), invoquant   une fonction de membre de conteneur ou de passage   un conteneur en tant qu'argument une   la fonction de bibliothèque n'invalidera pas   itérateurs à, ou changer les valeurs de,   objets dans ce conteneur.   [23.2.1 / 11]

Note 2

aucune fonction swap () n'invalide aucun   références, pointeurs ou itérateurs   se référant aux éléments de la   conteneurs échangés. [ Remarque: le   end () itérateur ne se réfère à aucun   élément, donc peut être invalidé.   -End note] [23.2.1 / 10]

Note 3

Autre que la mise en garde ci-dessus concernant swap(), il n'est pas clair si les itérateurs "fin" sont soumis aux règles par conteneur listées ci-dessus; vous devriez en tout cas supposer qu'ils le sont.

Note 4

vector et tout conteneurs associatifs non ordonnés soutien reserve(n) ce qui garantit qu'aucun redimensionnement automatique ne se produira au moins jusqu'à ce que la taille du conteneur augmente à n. Des précautions doivent être prises avec conteneurs associatifs non ordonnés parce qu'une future proposition permettra la spécification d'un facteur de charge minimum, ce qui permettrait de ressasser sur insert après assez erase les opé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.


315
2018-06-22 15:53



Il vaut probablement la peine d'ajouter un itérateur d'insertion de toute sorte (std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator) reste garanti tant que toutes les insertions sont effectuées via cet itérateur et qu'aucun autre événement d'invalidation d'itérateur ne se produit.

Par exemple, lorsque vous effectuez une série d'opérations d'insertion dans un std::vector en utilisant std::insert_iterator il est tout à fait possible que le vecteur subisse un événement de réallocation, 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 la séquence d'insertions en toute sécurité. Il n'y a pas besoin de s'inquiéter de déclencher la réallocation vectorielle du tout.

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 itérateur-invalide est déclenché par une action indépendante sur le conteneur, alors l'itérateur d'insertion devient é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 valide d'insertions dans le vecteur, même si le vecteur "décide" de se réallouer quelque part au milieu de ce processus.


33
2017-07-04 23:36



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

C ++ 03:

La réallocation invalide toutes les références, pointeurs et itérateurs   se référant aux éléments de la séquence. Il est garanti que non   La réallocation a lieu lors d'insertions qui se produisent après un appel à   reserve () jusqu'au moment où une insertion ferait la taille de la   vecteur supérieure à la taille spécifiée dans l'appel le plus récent à   réserve().

C ++ 11:

La réallocation invalide toutes les références, pointeurs et itérateurs   se référant aux éléments de la séquence. Il est garanti que non   La réallocation a lieu lors d'insertions qui se produisent après un appel à   reserve () jusqu'au moment où une insertion ferait la taille de la   vecteur supérieure à la valeur de la capacité ().

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, à la place, il devrait être"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 insert() provoque la taille du vecteur pour atteindre la valeur spécifiée dans le précédent reserve() appel (qui pourrait bien être plus petit que le courant capacity() depuis un reserve() pourrait entraîner un plus grand capacity() que demandé), tout insert() pourrait provoquer une réallocation et invalider tous les itérateurs et références. En C ++ 11, cela n'arrivera pas et vous pouvez toujours faire confiance capacity() savoir avec certitude que la prochaine réaffectation n'aura pas lieu avant que les dépassements de taille capacity().

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


18
2018-03-08 02:24