c++ - 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; });