Подтвердить что ты не робот

Почему стандартные итераторы диапазона [begin, end] вместо [begin, end]?

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

4b9b3361

ОТВЕТЫ

Ответ 1

Лучшим аргументом легко является тот, который сделан сам Дейкстра:

  • Вы хотите, чтобы размер диапазона был простым разностным концом & minus; begin;

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

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

Мудрость, стоящая за концом [begin, end), окупается снова и снова, когда у вас есть какой-либо алгоритм, который имеет дело с несколькими вложенными или повторенными вызовами на основе диапазонов, которые естественным образом связаны. В отличие от этого, использование двойного замкнутого диапазона будет приводить к побочным и крайне неприятным и шумным кодам. Например, рассмотрим раздел [n 0, n 1) [n 1, n 2) [n <суб > 2суб > , п <суб > 3суб > ). Другим примером является стандартный цикл итерации for (it = begin; it != end; ++it), который запускает end - begin раз. Соответствующий код был бы гораздо менее читабельным, если бы оба конца были включительно. Ndash; и представьте, как вы будете обрабатывать пустые диапазоны.

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

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

Ответ 2

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

Потому что:

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

Ответ 3

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

   +---+---+---+---+
   | 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. Dereferencing i дает элемент справа от него, то есть первый элемент второй последовательности.

Даже "пошаговое" для обратных итераторов внезапно становится очевидным: Обращение к этой последовательности дает:

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

В скобках ниже я написал соответствующие итераторы без обратного (базового). Видите ли, обратный итератор, принадлежащий i (который я назвал ri), по-прежнему указывает между элементами B и C. Однако из-за изменения последовательности, теперь элемент B находится справа от него.

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

Ответ 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) { ... }

Поскольку указатели на массивы являются итераторами в С++ (и синтаксис был разработан для этого), гораздо проще вызвать std::find(array, array + size, some_value), чем называть std::find(array, array + size - 1, some_value).

Кроме того, если вы работаете с полузакрытыми диапазонами, вы можете использовать оператор != для проверки конечного условия, потому что (если ваши операторы определены правильно) < подразумевает !=.

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

Однако нет простого способа сделать это с полностью закрытыми диапазонами. Вы застряли с <=.

Единственный тип итератора, который поддерживает операции < и > в С++, - это итераторы с произвольным доступом. Если вам приходилось писать оператор <= для каждого класса итератора в С++, вам нужно было бы полностью сопоставить все ваши итераторы, и у вас было бы меньше вариантов создания менее способных итераторов (таких как двунаправленные итераторы на std::list или итераторы ввода, которые работают с iostreams), если С++ использует полностью закрытые диапазоны.

Ответ 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++;
}

Ответ 7

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