C++ Find the number of elements in a range from an STL::multimap

I have a STL::multimap and I search it with equal_range to return an upper and lower bound. Can I find the number of elements in this range without iterating through them all and counting them one by one?

#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;
}

From stackoverflow

• Use std::distance algorithm to find the distance between the iterators. Like:

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

  Travis : Thanks for the quick reply! Would this save me any speed or does this do the same as I'm showing above? I'm showing at the bottom of this page: http://www.cplusplus.com/reference/std/iterator/distance/ that it might be faster O(1) but I'm not sure if this is a 'random access iterator' or not.

  Naveen : No, it will not save you any time. It is constant time for random access iterators (such as vector iterator). But since map has a bidirectinal iterator, it will linear time complexity.

  Travis : Ok thanks for your time here.

  Paul Baker : Multimap iterators are bidirectional, not random access. std::distance will thus need to repeatedly use operator++ in a similar way to your code.

• If you just want to count the number of elements with a given key, use count:

  int ct = mm.count(5);
  

  Travis : Indeed I could also use this but it seems to be the same speed as just iterating it myself (see the bottom of this page): http://www.cplusplus.com/reference/stl/multimap/count/ I don't think there's any free lunch to be found on this.

  Mike Seymour : It's certainly less code to write, and easier to read than the iteration. It may also be faster. The multimap could be implemented as something like a map of vectors, so count() would find the start, then look up the count, without having to iterate over the range. Of course, this is up to the implementor and can't be relied on at all.