我使用std::map按排序顺序存储一组数字。我希望能够在O(1(时间内获得小于或等于某个目标数字的数字计数器(不包括找到最大密钥<= target所需的时间(。有办法做到这一点吗？
例如，假设我有以下数字(存在重复的CAN((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(2(时间内的计数。我最初还设想使用std::map来存储键值对，其中值是键的出现次数，或者更好，然而，该值是键(包括重复项(的数量，即<= target。
这被称为秩查询，std::map没有提供任何比线性时间更好的方法。
的确，你可以在对数时间内找到迭代器，但没有办法在比线性时间更好的时间内获得迭代器和begin()之间的距离。为了让std::map提供这样的功能，它必须在红黑树的每个节点中保留子树大小的计数，这将减慢每次更新操作的速度，包括对于不关心进行排名查询的用户。
如果确实使用子树大小来扩充树，则可以在对数时间内进行排名查询。Boost.Interusive可能会有所帮助(我想有些人已经编写了必要的库来进行排名查询，但我现在在谷歌上找不到它们(。
我认为std::map/std::multimap中没有办法在恒定复杂度下获得两个迭代器之间的距离std::map/std::multimap提供了LegacyBidirectionalIterator，使用std::distance查找两个迭代器之间的距离具有线性复杂性。