unordered_set <int> :: iterator it + n的时间复杂度是多少？

Question

假设我有一个std::unordered_set<int>命名为myset,我想从返回一个随机数myset的O(1)时间.我首先rand()用来生成一个随机数:

int n = rand() %  myset.size();

然后,我做:

myset.begin() + n;

我想知道是否myset.begin() + n在O(n)或O(1)？

谢谢!

Answer 1

的std::unordered_set<>::iterator(其从产生myset.begin())是一个Constant ForwardIterator.参考

一个ForwardIterator支持增量(++myIterator),但不是随机的增量,不像RandomAccessIterator的.

因此myset.begin() + n不保证按标准编译.它不在这里编译.

您可以使用循环执行++递增n时间,但当然,复杂度至少为O(n).