Почему стандартные диапазоны итераторов [начало, конец) вместо [начало, конец]?

Question

Почему Стандарт определяет end() как единицу за концом, а не на фактическом конце?

Answer 1

Лучший аргумент - это аргумент Дейкстры :

• Вы хотите, чтобы размер диапазона был простой разницей end & minus; 1010 * начать *;

• включая нижнюю границу более «естественно», когда последовательности вырождаются в пустые, а также потому, что альтернатива ( исключая нижняя граница) потребует существования «один до "начало" "дозорного значения.

Вам все еще нужно объяснить, почему вы начинаете считать с нуля, а не с одного, но это не было частью вашего вопроса.

Мудрость, лежащая в основе соглашения [начало, конец), окупается снова и снова, когда у вас есть какой-либо алгоритм, который имеет дело с несколькими вложенными или повторяющимися вызовами конструкций на основе диапазона, которые естественным образом объединяются. Напротив, использование дважды закрытого диапазона повлечет за собой посторонний и крайне неприятный и шумный код. Например, рассмотрим раздел [ n ₀ , n ₁ ) [ n ₁ , n ₂ ) [ n ₂ , n ₃ ). Другим примером является стандартный цикл итерации for (it = begin; it != end; ++it), который выполняется end - begin раз. Соответствующий код был бы намного менее читабельным, если бы оба конца были включенными & ndash; и представьте, как бы вы справились с пустыми диапазонами.

Наконец, мы также можем привести хороший аргумент, почему подсчет должен начинаться с нуля: с полуоткрытым соглашением для только что установленных диапазонов, если вам дан диапазон N элементов (скажем, перечислите элементы массива), тогда 0 - это естественное «начало», так что вы можете записать диапазон как [0, N ), без каких-либо неловких смещений или исправлений.

В двух словах: тот факт, что мы не видим число 1 везде в алгоритмах, основанных на диапазоне, является прямым следствием и мотивацией для соглашения [начало, конец).

Answer 2

На самом деле, многие вещи, связанные с итераторами, внезапно приобретают гораздо больше смысла, если учесть, что итераторы не указывают на элементы последовательности, а между , с разыменованием, обращаясь к следующему элемент права на это. Тогда итератор "один конец" внезапно приобретает смысл:

   +---+---+---+---+
   | 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 находится справа от него.

Answer 3

Почему Стандарт определяет end() как один конец, а не фактический конец? Потому что:

1. Избегает специальной обработки пустых диапазонов. Для пустых диапазонов begin() равно end() &
2. Это упрощает конечный критерий для циклов, которые перебирают элементы: просто продолжайте до тех пор, пока end() не будет достигнуто.

Answer 4

Потому что тогда

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() в истинном конце?!

Answer 5

Итератор идиомы полузакрытых диапазонов [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 ++, вам нужно было бы сделать все ваши итераторы полностью сопоставимыми, и у вас было бы меньше вариантов для создания менее способных итераторов (таких как двунаправленные итераторы в * 1029). * или итераторы ввода, которые работают на iostreams), если в C ++ используются полностью закрытые диапазоны.

Answer 6

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

Answer 7

1. Если контейнер пуст, begin() == end().
2. C ++ Программисты, как правило, используют != вместо < (меньше чем) в условиях цикла, поэтому удобно иметь end(), указывающее на одну позицию в конце.