Итераторы произвольного доступа и deque

Question

Сегодня я читал какой-то текст, и он заявил, что, поскольку у std :: deque есть итератор с произвольным доступом, его сложность во времени скорости поиска элементов составляет O (1).Хотя я согласен с тем фактом, что временная сложность извлечения элемента составляет O (1), но при чем тут итератор с произвольным доступом?

Answer 1

Концепция RandomAccessIterator требует, чтобы операции + и - выполнялись в постоянное время:

С & # x5B; iterator.concept.random.access & # x5D; :

Концепция RandomAccessIterator добавляет поддержку для продвижения в постоянное время с помощью + =, +, - = и -, а также для вычисления расстояния в постоянное время с помощью -. Итераторы с произвольным доступом также поддерживают запись в массиве посредством подписки.

Это означает, что любой совместимый со стандартом контейнер, который реализует итератор с произвольным доступом, должен обеспечивать извлечение элемента в постоянное время.