Is there an elegant way to traverse 2 maps and compare values (maps have same type)

Question

lets say I have 2 maps:

map<int,vector<int>> id2courses;
map<int,vector <int>> id2allowed_courses;

And I would like for each key(id) see if list of courses contains only those courses that are allowed for that id. It can easily be done with a for loop, but I would like to exploit the fact that std::map is ordered, aka I would like to advance in both maps(incrementing the iterator with smaller key) and when I hit equal keys then I would like to do the comparisons. I know I can do it with nontrivial while loop, but I wonder is there a builtin STL way to do it

Answer 1

Using std::set_intersection is a bit of a hack:

map<int,vector<int>> id2courses;
map<int,vector <int>> i2allowed_courses;

set_intersection(id2courses.begin(), id2courses.end(),
                 i2allowed_courses.begin(), i2allowed_courses.end(),
                 null_output_iterator(),
                 compare_and_do_something_if_same_key);

The null_output_iterator is from the question Discarding the output of a function that needs an output iterator.

compare_and_do_something_if_same_key will be passed a pair<const int, vector<int>> from each map. If the keys are equal you can do the processing you want. You also need to return a boolean to represent the ordering of elements:

bool compare_and_do_something_if_same_key(
    pair<const int, vector<int>& a, pair<const int, vector<int>& b)
{
    if(a.first == b.first) {
        doProcessing(a, b);
    }
    return a.first < b.first;
}

Caveat Emptor: The documentation says the compare function mustn't modify the objects being compared. I take that to mean mustn't modify in a way that would cause ordering problems. As you're not ordering by the second value in the pair I don't think this matters too much.

edit for readability:

This could be wrapped up into a named function:

template<typename Map, typename KeyValueProcessor> 
void process_values_for_matching_keys(
    Map& map1, Map& map2, KeyValueProcessor& keyValueProcessor);

And used as:

process_pairs_for_matching_keys(id2courses, i2allowed_courses, doProcessing);

Answer 2

You may make use of set_intersection(), but this implementation, though easier to read will be not be as well performing. I would use a cycle and increment two iterators over the two maps. I don't think there is a faster solution. Even if there is something built-in it will perform at it best as good as this naive solution.