CODEWITHSUNDEEP
c++c++11
Haj Ayed Amir
Haj Ayed Amir

Reputation: 197

set_intersection with a custom set comparator

When I use the std::set_intersection function with a set that has custom comparator I don't get the expected result. The follow code outputs that {5,9,7} intersect {9} is empty set. However if I just use the normal comparator I get {9}.

#include <iostream>
#include <cstdlib>
#include <set>

using namespace std;
auto cmp = [](int* a, int* b) { return a < b; };
using stupid_set = set<int*, decltype(cmp)>;
int main() {
    int* n5 = new int(5);
    int* n9 = new int(9);
    int* n7 = new int(7);
    stupid_set s0 {n5, n9, n7};
    stupid_set s1 {n9};
    stupid_set i;
    for (auto s:s0) {
        cout << "s0:" << *s << endl;
    }
    for (auto s:s1) {
        cout << "s1:" << *s << endl;
    }
    set_intersection(s0.begin(), s0.end(), s1.begin(), s1.end(), std::inserter(i, i.begin()));
    for (auto x : i) {
        cout << "Int=" << *x << endl;
    }
}

Upvotes: 2

Views: 1013

Answers (2)

Daniel Langr
Daniel Langr

Reputation: 23497

There are multiple problems with your code, but the core one is that you use a custom comparator for sets, but not for std::set_intersection function call. This function also needs to compare elements, and, of course, must compare them with the same comparator.

Use:

struct cmp 
{
  bool operator()(int* a, int* b) const { return *a < *b; };
};

using stupid_set = set<int*, cmp>;

and 

set_intersection(
 s0.begin(), s0.end(),
 s1.begin(), s1.end(),
 std::inserter(i, i.begin()),
 cmp{}  // custom comparator used for sets
);

Whole live demo is here: https://godbolt.org/z/OAr3xV.

Note that if you omit the comparator, std::set_intersection will use operator< for set elements, and this operation is generally undefined for pointers.

If you really want to compare pointers and not the integer values there point to, you need to use std::less, since this defines order even for pointers in general:

struct cmp 
{
  bool operator()(int* a, int* b) const { return std::less<int*>{}(a, b); };
};

Again, you need to pass this comparator to std::set_intersection as well.

Live demo: https://godbolt.org/z/tLdfqn.

Upvotes: 4

NutCracker
NutCracker

Reputation: 12263

You are mixing compare function passed to the std::set and std::set_intersection. When passed to the std::set, Compare function is used for sorting because it is key comparison function. When passed to std::set_intersection it is used to define an intersection.

Try following:

#include <iostream>
#include <cstdlib>
#include <set>
#include <algorithm>

struct cmp {
   bool operator()(int *a, int *b) const {
      return *a < *b;
   }
};

using stupid_set = std::set<int*, cmp>;

int main() {
    int* n5 = new int(5);
    int* n9 = new int(9);
    int* n7 = new int(7);

    stupid_set s0 {n5, n9, n7};
    stupid_set s1 {n9};
    stupid_set i;

    for (auto s : s0) {
        std::cout << "s0:" << *s << std::endl;
    }

    for (auto s:s1) {
        std::cout << "s1:" << *s << std::endl;
    }

    std::set_intersection(
        s0.begin(),
        s0.end(),
        s1.begin(),
        s1.end(),
        std::inserter(i, i.begin()),
        cmp()
    );

    for (auto x : i) {
        std::cout << "Int=" << *x << std::endl;
    }
}

Check live

Upvotes: 0

Related Questions