C++严格弱序的介绍

严格弱序（strict weak ordering）

关联式容器（set、multiset、map和multimap）的排序准则的定义，和std::sort的排序准则定义必须遵守严格弱序，详细描述见官方解释(strict weak ordering.pdf)。

严格弱序的定义：

简单的来说就是a<b返回true，a=b和a>b返回false。

详细定义：

1. 必须是非对称的（antisymmetric）。

   对operator< 而言， 如果x < y为true， 则y < x为false。

   对判断式(predicate) op()而言，如果op(x, y)为true，则op(y, x)为false。

2. 必须是可传递的（transitive）。

对operator< 而言，如果x < y 为true且y < z为true， 则x < z 为false。

对判断式(predicate) op()而言，如果op(x, y)为true且op(y, z)为tru，则op(x, z)为true。

1. 必须是非自反的（irreflexive）

   对operator< 而言，x < x 永远是false

   对判断式(predicate) op()而言，op(x, x)永远是false。

2. 必须有等效传递性（transitivity of equivalence）

对operator< 而言，假如 !(a<b) && !(b<a) 为true且 !(b<c) && !(c<b) 为 true 那么!(a<c) && !(c<a) 也为true. 对判断式(predicate) op()而言， 假如 op(a,b), op(b,a), op(b,c), 和op(c,b) 都为 false, 那么op(a,c) and op(c,a) 也为false.

// 一个定义std::set<struct>的例子
#include <set>
#include <iostream>

struct ORDERING_EXAMPLE
{
    int x;
    int y;
    int z;

    /// 重载遵循严格弱序的运算符<
    bool operator < (const ORDERING_EXAMPLE& OtherStruct) const
    {
        if (this->x < OtherStruct.x)
            return true;
        if (OtherStruct.x < this->x)
            return false;

        // x == x则比较y
        if (this->y < OtherStruct.y)
            return true;
        if (OtherStruct.y < this->y)
            return false;

        // y == y则比较z
        if (this->z < OtherStruct.z)
            return true;

        return false;
    }
};

int main()
{
    std::set<ORDERING_EXAMPLE> setOrderingExample;

    ORDERING_EXAMPLE stOrderingExample0 = { 0, 0, 0 };
    ORDERING_EXAMPLE stOrderingExample1 = { 0, 1, 2 };
    ORDERING_EXAMPLE stOrderingExample2 = { 0, 1, 3 };
    ORDERING_EXAMPLE stOrderingExample3 = { 0, 1, 3 };

    setOrderingExample.insert(stOrderingExample0);
    setOrderingExample.insert(stOrderingExample1);
    setOrderingExample.insert(stOrderingExample2);
    setOrderingExample.insert(stOrderingExample3);

    return 0;
}

下面举一个会崩溃的例子对二维数组排序。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> temp(5, 1);
  std::vector<std::vector<int>> vec(5, temp);
  std::sort(vec.begin(), vec.end(),
            [](const std::vector<int> &l, const std::vector<int> &r) {
              if (l.size() == r.size()) {
                for (size_t i = 0; i < l.size(); ++i) {
                  if (l.at(i) == r.at(i)) {
                    continue;
                  } else {
                    return l.at(i) < r.at(i);
                  }
                }
                return true;  /// 这里会崩溃，改为false则不会而不会崩溃(遵循严格弱序)
              } else {
                return l.size() < r.size();
              }
            });
}

两个参数的重载符号简单示例

class key
{
public:
    int x;
    int y;

    bool operator<(const key& stOther)
    {
        if (x < stOther.x)
        {
            return true;
        }
        else if (x > stOther.x)
        {
            return false;
        }
        else if (y < stOther.y)
        {
            return true;
        }
        else if (y > stOther.y)
        {
            return false;
        }
        else
        {
            return false;
        }
    }
};

class key
{
public:
    int x;
    std::string y;

    bool operator<(const key& stOther)
    {
        if (x < stOther.x)
        {
            return true;
        }
        else if (x > stOther.x)
        {
            return false;
        }
        else if (y < stOther.y)
        {
            return true;
        }
        else if (y > stOther.y)
        {
            return false;
        }
        else
        {
            return false;
        }
    }
};