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

Question

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

Answer 1

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

Сложность

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

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

Типы элементов

[...]

iterator Постоянный двунаправленный итератор
const_iterator Постоянный двунаправленный итератор

Answer 2

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

См .: https://en.cppreference.com/w/cpp/iterator/advance