c++ реализация - Почему стандартные итераторы диапазона [begin, end] вместо [begin, end]?




4 Answers

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

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

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

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

Мудрость соглашения [начало, конец] окупается снова и снова, когда у вас есть какой-либо алгоритм, который имеет дело с несколькими вложенными или итерированными вызовами на основе диапазонов, которые естественно связаны. В отличие от этого, использование двойного замкнутого диапазона будет приводить к побочным и крайне неприятным и шумным кодам. Например, рассмотрим раздел [ 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 во всех диапазонах на основе алгоритмов, является прямым следствием и мотивом для соглашения [начало, конец].

итератора iterator

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




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

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




Идиома итератора полузакрытых диапазонов [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 ++ использует полностью закрытые диапазоны.




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



Related