Являются ли увеличивающиеся / уменьшающиеся итераторы контейнерных итераторов стандартной библиотеки детерминированными?
Существуют ли верхние границы времени, которое может потребоваться для увеличения / уменьшения итератора стандартной коллекции библиотек (например, std :: map)? (Предполагая, что сам контейнер не изменен.)
Решение
Нет, нет верхней границы времени, которое может потребоваться для увеличения / уменьшения итератора. В стандарте ничего не говорится о том, сколько времени занимает запуск любой программы. Насколько я знаю, все популярные компиляторы тоже молчат на эту тему.
Сказав это, однако, типичные реализации не делают ничего, что заняло бы значительное время. Здесь нет выделения памяти или файлового ввода-вывода (я полагаю, кроме страниц-страниц виртуальных машин).
Другие решения
Операция приращения для std::map итератор гарантированно имеет амортизированная постоянная Стоимость. То есть полный обход N элементы O (N). Это на самом деле верно для все итераторы (см. 24.2.1 / 8):
Все категории итераторов требуют только те функции, которые реализуются для данной категории в константе
время (амортизированное).