严格弱序（less函数、小于号重载）

前言¶

严格弱序，stick weak ordering，在以下场景会涉及到

对一个容器进行排序时，如使用std::sort
使用有序关联容器时，如使用std::set、std::map
使用std::less时
重载<操作符（小于）

其中，std::less与<操作符都需要满足严格弱序规则。

作用¶

对于内置类型，我们有三种方式来判断两个值的大小关系，即<、>、==。而对于自定义类型，实现这三种操作符是很累的。

但是，有了严格弱序的概念，我们实现严格弱序即可，而无需实现这三种操作符。

判定规则¶

假设bool comp(T lhs, T rhs)函数满足严格弱序。那么，我们如何比较a、b的大小呢？

若comp(a, b) == true，则判定a<b
若comp(b, a) == true，则判定a>b
若comp(a,b)==false && comp(b,a)==false，则判定a==b

解释

a严格弱序b，顾名思义，a的优先级严格比b小（可以简单理解为，a的数值小于b）
因此，如何判断a==b呢？如果a不严格弱序b、而且b也不严格弱序a，那就意味着a==b了

原理¶

事实上，<其实就是严格弱序，而<=就不是严格弱序

<号（满足严格弱序）¶

bool comp1(int lhs, int rhs)
{
    //lhs, 全称Left-hand operand，意为左操作数
    //rhs, 全称Right-hand operand，意为右操作数
    return lhs < rhs;
}

a	b	`comp1(a, b)` 即a<b	`comp1(b, a)` 即b<a	`comp1(a,b)==false && comp1(b,a)==false`
1	2	`1<2` => true	`2<1` => false	false
2	1	`2<1` => false	`1<2` => true	false
1	1	`1<1` => false	`1<1` => false	true

因此，根据严格弱序的判定规则，comp1能够成功区分a、b的大小。

<=号（不满足严格弱序）¶

bool comp2(int lhs, int rhs)
{
    return lhs <= rhs;
}

a	b	`comp2(a, b)` 即a<=b	`comp2(b, a)` 即b<=a	`comp2(a,b)==false && comp2(b,a)==false`
1	2	`1<=2` => true	`2<=1` => false	false
2	1	`2<=1` => false	`1<=2` => true	false
1	1	`1<=1` => true	`1<=1` => true	false

因此，根据严格弱序的规则，comp2不能够区分a==b的情况。

总结¶

简而言之，严格弱序，就是

a严格弱序b => a<b，不可能出现a==b的情况

编写满足严格弱序的函数，关键在于

对于相同的元素，无论是comp(a, b)，还是comp(b, a)都要返回false
如此，根据严格弱序函数，才能判断出a==b

总之，如何编写满足严格弱序的函数呢？

a<b，Less函数返回true
a==b，Less函数返回false
a>b，Less函数返回false

示例¶

编写严格弱序的方式有很多中，这就涉及C++的语法，本文并不展开。

以Point3D为例，编写其严格弱序的函数

Point3D涉及到浮点数判等问题，文示例阈值用的是1e-6

#include <iostream>
#include <set>

struct Point3D
{
    double x, y, z;

    Point3D(double xx, double yy, double zz) : x(xx), y(yy), z(zz) {}
    bool operator==(const Point3D& rhs) const
    {
        auto equal_zero = [](double v)->bool
        {
            return -1e-6 < v && v < 1e-6; //相等阈值1e-6
        };

        return equal_zero(this->x - rhs.x)
            && equal_zero(this->y - rhs.y)
            && equal_zero(this->z - rhs.z);
    }
    bool operator<(const Point3D& rhs) const
    {
        //根据严格弱序的规则：
        //  对于a==b的情况，无论comp(a, b)，还是comp(b, a)，两者都要返回false
        if (*this == rhs) return false;

        //排序方式，优先级：x轴优先级 > y轴 > z轴
        if (x < rhs.x) return true;
        else if (x > rhs.x) return false;
        else if (y < rhs.y) return true;
        else if (y > rhs.y) return false;
        else if (z < rhs.z) return true;
        else return false;
    }

    friend std::ostream& operator<<(std::ostream& os, const Point3D& pnt)
    {
        os << pnt.x << '\t' << pnt.y << '\t' << pnt.z;
        return os;
    }
};

int main()
{
    std::set<Point3D> pointSet;

    pointSet.emplace(4.4302740239554605, 3.25, 1.99999999998); //A
    pointSet.emplace(4.4302740239554605, 3.25, 2.00000000000); //==A

    pointSet.emplace(4.5, 3.25, 1.99999999998); //x > A.x
    pointSet.emplace(4.4302740239554605, 4.0, 1.99999999998); //y > A.y
    pointSet.emplace(4.4302740239554605, 3.25, 3.0); //z > A>z

    std::cout.precision(10);
    for (const auto& item : pointSet)
    {
        std::cout << item << std::endl;
    }

    return 0;
}

输出

4.430274024 3.25    2
4.430274024 3.25    3
4.430274024 4   2
4.5 3.25    2