A multimap's size reports the number of values it contains. I'm interested in the number of keys it contains. For example, given multimap<int, double> foo I'd like to be able to do this:
const auto keyCount = ???
One way to get this is to use a for-loop on a zero initialized keyCount:
for(auto it = cbegin(foo); foo != cend(foo); it = foo.upper_bound(foo->first)) ++keyCount;
This however, does not let me perform the operation inline. So I can't initialize a const auto keyCount.
A solution could be a lambda or function which wraps this for-loop such as:
template <typename Key, typename Value>
size_t getKeyCount(const multimap<Key, Value>& arg) {
size_t result = 0U;
for(auto it = cbegin(foo); foo != cend(foo); it = foo.upper_bound(foo->first)) ++result;
return result;
}
But I was hoping for something provided by the standard. Does such a thing exist?
1st, multimap doesn't contain a key count naively. So your question then is about how to use something from the algorithm library to find the count. The 2 constraints you have placed that preclude everything in the library are:
upper_bound used in a lambda, which has time complexity: O(log n)1 leaves us with: count, count_if, for_each, as well as most of the algorithms in the numeric library
2 eliminates consideration of all of these as each of them has time complexity: O(n)
As such your getKeyCount is preferable to any other option that the standard supplies.
Just a comment about another option that may be presented: the maintenance of keyCount whenever something is added or removed from foo, this may seem workable, but it requires a check before each insert if the inserted key exists, and a check after each removal if the removed key still exists. Aside from this, there is also the consideration of the danger of multi-threaded inoperability and the loss of code readability, where it's not clear that this keyCount must be maintained along with foo. Ultimately this a bad idea unless the key count is taken significantly more frequently than foo is updated.