std::set是否支持任何返回低于给定元素的元素数的方法？
我知道我们有lower_bound，它将迭代器返回到给定元素的下界；但它不会向我返回给定元素之前的元素数量。
我知道我可以从一开始迭代到下界迭代器；但在最坏的情况下这将花费CCD_ 3时间。我们在O(logn)中有这样的方法吗？
如果您有一个std::set，那么您可以像这样使用自定义std::set::lower_bound：
auto lb = s.lower_bound(key);
保证了CCD_ 7的复杂度。
为了获得元素的计数，你可以使用std::distance，如下所示：
auto count = std::distance(s.begin(), s.lower_bound(key));
但是，std::set不支持随机访问迭代器，因此std::distance调用具有O(n)复杂性。
如果你有一些排序范围，你仍然可以像这样使用lower_bound和distance：
auto lb = std::lower_bound(s.begin(), s.end(), key);
auto count = std::distance(s.begin(), lb);
但请注意，如果s不支持随机访问，则这两个操作都具有O(n)的复杂性。