c++ - 多集迭代器之间的距离

Question

我们能找到复杂度小于 O(n) 的多重集中的两个迭代器之间的距离吗？
我尝试使用迭代器标头提供的 std::distance() 函数。但它的内部实现对于多集迭代器是 O(n)。

Answer 1

multiset::iterator模型 BidirectionalIterator，而不是 RandomAccessIterator，所以std::distance只要求是线性的，而不是常数。