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

Possible duplicate of [is there an iterator across unique keys in a std::multimap?](http://stackoverflow.com/questions/9371236/is-there-an-iterator-across-unique-keys-in-a-stdmultimap) — Ciro Santilli OurBigBook.com, Dec 31 '16 at 22:28

score 50 · Accepted Answer · answered Jul 19 '12 at 06:20

50

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

answered Jul 19 '12 at 06:20

Jeeva

4,585
2
32
56

1

It will print all the elements – AJ. Jul 19 '12 at 06:27
I want all the keys just once - does not matter if the keys were repeated. – AJ. Jul 19 '12 at 06:35
9

@AJ see the `upper_bound` part, this should print every key only once – Fiktik Jul 19 '12 at 06:36
1

It involves searching in the whole map on every iteration. – Roman Mar 28 '13 at 13:53
3

@Roman: no it does not. See http://en.cppreference.com/w/cpp/container/multimap/upper_bound – Bklyn May 11 '16 at 20:17
@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. – Roman May 17 '16 at 21:46
1

I got a deprecation warning on `upper_bound` with the hint to use `equal_range().second`. After changing to that, everything worked fine. – Andreas Walter May 06 '20 at 06:31
i also used `equal_range().second` instead of `upper_bound()` and got improved efficiency – road_to_quantdom Nov 02 '21 at 12:27

jogojapan · Answer 2 · 2012-07-19T07:46:02.203

18

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.

edited Jul 19 '12 at 07:46

answered Jul 19 '12 at 06:47

jogojapan

68,383
11
101
131

2

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?). – Fractal Nov 15 '15 at 20:06
@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. – jogojapan Nov 16 '15 at 00:04
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. – Fractal Nov 17 '15 at 17:18
But you are not storing only the keys as required in the question... what are you storing exactly? – Sandburg Jul 19 '19 at 14:47
1

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 – road_to_quantdom Nov 02 '21 at 12:30
@road_to_quantdom Thanks for testing it! – jogojapan Nov 02 '21 at 15:49
i also used `equal_range().second` instead of `upper_bound` but their performance was somewhat similar – road_to_quantdom Nov 02 '21 at 18:47

score 9 · Answer 3 · answered Jul 19 '12 at 06:17

9

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

answered Jul 19 '12 at 06:17

Donotalo

12,748
25
83
121

1

-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 – Andrew Jul 19 '12 at 06:18
2

@Andrew `set` will only keep unique elements. It _will_ give unique keys. – Fiktik Jul 19 '12 at 06:19
1

+1 as I just wrote using a set as a comment in the other answer! ;) – Mare Infinitus Jul 19 '12 at 06:20
@Andrew on edit: unique means one of each kind. If there are two 'a' keys in multimap, then unique set must contain one 'a' – Fiktik Jul 19 '12 at 06:21
@Fiktik: generally unique means that there is one object of a kind. If there are two 'a' keys in a multimap then the key is not unique. – Andrew Jul 19 '12 at 06:23
@Andrew please take a look at `std::unique`. When talking about collections, term 'unique' is pretty precisely defined I think. – Fiktik Jul 19 '12 at 06:25
I think what Andrew means is "keys that occur only once in the multimap in the first place", and what Donotalo and Fiktik mean are "a deduplicated list of all keys". Both are valid interpretations of the English word "unique" I believe. – jogojapan Jul 19 '12 at 06:26
1

I agree that both interpretations are possible. Sorry, can't remove -1 until answer is edited – Andrew Jul 19 '12 at 06:29
The rationale behind your downvote is pedantic and unhelpful. The OP is clearly looking for the deduped list of keys, which `set` provides. It may not be the best possible way to skin this particular cat, but it is correct. – Tim Keating Apr 08 '13 at 15:44

score 3 · Answer 4 · answered Apr 05 '17 at 11:10

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

Andrew · Answer 5 · 2012-07-19T06:24:56.603

1

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

edited Jul 19 '12 at 06:24

answered Jul 19 '12 at 06:16

Andrew

24,218
13
61
90

why use a sorted list and not just a set? the set will already prove uniqueness. – Mare Infinitus Jul 19 '12 at 06:19
@MareInfinitus: because if there are two keys 'a' in the multimap the key 'a' will be in the set, but it's not unique – Andrew Jul 19 '12 at 06:20
1

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. – Mare Infinitus Jul 19 '12 at 06:22

score 0 · Answer 6 · answered Mar 22 '19 at 21:45

Other option would be to insert them into a vector and then just use, std::sort and std::unique

template<typename Container> static
std::vector<typename Container::key_type> unique_keys(Container A)
{

    using ValueType = typename Container::key_type;

    std::vector<ValueType> v;

    for(auto ele : A)
    {
        v.push_back(ele.first);
    }

    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    v.resize(distance(v.begin(),it));

    return v;
}

score 0 · Answer 7 · answered Dec 10 '19 at 16:27

This can be done in O(N) where N is the size of your map; your keys do not need to have an order operator:

template<typename Container>
std::vector<typename Container::key_type> UniqueKeys (const Container &A)
{
std::vector<typename Container::key_type> v;
auto prevIter = A.begin ();

for (auto iter = A.begin (); iter != A.end(); ++iter)
    {
    if (prevIter->first == iter->first)
        continue;

    v.push_back (prevIter->first);
    prevIter = iter;
    }

if (prevIter != A.end ())
    v.push_back (prevIter->first);

return v;
}

How can I get all the unique keys in a multimap

7 Answers7

Linked