11

我需要在 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) 时间的索引吗？

4

5 回答 5

4

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

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

然而，正如评论所指出的，距离的运行时间取决于所使用的迭代器的类型。在集合的情况下，这是一个双向迭代器，距离为 O(n)。

于 2012-09-21T12:02:37.587 回答
3

您可以使用排序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>>wherecomp_first_of_pair只是为了set排序T，第二个int是为了保持位置？

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

于 2012-09-21T15:50:53.377 回答
3

您可以使用有序集合在 O(log(N)) 中找到集合中元素的索引：https ://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ 。这被实现为红黑树。我知道这个话题很老了，但它可能对未来的读者有所帮助。

于 2019-06-09T08:20:16.270 回答
1

您不能将 matematics 与双向迭代器一起使用。所以唯一可以接受的方法是自己计算（你插入集合中有多少int小于 X）。

但是，如果您已经将“数据收集”和“数据使用”阶段完全分开 - 可能值得将std::set替换为排序的std::vector。它更难维护，但有自己的好处，包括迭代器数学（因此您可以使用std::binary_search使用 O(log n) 进行搜索，使用 O(1) 进行距离）

于 2012-09-21T12:12:45.003 回答
1

如果计算索引确实是您的瓶颈，那么我看到 2 个选项：

  • 存储索引。无论是在节点本身还是在单独的std::map. 当然，这意味着您必须保持此缓存更新。
  • 使用std::vector. 这并不像最初看起来那么糟糕。如果您始终对向量进行排序，则可以像使用set. 性能将类似于set。最大的缺点是：节点可能会被复制很多。（这可以通过使用指针boost:shared_ptr或std::unique_ptr[仅限 c++11] 来补偿）
    查找您使用的元素std::lower_bound。
    而不是 insert/push_back 你这样做：insert( lower_bound(b,e,x), x )
于 2012-09-25T07:37:22.177 回答