Pourquoi sont standard itérateur intervalle [début, fin) au lieu de [début, fin]?

Question

Pourquoi le C++ standard définissent end() comme un passé la fin, au lieu d'être à la fin?

Answer 1

Le meilleur argument facilement est celle faite par Dijkstra lui-même:

• Vous voulez que la taille de la portée à une simple différence de la fin − de commencer;

• dont la limite inférieure est plus "naturel" que lorsque des séquences dégénérées à vide, et aussi parce que l'alternative (à l'exclusion de la limite inférieure) supposent l'existence d'un "avant le début des" sentinelles de la valeur.

Vous avez encore besoin de justifier pourquoi vous commencez à compter à zéro plutôt que de un, mais ce n'était pas une partie de votre question.

La sagesse derrière l' [début, fin) de la convention de paie à temps et à nouveau lorsque vous avez toute sorte d'algorithme qui traite de multiples imbriquées ou itéré calles de gamme à base de constructions, de la chaîne naturellement. En revanche, à l'aide d'un doublement fermée gamme subirait tout-en-un et extrêmement désagréable et bruyant code. Par exemple, considérons une partition de [n₀, n₁)[n₁, n₂)[n₂,n₃). Un autre exemple est le standard de la boucle d'itération for (it = begin; it != end; ++it), qui s'exécute end - begin temps. Le code correspondant serait beaucoup moins lisible si les deux extrémités ont été inclus et imaginez comment vous pouvez gérer vide plages.

Enfin, on peut aussi faire un bon argument pourquoi le comptage doit commencer à zéro: Avec la demi-ouvert de convention pour les plages qui nous vient de mettre en place, si vous êtes donné une gamme de N éléments (dire à énumérer les membres d'un tableau), alors 0 est le "début" de sorte que vous pouvez écrire que la fourchette [0, N), sans maladroites des décalages ou des corrections.

En un mot: le fait que nous ne voyons pas le nombre 1 partout dans la gamme de base des algorithmes est une conséquence directe de l', et de la motivation, de la [début, fin) de la convention.

Answer 2

En fait, beaucoup de itérateur choses liées soudainement fait beaucoup plus de sens si l'on considère les itérateurs ne pointe pas sur les éléments de la séquence, mais entre les deux, avec déférence accéder à l'élément suivant. Ensuite, le "passé" de fin d'itérateur rend soudainement sens immédiat:

   +---+---+---+---+
   | 1 | 2 | 3 | 4 |
   +---+---+---+---+
   ^               ^
   |               |
 begin            end

Évidemment begin points au début de la séquence, et end de points à la fin de la même séquence. Un déréférencement begin accède à l'élément 1, et de déférence end n'ont pas de sens, car il n'y a aucun élément de droit. Aussi, l'ajout d'un itérateur i dans le milieu donne

   +---+---+---+---+
   | 1 | 2 | 3 | 4 |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
 begin     i      end

et vous voyez immédiatement que la gamme d'éléments de l' begin de i contient les éléments 1 et 2 tandis que la gamme d'éléments de l' i de end contient les éléments 3 et 4. Un déréférencement i donne à l'élément de droite, qui est le premier élément de la deuxième séquence.

Même le "tout-en-un" pour inverser les itérateurs d'un coup, devient évidente de cette façon: Inverser cette séquence donne:

   +---+---+---+---+
   | 4 | 3 | 2 | 1 |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
rbegin     ri     rend
 (end)    (i)   (begin)

J'ai écrit le correspondant non l'inverse (de base) des itérateurs entre parenthèses ci-dessous. Vous le voyez, l'itérateur inverse, appartenant à l' i (que j'ai nommé ri) toujours les points entre les deux éléments 2 et 3. Cependant, en raison de l'inversion de la séquence, en maintenant l'élément 2 est sur la droite.

Answer 3

Pourquoi la Norme de définir end() comme un passé la fin, au lieu d'être à la fin?

Parce que:

1. Il évite un traitement spécial pour vider les plages. Pour vider les plages, begin() est égal à end() &
2. Il fait la fin critère simple pour boucle qui itère sur les éléments: Les boucles tout simplement continuer tant que end() n'est pas atteint.

Answer 4

Car alors

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

et vous n'aurez pas à faire maladroite des choses comme

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

et vous n'aurez pas accidentellement écrire de 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: Que serait - find() de retour si end() a souligné un élément valide?
Avez-vous vraiment envie d'un autre membre demande l' invalid() qui retourne un invalide itérateur?!
Deux itérateurs est déjà assez pénible...

Oh, et voir ce poste.

---

Aussi:

Si l' end a été avant le dernier élément, comment voulez-vous insert() à la fin?!

Answer 5

L'itérateur idiome de la moitié fermé gammes [begin(), end()) est à l'origine basée sur l'arithmétique des pointeurs de simples tableaux. Dans ce mode de fonctionnement, vous avez des fonctions qui lui ont été transmis un tableau et une taille.

void func(int* array, size_t size)

La conversion à demi-fermé gammes [begin, end) est très simple, quand vous avez cette information:

int* begin;
int* end = array + size;

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

Travailler avec entièrement clos des plages, il est plus difficile:

int* begin;
int* end = array + size - 1;

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

Depuis pointeurs de tableaux sont des itérateurs en C++ (et la syntaxe a été conçu pour permettre cela), il est beaucoup plus facile d'appeler std::find(array, array + size, some_value) que c'est appeler std::find(array, array + size - 1, some_value).

---

De Plus, si vous travaillez avec des demi-clos des plages, vous pouvez utiliser l' != de l'opérateur afin de vérifier la condition de fin, parce que (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 entièrement clos des plages. Vous êtes coincé avec <=.

Le seul type d'itérateur qui soutient < et > des opérations en C++ sont en accès aléatoire itérateurs. Si vous aviez à écrire un <= opérateur pour chaque classe iterator en C++, vous devez faire tous vos itérateurs entièrement comparables, et il y aurait moins de choix pour la création de moins en moins capable itérateurs (tels que les itérateurs bidirectionnels sur std::list, ou l'entrée des itérateurs qui opèrent sur iostreams) si C++ utilisé entièrement clos des plages.