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


204

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


19
Zgaduję „ponieważ to, co mówi standard”, nie da rady, prawda? :)
Luchian Grigore

39
@LuchianGrigore: Oczywiście, że nie. To podważyłoby nasz szacunek dla (osób stojących za) standardu. Powinniśmy oczekiwać, że istnieje powód wyboru dokonanego przez standard.
Kerrek SB

4
Krótko mówiąc, komputery nie liczą się jak ludzie. Ale jeśli zastanawiasz się, dlaczego ludzie nie liczą się jak komputery, polecam The Nothing That Is: A Natural History of Zero, aby uzyskać dogłębne spojrzenie na kłopoty, jakie ludzie odkryli, że liczba jest o jeden mniejsza niż jeden.
John McFarlane

8
Ponieważ istnieje tylko jeden sposób na wygenerowanie „ostatniego”, często nie jest tani, ponieważ musi być prawdziwy. Generowanie „spadłeś z krawędzi klifu” jest zawsze tanie, zrobi to wiele możliwych reprezentacji. (void *) „ahhhhhhh” zrobi dobrze.
Hans Passant

6
Spojrzałem na datę pytania i przez chwilę myślałem, że żartujesz.
Asaf

Odpowiedzi:


286

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 0 , n 1 ) [ n 1 , n 2 ) [ n 2 , n 3 ). 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].


2
Typowe C dla iteracji pętli w tablicy o rozmiarze N to „dla (i = 0; i <N; i ++) a [i] = 0;”. Teraz nie można tego wyrazić bezpośrednio za pomocą iteratorów - wielu ludzi zmarnowało czas, próbując nadać <sens. Ale prawie równie oczywiste jest powiedzenie „for (i = 0; i! = N; i ++) ...” Odwzorowanie 0 na początek i N na koniec jest zatem wygodne.
Krazy Glew

3
@KrazyGlew: Celowo nie umieściłem typów w moim przykładzie pętli. Jeśli myślisz begini endjak ints z wartościami 0i N, odpowiednio, to pasuje idealnie. Prawdopodobnie jest to !=stan bardziej naturalny niż tradycyjny <, ale nigdy tego nie odkryliśmy, dopóki nie zaczęliśmy myśleć o bardziej ogólnych kolekcjach.
Kerrek SB

4
@KerrekSB: Zgadzam się, że „nigdy nie odkryliśmy, że [! = Jest lepszy], dopóki nie zaczęliśmy myśleć o bardziej ogólnych kolekcjach”. IMHO jest jedną z rzeczy, za które Stepanov zasługuje na uznanie - mówiąc o kimś, kto próbował napisać takie biblioteki szablonów przed STL. Będę jednak spierał się o to, że „! =” Jest bardziej naturalny - a raczej twierdzę, że! = Prawdopodobnie wprowadził błędy, które <mogłyby się wyłapać. Pomyśl o (i = 0; i! = 100; i + = 3) ...
Krazy Glew

@KrazyGlew: Twój ostatni punkt jest nieco nie na temat, ponieważ sekwencja {0, 3, 6, ..., 99} nie ma formy, o którą poprosił PO. Jeśli chcesz, aby tak było, powinieneś napisać ++-powtarzalny szablon iteratora step_by<3>, który miałby wówczas pierwotnie reklamowaną semantykę.
Kerrek SB

@KrazyGlew Nawet jeśli <kiedyś ukryje błąd, i tak jest to błąd . Jeśli ktoś użyje tego, !=kiedy powinien <, to jest to błąd. Nawiasem mówiąc, tego króla błędów można łatwo znaleźć dzięki testom jednostkowym lub stwierdzeniom.
Phil1970

80

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.


2
To jest najlepsza odpowiedź IMHO, ale myślę, że lepiej byłoby ją zilustrować, gdyby iteratory wskazywały na liczby, a elementy znajdujące się między liczbami (składnia foo[i]) są skrótem dla pozycji bezpośrednio po pozycji i). Myśląc o tym, zastanawiam się, czy użyteczne byłoby, gdyby język miał osobne operatory dla „elementu bezpośrednio po pozycji i” i „elementu tuż przed pozycją i”, ponieważ wiele algorytmów działa z parami sąsiednich elementów i mówi „ Elementy po obu stronach pozycji i mogą być czystsze niż „Elementy w pozycjach i i i + 1”.
supercat

@ supercat: Liczby nie miały wskazywać pozycji / indeksów iteratora, ale same elementy. Zastąpię cyfry literami, aby było to bardziej zrozumiałe. Rzeczywiście, przy podanych liczbach begin[0](zakładając , że iterator o dostępie swobodnym) uzyskałby dostęp do elementu 1, ponieważ 0w mojej przykładowej sekwencji nie ma elementu .
celtschk

Dlaczego słowo „start” jest używane zamiast „start”? W końcu „start” jest czasownikiem.
user1741137,

@ user1741137 Myślę, że „początek” ma być skrótem „początek” (co teraz ma sens). „początek” jest za długi, „początek” brzmi jak niezłe dopasowanie. „start” byłoby w konflikcie z czasownikiem „start” (na przykład, gdy musisz zdefiniować funkcję start()w swojej klasie, aby rozpocząć określony proces lub cokolwiek innego, byłoby denerwujące, gdyby kolidował z już istniejącym).
Fareanor

74

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.

64

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 ?!


2
To bardzo niedoceniana odpowiedź. Przykłady są zwięzłe i od razu do rzeczy, a „także” nie zostały powiedziane przez nikogo innego i są to rzeczy, które wydają się bardzo oczywiste z perspektywy czasu, ale uderzają mnie jak objawienia.
underscore_d

@underscore_d: Dziękuję !! :)
user541686,

btw, na wypadek, gdybym wydawał się hipokrytą za brak entuzjazmu, to dlatego, że zrobiłem to już w lipcu 2016 roku!
underscore_d

@underscore_d: hahaha Nawet tego nie zauważyłem, ale dzięki! :)
user541686,

22

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.


8

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++;
}

0
  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.
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.