在c++std::set(通常使用红黑二叉搜索树实现)中，元素是自动排序的，任意位置的键查找和删除需要时间O(log n)[平销，即忽略当前容量过大时的重新分配]。
在有序的c++std::vector中，查找也很快(实际上可能比std::set快一点)，但是插入很慢(因为保持排序需要时间O(n))。
然而，排序后的c++std::vectors还有另一个特性:它们可以快速(在O(log n)时间内)找到一个范围内的元素数量。
。，一个经过排序的c++std::vector可以快速回答:给定x,y之间有多少个元素?
std::set可以快速找到指向范围开始和结束的迭代器，但不知道范围内有多少元素。
那么是否存在数据结构它允许c++std::set的所有速度(快速查找和删除)，但也允许在给定范围内快速计算元素的数量?
(这里快，我指的是O(log n)或者log n的多项式，甚至是根号n。只要它比O(n)快，因为O(n)几乎等同于平凡的O(n log n)来搜索所有内容
(如果不可能，甚至在一个固定因子内的数字估计也是有用的。对于整数，一个平凡的上界是y-x+1，但是如何得到下界呢?对于任意有排序的对象，没有这样的估计)
编辑:我刚刚看到相关问题，本质上是问是否可以计算前面元素的个数。(对不起，我的错，没有看到它之前)。这显然等同于这个问题(要得到一个范围内的数字，只需计算开始/结束元素和相减，等等。)
然而，这个问题也允许数据被计算一次，然后被固定，不像这里，所以问题(和排序的向量答案)实际上不是这个问题的重复。
您正在寻找的数据结构是订单统计树
它通常被实现为一个二叉搜索树，其中每个节点额外存储其子树的大小。
不幸的是，我很确定STL不提供。
所有数据结构都有其优缺点，这就是标准库提供大量容器的原因。
规则是在修改的快速性和数据提取的快速性之间取得平衡。在这里，您希望轻松访问范围中的元素数量。在基于树的结构中，一种可能性是在每个节点中缓存其子树的元素数量。这将在每次插入或删除时增加平均log(N)次操作(树的高度)，但会大大加快范围内元素数量的计算速度。不幸的是，很少有c++标准库中的类是为派生而定制的(而且我相信std::set不是)，所以你必须从头开始实现你的树。
也许您正在寻找C++https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html的LinkedHashSet替代品。