Pourquoi push_back ou push_front invalident-ils les iterators de deque?

Le standard C ++ ne spécifie pas comment deque est implémenté. Il n’est pas nécessaire d’atsortingbuer un nouvel espace en allouant un nouveau bloc et en le chaînant sur les précédents. Tout ce qui est nécessaire est que l’insertion à chaque extrémité soit amortie en temps constant.

Ainsi, bien qu’il soit facile de voir comment implémenter deque de telle sorte que cela donne la garantie que vous voulez [*], ce n’est pas la seule façon de le faire.

[*] Les iterators ont une référence à un élément, plus une référence au bloc dans lequel ils se trouvent, afin qu’ils puissent continuer d’avancer / reculer jusqu’aux extrémités du bloc lorsqu’ils les atteignent. De plus, je suppose une référence au deque lui-même, de sorte que l’ operator+ puisse être à temps constant comme prévu pour les iterators à access aléatoire – suivre une chaîne de liens d’un bloc à l’autre n’est pas suffisant.

Ce qui est plus intéressant, c’est que push_back et push_front n’invalident aucune référence aux éléments d’un deque. Seuls les iterators doivent être considérés comme invalides.

La norme, à ma connaissance, ne dit pas pourquoi. Toutefois, si un iterator implémenté était conscient de ses voisins immédiats – comme une liste, – cet iterator deviendrait invalide s’il pointait vers un élément qui se trouvait à la fois au bord du deque et au bord d’un bloc.

Je suppose. push_back / push_front peut allouer un nouveau bloc de mémoire. Un iterator de deque doit savoir quand l’opérateur d’incrémentation / décrémentation doit sauter dans le bloc suivant. L’implémentation peut stocker ces informations dans l’iterator lui-même. Incrémenter / décrémenter un ancien iterator après push_back / push_front peut ne pas fonctionner comme prévu.

Ce code peut échouer ou non avec une erreur d’exécution. Sur mon Visual Studio, il a échoué en mode débogage mais a abouti à la conclusion en mode de publication. Sous Linux, cela causait une erreur de segmentation.

 #include  #include  int main() { std::deque x(1), y(1); std::deque::iterator iterx = x.begin(); std::deque::iterator itery = y.begin(); for (int i=1; i<1000000; ++i) { x.push_back(i); y.push_back(i); ++iterx; ++itery; if(*iterx != *itery) { std::cout << "increment failed at " << i << '\n'; break; } } } 

L’essentiel est de ne pas formuler d’hypothèses, mais de traiter l’iterator comme s’il était invalidé.

Même si cela fonctionne bien maintenant, une version ultérieure du compilateur ou du compilateur d’une autre plate-forme pourrait arriver et casser votre code. Alternativement, un collègue peut venir et décider de transformer votre deque en un vecteur ou une liste chaînée.

Même lorsque vous allouez des morceaux, un insert entraînera la réallocation de ce morceau en particulier s’il n’y a pas assez d’espace (comme dans le cas des vecteurs).

Un iterator n’est pas simplement une référence aux données. Il faut savoir incrémenter, etc.

Afin de prendre en charge l’access aléatoire, les implémentations disposeront d’un tableau dynamic de pointeurs vers les morceaux. L’iterator deque pointe dans ce tableau dynamic. Lorsque la deque grandit, il peut être nécessaire d’atsortingbuer un nouveau bloc. Le tableau dynamic s’agrandira, invalidant ses iterators et, par conséquent, les iterators de deque.

Ainsi, les morceaux ne sont pas réalloués, mais le tableau de pointeurs sur ces morceaux peut l’être. En effet, comme l’a noté Johannes Schaub, les références ne sont pas invalidées.

Notez également que les garanties d’iterator de deque ne sont pas inférieures à celles de vecteur, qui sont également invalidées lorsque le conteneur grandit.

Parce que la norme dit que c’est possible. Il n’impose pas que deque soit implémenté sous forme de liste de morceaux. Il impose une interface particulière avec des conditions préalables et postérieures particulières et des minimums de complexité algorithmique particuliers.

Les développeurs sont libres d’implémenter la chose de la manière qui leur convient, à condition qu’elle réponde à toutes ces exigences. Une implémentation judicieuse peut utiliser des listes de morceaux ou une autre technique avec différents compromis.

Il est probablement impossible de dire qu’une technique est ssortingctement meilleure qu’une autre pour tous les utilisateurs dans toutes les situations. C’est pourquoi la norme laisse aux développeurs une certaine liberté de choix.