Règles d’invalidation itérateur

Question

Quelles sont les itérateur invalidation des règles pour le C++ conteneurs?

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

_{(Note: Ceci est destiné à être une entrée à Débordement de Pile du C++ FAQ. Si vous voulez une critique de l'idée de fournir une FAQ dans ce formulaire, puis de la poster sur meta qui a commencé tout cela serait l'endroit pour le faire. Les réponses à cette question sont surveillés en C++ salon, où la FAQ idée a commencé à en premier lieu, de sorte que votre réponse est très probablement le faire lire par ceux qui sont venus avec l'idée.)}

Answer 1

C++03 (Source: Iterator Invalidation Des Règles (C++03))

---

Insertion

Les conteneurs de séquence

• vector: tous les itérateurs et les références avant le point d'insertion ne sont pas affectées, à moins que le nouveau conteneur de la taille est supérieure à la capacité précédente (dans ce cas, tous les itérateurs et les références sont invalidés) [23.2.4.3/1]
• deque: tous les itérateurs et les références sont invalidés, à moins que le insérée membre est à la fin (avant ou arrière) de la deque (dans ce cas, tous les itérateurs sont invalidés, mais les références à des éléments ne sont pas affectés) [23.2.1.3/1]
• list: tous les itérateurs et les références affectée [23.2.2.3/1]

Conteneurs associatifs

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

Conteneur des adaptateurs

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

---

L'effacement

Les conteneurs de séquence

• vector: chaque itérateur de référence et après le point d'effacement est invalidé [23.2.4.3/3]
• deque: tous les itérateurs et les références sont invalidés, à moins que le effacé les membres sont à la fin (avant ou arrière) de la deque (dans ce cas, seuls les itérateurs et les références à la effacées les membres sont invalidés) [23.2.1.3/4]
• list: seuls les itérateurs et les références à la effacées élément est invalidé [23.2.2.3/3]

Conteneurs associatifs

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

Conteneur des adaptateurs

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

---

Le redimensionnement

• vector: conformément à insérer/effacer [23.2.4.2/6]
• deque: conformément à insérer/effacer [23.2.1.2/1]
• list: conformément à insérer/effacer [23.2.2.2/1]

---

Note 1

À moins d'indication contraire(soit explicitement ou par la définition d'une fonction en ce qui concerne les autres fonctions), en invoquant un conteneur en fonction de membre ou de passage un conteneur comme un argument pour une fonction de la bibliothèque ne doit pas invalider les itérateurs , ou modifier les valeurs de, les objets à l'intérieur du conteneur. [23.1/11]

Note 2

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

Note 3

Les règles pour l'invalidation de pointeurs sont les mêmes que les règles de l'invalidation de références.

Answer 2

C++11 (Source: Iterator Invalidation des Règles (C++0x))

---

Insertion

Les conteneurs de séquence

• vector: tous les itérateurs et les références avant le point d'insertion ne sont pas affectées, à moins que le nouveau conteneur de la taille est supérieure à la capacité précédente (dans ce cas, tous les itérateurs et les références sont invalidés) [23.3.6.5/1]
• deque: tous les itérateurs et les références sont invalidés, à moins que le insérée membre est à la fin (avant ou arrière) de la deque (dans ce cas, tous les itérateurs sont invalidés, mais les références à des éléments ne sont pas affectés) [23.3.3.4/1]
• list: tous les itérateurs et les références affectée [23.3.5.4/1]
• forward_list: tous les itérateurs et les références affectée (s'applique à l' insert_after) [23.3.4.5/1]
• array: (n/a)

Conteneurs associatifs

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

Des ménagères de conteneurs associatifs

• unordered_[multi]{set,map}: tous les itérateurs invalidé lors de la redéfinition de se produit, mais les références affectée [23.2.5/8]. La redéfinition de ne pas se produire si l'insertion n'est pas la cause du conteneur de la taille de dépasser z * B où z est le maximum du facteur de charge et B le nombre de seaux. [23.2.5/14]

Conteneur des adaptateurs

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

---

L'effacement

Les conteneurs de séquence

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

Conteneurs associatifs

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

Non ordonnée conteneurs associatifs

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

Conteneur des adaptateurs

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

---

Le redimensionnement

• vector: conformément à insérer/effacer [23.3.6.5/12]
• deque: conformément à insérer/effacer [23.3.3.3/3]
• list: conformément à insérer/effacer [23.3.5.3/1]
• forward_list: conformément à insérer/effacer [23.3.4.5/25]
• array: (n/a)

---

Note 1

À moins d'indication contraire(soit explicitement ou par la définition d'une fonction en ce qui concerne les autres fonctions), en invoquant un conteneur en fonction de membre ou de passage un conteneur comme un argument pour une fonction de la bibliothèque ne doit pas invalider les itérateurs , ou modifier les valeurs de, les objets à l'intérieur du conteneur. [23.2.1/11]

