Pourquoi les plages d'itérateurs standard [début, fin) au lieu de [début, fin]?

Pourquoi la norme définit-elle end()comme dépassant la fin, plutôt qu'à la fin réelle?

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

• Vous voulez que la taille de la plage à être une simple différence fin  -  commencer ;

• l'inclusion de la borne 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 borne 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 [début, fin] est payante à maintes reprises lorsque vous avez une sorte d'algorithme qui traite de multiples appels imbriqués ou itérés vers des constructions basées sur une plage, qui s'enchaînent naturellement. En revanche, l'utilisation d'une plage doublement fermée entraînerait des codes décalés et extrêmement désagréables et bruyants. Par exemple, considérons une partition [ n ₀ , n ₁ ) [ n ₁ , n ₂ ) [ n ₂ , n ₃ ). Un autre exemple est la boucle d'itération standard for (it = begin; it != end; ++it), qui s'exécute end - beginfois. Le code correspondant serait beaucoup moins lisible si les deux extrémités étaient inclusives - et imaginez comment vous géreriez des plages vides.

Enfin, nous pouvons également expliquer pourquoi le comptage devrait commencer à zéro: avec la convention semi-ouverte pour les plages que nous venons d'établir, si l'on vous donne une plage de N éléments (par exemple pour énumérer les membres d'un tableau), alors 0 est le "début" naturel afin que vous puissiez écrire la plage en [0, N ), sans aucun décalage ou correction gênant.

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

En fait, beaucoup de choses liées aux itérateurs ont soudain beaucoup plus de sens si vous considérez que les itérateurs ne pointent pas sur 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'itérateur "one past end" prend tout de suite un sens immédiat:

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

Manifestement, beginpointe vers le début de la séquence et endpointe vers la fin de la même séquence. Le déréférencement beginaccède à l'élément A, et le déréférencement endn'a aucun sens car il n'y a pas d'élément directement. De plus, l'ajout d'un itérateur iau milieu donne

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

et vous voyez immédiatement que la plage d'éléments de beginà icontient les éléments Aet Bque la plage d'éléments de ià endcontient les éléments Cet D. Le déréférencement idonne à l'élément le droit, c'est-à-dire le premier élément de la deuxième séquence.

Même le "off-by-one" pour les itérateurs inversés devient soudainement évident de cette façon: inverser cette séquence donne:

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

J'ai écrit les itérateurs non inverses (de base) correspondants entre parenthèses ci-dessous. Vous voyez, l'itérateur inverse appartenant à i(que j'ai nommé ri) pointe toujours entre les éléments Bet C. Cependant, en raison de l'inversion de la séquence, l'élément Best maintenant à sa droite.

Pourquoi la norme définit-elle end()comme dépassant la fin, plutôt qu'à la fin réelle?

Car:

1. Il évite une manipulation spéciale 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 itèrent sur les éléments: Les boucles continuent simplement tant qu'elles end()ne sont pas atteintes.

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 du 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 find()retournerait si end()pointé vers un élément valide?
Avez - vous vraiment voulez un autre membre appelé invalid()qui retourne un itérateur invalide ?!
Deux itérateurs est déjà assez douloureux ...

Oh, et voyez cet article connexe .

Aussi:

Si endc'était avant le dernier élément, comment feriez-vous insert()à la vraie fin?!

L'idiome de l'itérateur des plages semi-fermées [begin(), end())est à l'origine basé sur l'arithmétique des pointeurs pour les tableaux simples. Dans ce mode de fonctionnement, vous auriez des fonctions auxquelles un tableau et une taille ont été transmis.

void func(int* array, size_t size)

La conversion en plages semi-fermées [begin, end)est très simple lorsque vous disposez de ces informations:

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

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

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

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

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

Comme les pointeurs vers les tableaux sont des itérateurs 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 semi-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'itérateur qui prend en charge <et >opère en C ++ sont les itérateurs à accès aléatoire. Si vous deviez écrire un <=opérateur pour chaque classe d'itérateurs en C ++, vous auriez à rendre tous vos itérateurs entièrement comparables et vous auriez moins de choix pour créer des itérateurs moins capables (tels que les itérateurs bidirectionnels std::listou les itérateurs d'entrée). qui fonctionnent iostreams) si C ++ utilisait des plages entièrement fermées.

Avec le end()pointage après 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);
}

En end()pointant sur 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 à la !=place de <(moins que) dans des conditions de boucle, il est donc pratique de end()pointer vers une position à la fin.