Delete all not found i.e. delete all key/values in map not found in set

Question

I tried but failed to get the following working with std::algorithms: I have a a std::map<key_t,value_t> cache and a std::set<key_t> selected_items and I want to delete key/value pairs from cache, except for keys contained in selected_items.

Here's what I wrote without algorithms:

//This could really be written better with std::algorithms but time...
//Delete old
for (auto pair = cache.begin(); pair != cache.end(); ) {
    if (selected_items.find(pair->first) == selected_items.end())
        pair = cache.erase(pair);
    else
        ++pair;
}

To make use of the algorithms library, I figured I need to use std::set_difference with a compare function and either std::remove or std::map::erase. But I can't connect the pieces, failed at:

1. What's the correct compare function?
2. Do I have to generate a temporary set with the keys that should be deleted, or can I use the output iterator directly for the remove/erase?

How should my code look?

Answer 1

This is actually a very interesting question! It turns out that there are several difficulties involved...

• std::map uses a std::pair<const Key, T> which makes copying/moving of the std::pairs impossible (note the const)
• no algorithm can perform an actual call to std::map<>::erase()because it would invalidate the current iterator
• a standard way to reorder the elements in cache (with a e.g simple call to std::partition) and then to drop the last elements in cache cannot work due to point 1

Therefore you have two possibilities:

• Build your own loop that calls erase appropriately
• Use <algorithm> and a second map that stores the results

Since you are only interested in the second option, we can examine e.g. the use of std::set_difference() which indeed does exactly what you want.
However since the iterators of the std::map and the std::set point to different kinds of objects (std::pair and Key), we have to be careful with our Comparator.
A naive approach is simply to supply a function that takes a const std::pair & and a const Key &. But this does not work on my machine! (I do not know if this is a bug... Mac OS X 10.10.5) because std::set_difference() decides to sometimes call the Comparator with the arguments in reversed order...

Long story short, here is a solution featuring SFINAE and std::set_difference():

#include <map>
#include <set>
#include <iterator>
#include <algorithm>

using Key = int;
using Value = char;

using Pair = std::map<Key,Value>::value_type;

struct Comparator
{
    // Maybe use a custom comparator instead of '<' (see std::set documentation)
    template<class P, class K> auto operator()( const P &p, const K &k ) -> decltype(p.first < k)
    { return (p.first < k); }
    template<class P, class K> auto operator()( const K &k, const P &p ) -> decltype(k < p.first)
    { return (k < p.first); }
};

int main( void )
{
    std::map<Key,Value> cache = { {1, 'a'}, {2, 'b'}, {3, 'c'}, {4, 'd'} };
    std::set<Key> selected_items = { 2, 4 };

    std::map<Key,Value> new_cache;
    std::set_difference( cache.begin(), cache.end(),
                        selected_items.begin(), selected_items.end(),
                        std::inserter( new_cache, new_cache.end() ),
                        Comparator() );
    cache = std::move( new_cache ); // Don't use new_cache from here on

    return 0;
}