Dlaczego Standardowe zakresy iteratorów [początek, koniec] zamiast [początek, koniec]?

Dlaczego Standard definiuje się end()jako jeden za końcem, a nie na samym końcu?

Najlepszym argumentem łatwo jest ten sam Dijkstra :

• Chcesz, aby wielkość zakresu była prostą różnicą koniec  -  początek ;

• uwzględnienie dolnej granicy jest bardziej „naturalne”, gdy sekwencje ulegają degeneracji do pustych, a także dlatego, że alternatywa (z wyłączeniem dolnej granicy) wymagałaby istnienia wartości wartownika „jeden przed początkiem”.

Nadal musisz uzasadnić, dlaczego zaczynasz liczyć od zera zamiast jednego, ale to nie było częścią twojego pytania.

Mądrość konwencji [początek, koniec] opłaca się raz po raz, gdy masz jakiś algorytm, który zajmuje się wieloma zagnieżdżonymi lub iterowanymi wywołaniami do konstrukcji opartych na zakresie, które łączą się w sposób naturalny. Natomiast użycie podwójnie zamkniętego zakresu wiązałoby się z niepotrzebnym i wyjątkowo nieprzyjemnym i hałaśliwym kodem. Rozważmy na przykład partycję [ n ₀ , n ₁ ) [ n ₁ , n ₂ ) [ n ₂ , n ₃ ). Innym przykładem jest standardowa pętla iteracyjna for (it = begin; it != end; ++it), która działaend - begin razy. Odpowiedni kod byłby znacznie mniej czytelny, gdyby oba końce były włączone - i wyobraź sobie, jak poradzisz sobie z pustymi zakresami.

Na koniec możemy również podać dobry argument, dlaczego liczenie powinno zaczynać się od zera: przy pół-otwartej konwencji dla zakresów, którą właśnie ustaliliśmy, jeśli otrzymasz zakres N elementów (powiedzmy, aby wyliczyć elementy tablicy), to 0 jest naturalnym „początkiem”, dzięki czemu można zapisać zakres jako [0, N ), bez żadnych niewygodnych przesunięć lub korekt.

W skrócie: fakt, że nie widzimy liczby 1wszędzie w algorytmach opartych na zakresie, jest bezpośrednią konsekwencją i motywacją dla konwencji [początek, koniec].

W rzeczywistości wiele rzeczy związanych z iteratorem ma nagle znacznie większy sens, jeśli weźmie się pod uwagę, że iteratory nie wskazują na elementy sekwencji, ale pomiędzy nimi , a dereferencje uzyskują dostęp do następnego elementu bezpośrednio do niego. Wtedy iterator „jeden koniec” nagle ma natychmiastowy sens:

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

Oczywiście beginwskazuje na początek sekwencji i endwskazuje na koniec tej samej sekwencji. Dereferencje uzyskują begindostęp do elementu A, a dereferencje endnie mają sensu, ponieważ nie ma odpowiedniego elementu. Ponadto dodanie iteratora iw środku daje

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

i od razu widać, że zakres elementów od begindo izawiera elementy, Aa Bzakres elementów od ido endzawiera elementy Ci D. Dereferencjei dają pierwszeństwo pierwiastkowi, czyli pierwszemu elementowi drugiej sekwencji.

Nawet „off-by-one” dla iteratorów wstecznych nagle staje się oczywiste w ten sposób: odwrócenie tej sekwencji daje:

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

Odpowiednie iteratory nieodwrócone (podstawowe) napisałem w nawiasach poniżej. Widzisz, iterator do tyłu należący do i(który wymieniłem ri) nadal wskazuje między elementami Bi C. Jednak ze względu na odwrócenie sekwencji element Bjest teraz po prawej stronie.

Dlaczego Standard definiuje się end()jako jeden za końcem, a nie na samym końcu?

Ponieważ:

1. Pozwala to uniknąć specjalnego obchodzenia się z pustymi zakresami. W przypadku pustych zakresów begin()jest równa end()&
2. Ułatwia to końcowe kryterium dla pętli, które iterują po elementach: Pętle po prostu kontynuują, dopóki end()nie zostaną osiągnięte.

Ponieważ wtedy

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

i nie będziesz musiał robić takich niezręcznych rzeczy jak

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

i nie przypadkowo napiszesz błędny kod jak

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

Ponadto: co by zwróciło, find()gdyby end()wskazał prawidłowy element?
Czy naprawdę chcesz innego członka o nazwie, invalid()który zwraca nieprawidłowy iterator ?!
Dwa iteratory są już dość bolesne ...

Aha, i zobacz ten powiązany post .

Również:

Gdyby endbyło przed ostatnim elementem, jak byś to zrobił insert()na prawdziwym końcu ?!

Idiom iteratora półzamkniętych zakresów [begin(), end())jest pierwotnie oparty na arytmetyce wskaźnika dla tablic prostych. W tym trybie pracy będziesz mieć funkcje, którym przekazano tablicę i rozmiar.

void func(int* array, size_t size)

Przekształcenie w półzamknięte zakresy [begin, end)jest bardzo proste, jeśli masz takie informacje:

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

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

Aby pracować z całkowicie zamkniętymi zakresami, trudniej:

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

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

Ponieważ wskaźniki do tablic są iteratorami w C ++ (a składnia została zaprojektowana, aby to umożliwić), o wiele łatwiej jest wywoływać std::find(array, array + size, some_value)niż wywoływać std::find(array, array + size - 1, some_value).

Ponadto, jeśli pracujesz z pół-zamkniętymi zakresami, możesz użyć !=operatora, aby sprawdzić warunek końcowy, ponieważ (jeśli twoje operatory są poprawnie zdefiniowane) <implikuje !=.

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

Jednak nie ma łatwego sposobu na zrobienie tego przy całkowicie zamkniętych zakresach. Utknąłeś z <=.

Jedynym rodzajem iteratora, który obsługuje <i >działa w C ++, są iteratory o dostępie swobodnym. Gdybyś musiał napisać <=operator dla każdej klasy iteratora w C ++, musiałbyś uczynić wszystkie swoje iteratory w pełni porównywalnymi i miałbyś mniej możliwości tworzenia mniej zdolnych iteratorów (takich jak iteratory dwukierunkowe włączone std::listlub iteratory wejściowe które działają dalej iostreams), jeśli C ++ używał całkowicie zamkniętych zakresów.

Z end()wskazując jeden za końcem, to jest łatwe do iteracji zbiór z pętli for:

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

Po end()wskazaniu ostatniego elementu pętla byłaby bardziej złożona:

iterator it = collection.begin();
while (!collection.empty())
{
    DoStuff(*it);

    if (it == collection.end())
        break;

    it++;
}

1. Jeśli pojemnik jest pusty begin() == end().
2. Programiści C ++ mają tendencję do używania !=zamiast <(mniej niż) w warunkach pętli, dlatego end()wskazanie jednej pozycji jest wygodne.