how can I get a std::set of keys to a std::map

Question

I was writing an algorithm this morning and I ran into a curious situation. I have two std::maps. I want to perform a set intersection on the sets of the keys of each (to find which keys are common to both maps). At some point in the future, I think it's likely I'll also want to perform set subtraction here as well. Luckily, the STL includes functions for both of those operations. The problem is, I can't seem to get a std::set of the keys out of a std::map. Is there any way to do this? I'm looking for something that would be this simple, like it is in Java:

std::set<Foo> keys = myMap.getKeySet();

My understanding is that I can't use the std::set_intersection() function directly on iterators into the maps because the maps expose std::pair objects instead of just keys. Also, I don't think the map guarantees order. I'm also interested in performing this same operation on a pair of std::multimaps, if that makes any difference.

EDIT: I forgot to mention initially that due to the age of the compiler I'm forced to use (MSVC++ 6), most of the nifty template tricks that are available in boost can not be used.

Answer 1

What you basically want is a copy, as std::map doesn't keep the keys in a std::set. std::copy assumes that the value types are compatible, which isn't the case here. The std::map::value_type is a std::pair. You want to copy only the first part of the pair, which means you need a std::transform. Now, since you will be using an insert_iterator on the set, order doesn't matter. The std::set will sort on insertion, even though the map was already sorted.

[edit] Code might be easier. Top of my head, not compiled.

std::transform(MyMap.begin(), MyMap.end(),
    std::inserter(MySet, MySet.end()),
    boost::bind(&std::pair<Key,Value>::first, _1));

If you've got SGI's select1st, you don't need the boost::bind.

[edit] Updated for C++14

std::transform(MyMap.begin(), MyMap.end(),
    std::inserter(MySet, MySet.end()),
    [](auto pair){ return pair.first; });

Answer 2

Map does guarantee order; that's why it's called a sorted associative container. You can use set_intersection with a custom comparator function, the second variant listed here.

So, something like

bool your_less(const your_map::value_type &v1, const your_map::value_type &v2)
{ return v1.first < v2.first; }

set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(), your_output_it, your_less);

should do the trick. (It is also possible to use boost::lambda and bind to avoid writing a temporary function.)

The default operator< over pairs compares both components. Since you need equivalence only over the first part of the pair (the map key), you need to define your own comparison operator that provides such relation (which is what the function above does).

Answer 3

In practice,

yourmap::const_iterator mi;
set<key_type> k;
for (mi = yourmap.begin(); mi != yourmap.end(); ++mi)
  k.insert(mi->first);
return k; 

Answer 4

You can use the versatile boost::transform_iterator to return an iterator that returns only the keys (and not the values). See How to retrieve all keys (or values) from a std::map and put them into a vector?

Answer 5

The best non-SGI, non-boost STL algorithm-friendly solution is to extend map::iterator like so:

template<typename map_type>
class key_iterator : public map_type::iterator
{
public:
    typedef typename map_type::iterator map_iterator;
    typedef typename map_iterator::value_type::first_type key_type;

    key_iterator(const map_iterator& other) : map_type::iterator(other) {} ;

    key_type& operator *()
    {
        return map_type::iterator::operator*().first;
    }
};

// helpers to create iterators easier:
template<typename map_type>
key_iterator<map_type> key_begin(map_type& m)
{
    return key_iterator<map_type>(m.begin());
}
template<typename map_type>
key_iterator<map_type> key_end(map_type& m)
{
    return key_iterator<map_type>(m.end());
}

and then use them like so:

        map<string,int> test;
        test["one"] = 1;
        test["two"] = 2;

        set<string> keys;

//      // method one
//      key_iterator<map<string,int> > kb(test.begin());
//      key_iterator<map<string,int> > ke(test.end());
//      keys.insert(kb, ke);

//      // method two
//      keys.insert(
//           key_iterator<map<string,int> >(test.begin()),
//           key_iterator<map<string,int> >(test.end()));

        // method three (with helpers)
        keys.insert(key_begin(test), key_end(test));

Answer 6

You can just iterate through and add each key to a set. Sets and maps are both ordered, unordered variants are not.

Answer 7

I found good link for your question here

and have some code for your problem:

    #include <iostream>
    #include <map>
    #include <set>
    #include <iterator>

    typedef std::map<std::string, int> MyMap;

    // also known as select1st in SGI STL implementation
    template<typename T_PAIR>
    struct GetKey: public std::unary_function<T_PAIR, typename T_PAIR::first_type>
    {
        const typename T_PAIR::first_type& operator()(const T_PAIR& item) const
        {
            return item.first;
        }
    };

    int main(int argc, char** argv)
    {
        MyMap m1,m2;

        m1["a"] = 1;
        m1["b"] = 2;
        m2["c"] = 3;
        m2["b"] = 3;

        std::set<std::string> s;
        std::transform(m1.begin(), m1.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>());
        std::transform(m2.begin(), m2.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>());
        std::copy(s.begin(), s.end(), std::ostream_iterator<std::string>(std::cout, " "));
        std::cout << std::endl;
        return 0;
    }

Answer 8

You could perhaps create an iterator for a map which only yields the keys using boost::adapters::map_key, see example in the boost::adapters::map_key documentation. This appears to have been introduced in Boost 1.43, and is supposed to be C++ 2003 compatible, but I don't know about VC++ 6 specifically, which is from the C++ 98 era.

Answer 9

Building up from the answer from zvrba and the comment from dianot:

Just make the receiving collection be a vector of pairs instead of a map, and the problem pointed by dianot is over. So, using zvrba example:

std::vector<std::pair<keytype, valtype>> v;

set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(),
std::back_inserter(v), []( std::pair<keytype, valtype> const & a,
std::pair<keytype, valtype> const & b){return a.first < b.first;});

So without constructing intermediate copies or sets we can get efficiently the intersection of two maps. This construction compiles with gcc5.3.

Answer 10

I had the same problem. I solved it by using function templates

template <class T, class U>
set<T> getSetFromKeys(map<T,U> mapWithKeys){

  set<T> outputSet;

  for (pair<const T, U> keyValuePair : mapWithKeys) {
    outputSet.insert(keyValuePair.first);
  }

  return outputSet; 
}

In this way I had a generic way of extracting keys from maps in my application.

Answer 11

As MSalters says you might want to just create a set of the keys. This may be good enough for a small map.

A quick way to do this is:

std::set<Foo> keys;
for (auto &iter : myMap)
{
   keys.insert(iter.first);
}