std::advance 在 std::multiset 的迭代器上是否在常数时间内完成？

Is std::advance on an iterator of std::multiset done in constant time?

我想知道在 std::multiset 的迭代器上调用 std::advance 是否在常数时间内完成。

不可以，只有随机访问迭代器才能在常数时间内前进。否则，它是距离上的线性时间。

参见：https://en.cppreference.com/w/cpp/iterator/advance

从std::advance，我们看到

Complexity

Linear. However, if InputIt additionally meets the requirements of RandomAccessIterator, complexity is constant.

由于 std::*map 和 std::*set 系列中的任何模板都不满足 RandomAccessIterator 要求，因此它是线性的。来自例如here:

Member types

[...]

iterator               Constant BidirectionalIterator
const_iterator    Constant BidirectionalIterator