Is there a way to intersect/diff a std::map and a std::set?

Question

I'm wondering if there a way to intersect or make the differences between two structures defined as std::set<MyData*> and std::map<MyData*, MyValue> with standard algorithms (like std::set_intersect)

The problem is that I need to compute the difference between the set and the keyset of the map but I would like to avoid reallocating it (since it's something that is done many times per second with large data structures). Is there a way to obtain a "key view" of the std::map? After all what I'm looking is to consider just the keys when doing the set operation so from an implementation point it should be possible but I haven't been able to find anything.

Answer 1

You can use transform_iterator from boost in order to adapt the std::map iterator and to return only the keys:

#include <algorithm>
#include <iostream>
#include <map>
#include <iterator>
#include <string>
#include <set>
#include <vector>

#include <boost/iterator/transform_iterator.hpp>

typedef std::map<std::string, int> map_t;
typedef std::set<std::string> set_t;

const map_t::key_type & getKey(const map_t::value_type & pair)
{
    return pair.first;
}

typedef const map_t::key_type & (*getKey_t)(const map_t::value_type &);

typedef boost::transform_iterator<getKey_t, map_t::iterator> key_iterator_t;

int main()
{
    map_t map;
    map["a"]=1; map["b"]=2;
    set_t set;
    set.insert("a"); set.insert("c");

    std::vector<std::string> v;

    std::set_intersection(set.begin(), set.end(),
        key_iterator_t(map.begin(), getKey),
        key_iterator_t(map.end(), getKey),
        std::back_inserter(v));
    std::copy(v.begin(), v.end(),
        std::ostream_iterator<std::string>(std::cout," , "));
}

Answer 2

set_intersection works on ordered collections. You can write a custom iterator that wraps the standard map iterator and returns the key. You can then use this with set_intersect