c++ set_intersection compare function

Question

When using the functions in <algorithm>, there is usually one extra argument to customize the comparison. But I am not quite understand about the description about the argument (Documentation of set_intersection).

Binary function that accepts two arguments of the types pointed by the input iterators, and returns a value convertible to bool. The value returned indicates whether the first argument is considered to go before the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

It describes that the function should return the order of two arguments. But what about in the matching function, For example:

#include <algorithm>
#include <iostream>

using namespace std;

void print (const char* name, int* start, int* end) {
    cout << name << ": ";
    while (start < end) 
        cout << *start++ << ", ";
    cout << endl;
}

bool func1 (int a, int b) { return a==b; }
bool func2 (int a, int b) { return a+b == 8; }

int main() {
  int set1[6] = {0, 1, 2, 4, 2, 4};
  int set2[6] = {1, 2, 3, 4, 5, 6};

  int set_without_comp[6];
  int* end_wo = set_intersection(set1, set1+6, set2, set2+6, set_without_comp);
  print ("set_without_comp", set_without_comp, end_wo);

  int set_with_comp1[6];
  int *end_w1 = set_intersection(set1, set1+6, set2, set2+6, set_with_comp1, func1);
  print ("set_with_comp1", set_with_comp1, end_w1);

  int set_with_comp2[6];
  int *end_w2 = set_intersection(set1, set1+6, set2, set2+6, set_with_comp2, func2);
  print ("set_with_comp2", set_with_comp2, end_w2);
}

We get outputs:

set_without_comp: 1, 2, 4, 
set_with_comp1: 0, 1, 2, 2, 4, // Expect 1, 2, 4, 
set_with_comp2: 0, 1, 2, 2, 4, // Expect 2, 4, (maybe 6)

How to interpret the results, and what is the right way to write a comparison function in using of <algorithm> functions, and how to write one that can give me the expected results?

Answer 1

std::set_intersection expects a function that relates two elements in the same way they are stored in the set. It's not a function to describe what elements are the same, because the function does that work internally.

So, in your example, set1 is not a proper set because it's not in order (ascending order, for example). If it was in order, you could use in std::set_intersection the same order function. For example:

int set1[6] = {0, 1, 2, 2, 2, 4}; // in order (<)

bool func1 (int a, int b) { return a < b; } // the only valid function

The ability to explicitly say what order function you want to use is useful when you deal with complex objects that don't have a implicit order. For example:

struct Person {
  std::string name;
  int age;
};

bool ascendingAge(const Person& guy1, const Person& guy2) {
  return guy1.age < guy2.age;
}

...

std::intersection(..., ..., ascendingAge);