How can I get all the unique keys in a multimap

Question

I have a multimap and I want get all the unique keys in it to be stored in a vector.

  multimap<char,int> mymm;
  multimap<char,int>::iterator it;
  char c;

  mymm.insert(pair<char,int>('x',50));
  mymm.insert(pair<char,int>('y',100));
  mymm.insert(pair<char,int>('y',150));
  mymm.insert(pair<char,int>('y',200));
  mymm.insert(pair<char,int>('z',250));
  mymm.insert(pair<char,int>('z',300));

How can I do this? there is way to count number of elements with a key but none to count number of unique keys in a multimap.

Added: By unique I mean all the keys in multimap once - they can be repeated or occur once in multimap.

So unique keys here are - x, y and z

Solution 1

I tried this and it worked

for(  multimap<char,int>::iterator it = mymm.begin(), end = mymm.end(); it != end; it = mymm.upper_bound(it->first))
  {
      cout << it->first << ' ' << it->second << endl;
  }

Solution 2

Since the entries of a std::multimap<> are implicitly sorted and come out in sorted order when iterating through them, you can use the std::unique_copy algorithm for this:

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

  /* ...Your existing code... */

  /* Create vector of deduplicated entries: */
  vector<pair<char,int>> keys_dedup;
  unique_copy(begin(mymm),
              end(mymm),
              back_inserter(keys_dedup),
              [](const pair<char,int> &entry1,
                 const pair<char,int> &entry2) {
                   return (entry1.first == entry2.first);
               }
             );

  /* Print unique keys, just to confirm. */
  for (const auto &entry : keys_dedup)
    cout << entry.first << '\n';

  cout.flush();
  return 0;
}

The extra work added by this is linear in the number of entries of the multimap, whereas using a std::set or Jeeva's approach for deduplication both add O(n log n) computational steps.

Remark: The lambda expression I use assumes C++11. It is possible to rewrite this for C++03.

Solution 3

Iterate through all elements of mymm, and store it->first in a set<char>.

Solution 4

easiest way would be to put the keys of multimap in an unordered_set

unordered_multimap<string, string> m;

//insert data in multimap

unordered_set<string> s;         //set to store the unique keys

for(auto it = m.begin(); it != m.end(); it++){
    if(s.find(it->first) == s.end()){
        s.insert(it->first);
        auto its = m.equal_range(it->first);
        for(auto itr=its.first;itr!=its.second;itr++){
            cout<<itr->second<<" ";
        }
    }
}

Solution 5

I think you can do something like this in case by unique you mean the key that is contained in the multimap only once:

1) construct a sorted list of all keys in your map

2) iterate over the list and find unique keys. It's simple since all duplicates will be near each other in a sorted container

If you want just all keys - use std::set as Donotalo suggested

View more solutions

Comments

[Ciro Santilli OurBigBook.com]

Possible duplicate of is there an iterator across unique keys in a std::multimap?

[Andrew]

-1. it will not give unique keys. It will give all keys. For example if there are two keys 'a' you will have the key 'a' in your set, but it's not unique

[Fiktik]

@Andrew set will only keep unique elements. It will give unique keys.

[Mare Infinitus]

why use a sorted list and not just a set? the set will already prove uniqueness.

[Mare Infinitus]

+1 as I just wrote using a set as a comment in the other answer! ;)

[Mare Infinitus]

a is a key, even if it is used multiple times, it is still a key that has to be stored. At least I understand the question as not wanting a list of keys that are not used multiple times, but a list of keys.

[AJ.]

It will print all the elements

[Andrew]

I agree that both interpretations are possible. Sorry, can't remove -1 until answer is edited

[Fiktik]

@AJ see the upper_bound part, this should print every key only once

[Roman]

It involves searching in the whole map on every iteration.

[Fractal]

Why doesn't the std::multimap already have within it a simple vector/list/set/map of all the unique keys. This seems like it would be useful and not that much overhead. Does this feature not exists because people wouldn't use this functionality that much or rather because the overhead is more than what i am guessing it would be? I would not think space would be a requirement (Right?).

[jogojapan]

@Fractal I'm not sure I understand your proposal completely. An extra data structure for this would take O(n) extra space, no? One thing that would be nice, though, is an interface (e.g. a special iterator) that would return the unique keys one by one.

[Fractal]

Yes, true ... it would be O(n) extra space. I don't think of space as actually being an issue but maybe in my work I don't deal with large enough groups of data to understand how that would be a strain/issue. Yes, a special iterator would be ideal.

[Bklyn]

@Roman: no it does not. See en.cppreference.com/w/cpp/container/multimap/upper_bound

[Roman]

@Bklyn: upper_bound searches in the whole map, just as I said. Better algorithm for OP problem could search next key only in keys greater than previously found key, but there is no such function in c++ multimap.

[Sandburg]

But you are not storing only the keys as required in the question... what are you storing exactly?

[Andreas Walter]

I got a deprecation warning on upper_bound with the hint to use equal_range().second. After changing to that, everything worked fine.

[road_to_quantdom]

i also used equal_range().second instead of upper_bound() and got improved efficiency

[road_to_quantdom]

i'm not sure if this is more efficient than @jeeva's approach. for my data-set , my benchmark says this took ~1-2 seconds while Jeeva's approach took .3 seconds. I had about 4.7million values, 3642 of which were unique

[jogojapan]

@road_to_quantdom Thanks for testing it!

[road_to_quantdom]

i also used equal_range().second instead of upper_bound but their performance was somewhat similar