Работает ли std::advance на итераторе std::multiset за постоянное время?

Question

Я хотел бы знать, если вызов std::advance на итераторе std::multiset выполняется в постоянное время.

Answer 1

От std::advance, Мы видим, что

сложность

Linear. Однако, если InputIt дополнительно соответствует требованиям RandomAccessIterator, сложность постоянна.

Как любой шаблон из std::*map а также std::*set семья не выполняет RandomAccessIterator требования, это линейно. Например, отсюда:

Типы участников

[...]

iterator Константа Двунаправленного Итератора
const_iterator Константа Двунаправленного Итератора

Answer 2

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

Смотрите: https://en.cppreference.com/w/cpp/iterator/advance