C++ std::set 索引的插入

Question

我遇到了以下问题:

假设我有一个名为 Numbers 的 std::set，包含 n 个值。我想插入第 (n+1) 个值(等于 x)，我事先知道它还不在集合中。我需要的是一些方法来检查它将插入到哪个位置，或者等价地，Numbers 中已经包含了多少小于 x 的元素。

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

Answer 1

set 中没有“位置”，只有迭代器，set 没有给你关于实现的 promise 。您可以使用 lower/upper_bound 和 count 元素，但我认为它不会考虑内部因素。