我正在使用 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让我获得最大值(value)的迭代器<=4 ，然后遍历迭代器并总结每个键的计数，但这是 O(n) 时间。
编辑1:
请注意，可能有重复的数字
编辑2:
我错误地指出搜索需要在 O(1) 时间内完成。我知道任何排序的容器都不可能，最好的情况是 O(LogN)。当我最初说 O(1) 时，我设想已经找到最大键 <= target ，然后使用此键在 O(1) 时间内找到计数。我最初也设想使用 std::map存储键值对，其中值是键的出现次数，或者更好，但值是键的数量(包括重复项)，即 <= target .
最佳答案
这称为排名查询，std::map没有提供任何比线性时间更好的方法。
确实，您可以在对数时间内找到迭代器，但无法获得该迭代器与 begin() 之间的距离。在优于线性时间。为了 std::map为了提供这样的功能，它必须对红黑树的每个节点中的子树大小进行计数，这会减慢每次更新操作，包括不关心进行排名查询的用户。
如果您确实使用子树大小来增加树，您可以在对数时间内进行排名查询。 Boost.Intrusive可以提供帮助(我想有些人已经编写了必要的库来进行排名查询，但我现在在 Google 上找不到它们)。
关于c++ - std::map 有没有办法在 O(1) 时间内给出所有键 <= target_key 的计数器？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60552148/