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

Answer 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;
  }

Answer 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.

Answer 3

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

Answer 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<<" ";
        }
    }
}