c++ set_intersection 比较函数

Question

使用<algorithm>中的函数时，通常会有一个额外的参数来自定义比较。但是我不太明白关于参数的描述(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.

说明函数应该return两个参数的顺序。但是在匹配函数中呢，例如：

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

我们得到输出：

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)

如何解释结果，在使用 <algorithm> 函数时写比较函数的正确方法是什么，如何写一个能给我预期结果的函数？

Answer 1

std::set_intersection 需要一个函数，该函数以两个元素存储在集合中的方式关联两个元素。它不是描述哪些元素相同的函数，因为函数在内部完成了这些工作。

因此，在您的示例中，set1 不是正确的集合，因为它没有按顺序排列（例如，升序）。如果是有序的，您可以在 std::set_intersection 中使用相同的排序函数。例如：

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

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

在处理没有隐含顺序的复杂对象时，明确说明要使用的排序函数的功能很有用。例如：

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

bool func1 (int a, int b) { return a==b; } 和 bool func2 (int a, int b) { return a+b == 8; } 都没有回答 a 是否必须在 b 之前。通过比较器等函数后得到的结果不能是 "interpreted"：它们是依赖于实现的废话，因为错误地使用了 STL - 它期望一个函数说明 a 是否必须在 b 之前，但得到一个做其他事情的功能。一些有效比较器的例子是：

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

Answer 3

比较功能提供排序顺序。默认是std::less，这里是how to write such functions。如果要保持整数的升序排序，保持默认即可，不要指定任何比较函数。

c++ set_intersection 比较函数

c++ set_intersection compare function

c++

algorithm

comparison