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

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

Answer 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>>

，其中

comp_first_of_pair

只是让

set

仅按

T

排序，第二个

int

用于保持集合中的位置？

只是一些想法 - 拥有均匀的

O(1)

距离时间......

Answer 4

您不能将数学与双向迭代器一起使用。所以唯一可以接受的方法就是自己数一下（你插入集合中的X比X少了多少个int）。

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

Answer 5

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

• 存储索引。要么在节点本身中，要么在单独的

  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 )