Вычитание и сравнение итераторов с произвольным доступом: почему и где?
Я разрабатываю небольшую библиотеку для своей работы, и я извлек несколько классов из стандартного категория итератора с произвольным доступом. Это позволяет мне использовать такие вещи, как черты итераторов, и не слишком беспокоиться, когда я использую стандартные библиотеки, такие как algorithm например. Конечно, я знаю, что не должен, и что я мог либо выбрать двунаправленная категория вместо этого или даже реализовать свой собственный. Но это не главное.
ИМО, «разрыв» между категориями двунаправленного и произвольного доступа слишком велик, и я не понимаю необходимости операторов вычитания и сравнения между итераторами — то есть: a-b, a<b а также a>b (и свободные варианты их).
Почему стандарт навязывает реализацию этих операторов, и может ли кто-нибудь дать мне пример, в котором недостаточно теста на равенство, смешанных итераторно-скалярных арифметических (составных или нет) операторов и оператора разыменования смещения?
Решение
Одним из распространенных случаев, когда вам нужна разница между итераторами, является бинарный поиск: не зная расстояния, вы не знали бы, сколько вам нужно добавить к итератору с левой стороны, чтобы добраться до средней точки в O(1) время. Как только вы знаете расстояние, вы можете применить смешанную итератор-скалярную арифметику, чтобы добраться до середины, также в постоянное время.
Обратите внимание, что вы можете найти расстояние, последовательно увеличивая один итератор, пока не доберетесь до другого, но для этого потребуется O(n) время.
Вам также нужно a < b Сравнение, чтобы узнать, какой итератор находится слева, а какой — справа. Без этого сравнения вы не сможете проверить входные данные для вашего алгоритма двоичного поиска.
Я нахожу странным [то, что] оператор вычитания должен возвращать int, а не итератор, хотя «логически» я ожидал бы, что арифметическая операция между двумя объектами одного типа также возвращает объект этого типа.
Вычитание дает вам расстояние — количество шагов от одной точки до другой. Это скалярное число, не зависящее от типа итератора. Симметрия здесь проста:
iteratorA + scalar = iteratorB
простые арифметические правила говорят нам, что
scalar = iteratorB - iteratorA
Другие решения