Note 2

pas de swap() la fonction invalide toute des références, des indicateurs ou des itérateurs en se référant aux éléments de la les conteneurs d'être échangé. [ Note: L' fin() itérateur ne fait pas référence à élément, de sorte qu'il peut être invalidé. -la note de fin ] [23.2.1/10]

Note 3

Autres que la réserve mentionnée ci-dessus concernant l' swap(), il n'est pas clair si "fin" les itérateurs sont soumis à l'énumérés ci-dessus, par-conteneur des règles; vous devez supposer que, de toute façon, qu'ils sont.

Note 4

vector et tous les non-ordonnée des conteneurs associatifs de soutien reserve(n) qui garantit qu'aucun redimensionnement automatique se poursuivront au moins jusqu'à ce que la taille du récipient pousse à l' n. Des précautions doivent être prises avec non ordonnée conteneurs associatifs en raison d'une future proposition permettra à la spécification d'un minimum de facteur de charge, ce qui permettrait à la redéfinition de se produire sur insert après un nombre suffisant d' erase des opérations de réduire la taille du conteneur en dessous du minimum; la garantie doit être considéré comme potentiellement nulle après un erase.

Answer 3

Il est probablement utile d'ajouter que d'un itérateur d'insertion de tout type (std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator) est garantie reste valide aussi longtemps que toutes les insertions sont réalisées à travers cet itérateur et pas d'autres itérateur-invalider événement se produit.

Par exemple, lorsque vous effectuez une série d'opérations d'insertion en std::vector par l'aide d' std::insert_iterator il est tout à fait possible que le vecteur de l'expérience d'une réaffectation de l'événement, ce qui entraînera la nullité de tous les itérateurs que "le point" dans ce vecteur. Toutefois, l'insertion d'itérateur en question est garantie reste valide, c'est à dire que vous pouvez en toute sécurité continuer la séquence d'insertions. Il n'y a pas besoin de s'inquiéter à propos du déclenchement de vecteur de réaffectation.

Encore une fois, cela ne s'applique qu'aux insertions effectuées par le biais de l'insertion d'itérateur lui-même. Si l'itérateur-invalider événement est déclenché par une action sur le conteneur, puis l'insérer itérateur devient invalidés en conformité avec les 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 réaffecter quelque part au milieu de ce processus.

Answer 4

Depuis que cette question attire tant de voix et devient une FAQ, je suppose qu'il serait mieux d'écrire une réponse distincte à mentionner une différence significative entre le C++03 et C++11 en ce qui concerne l'impact de l' std::vectors'insertion de l'opération sur la validité des itérateurs et les références à l'égard reserve() et capacity(), dont la plus upvoted réponse manqué de remarquer.

C++ 03:

Réaffectation annule tous les renvois, les pointeurs et les itérateurs se référant à des éléments dans la séquence. Il est garanti qu'aucun réaffectation a lieu pendant les insertions qui se produisent après un appel à (réserve) jusqu'au moment où une insertion ferait la taille de la vecteur plus grande que la taille spécifiée dans l'appel le plus récent pour (réserve).

C++11:

Réaffectation annule tous les renvois, les pointeurs et les itérateurs se référant à des éléments dans la séquence. Il est garanti qu'aucun réaffectation a lieu pendant les insertions qui se produisent après un appel à (réserve) jusqu'au moment où une insertion ferait la taille de la vecteur plus grande que la valeur de la capacité().

Donc, en C++03, il 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 la réponse, au lieu de cela, il doit être "greater than the size specified in the most recent call to reserve()". C'est une chose que le C++03 diffère du C++11. En C++03, une fois l' insert() causes de la taille du vecteur d'atteindre la valeur spécifiée dans la précédente reserve() appel (ce qui pourrait bien être plus petite que l'actuelle capacity() depuis reserve() pourrait entraîner un plus grand capacity() que demandé), tout insert() pourrait provoquer la réaffectation et la nullité de tous les itérateurs et les références. En C++11, cela ne se produira pas et vous pouvez toujours vous fier capacity() savoir avec certitude que la prochaine réaffectation n'aura pas lieu avant la taille des viaducs capacity().

En conclusion, si vous travaillez avec un C++03 vecteur et vous voulez vous assurer une réaffectation de ne pas se produire lorsque vous effectuez l'insertion, c'est la valeur de l'argument-vous déjà passé à l' reserve() que vous devriez vérifier la taille contre, pas la valeur de retour d'un appel à l' capacity(), sinon vous risquez d'obtenir vous-même surpris à un "prématuré" de réaffectation.