std :: set begin()和std :: set迭代器之间的距离为O(logn)

Question

我需要在std :: set中找到元素的索引.此索引可以显示为迭代器从头开始的距离.一种方法是:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);

这显然需要O(n)时间.但我们知道,在内部使用set实现的二叉搜索树中根的距离可以在O(log n)时间内找到.

他们以任何方式实现相同的功能,在C++中设置O(log n)时间的索引吗？

Answer 1

您可以使用该函数std::set<>::find来搜索元素x并计算到集合中第一个迭代器的距离。

std::distance(s.begin(), s.find(x))

然而，正如注释所示，距离的运行时间取决于所使用的迭代器的类型。对于集合，这是一个双向迭代器，距离为 O(n)。

Answer 2

您可以使用排序的std::vector<int>. 如果已排序，则可以在 中找到元素O(log n)。你可以在常数时间内找到距离O(1)。

通过排序向量，我的意思是每次插入后（或多次插入后）std::sort(v.begin(), v.end());

如果你的内部类型std::set<T>不像int- 你可以保留 -std::set<T>和迭代器的排序向量std::vector<std::set<T>::iterator>。但保持这些结构同步并非易事。也许你可以添加一些类似的位置T？或者保留std::set<std::pair<T,int>, comp_first_of_pair<T>>哪里comp_first_of_pair只是为了set排序T而第二个int是为了保持集合中的位置？

只是一些想法 - 拥有均匀的O(1)距离时间......