How can I get all the unique keys in a multimap

user_189206 0
Viewed 28447

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

multimap std stl c++
7 Answers

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

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