c++ - std::map 有没有办法在 O(1) 时间内给出所有键 <= target_key 的计数器？

Question

我std::map用来按排序顺序存储一组数字。我希望能够在 O(1) 时间内获得小于或等于某个目标数字的数字计数器（不包括找到最大键所需的时间<= target）。有没有办法做到这一点？

例如，假设我将以下数字（可以存在重复）(1,0,5,2,3,8)存储为 中的键std::map，并且我有一个target_key = 4. 我想用来std::map给我解决方案4，因为数组中有 4 个数字<=4。

我不确定是否std::map设置为执行此操作。我唯一能想到的就是使用std::upper_bound让我获得最大值的迭代器<=4，然后循环遍历迭代器并总结每个键的计数，但那是 O(n) 时间。

编辑1：

请注意，可能有重复的数字

编辑2：

我错误地指出搜索需要在 O(1) 时间内完成。我知道任何排序的容器都不可能，最好的情况是 O(LogN)。当我最初说 O(1) 时，我设想已经找到了最大键 ，<= target然后使用这个键在 O(1) 时间内找到计数。我最初也设想使用std::map来存储键值对，其中值是键的出现次数，或者更好，但是，值是键的数量（包括重复项），即<= target.

标签： c++stdmapupperbound

Answer 1

这称为排名查询，并std::map没有提供任何比线性时间更好的方法。

确实，您可以在对数时间内找到迭代器，但没有办法begin()在比线性时间更好的时间内获得该迭代器之间的距离。为了std::map提供这样的功能，它必须对红黑树的每个节点中的子树大小进行计数，这会减慢每个更新操作，包括不关心进行排名查询的用户。

如果您确实使用子树大小来增加树，您可以在对数时间内进行排名查询。Boost.Intrusive可以提供帮助（我想有些人已经编写了必要的库来进行排名查询，但我现在在 Google 上找不到它们）。