Почему стандартные диапазоны итераторов [начало, конец) вместо [начало, конец]?
Почему Стандарт определяет end() как один за концом, а не за реальный конец?
7 ответов
Лучшим аргументом легко является тот, который выдвинул сам Дейкстра:
Вы хотите, чтобы размер диапазона был простой разницей - начало;
включение нижней границы является более "естественным", когда последовательности вырождаются в пустые, а также потому, что альтернатива (исключая нижнюю границу) потребует существования значения "один перед началом".
Вам все еще нужно объяснить, почему вы начинаете считать с нуля, а не с одного, но это не было частью вашего вопроса.
Мудрость, лежащая в основе соглашения [начало, конец), окупается снова и снова, когда у вас есть какой-либо алгоритм, который имеет дело с несколькими вложенными или повторяющимися вызовами конструкций на основе диапазона, которые естественным образом объединяются. Напротив, использование дважды закрытого диапазона повлечет за собой посторонний и крайне неприятный и шумный код. Например, рассмотрим раздел [ n 0, n 1) [ n 1, n 2) [ n 2, n 3). Другой пример - стандартный итерационный цикл for (it = begin; it != end; ++it), который работает end - begin раз. Соответствующий код был бы намного менее читабельным, если бы оба конца были включительно - и представьте, как вы будете обрабатывать пустые диапазоны.
Наконец, мы также можем привести хороший аргумент, почему подсчет должен начинаться с нуля: с полуоткрытым соглашением для диапазонов, которое мы только что установили, если вам дан диапазон из N элементов (скажем, для перечисления членов массива), тогда 0 является естественным "началом", так что вы можете записать диапазон как [0, N), без каких-либо неловких смещений или исправлений.
В двух словах: тот факт, что мы не видим число 1 повсюду в алгоритмах, основанных на диапазоне, это прямое следствие и мотивация соглашения [начало, конец).
На самом деле, многие вещи, связанные с итераторами, внезапно приобретают гораздо больший смысл, если учесть, что итераторы указывают не на элементы последовательности, а между ними, с разыменованием доступа к следующему элементу прямо к нему. Тогда итератор "один конец" внезапно приобретает смысл:
+---+---+---+---+
| A | B | C | D |
+---+---+---+---+
^ ^
| |
begin end
очевидно begin указывает на начало последовательности, и end указывает на конец той же последовательности. Разыменование begin получает доступ к элементу Aи разыменование end не имеет смысла, потому что нет никакого права на это. Также добавляем итератор i в середине дает
+---+---+---+---+
| A | B | C | D |
+---+---+---+---+
^ ^ ^
| | |
begin i end
и вы сразу видите, что диапазон элементов из begin в i содержит элементы A а также B в то время как диапазон элементов из i в end содержит элементы C а также D, Разыменование i дает право на элемент, то есть первый элемент второй последовательности.
Даже "отключенный" для обратных итераторов внезапно становится очевидным при таком способе: изменение этой последовательности дает:
+---+---+---+---+
| D | C | B | A |
+---+---+---+---+
^ ^ ^
| | |
rbegin ri rend
(end) (i) (begin)
Я написал соответствующие не обратные (базовые) итераторы в скобках ниже. Вы видите, обратный итератор, принадлежащий i (который я назвал ri) еще точки между элементами B а также C, Однако из-за изменения последовательности, теперь элемент B на право на это.
Почему Стандарт определяет end() как один за концом, а не за реальный конец?
Так как:
- Это позволяет избежать специальной обработки пустых диапазонов. Для пустых диапазонов,
begin()равноend()& - Это делает конечный критерий простым для циклов, которые перебирают элементы: циклы просто продолжаются до тех пор, пока
end()не достигается
Потому что тогда
size() == end() - begin() // For iterators for whom subtraction is valid
и вам не придется делать неловкие вещи, как
// Never mind that this is INVALID for input iterators...
bool empty() { return begin() == end() + 1; }
и вы не будете случайно писать ошибочный код, такой как
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
Также: что бы find() вернуть, если end() указал на действительный элемент?
Вы действительно хотите, чтобы другой участник назвал invalid() который возвращает неверный итератор?!
Два итератора уже достаточно болезненны...
О, и посмотрите этот пост.
Также:
Если end был до последнего элемента, как бы вы insert() в истинном конце?!
Итератор идиома полузакрытых диапазонов [begin(), end()) изначально основан на арифметике указателей для простых массивов. В этом режиме работы у вас будут функции, которым передан массив и размер.
void func(int* array, size_t size)
Преобразование в полузакрытые диапазоны [begin, end) это очень просто, когда у вас есть эта информация:
int* begin;
int* end = array + size;
for (int* it = begin; it < end; ++it) { ... }
Работать с полностью закрытыми диапазонами сложнее:
int* begin;
int* end = array + size - 1;
for (int* it = begin; it <= end; ++it) { ... }
Поскольку указатели на массивы являются итераторами в C++ (и синтаксис был разработан для этого), вызывать их намного проще std::find(array, array + size, some_value) чем это назвать std::find(array, array + size - 1, some_value),
Кроме того, если вы работаете с полузакрытыми диапазонами, вы можете использовать != оператор для проверки конечного условия, потому что (если ваши операторы определены правильно) < подразумевает !=,
for (int* it = begin; it != end; ++ it) { ... }
Однако не существует простого способа сделать это с полностью закрытыми диапазонами. Вы застряли с <=,
Единственный вид итератора, который поддерживает < а также > операции в C++ являются итераторами с произвольным доступом. Если бы вам пришлось написать <= оператор для каждого класса итераторов в C++, вам нужно будет сделать все ваши итераторы полностью сопоставимыми, и у вас будет меньше вариантов для создания менее способных итераторов (таких как двунаправленные итераторы на std::listили входные итераторы, которые работают на iostreams) если в C++ используются полностью закрытые диапазоны.
С end() указывая на конец, легко выполнить итерацию коллекции с помощью цикла for:
for (iterator it = collection.begin(); it != collection.end(); it++)
{
DoStuff(*it);
}
С end() указывая на последний элемент, цикл будет более сложным:
iterator it = collection.begin();
while (!collection.empty())
{
DoStuff(*it);
if (it == collection.end())
break;
it++;
}
- Если контейнер пуст,
begin() == end(), - Программисты C++ склонны использовать
!=вместо<(меньше чем) в условиях цикла, следовательно, имеяend()удобно указывать на позицию "один за другим".