std::map 有没有办法在 O(1) 时间内给出所有 <= target_key 键的计数器？
Is there a way for std::map to give a counter of all keys <= target_key in O(1) time?
我正在使用 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)的时候，我的设想是已经找到了最大的key也就是<= target，然后用这个key在O(1)的时间内求出count。我最初还设想使用 std::map 来存储键值对，其中值是键出现的次数，或者更好的是，值是键的数量（包括重复项）是 <= target.
这称为 rank 查询，std::map 没有提供任何比线性时间更好的方法。
确实可以在对数时间内找到迭代器，但无法在比线性时间更好的时间内获得该迭代器与 begin() 之间的距离。为了 std::map 提供这样的功能，它必须在红黑树的每个节点中保留子树大小的计数，这会减慢每个更新操作，包括对于不关心的用户进行排名查询。
如果你用子树的大小来扩充树，你可以在对数时间内进行排名查询。 Boost.Intrusive 可以提供帮助（我想有些人已经编写了必要的库来进行排名查询，但我现在无法在 Google 上找到它们）。
我认为在 std::map/std::multimap 中无法获得两个复杂度不变的迭代器之间的距离。
std::map/std::multimap 提供 LegacyBidirectionalIterator 并使用 std::distance找到两个迭代器之间的距离具有线性复杂度。
我正在使用 std::map 按排序顺序存储一组数字。我希望能够在 O(1) 时间内获得小于或等于某个目标数字的数字计数器（不包括找到最大密钥 <= target 所需的时间）。有办法吗？
例如，假设我有以下数字（可能存在重复项）(1,0,5,2,3,8) 作为键存储在 std::map 中，并且我有一个 target_key = 4。我想使用 std::map 给我解决方案 4 因为数组 <=4.
我不确定 std::map 是否设置为执行此操作。我唯一能想到的是使用 std::upper_bound 为我获取最大值 <=4 的迭代器，然后遍历迭代器并对每个键的计数求和，但那是 O(n)时间。
编辑 1：
注意可能有重复的数字
编辑 2：
我说错了，搜索需要在 O(1) 时间内完成。我知道这对于任何排序的容器都是不可能的，最好的情况是 O(LogN)。当初说O(1)的时候，我的设想是已经找到了最大的key也就是<= target，然后用这个key在O(1)的时间内求出count。我最初还设想使用 std::map 来存储键值对，其中值是键出现的次数，或者更好的是，值是键的数量（包括重复项）是 <= target.
这称为 rank 查询，std::map 没有提供任何比线性时间更好的方法。
确实可以在对数时间内找到迭代器，但无法在比线性时间更好的时间内获得该迭代器与 begin() 之间的距离。为了 std::map 提供这样的功能，它必须在红黑树的每个节点中保留子树大小的计数，这会减慢每个更新操作，包括对于不关心的用户进行排名查询。
如果你用子树的大小来扩充树，你可以在对数时间内进行排名查询。 Boost.Intrusive 可以提供帮助（我想有些人已经编写了必要的库来进行排名查询，但我现在无法在 Google 上找到它们）。
我认为在 std::map/std::multimap 中无法获得两个复杂度不变的迭代器之间的距离。
std::map/std::multimap 提供 LegacyBidirectionalIterator 并使用 std::distance找到两个迭代器之间的距离具有线性复杂度。