当'advance()'用于C++中的std::设置时，它的运行时复杂度是多少？

提问者：小点点

我对std::advance()用于std::set时的运行时复杂性感到好奇。

例如。

std::set<in> s;
auto x=s.begin();
advance(x,n/2);

上面的代码需要多少时间（n的顺序）。

共2个答案

匿名用户

std::set具有双向迭代器。双向迭代器是可递增和可递减的，但不是可随机访问寻址的--这意味着要到达nn个节点需要递增n次。

这意味着前进N将是O(N)

匿名用户

根据std::advance在CPPreference上的文档:

复杂性

线性的。

但是，如果InputIt额外满足LegacyRandomAccessIterator的要求，那么复杂性是恒定的。

因此，除非您手上有一个LegacyRandomAccessIterator（比如int[100])，否则您的复杂性是线性的。然而，std::set“只有”一个LegacyBidirectionalIterator，它比随机访问弱。

所以，你在这里，你保证有线性运行时。