多重集合迭代器之间的距离

Question

4

我们能否以小于O(n)的复杂度找到multiset中两个迭代器之间的距离？
我尝试使用iterator头文件提供的std::distance()函数。但是对于multiset iterator，它的内部实现是O(n)。

- rohangulati

2

不，O(n) 在这种情况下是最好的选择。 - Yuushi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ecatmur · Accepted Answer

multiset::iterator是双向迭代器，而不是随机访问迭代器，因此std::distance只要求是线性的，而不必是常数级别的。