set容器的Compare

set的声明¶

std::set是一个有序、去重的集合，内部需要比较两个元素的大小。因此在定义实例化set模板时，需要传入一个比较函数，即Compare。

template <
    class T, // set::key_type/value_type 
    class Compare = less<T>,        // set::key_compare/value_compare           
    class Alloc = allocator<T>      // set::allocator_type           
>
class set;

Compare有默认值，即std::less<T>

对于C++内置函数，STL提供了默认的less。如std::less<int>、std::less<char>等等
但对于自定义函数，需要自己定义less规则，以告诉STL，元素该如何排序
因此，在本文语境下，可以理解为Compare即Less。对Compare的要求，即是Less的要求

Compare的说明（Less的说明）¶

A binary predicate that takes two arguments of the same type as the elements and returns a bool. The expression comp(a,b), where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines.

Compare是一个二进制谓词，接收两个与元素类型相同的参数，并返回true

bool Compare(T a, T b);

表达式comp(a,b)

comp是Compare类型的对象
a、b是key类型的值
如果a在b之前，要返回true（即a小于b，就返回true）
此函数要满足严格弱序（the strict weak ordering）

The set object uses this expression to determine both the order the elements follow in the container and whether two element keys are equivalent (by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)). No two elements in a set container can be equivalent.

set对象使用这个表达式，来确定两个元素的顺序与两个元素是否相等

是不是很好奇，Compare只是Less，并没有Equal信息，它是如何判断相等的？

利用条件反射(reflexively)
!comp(a,b) && !comp(b,a)表达式为true时，认为a==b

简而言之

调用comp(a, b)
调用comp(b, a)
如果，两次返回的都是false，则认为a、b相等

This can be a function pointer or a function object (see constructor for an example). This defaults to less<T>, which returns the same as applying the less-than operator (a<b)

Compare可以是一个函数指针，也可以是一个函数对象（有关示例，请参阅构造函数）

默认值为less<T>，返回值应与<运算符相同（即a<b表达式的结果）

Aliased as member types set::key_compare and set::value_compare.

在std::set中，Compare的别名是set::key_compare与std::value_compare

定义方式¶

如何定义一个比较函数呢？

仿函数形式¶

可以使用仿函数的形式定义，即重载()操作符。

struct PointLess
{
    bool operator()(const Point& lhs, const Point& rhs);
    //lhs, 全称Left-hand operand，意为左操作数
    //rhs, 全称Right-hand operand，意为右操作数
}

//虽然有了PointLess，但STL还是不知道如何比较Point
//因此要在定义std::set<Point>时，将PointLess传入
std::set<Point, PointLess> mySet;

重载类型的<操作符¶

可以重载类型的<操作符。

struct Point
{
    bool operator<(const Point& rhs);
    //this即左操作符
    //传进来的rhs是右操作符
}

//与仿函数形式不同的是，这里无需传入
//因为operator<是定义在Point中的，STL已经知道如何比较了
std::set<Point> mySet;