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.