在C++中，如何从STL::multimap中查找一个范围内的元素数量？

Question

我有一个STL::multimap，使用equal_range进行搜索以返回上下界。我是否可以在不迭代所有元素并逐个计数的情况下找到此范围内的元素数量？

#include <iostream>
#include <map>

using namespace std;

int main () {
    multimap<int,int> mm;
    pair<multimap<int, int>::iterator,multimap<int, int>::iterator> ret;
    multimap<int,int>::iterator retit;

    for (int n=0; n<100; n++) {
        mm.insert ( make_pair( rand()%10,rand()%1000) );
    }

    ret = mm.equal_range(5);

    int ct = 0;
    for (retit=ret.first; retit!=ret.second; ++retit) {
        cout << retit->second << endl;
            ct++;
    }
    cout << ct << endl;

    return 0;
}

- Travis

Answer 1

使用std::distance算法来查找迭代器之间的距离。比如:

int ct1 = std::distance(ret.first, ret.second);

- Naveen

---

谢谢您的快速回复！这样做会让我节省时间吗，还是和我上面展示的一样？我在这个页面底部展示了：http://www.cplusplus.com/reference/std/iterator/distance/ 说它可能更快O（1），但我不确定它是否为“随机访问迭代器”。 - Travis

不，这并不会节省你任何时间。对于随机访问迭代器（例如向量迭代器），它是常数时间。但由于 map 具有双向迭代器，因此它的时间复杂度为线性。 - Naveen

Multimap 迭代器是双向的，而不是随机访问的。因此，std::distance 将需要以类似于您的代码的方式重复使用 operator++。 - user200783

Answer 2

如果您只想计算具有给定键的元素数量，请使用count：

int ct = mm.count(5);

- Mike Seymour

---

实际上我也可以使用这个，但它似乎和我自己迭代的速度一样快（请参见此页面底部）：http://www.cplusplus.com/reference/stl/multimap/count/ 我认为在这方面并没有什么免费的午餐。 - Travis

这肯定比迭代少写代码，更容易阅读。这也可能更快。multimap 可以实现为向量映射的一种形式，因此 count() 可以找到起点，然后查找计数，而无需迭代整个范围。当然，这取决于实现者，并且不能完全信赖。 - Mike Seymour