我需要在std::set中查找一个元素的索引。这个索引可以视为迭代器从开头开始的距离。 一种方法是：
for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);
这显然需要 O(n) 时间。但是我们知道，在 C++ 的 set 内部实现的二叉搜索树中，从根节点到指定节点的距离可以在 O(log n) 的时间内找到。
那么有没有办法在 C++ 的 set 中实现相同的操作，在 O(log n) 的时间内找到某个元素的索引呢？
std::set<>::find来搜索元素x并计算集合第一个迭代器的距离。std::distance(s.begin(), s.find(x))
然而，评论显示距离的运行时间取决于使用的迭代器类型。在集合的情况下，这是一个双向迭代器，距离为O(n)。
O(log n + m)，虽然如此。但据我所知，这已经是最好的了。 - Xeostd::set的distance为O(N)。这就像魔法一样！ - Chris Vilchesstd::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 仅用于根据 T 对set 进行排序，第二个int用于保持设置中的位置？O(1)的距离时间......std::set<> 中插入的成本为 O(log n) - n 次插入：O(n Log n)。你不能在双向迭代器中使用数学运算。因此，唯一可接受的方法是自己计算（插入到集合中的小于X的int数量）。
但是，如果您已经清晰地分离了“数据收集”和“数据使用”阶段-可能值得用排序的std::vector替换std::set。它更难维护，但有自己的好处，包括迭代器数学（因此您可以使用std::binary_search进行O(log n)搜索，并使用O(1)获取距离）。
如果计算索引真的是您的瓶颈，那么我看到有两个选项：
std::map中进行存储。当然，这意味着您必须保持此缓存已更新。std::vector。这并不像一开始看起来那么糟糕。如果您始终保持向量排序，则可以像使用set一样使用它。性能将类似于set。最大的缺点是：节点可能会被频繁复制。（这可以通过使用指针、boost:shared_ptr或std::unique_ptr [仅限c++11]来补偿）std::lower_bound。insert( lower_bound(b,e,x), x )
O(log n)的时间复杂度找到距离吗？set通常是红黑树，每个节点并没有太多关于其左右子树元素数量的信息。请记住，你寻找的不是从根节点直接到叶子节点的距离，而是指定叶子节点左侧的叶子节点总数。 - Steve Jessop