Find set_difference between set and map keys

Question

I would like to ask if it is possible to provide an example on how I can find the difference between a set and keys of a map using set_difference

I know that another question std::set_difference is it possible to compare set and map Keys? but it points to another question without a clear example. I need a solution without using boost library

#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(result, result.end()));

Answer 1

You can do it with a custom comparator. Standard algorithms use strict weak ordering. To test for equality of two elements, the comparator needs to be aplied twice. Two elements are equal when both comp(first, second) and comp(second, first) return false (where comp is the comparator function). Since the elements you want to compare are of different types, one comparator won't do - you'll need two overloads:

struct cmp {
    bool operator()(int i, const std::pair<int, double>& p) const
    {
        return i < p.first;
    }

    bool operator()(const std::pair<int, double>& p, int i) const
    {
        return p.first < i;
    }

};

int main()
{

    std::set<int> s1 { 1, 2, 3, 4 };
    std::map<int, double> s2 { {1, 0}, {2,0}, {4,0} };

    std::set<int> result;

    std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
        std::inserter(result, result.end()), cmp());

    std::cout << *result.begin(); // will print 3

}

Answer 2

@Superlokkus @jrok I know this post is about a year late... Still would prefer to maybe clarify the problem. There is a problem with MS Visual Studio when the comparison operator is overloaded. The thing is that there are two combinations that are not being accounted for:

struct cmp {
    bool operator()(const int& i, const std::pair<int, double>& p) const
    {
        return i < p.first;
    }
    bool operator()(const std::pair<int, double>& p, const int& i) const
    {
        return p.first < i;
    }
    bool operator()(const std::pair<int, double>& p1,
        const std::pair<int, double>& p2) const
    {
        return p1.first < p2.first;
    }
    bool operator()(const int& i1, const int& i2) const
    {
        return i1 < i2;
    }
};

By inserting the last two operators we are inserting all of the options that the compiler needs to obtain the difference. In fact, I recommend using the const int& instead of simply int as presented in the first two operators. For small cases, this is not relevant but when we have really big arrays of pairs, ints or even worse, really big containers, then the operation will be memory bound as we will have lot of memory accesses. By using this we pass the reference of the parameter and have no need to copy the parameter therefore avoiding a copy operation and filling out the cache with another set of values that are completely unnecessary.

As a last note, I find that it is quite weird that the first solution proposed by @jrok compiles perfectly in release mode (MSVC 2013) and not in debug. It would be nice to know why!

Answer 3

My own slight preference of how to write the comparison predicate is:

class KeyLess
{
    public:

      template< typename KeyType >
      static KeyType getKey( const KeyType& k ) 
      {  
          return k;
      }

      template< typename KeyType, typename ValueType >
      static KeyType getKey( std::pair< const KeyType, ValueType > const& p ) 
      {         
          return p.first;
      }

      template< typename L, typename R >
      bool operator()( const L& l, const R& r ) const
      {
          return getKey( l ) < getKey( r );
      }
};

You can now use this all over your code.