c++ - 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 . Ref

A ForwardIterator支持递增(++myIterator)但不支持随机递增，不像RandomAccessIterator .

因此myset.begin() + n不保证按标准编译。它不编译 here .

你可以做 ++增量n循环，但当然，复杂度至少为 O(n)。