Почему "! =" Используется с итераторами вместо "<"?

Question

Я привык писать такие циклы:

for (std::size_t index = 0; index < foo.size(); index++)
{
    // Do stuff with foo[index].
}

Но когда я вижу циклы итераторов в чужом коде, они выглядят так:

for (Foo::Iterator iterator = foo.begin(); iterator != foo.end(); iterator++)
{
    // Do stuff with *Iterator.
}

Я считаю iterator != foo.end() отключенным. Это также может быть опасно, если iterator увеличивается более чем на единицу.

Кажется более правильным использование iterator < foo.end(), но я никогда не вижу этого в реальном коде. Почему нет?

Answer 1

Все итераторы равноправны. Только итераторы с произвольным доступом являются сравнительно сопоставимыми. Входные итераторы, прямые итераторы и двунаправленные итераторы не могут быть сравнительно сопоставлены.

Таким образом, сравнение с использованием != является более общим и гибким, чем сравнение с использованием <.

---

Существуют разные категории итераторов, поскольку не все диапазоны элементов имеют одинаковые свойства доступа. Например,

• если у вас есть итераторы в массиве (непрерывная последовательность элементов), их сравнительно легко сравнивать; вам просто нужно сравнить индексы указанных элементов (или указатели на них, поскольку итераторы, вероятно, просто содержат указатели на элементы);

• если у вас есть итераторы в связанном списке, и вы хотите проверить, является ли один итератор «меньше» другого итератора, вы должны пройти узлы связанного списка от одного итератора, пока один из них не достигнет другого итератор или вы достигли конца списка.

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

---

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

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

Некоторые реализации стандартной библиотеки (например, реализация стандартной библиотеки Visual C ++) содержат полезный код отладки, который выдвигает утверждение, когда вы делаете что-то недопустимое с итератором, подобным этому.

Answer 2

Краткий ответ: поскольку Iterator - это не число, это объект.

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

Вам не нужно беспокоиться об «пропущенных» End().Это также не число, это объект, представляющий конец коллекции.Не имеет смысла иметь итератор, который проходит мимо него, и на самом деле это не может.