How to subtract one list of map keys from another and get new map (map A - mab B = map C)

Question

So I have 2 std::maps <string, shared_ptr<file> > one is 'old' one is 'new' I want to get what files were removed and so be capable to iterate thrue differene and do some stuff to shared_ptr. Is such thing possible and how to do it?

Answer 1

While it's easy enough to write this yourself (iterate over A and check if the key is present in B), this looks like a job for std::set_difference. We'll need a lambda or some custom predicate to compare keys, though:

#include <iterator>
#include <map>
#include <string>
#include <algorithm>

typedef std::map<std::string, MyPtr> my_map;

my_map A; // given
my_map B; // given

void make_a_difference()
{
  my_map C; // will hold the result

  std::set_difference(A.begin(), A.end(),
                      B.begin(), B.end(),
                      std::insert_iterator<my_map>(C, C.end()),
              [](const my_map::value_type & a, const my_map::value_type & b)
              { return a.first < b.first; }
                     );
}

If you want to write this yourself, you should consider taking advantage of the fact that both ranges are already sorted, so you can do better than a flat search for existence by advancing two iterators in parallel.

If you don't have C++11, just use this predicate instead of the lambda:

bool my_comp(const my_map::value_type & a, const my_map::value_type & b)
{
  return a.first < b.first;
}

Beware that there is no comparison on the mapped type! So if you have the same string key in both maps, then there will be no such item in the result, even if the two mapped values differ. If this is undesirable, you need a different output container (e.g. a std::multimap<my_map::key_type, my_map::mapped_type>) and a different predicate.