Pourquoi les plages d’iterators standard au lieu de ?

Pourquoi la norme définit-elle end() comme une au-delà de la fin, au lieu de la fin réelle?

Le meilleur argument est facilement celui de Dijkstra lui – même :

  • Vous voulez que la taille de la plage soit une simple différence de fincommencez ;

  • l’inclusion de la limite inférieure est plus “naturelle” lorsque les séquences dégénèrent en séquences vides, et aussi parce que l’alternative (à l’ exclusion de la limite inférieure) nécessiterait l’existence d’une valeur sentinelle “un avant le début”.

Vous devez toujours justifier pourquoi vous commencez à compter à zéro plutôt qu’à un, mais cela ne faisait pas partie de votre question.

La sagesse derrière la convention [begin, end] est souvent utile lorsque vous disposez de tout type d’algorithme qui traite de multiples appels nesteds ou itérés vers des constructions basées sur des plages, qui enchaînent naturellement. En revanche, utiliser une plage doublement fermée entraînerait des codes non conformes et extrêmement déplaisants et bruyants. Par exemple, considérons une partition [ n 0 , n 1 ) [ n 1 , n 2 ) [ n 2 , n 3 ]. Un autre exemple est la boucle d’itération standard for (it = begin; it != end; ++it) , qui exécute les heures de end - begin . Le code correspondant serait beaucoup moins lisible si les deux extrémités étaient inclusives – et imaginez comment vous gériez les plages vides.

Enfin, nous pouvons également faire un bon argument pour savoir pourquoi le comptage devrait commencer à zéro: avec la convention semi-ouverte pour les plages que nous venons d’établir, si on vous donne une gamme de N éléments (par exemple pour énumérer les membres d’un tableau), 0 est le “début” naturel pour que vous puissiez écrire la plage sous la forme [0, N ], sans aucun décalage ou correction gênant.

En bref: le fait que nous ne voyons pas le numéro 1 partout dans les algorithmes basés sur les plages est une conséquence directe et une motivation pour la convention [début, fin].

Pourquoi la norme définit-elle end() comme une au-delà de la fin, au lieu de la fin réelle?

Car:

  1. Il évite une manipulation particulière pour les plages vides. Pour les plages vides, begin() est égal à end() &
  2. Cela rend le critère de fin simple pour les boucles qui parcourent les éléments: Les boucles continuent simplement tant que end() n’est pas atteint.

En fait, beaucoup de choses liées à un iterator ont soudainement plus de sens si vous considérez les iterators ne pointant pas vers les éléments de la séquence mais entre les deux , le déréférencement accédant directement à l’élément suivant. Ensuite, l’iterator “one past end” prend soudainement tout son sens:

  +---+---+---+---+ | A | B | C | D | +---+---+---+---+ ^ ^ | | begin end 

De toute évidence, les points de début begin au début de la séquence et les points de end à la fin de la même séquence. Déréférencer le begin accède à l’élément A , et la end déréférencement n’a pas de sens car il n’y a pas d’élément approprié. En outre, l’ajout d’un iterator au milieu donne

  +---+---+---+---+ | A | B | C | D | +---+---+---+---+ ^ ^ ^ | | | begin i end 

et vous voyez immédiatement que la gamme d’éléments de begin à i contient les éléments A et B tandis que la gamme d’éléments de i à la end contient les éléments C et D Déréférencer i donne l’élément droit, c’est le premier élément de la deuxième séquence.

Même le “off-by-one” pour les iterators inverses devient soudainement évident de cette manière: Inverser cette séquence donne:

  +---+---+---+---+ | D | C | B | A | +---+---+---+---+ ^ ^ ^ | | | rbegin ri rend (end) (i) (begin) 

J’ai écrit les iterators non inverses (de base) correspondants entre parenthèses ci-dessous. Vous voyez, l’iterator inverse appartenant à i (que j’ai nommé ri ) pointe toujours entre les éléments B et C Cependant, en raison de l’inversion de la séquence, l’élément B est maintenant à droite.

Parce qu’alors

 size() == end() - begin() // For iterators for whom subtraction is valid 

et vous n’aurez pas à faire des choses maladroites comme

 // Never mind that this is INVALID for input iterators... bool empty() { return begin() == end() + 1; } 

et vous n’écrirez pas accidentellement un code erroné comme

 bool empty() { return begin() == end() - 1; } // a typo from the first version // of this post // (see, it really is confusing) bool empty() { return end() - begin() == -1; } // Signed/unsigned mismatch // Plus the fact that subtracting is also invalid for many iterators 

Aussi: Qu’est-ce que find() renverrait si end() désignait un élément valide?
Voulez-vous vraiment un autre membre appelé invalid() qui renvoie un iterator invalide?!
Deux iterators sont déjà assez pénibles …

Oh, et voir ce post connexe .


Aussi:

Si la end était avant le dernier élément, comment inséreriez-vous insert() à la vraie fin?!

L’identificateur d’iterator des plages à moitié fermées [begin(), end()) est à l’origine basé sur l’arithmétique de pointeur pour les tableaux simples. Dans ce mode de fonctionnement, vous auriez des fonctions ayant passé un tableau et une taille.

 void func(int* array, size_t size) 

La conversion en plages semi-fermées [begin, end) est très simple lorsque vous avez cette information:

 int* begin; int* end = array + size; for (int* it = begin; it < end; ++it) { ... } 

Pour travailler avec des plages entièrement fermées, c'est plus difficile:

 int* begin; int* end = array + size - 1; for (int* it = begin; it <= end; ++it) { ... } 

Les pointeurs vers les tableaux étant des iterators en C ++ (et la syntaxe a été conçue pour permettre cela), il est beaucoup plus facile d'appeler std::find(array, array + size, some_value) que d'appeler std::find(array, array + size - 1, some_value) .


De plus, si vous travaillez avec des plages à moitié fermées, vous pouvez utiliser l'opérateur != Pour vérifier la condition de fin, car (si vos opérateurs sont définis correctement) < implique != .

 for (int* it = begin; it != end; ++ it) { ... } 

Cependant, il n'y a pas de moyen facile de le faire avec des plages entièrement fermées. Vous êtes coincé avec <= .

Le seul type d'iterator qui prend en charge les opérations < et > en C ++ sont les iterators à access aléatoire. Si vous deviez écrire un opérateur <= pour chaque classe d'iterators en C ++, vous devriez rendre tous vos iterators totalement comparables, et vous auriez moins de choix pour créer des iterators moins performants (tels que les iterators bidirectionnels sur std::list , ou les iterators d'entrée qui fonctionnent sur iostreams ) si C ++ utilisait des plages entièrement fermées.

Avec la end() pointant vers la fin, il est facile d’itérer une collection avec une boucle for:

 for (iterator it = collection.begin(); it != collection.end(); it++) { DoStuff(*it); } 

Avec end() pointant vers le dernier élément, une boucle serait plus complexe:

 iterator it = collection.begin(); while (!collection.empty()) { DoStuff(*it); if (it == collection.end()) break; it++; } 
  1. Si un conteneur est vide, begin() == end() .
  2. Les programmeurs C ++ ont tendance à utiliser != lieu de < (moins que) dans des conditions de boucle, par conséquent, avoir comme end() pointer sur une position un-du-côté est pratique.