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);

Answer 2

Neither bool func1 (int a, int b) { return a==b; }, nor bool func2 (int a, int b) { return a+b == 8; } answer whether a must go before b. The results you get after passing such functions as comparators cannot be "interpreted": they are implementation-dependent nonsense because STL is used wrongfully - it expects a function that says whether a must go before b, but gets a function that does something else. Some examples of valid comparators are:

bool func1 (int a, int b) { return a<b; }
bool func2 (int a, int b) { return a>b; }

Answer 3

The comparison function provides a sorting order. The default is std::less and here is how to write such functions. If you want to keep the ascending sort order for the integers, just keep the default and don't specify any comparison function.