查找多重集中小于或等于 k ​​的元素数量

我有一个多重集，实现如下：

#include <bits/stdc++.h>
using namespace std;

multiset <int> M;

int numunder(int k){
    /*this function must return the number of elements smaller than or equal to k
    in M (taking multiplicity into account).
    */
}

起初我以为我可以返回 M.upper_bound(k)-M.begin()+1 。不幸的是，我们似乎无法像这样减去指针。我们最终不得不实现一个 AVLNodes 结构。有没有办法利用 c++ std 让它发挥作用？

严格遵守您的建议M.upper_bound(k)-M.begin()+1解决方案（显然无法编译，因为多重映射迭代器是一个双向迭代器，没有实现operator-），你可以使用标准::距离 http://en.cppreference.com/w/cpp/iterator/distance获取两个多重映射迭代器之间的距离以获得正确的解决方案。

请注意，该解决方案将有O(n)复杂性，因为如果迭代器不是随机访问迭代器，std::distance只会递增作为第一个参数传入的迭代器，直到找到作为第二个参数传入的迭代器。

我也真的不认为这个问题可以比O(n)复杂性与std::multiset.