Efficiently count number of entries between two std::multimap iterators

Question

I would like to count the number of entries between two iterators of an std::multimap in less than O(N) time. Are there any tricks or clever ways to do this?

Since std::multimap has bidirectional iterators, my understanding is that something like std::distance could do this in O(N) time.

Additional details: The multimap's key is an N-tuple. I'm trying to find the number of entries in the multimap whose key's first element is 0. The options for the first element of they key are 0 and 1, and the multimap uses a strict weak ordering in which the first element of the key is always the most important. i.e., all elements with 0 come before any elements with 1.

Context: The iterators are returned by equal_range, which runs in logarithmic time. Declaratively, I'd like to measure the length of the range.

Thank you.

Answer 1

What you are looking for is so-called heterogeneous comparison lookup that was proposed in N3465. It allows for a different but compatible comparison function in the equal_range member function that is being used to store the Key. In your case, the lookup comparison operator (first tuple member) would be different from but consistent with the tuple lexicographical comparison.

Unfortunately, only a small portion of that paper has been accepted into the draft C++14 Standard, according to this Q&A. However, the N3465 paper's author is also the author of Boost.MultiIndex that has implemented this feature. You can emulate a std::multimap by following the Boost.MultiIndex documentation.

Once you have used the generalized equal_range member function of an adapted boost::multiindex_container, you can then simply do std::distance() on the returned iterators. Complexity would be logarithmic in the container size for the equal_range and linear in the size of the returned iterator range. If you are not interested in the result but only in the count, there is also a generalized count() member function returning that in the same logarithmic + linear time.