Являются ли увеличивающиеся / уменьшающиеся итераторы контейнерных итераторов стандартной библиотеки детерминированными?

Существуют ли верхние границы времени, которое может потребоваться для увеличения / уменьшения итератора стандартной коллекции библиотек (например, std :: map)? (Предполагая, что сам контейнер не изменен.)

1

Решение

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

Сказав это, однако, типичные реализации не делают ничего, что заняло бы значительное время. Здесь нет выделения памяти или файлового ввода-вывода (я полагаю, кроме страниц-страниц виртуальных машин).

1

Другие решения

Операция приращения для std::map итератор гарантированно имеет амортизированная постоянная Стоимость. То есть полный обход N элементы O (N). Это на самом деле верно для все итераторы (см. 24.2.1 / 8):

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

3

По вопросам рекламы [email protected]