Dlaczego Standardowe zakresy iteratora są [begin, end] zamiast [begin, end]?
Dlaczego Standard definiuje end()
jako jeden po końcu, a nie na samym końcu?
7 answers
Najlepszym argumentem jest ten, który przedstawił Sam Dijkstra:
Chcesz, aby rozmiar zakresu był różnicą prostą end - begin;
Włączenie dolnej granicy jest bardziej "naturalne", gdy sekwencje zdegenerują się do pustych, a także dlatego, że alternatywa (wyłączając dolną granicę) wymagałaby istnienia wartości wartowniczej "przed-początkiem".
Nadal musisz uzasadnić dlaczego zaczynasz liczyć od zera, a nie od jednego, ale to nie było częścią twojego pytania.
Mądrość stojąca za konwencją [begin, end] opłaca się raz po raz, gdy masz jakiś algorytm, który zajmuje się wieloma zagnieżdżonymi lub iteracyjnymi wywołaniami do konstrukcji opartych na zakresach, które naturalnie łączą się. Z kolei użycie zakresu podwójnie zamkniętego powodowałoby off-by-One oraz niezwykle nieprzyjemny i hałaśliwy kod. Na przykład rozważmy partycję [ n0, n1)[n1, n2)[n2,n3). Innym przykładem jest standardowa pętla iteracji for (it = begin; it != end; ++it)
, która uruchamia end - begin
razy. Odpowiedni kod byłby znacznie mniej czytelny, gdyby oba końce były włączone – i wyobraź sobie, jak radzisz sobie z pustymi zakresami.
Wreszcie, możemy również zrobić miły argument, dlaczego liczenie powinno zaczynać się od zera: z półotwartą konwencją dla zakresów, które właśnie ustaliliśmy, jeśli podano zakres N elementów (np. aby wyliczyć elementy tablicy), to 0 jest naturalnym "początkiem", więc można zapisać zakres jako [0, N), bez żadnych niewygodnych korekt i korekt.
W skrócie: fakt, że nie widzimy liczby 1
wszędzie w algorytmach opartych na zakresach jest bezpośrednią konsekwencją i motywacją dla konwencji [begin, end].
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-07-04 10:41:40
Dlaczego Standard definiuje end()
jako jeden po końcu, a nie na samym końcu?
Ponieważ:
- unika specjalnej obsługi pustych zakresów. Dla pustych zakresów
begin()
jest równeend()
& - to sprawia, że kryterium końcowe jest proste dla pętli, które iterują nad elementami: pętle po prostu
Kontynuuj tak długo, jak długo
end()
nie zostanie osiągnięty.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-04-01 14:54:12
Właściwie, wiele rzeczy związanych z iteratorem nagle nabiera większego sensu, jeśli weźmiemy pod uwagę Iteratory nie wskazujące na elementy sekwencji, ale pomiędzy , z dereferencją dostępującą do następnego elementu bezpośrednio do niego. Następnie iterator "one past end" nagle nabiera natychmiastowego sensu: {]}
+---+---+---+---+
| A | B | C | D |
+---+---+---+---+
^ ^
| |
begin end
Oczywiście begin
wskazuje na początek sekwencji, a end
wskazuje na koniec tej samej sekwencji. Dereferencja begin
uzyskuje dostęp do elementu A
, oraz dereferencja end
nie ma sensu, ponieważ nie ma w tym żadnego elementu. Ponadto dodanie iteratora i
w środku daje
+---+---+---+---+
| A | B | C | D |
+---+---+---+---+
^ ^ ^
| | |
begin i end
I od razu widać, że zakres elementów od begin
do i
zawiera elementy A
i B
, podczas gdy zakres elementów od i
do end
zawiera elementy C
i D
. Dereferencja i
daje element prawa do niego, czyli pierwszy element drugiego ciągu.
Nawet "off-by-one" dla odwrotnej Iteratory nagle stają się oczywiste w ten sposób: odwrócenie tej sekwencji daje: {]}
+---+---+---+---+
| D | C | B | A |
+---+---+---+---+
^ ^ ^
| | |
rbegin ri rend
(end) (i) (begin)
Napisałem odpowiednie Iteratory nie-odwrotne (bazowe) w nawiasach poniżej. Widzisz, iterator odwrotny należący do i
(który nazwałem ri
) wciąż punkty pomiędzy elementami B
i C
. Jednak ze względu na odwrócenie sekwencji, teraz element B
jest po prawej stronie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-17 17:03:05
Ponieważ wtedy
size() == end() - begin() // For iterators for whom subtraction is valid
I nie będziesz musiał robić niezręcznych rzeczy takich jak
// Never mind that this is INVALID for input iterators...
bool empty() { return begin() == end() + 1; }
I nie napiszesz przypadkiem błędnego kodu 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
Również: co by find()
zwróciło, gdyby end()
wskazywało na poprawny element?
Czy naprawdę chcesz innego członka o nazwie invalid()
, który zwraca nieprawidłowy iterator?!
Dwa Iteratory są już wystarczająco bolesne...
Oh, I Zobacz to related post .
Także:
Gdyby end
było przed ostatnim elementem, jak insert()
na prawdziwym końcu?!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-04-01 16:10:59
Idiom iteratora półzamkniętych zakresów [begin(), end())
jest pierwotnie oparty na arytmetyce wskaźników dla zwykłych tablic. W tym trybie pracy, będziesz miał funkcje, które zostały przekazane tablicy i rozmiar.
void func(int* array, size_t size)
Konwersja na półzamknięte zakresy [begin, end)
jest bardzo prosta, gdy masz taką informację:
int* begin;
int* end = array + size;
for (int* it = begin; it < end; ++it) { ... }
Aby pracować z całkowicie zamkniętymi zakresami, jest 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 na to zaprojektowana), jest to dużo łatwiejsze do wywołania std::find(array, array + size, some_value)
niż do wywołania std::find(array, array + size - 1, some_value)
.
Plus, jeśli pracujesz z półzamkniętymi zakresami, możesz użyć operatora !=
do sprawdzenia warunku końcowego, becuase (jeśli Twoje operatory są poprawnie zdefiniowane) <
implikuje !=
.
for (int* it = begin; it != end; ++ it) { ... }
Jednak nie ma łatwego sposobu, aby to zrobić z całkowicie zamkniętymi zakresami. Utknąłeś z <=
.
<
i >
W C++ są Iteratory o dostępie losowym. Gdybyś musiał napisać Operator <=
dla każdej klasy iteratora w C++, musiałbyś uczynić wszystkie Iteratory w pełni porównywalnymi i miałbyś mniej możliwości tworzenia mniej wydajnych iteratorów (takich jak dwukierunkowe Iteratory na std::list
lub Iteratory wejściowe działające na iostreams
), gdyby C++ używał w pełni zamkniętych zakresów.Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-04-01 14:05:22
Z end()
wskazując jeden za końcem, łatwo jest iterować zbiór za pomocą pętli for:
for (iterator it = collection.begin(); it != collection.end(); it++)
{
DoStuff(*it);
}
Z end()
wskazaniem na ostatni element, pętla byłaby bardziej złożona:
iterator it = collection.begin();
while (!collection.empty())
{
DoStuff(*it);
if (it == collection.end())
break;
it++;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-05-17 20:12:53
- jeśli pojemnik jest pusty,
begin() == end()
. - Programiści C++ mają tendencję do używania
!=
zamiast<
(mniej niż) w Warunkach pętli, dlatego posiadanieend()
wskazywania na jedną pozycję poza końcem jest wygodne.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-11-27 15:34:48