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

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

Answer 2

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.

Answer 3

You can use the versatile boost::transform_iterator to return an iterator that returns only the keys (and not the values). See http://stackoverflow.com/questions/110157/how-to-retrieve-all-keys-or-values-from-a-stdmap/110228#110228

Answer 4

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 5

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 6

Hi, 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 7

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