3

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?

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
  • Maybe std::multimap is not the best data structure for you. For example `std::map>` could work better. – Slava Dec 20 '17 at 14:47
  • 1
    what about `const auto keyCount = std::accumulate(...` that wraps the for loop? – 463035818_is_not_an_ai Dec 20 '17 at 14:51
  • @Slava That suffers from the `vector` of `vector`s problem: https://stackoverflow.com/q/38244435/2642059 (Though this may still be my best option, I'd still like an answer to the question.) – Jonathan Mee Dec 20 '17 at 14:51
  • 1
    @tobi303 I doubt `std::accumulate()` can jump over unique keys – Slava Dec 20 '17 at 14:56
  • @tobi303 I was going to lash out that that would require me to step through all the elements in the `multimap` but as I think about it I'm pretty sure `upper_bound` is doing just that. I suppose to your point we could probably do this using `count_if` or `for_each` as well :( I'm assuming that's going to be as good of an answer as I'm going to get, if you type up I'll accept. – Jonathan Mee Dec 20 '17 at 14:57
  • @Slava, I... don't think that `upper_bound` jumps keys does it? – Jonathan Mee Dec 20 '17 at 14:58
  • @Slava Op, no, cancel that it does a binary search: http://en.cppreference.com/w/cpp/container/multimap/upper_bound#Complexity – Jonathan Mee Dec 20 '17 at 14:59
  • it was just a blind guess. If I find the time later I will write an answer, but atm my compile times are rather short :P – 463035818_is_not_an_ai Dec 20 '17 at 15:02

3 Answers3

0

No, there is no built-in in the standard to do this. Consider that your count function works because a multimap is internally sorted. Typical implementations such as libstdc++ use red-black trees for the internal representation. You would need to walk the tree in order to count all the (unique) keys. It's unavoidable.

user9124890
  • 36
  • 1
0

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:

  1. Must be used inline, so a count, not an iterator must be returned
  2. Must perform at least as well as 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.

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
0

If you only are creating multimap and inserting values in it, you can keep a companion map to record different types of keys. That size of that map will give you key count.

sanjivgupta
  • 396
  • 3
  • 12
  • This probably should have been a comment :( See also the problems presented in the second half of this answer: https://stackoverflow.com/a/47928082/2642059 – Jonathan Mee Sep 20 '18 at 17:12