C++中std::set插入的索引位置

Question

我遇到了以下问题：

假设我有一个名为Numbers的std::set，其中包含n个值。我想插入第(n+1)个值（等于x），我事先知道它尚未在集合中。我需要的是一种检查方式，它将被插入到哪个位置，或者说，已经包含在Numbers中的小于x的元素有多少。

我肯定知道一些以O(n)的方式完成它的方法，但我需要的是O(log(n))。理论上可能是可能的，因为std::set通常实现为二叉搜索树（只有在每个顶点存储每个子树大小的信息时，才可能是O(log(n))）。问题是它是否技术上可行，如果是，如何做到。

- Dmitriy Korolevich

---

在常规的二叉搜索树、std::set或其他数据结构中，在插入叶子节点之前计算元素数量不是O(log N)操作。您是否考虑使用堆结构？ - Captain Giraffe

这更像是修改过的BST，每个顶点都附加了额外的数据（left_subtree_size，right_subtree_size）。据我所知，保持这种结构的一致性将会花费大部分算法的两倍时间，并且将O(n)添加到BST本身的大小中，这是一个开销，但对于我的任务来说是可以接受的。 - Dmitriy Korolevich

一个自制的二叉搜索树应该能够处理这个问题。我可以建议每个顶点使用单一的树大小值。 - Captain Giraffe

谢谢您的建议。实际上，两个都是 :) - Dmitriy Korolevich

Answer 1

在集合中没有“位置”这个概念，只有迭代器，并且集合不保证实现。你可以使用lower/upper_bound和count元素，但我认为它不会考虑内部实现。

- Michael Krelin - hacker

Answer 2

所有的set函数都将使用迭代器进行操作；set的迭代器是双向的，而不是随机访问的，因此确定位置将是一个O(n)的操作。

在集合中插入新元素时，您不需要知道位置，插入操作的时间复杂度为O(log n)。

- Mark Ransom

---

我知道“set”的迭代器是双向的，但我只希望针对“index_of”问题，“set”可能具有利用其“有序性”的特定机制。 - Dmitriy Korolevich

关于“不需要知道位置”：不幸的是，正是我算法所需的“index_of”。 - Dmitriy Korolevich

@DmitriyKorolevich，“set”通常被实现为一棵树，而在树中获取相对位置的唯一方法是遍历它，这正是迭代器所做的。 - Mark Ransom

我稍微不同意“在树中获取相对位置的唯一方法”的观点。假设每个顶点都存储其左右子树的大小，您可以在不实际遍历所有小于x的元素的情况下使用O(log(n))计算索引。即使这种实现会增加内存和速度的常数，但它也不会破坏集合的渐近复杂度。然而，由于“set”是为了通用生产力而设计的，所以我担心这不是重点，因此，对于这件事，我可能需要编写自己的树 :( - Dmitriy Korolevich

据我所知，std::set中的节点不需要存储它们的子树大小。目前没有标准方法可以达成你想要的效果。 - bames53

Answer 3

改为：

std::set<MyT> mySet;

使用：

std::set<std::pair<MyT,int>> mySet;

例如，接下来：

//inserting a std::vector<MyT> myVec:
for (int i=0; i<myVec.size(); i++)
      mySet.insert( std::pair<MyT,int>(myVec[i], i) );

排序后的结果：

for (auto it=mySet.begin(); it!=mySet.end(); ++it)
  cout << it->first << " index=" << it->second << "\n";

- Yigal Eilam

Answer 4

你可以使用set::lower_bound在O(lon(n))的时间复杂度内找到新元素应该插入的“位置”，但它只是一个迭代器。std::set::iterator是双向的，而不是随机访问的，因此你无法在O(lon(n))的时间复杂度内计算比新元素小的元素数量。

- Andriy Tylychko

Answer 5

也许你应该使用set::lower_bound()，根据这个文档(http://lafstern.org/matt/col1.pdf)，它的时间复杂度应该是与log N成正比。

- baderman

---

问题在于，尽管 set::lower_bound() 本身的时间复杂度为 O(log(n))，但我所看到的检查小于 x 的元素数量的唯一方法是执行 (std::set(Numbers.begin(), std::lower_bound(Numbers.begin(), Numbers.end(), x))).size()，其中包括 'set' 的迭代器构造函数，其时间复杂度为 O(n)。 - Dmitriy Korolevich

找到该项的时间复杂度为O(log n)，但将该项转换为集合中的排名则不幸是O(n)。 - Mark Ransom