Possible: Set Operations on Disparate Maps with Same Key Type?

Question

Let's say I have two maps:

typedef int Id;
std::map<Id, std::string> idToStringMap;
std::map<Id, double>      idToDoubleMap;

And let's say I would like to do a set operation on the keys of the two maps. Is there an easier way to do this than to create a custom "inserter" iterator? such that I could do something like:

std::set<Id> resultSet;
set_difference( idToStringMap.begin(), idToStringMap.end(), 
                idToDoubleMap.begin(), idToDoubleMap.end(), resultSet.begin() );

My experimentation results imply that it will be necessary to create a custom inserter and perhaps a custom key comparer to do this, but I want for some insight/shortcut before doing so.

Answer 1

I don't think this is possible using just the stl without a custom iterator. You should create a generic select_1st_iterator. This would wrap any iterator to a pair and return the itr->first when dereferenced.

Note: some extensions to the stl have a select1st functor that takes a pair and returns the first element. But I have not seen an iterator version.

If you are planning to write an iterator I would suggest that you use the boost iterator library. The most likely candidate for the select_1st_iterator is the transfor_iterator

Assuming select_1st_iterator is a function that creates the real select_1st_iterator_t type, it could look like:

NOTE: your code will crash if you don't use an insert_iterator for resultSet

template<class T>
select_1st_iterator_t<T> select_1st_iterator<T>(itr)
{
    return select_1st_iterator_t<T>(itr);
}

std::set<Id> resultSet;
set_difference(
    select_1st_iterator(idToStringMap.begin()), 
    select_1st_iterator(idToStringMap.end()),
    select_1st_iterator(idToDoubleMap.begin()),
    select_1st_iterator(idToDoubleMap.end()),
    std::inserter(resultSet, resultSet.begin()) );

Answer 2

My solution using iain's advice:

template <typename T>
class Select1st 
 : public std::unary_function<T&,typename T::first_type>
{
     public:
         int operator() (T & value) const 
         {
             return value.first;
         }
};

template <typename T>
class KeyGrabItorAdapter 
 : public boost::transform_iterator< Select1st<typename T::value_type>,
                                                    typename T::iterator >
{
    public:
        KeyGrabItorAdapter( typename T::iterator itor )
            : boost::transform_iterator<Select1st<typename T::value_type>,
                                                       typename T::iterator>
                  ( itor, Select1st<typename T::value_type>() )         
        {
        }

};

having the preceeding allows the following:

typedef std::map<int, int>    IntToIntMap;
IntToIntMap    intToIntMapA;
IntToIntMap    intToIntMapB;

typedef std::map<int, double> IntToDoubleMap;
IntToDoubleMap intToDoubleMapA;
IntToDoubleMap intToDoubleMapB;

KeyGrabItorAdapter<IntToIntMap>    grabFirstABegin(    intToIntMapA.begin() ) ;
KeyGrabItorAdapter<IntToIntMap>    grabFirstAEnd(      intToIntMapA.end()   ) ;
KeyGrabItorAdapter<IntToDoubleMap> grabFirstBBegin( intToDoubleMapB.begin() ) ;
KeyGrabItorAdapter<IntToDoubleMap> grabFirstBEnd(   intToDoubleMapB.end()   ) ;

std::set<int> intResultSet;

set_difference( grabFirstABegin, grabFirstAEnd,
                grabFirstBBegin, grabFirstBEnd,
                    inserter( intResultSet, intResultSet.begin()),
                        intToIntMapA.key_comp() );