如何用C++的std::map统计小于等于指定键的键的数量？

直接用std::upper_bound配合std::distance就能轻松实现需求：

• std::upper_bound会返回指向第一个大于目标键的迭代器，从map.begin()到这个迭代器之间的所有元素，键都小于等于目标值。用std::distance(map.begin(), it)就能直接得到符合条件的元素数量。
  示例代码：

  #include <map>
  #include <iterator>
  
  int count_less_or_equal(const std::map<int, std::string>& my_map, int target) {
      auto it = my_map.upper_bound(target);
      return std::distance(my_map.begin(), it);
  }
  

为什么不用std::lower_bound？
lower_bound返回的是第一个不小于目标键的迭代器。如果目标键存在于map中，这个迭代器指向该键本身；如果不存在，则指向第一个大于它的键。这种情况下要统计<=目标键的数量，需要额外判断迭代器指向的元素是否等于目标键，再调整计数，步骤比upper_bound繁琐，不如后者直接。

性能注意事项 #

由于std::map的迭代器是双向迭代器，std::distance需要遍历从begin到目标迭代器的所有元素，时间复杂度为O(n)。如果你的map包含大量元素，这个方法的性能会比较差。标准C++库没有提供O(logn)的直接统计方式，此时可以考虑使用支持顺序统计的扩展数据结构（比如GNU的policy-based data structures），或者自行维护额外的有序辅助结构来快速计算数量。

内容的提问来源于stack exchange，提问作者user308485