Por que os intervalos padrão do iterador são em vez de ?

Por que o padrão define end() como passado do final, em vez de no final real?

O melhor argumento é facilmente aquele feito pelo próprio Dijkstra :

  • Você quer que o tamanho do intervalo seja um simples fim de diferença – comece ;

  • incluindo o limite inferior é mais “natural” quando as sequências se degeneram para as vazias, e também porque a alternativa ( excluindo o limite inferior) exigiria a existência de um valor sentinela “um-antes-do-princípio”.

Você ainda precisa justificar por que começa a contar com zero em vez de um, mas isso não fazia parte da sua pergunta.

A sabedoria por trás da convenção [begin, end] vale a pena quando você tem qualquer tipo de algoritmo que lida com várias chamadas aninhadas ou iteradas para construções baseadas em intervalos, que são encadeadas naturalmente. Por outro lado, o uso de um alcance duplamente fechado criaria códigos off-by-ones e extremamente desagradáveis ​​e ruidosos. Por exemplo, considere uma partição [ n 0 , n 1 ) [ n 1 , n 2 ) [ n 2 , n 3 ). Outro exemplo é o loop de iteração padrão for (it = begin; it != end; ++it) , que executa os tempos de end - begin . O código correspondente seria muito menos legível se ambas as extremidades fossem inclusivas – e imagine como você lidaria com intervalos vazios.

Finalmente, também podemos fazer um bom argumento porque a contagem deve começar no zero: Com a convenção semiaberta para intervalos que acabamos de estabelecer, se você receber um intervalo de N elementos (digamos, para enumerar os membros de uma matriz), 0 é o “começo” natural para que você possa escrever o intervalo como [0, N ), sem quaisquer deslocamentos ou correções inadequados.

Em poucas palavras: o fato de não vermos o número 1 em todos os lugares nos algoritmos baseados em intervalos é uma conseqüência direta e motivadora da convenção [início, fim].

Por que o padrão define end() como passado do final, em vez de no final real?

Porque:

  1. Evita o manuseio especial para intervalos vazios. Para intervalos vazios, begin() é igual a end() e
  2. Torna o critério final simples for loops que iteram sobre os elementos: Os loops simplesmente continuam enquanto end() não é atingido.

Na verdade, muitas coisas relacionadas ao iterador de repente fazem muito mais sentido se você considerar que os iteradores não apontam para os elementos da sequência, mas entre eles , com a desreferência acessando o próximo elemento diretamente para ela. Então, o iterador “one past end” faz sentido imediato:

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

Obviamente, begin apontar para o início da sequência e finalize para o final da mesma sequência. A desreferenciação begin acessa o elemento A , e o end desreferenciação não faz sentido, porque não há elemento certo para isso. Além disso, adicionando um iterador i no meio dá

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

e você vê imediatamente que o intervalo de elementos de begin para i contém os elementos A e B enquanto o intervalo de elementos de i to end contém os elementos C e D A desreferenciação i fornece o elemento correto, que é o primeiro elemento da segunda sequência.

Até mesmo o “off-by-one” para os iteradores reversos se torna óbvio dessa maneira: Invertendo essa sequência:

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

Eu escrevi os iteradores correspondentes não-reversos (base) entre parênteses abaixo. Você vê, o iterador reverso pertencente a i (que eu chamei de ri ) ainda aponta entre os elementos B e C No entanto, devido à reversão da sequência, agora o elemento B está à direita.

Porque então

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

e você não terá que fazer coisas estranhas como

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

e você não vai escrever acidentalmente códigos errados como

 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 

Também: O que seria find() return if end() apontado para um elemento válido?
Você realmente quer outro membro chamado invalid() que retorna um iterador inválido ?!
Dois iteradores já são dolorosos o suficiente …

Ah, e veja este post relacionado .


Além disso:

Se o end foi antes do último elemento, como você insert() no final verdadeiro ?!

O idioma do iterador de intervalos semifechados [begin(), end()) é originalmente baseado na aritmética de pointers para matrizes simples. Nesse modo de operação, você teria funções que foram passadas uma matriz e um tamanho.

 void func(int* array, size_t size) 

A conversão para intervalos semifechados [begin, end) é muito simples quando você tem essa informação:

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

Para trabalhar com intervalos totalmente fechados, é mais difícil:

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

Como os pointers para arrays são iteradores em C ++ (e a syntax foi projetada para permitir isso), é muito mais fácil chamar std::find(array, array + size, some_value) do que chamar std::find(array, array + size - 1, some_value) .


Além disso, se você trabalha com intervalos semifechados, você pode usar o operador != Para verificar a condição final, porque (se seus operadores estão definidos corretamente) < implica != .

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

No entanto, não há uma maneira fácil de fazer isso com intervalos totalmente fechados. Você está preso com <= .

O único tipo de iterador que suporta as operações < e > em C ++ são os iteradores de access random. Se você tivesse que escrever um operador <= para cada iterador em C ++, você teria que tornar todos os seus iteradores totalmente comparáveis, e você teria menos opções para criar iteradores menos capazes (como os iteradores bidirecionais em std::list , ou os iteradores de input que operam no iostreams ) se o C ++ usou intervalos totalmente fechados.

Com o end() apontando um passado para o final, é fácil iterar uma coleção com um loop for:

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

Com o end() apontando para o último elemento, um loop seria mais complexo:

 iterator it = collection.begin(); while (!collection.empty()) { DoStuff(*it); if (it == collection.end()) break; it++; } 
  1. Se um container estiver vazio, begin() == end() .
  2. Programadores C ++ tendem a usar != vez de < (menor que) em condições de loop, portanto, ter end() apontando para uma posição off-the-end é conveniente.