C++ 严格弱序

ACM C/C++ 编程 数学
发布日期:   2022-01-06
更新日期:   2026-09-13
文章字数:   6.2k
阅读时长:   24 分
阅读次数:  

STL sort

STL的std::sort函数是基于Musser在1996年提出的内省排序（Introspective sort）算法实现。这个算法是个缝合怪，它汲取了插入排序、堆排序以及快排的优点：

  • 针对大数据量，使用快排，时间复杂度是O(NlogN)；
  • 若快排递归深度超过阈值__depth_limit ，改用堆排序，防止快排递归过深，同时保持时间复杂度仍是O(NlogN)；
  • 当数据规模小于阈值_S_threshold时，改用插入排序。

std::__sort

std::sort函数在内部就是直接调用的std::__sort函数。因此下面，直接从std::__sort函数开始分析。

std::__sort代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
  if (__first != __last)
  {
    // 先是完成局部有序
    std::__introsort_loop(__first, __last,
                          std::__lg(__last - __first) * 2, 
                          __comp);
    // 再完全有序
    std::__final_insertion_sort(__first, __last, __comp);
  }
}

可以看出，std::__sort主体上分为两个部分：

  1. 首先，由__introsort_loop函数使得[__first, __last)区间在多个局部有序；
  2. 其次，对第一步的结果，再进行一次插入排序std::__final_insertion_sort，保证整个[__first, __last)区间有序。

下面从以上两点进行详述。

为便于讲解，在下面的描述中，将比较器_Compare当作默认的std::less来处理。

std::__introsort_loop

__introsort_loop函数，其代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename _RandomAccessIterator, typename _Size, typename _Compare>
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
                      _Size __depth_limit, 
                      _Compare __comp)
{
  // 限制条件1
  while (__last - __first > int(_S_threshold)) {
     // 限制条件2
    if (__depth_limit == 0) {
      std::__partial_sort(__first, __last, __last, __comp); // 堆排序
      return;
    }
     
    //下面是快排
    --__depth_limit; 
    _RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp); // 寻找轴点
    std::__introsort_loop(__cut, __last, __depth_limit, __comp);                             // 递归
    __last = __cut;
  }
}

从上面可以看出，__introsort_loop函数是个递归函数，并且存在两个限制条件，或者说是递归基：

  1. 每次递归时，[__first, __last)区间的元素个数必须大于_S_threshold：

    当不满足这个条件时，__introsort_loop函数就开始返回，这会导致元素个数小于阈值_S_threshold的小区间仍然是无序的。

    那么这部分小区间怎么实现有序呢？？？

  2. 最大递归深度__depth_limit：

    当__depth_limit==0时，快排递归深度达到限制，为避免递归层数过深，STL就对当前的 [__first, __last) 区间进行堆排序。

    从另一个角度看，相当于通过 __depth_limit 限制条件，将__introsort_loop函数划分为快排、堆排两部分，而且不一定每次都会调用堆排，需要满足__depth_limit限制条件。

因此，__introsort_loop函数能正常递归，需要满足以下条件：

1
__last - __first > int(_S_threshold) && __depth_limit > 0

下面就从这两个限制点继续讲解。

_S_threshold

下面，开始讲解第【1】个限制条件_S_threshold。

我们把先深度限制条件__depth_limit去掉，只看快排部分。那么 __introsort_loop 函数的while循环可简洁如下：

1
2
3
4
5
6
7
8
9
10
 while (__last - __first > int(_S_threshold)) {
   // ...
  
   // 寻找分割区间的轴点
   auto __cut = std::__unguarded_partition_pivot(__first, __last, __comp);
   // 在右分支递归
   std::__introsort_loop(__cut, __last, __depth_limit, __comp);
   // 进入左分支
   __last = __cut;
}

有没有发现，这个快排的实现异常简洁？

在__introsort_loop函数实现中，第一眼看上去似乎只有右分支递归，而忽略了左侧分支？

这一切都是为了效率。

STL将 __introsort_loop 放在了while循环中，寻找到分割 [__first, __last)区间的分割点__cut后，每次先进入右分支递归，在右侧分支递归回来之后，下一步是：

1
__last = __cut;

这样，在下一个循环中进入左分支。

相比较常规快排实现，最直观的感受，就是减少一次函数调用的开销。此外，进入左分支后，可能就不满足__last - __first > int(_S_threshold) 限制条件，那么当前循环就退出了，避免递归。

因此，当 __introsort_loop函数因不满足_S_threshold阈值条件，逐层返回到std::__sort函数中时，完整的[__first, __last)区间中会有许多元素个数小于_S_threshold的无序区间，他们的有序性留给最后的插入排序__final_insertion_sort函数来完成。

std::__unguarded_partition_pivot

快排的最后一点，我们来看看STL是如何寻找分割位置__cut 的。这一部分是由__unguarded_partition_pivot函数实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
                            _RandomAccessIterator __last,
                            _Compare __comp)
{
  // 中间位置
  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
  // 取三点的中值，并置于 __first 处
  std::__move_median_to_first(__first, 
                              __first + 1, __mid, __last - 1,
                              __comp);
    
  // 对 [__first, __last) 进行分割，并返回分割点 __cut
  return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}

__unguarded_partition_pivot的实现分为两步：

  1. 选择一个轴点pivot，用于后续比较。
  2. 基于该轴点 pivot分割[__first, __last)区间，使得 [__first, __cut)区间的元素不大于 pivot，[__cut, __last)区间的元素不小于pivot。

下面从这两点进行讲解。

std::__move_median_to_first

__move_median_to_first函数，用意很明显，就是找出__a、__b、__c的中值，并将这个中值放在__result位置处。因此，根据传入参数，就是找出__first+1、__mid、__last-1三个位置的中值，并将中值和__first位置的值进行交换。

这个函数比较简单，其中的iter_swap函数是交换两个迭代器指向的值，具体代码解释如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template <typename _Iterator, typename _Compare>
void
__move_median_to_first(_Iterator __result, 
                       _Iterator __a, _Iterator __b, _Iterator __c, 
                       _Compare __comp)
{
  // __a < __b 
  if (__comp(__a, __b))
  {
    // __a < __b < __c 
    if (__comp(__b, __c))  
      std::iter_swap(__result, __b); // __b
    // __a < __c  <=  _b 
    else if (__comp(__a, __c))
      std::iter_swap(__result, __c); // _c
    else
     // __c <= __a < __b 
      std::iter_swap(__result, __a);  // _a
  }
  // __b <= __a < __c
  else if (__comp(__a, __c))
    std::iter_swap(__result, __a);   // __a
   // __b <= c <= a
  else if (__comp(__b, __c))
    std::iter_swap(__result, __c);   // _c
  else
   // __c <= _b <= __a
    std::iter_swap(__result, __b);  // _b
}
std::__unguarded_partition

上面找到待比较的轴点pivot之后，下面就是分割[__first, __last)区间。

分割的核心思想：寻找分割位置__cut，使得[__first, __cut)区间的元素都不大于 pviot，[__cut, __last)区间的元素都不小于pivot，然后返回分割点__cut的位置。

这部分代码讲解，见下面代码注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
                      _RandomAccessIterator __pivot, 
                      _Compare __comp)
{
  while (true)
  { 
    while (__comp(__first, __pivot)) ++__first; // *__first < *__pivot 
    /*** 跳出循环时，满足：*__first >= *__pivot  ***/
    --__last;
    while (__comp(__pivot, __last))  --__last; // *__pivot < *__last
    /*** 跳出循环时，满足：*__pivot >= *__last  ***/
      
    if (!(__first < __last))  // __fist >= __last ，表示左右边界相遇，此轮遍历结束
      return __first;        // 返回分割点位置
     
    /**  经过上面两个while循环，
     *   此时： *__first >= *__pivot &&  *__pivot >= *__last
     *   不满足分割要求，因此需要交换__first, __last 两点的值
     */
    std::iter_swap(__first, __last);  
    ++__first;
  }
}

by the way

__unguarded_partition函数，有个__unguarded 前缀，表示这个函数里没有越界检测。

那么问题来了，为什么可以没有越界检测？

以pivot左侧的区间为例：

1
2
3
4
// 无越界检测版本
while (__comp(__first, __pivot)) ++__first;      
// 常见实现版本
while (__first < __last && __comp(__first, __pivot)) ++__first;

首先，明确两点：

  • __unguarded_partition中传入参数__first，实际上是__unguarded_partition_pivot函数中的__first+1位置；
  • __unguarded_partition中传入参数__pivot，实际上是__unguarded_partition_pivot函数中的__first位置。

__pivot是__unguarded_partition_pivot函数中的三个点（__first+1、__mid、__last-1）的中值，即__pivot值肯定并不是最大的。

因此，在__unguarded_partition函数中：

  1. ++__first时，肯定存在一个点__pos，其值不小于 __pivot处的值；
  2. 要使得__comp(__first, __pivot)为true，必须是*__first < *__pivot；
  3. 又因为至少存在一个点__pos，满足*__pos >= *__pivot，使得__comp(__first, __last)为false，

因此，__first > __last的越界情况就不会发生，最终__first会在某个位置停下。同理右侧区间的判断。

因此，即使不要边界检测，也不会发生越界错误。

隐藏的BUG

但是注意了，__unguarded_partition函数，没有引入边界检测仍能正确运行，是基于正确的比较器算法。可当用户传入错误的比较器算法时，比如本文开篇自定义的比较器算法，就容易产生BUG，还是难以检测的BUG。

打开cppreference，可以看到STL要求std::sort的比较器是符合严格弱序性质的，其中容易导致BUG的是这么一条：

当比较器对象comp传入两个相等对象，返回值必须是false！！！

如果不符合严格弱序性质，则会在某些数据下会导致coredump。

假设某个小区间，数据分布如下：

1
2
数据：1   1   1   2   
索引：0   1   2   3

按照__move_median_to_first函数中的轴点选择法，最终选出的pivot是索引为1处的值，然后索引0、1处的值互换，将轴点置于first处。

下面基于不同的比较器算法来寻找分割点__cut位置。

为便于下文分析叙述：pivot简写为p，first简写为f，last简写为l。

Case1：比较器符合严格弱序关系

当std::sort传入的比较器Compare符合严格弱序关系，对该数据执行到__unguarded_partition函数时，迭代流程如下：

第一轮迭代后：

1
2
3
4
数据：1   1   1   2    
索引：0   1   2   3   
     ^   ^   ^   
     p   f   l

第二轮迭代后：

此时last指针，到了first指针位置，迭代结束。

1
2
3
4
数据：1   1   1   2   
索引：0   1   2   3  
     ^   ^      
     p  f/l

此时，分割点__cut就是first指针位置，其左侧的元素不比pivot大，其右侧不比pivot小。

Case 2：比较器不符合严格弱序关系

当std::sort传入的比较器Compare不符合严格弱序关系，即comp(a,a)==true，再执行到__unguarded_partition_pivot函数时，迭代流程如下：

第一轮迭代：

实际上，在第一轮迭代中，last指针就越界了。

因为last在左移的过程中，其取值依次是2、1、1、1，都会使得comp(pivot, last)返回true，进而导致语句 while (__comp(__pivot, __last)) --__last;一直执行，最终就导致last越界。

1
2
3
4
数据：1   1   1   2   
索引：0   1   2   3  
     ^   ^      
     p   f

总结来说，严格弱序关系，能保证 ：

  1. while (__comp(__first, __pivot)) ++__first; 在++__first的过程中，不会越界。

    原理还是上面分析的那样，即使__first+1、__mid、__last-1三个值都是相等，取得的轴点pivot在弱序关系中，使得comp(__first, __pivot)一直为false，这样while循环就进行不下去。

    如果没有严格弱序关系保证，则就会越界。

  2. while (__comp(__pivot, __last)) --__last;

    原理同上。

为了验证上面这个猜想，我自己写了个demo。

在数组vec里全是一样的数字，数组元素个数必须超过_S_threshold阈值（默认值16）才能触发std::sort的快排行为。

注意，代码必须在MSVC下编译运行，因为GCC对于某些越界行为并不报错，不如MSVC严格（没有测试clang）。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <vector>
#include <algorithm>

int main(int argc, char const* argv[]) {
    
    std::vector<int> vec{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};  // 全是一样的元素，且必须超过16个元素
    std::sort(vec.begin(), vec.end(),
             [](const int& lhs, const int& rhs)
             {
                return lhs <= rhs; // BUG，修改为: return lhs < rhs; 才行
             });
    return 0;
}

__depth_limit

好嘞，下面开始讲解第【2】个限制条件__depth_limit。

当快排的递归深度，达到阈值 __depth_limit时，STL使用堆完成当前[__first, __last)区间的排序。下面我们把快排部分去掉，只看堆排序部分，那么 __introsort_loop 函数的while循环可简洁如下：

1
2
3
4
5
6
7
while (__last - __first > int(_S_threshold)) {
    if (__depth_limit == 0) {
      std::__partial_sort(__first, __last, __last, __comp);
      return;
    }
    //...
}

显而易见，堆排是由__partial_sort函数完成。

std::__partial_sort

__partial_sort函数，旨在取出 [__first, __last)区间前__middle - _frist个最小元素，并将其按照_Cpmpare比较策略进行排序后，有序存放在 [__first, __middle)区间，其余的节点放在[__middle, __last)区间。

__partial_sort函数实现如下（关于堆的实现，可以参考侯捷老师的《STL源码剖析》书籍）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 上层调用
std::__partial_sort(__first, __last, __last, __comp);

// 函数原型
template <typename _RandomAccessIterator, typename _Compare>
inline void
__partial_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __middle,
               _RandomAccessIterator __last,
               _Compare __comp)
{
  // 先建堆，并使 [first, middle) 区间存放前 middle-first 个最小值
  std::__heap_select(__first, __middle, __last, __comp);
  
  // 对 [first, middle) 区间元素进行排序
  std::__sort_heap(__first, __middle, __comp);
}

因此，经过 __partial_sort函数后：

  • [__first, __middle)区间，有序存储了[__first, __last)区间的前__middle - _frist个最小元素；
  • [__middle, __last)区间，无序存储[__first, __last)区间剩余元素。

在 __introsort_loop 函数中调用 __partial_sort 函数时，__middle参数和__last参数都是__last，因此实现的就是[__first, __last)区间的全排序。

std::__final_insertion_sort

当 __introsort_loop 函数执行完毕，最后一步需要将整个数据变得有序，这由__final_insertion_sort函数完成。

在讨论 __final_insertion_sort之前，先回顾下 __introsort_loop函数，它返回有两种可能：

  1. _S_threshold：递归到某个[__first, __last)区间时，其元素个数__last - __first <= _S_threshold时，结束递归。

    __introsort_loop函数返回到std::__sort函数时，整个大的区间中还存在一些元素个数不足_S_threshold的小区间仍然是无序的。

  2. __depth_limit：递归层次超过限制__depth_limit。

因此，当执行__final_insertion_sort函数时，当前大区间[__first, __last)只存在局部无序，主体上是有序的。这种情况，非常适用于插入排序，此时时间复杂度是O(N)。

为了进一步优化，加速排序的速度，STL针对两种情况分别求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename _RandomAccessIterator, typename _Compare>
void
__final_insertion_sort(_RandomAccessIterator __first,
                       _RandomAccessIterator __last, 
                       _Compare __comp)
{
  // 大数据量
  if (__last - __first > int(_S_threshold))
  {
    std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
    std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp);
  }
  else
   // 小数量量直接使用插入排序，不用经过快排、堆排
    std::__insertion_sort(__first, __last, __comp);
}
std::__insertion_sort

__insertion_sort函数是按照标准的插入排序实现。

插入排序的核心思想：将整个序列视为两个部分，『有序的前缀』和『无序的后缀』，再通过循环迭代，不断地将后缀的首元素转移插入到前缀中，保持前缀仍然有序。当后缀为空，整个序列有序。

时间复杂度：如果当前序列已经完全有序，则插入排序时间复杂度是O(N)，完全逆序则O(N^2)。

运行到 __insertion_sort时，整个数据规模主体保持有序，局部小区间无序，非常适合使用插入排序，算法步骤如下：

  • 初始状态下，前缀序列中只有__first一个元素，后缀序列则是[__first+1, __last)区间的元素；
  • 对[__first+1, __last)区间的元素进行遍历，不断将后缀序列的首元素，插入到前缀序列中。

在 __insertion_sort函数中，对于后缀序列[__first+1, __last)区间的每个元素__i：

  • 先判断__i位置的元素是否小于__first；

    如果是，则直接将[__first, __i)区间的元素整体后移一位，再将__i位置的元素插入到原先__first位置处。这样就避免了从__i位置一路比较到__first位置，才找到__i在前缀序列中的待插入位置，即节省了比较开销。

  • 如果否，则需要在(__first, __i)区间寻找合适的位置__pos，使得 *(__pos-1) <= *__i < *__pos

    这个部分是由__unguarded_linear_insert函数完成，这个函数前面也有 __unguarded 前缀，也是没有边界检测的意思。

__insertion_sort函数，整个代码解释如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <typename _RandomAccessIterator, typename _Compare>
void
__insertion_sort(_RandomAccessIterator __first,
                 _RandomAccessIterator __last, 
                 _Compare __comp)
{
  if (__first == __last) return;

  /*** 下面要将 (fist, last) 区间的每个元素 __i 都插入到前缀序列中 ***/
    
  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
  {
    /* case 1:  *__i < *__first 时，则将 [__first, __i)区间后移，
     *          再将 *__i 插入到原先 __first 位置
     */
    if (__comp(__i, __first))
    {
      auto __val = std::move(*__i);              // 待插入的值
      std::move_backward(__first, __i, __i + 1); // 将 [_first, _i) 区间的元素朝后移动一个位置
      *__first = std::move(__val);               // 将 __i 位置处的值移动到 __first 处
    }
    else
    {
      /* case 2:  *__i >= *__fist 时，
       *          此时需要在有序前缀 (fist，_i)区间中，寻找合适的位置再插入
       */
      std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
    }
  } // for-end
}
std::__unguarded_linear_insert

__unguarded_linear_insert函数，在有序前缀(__first, __last)中寻找合适的位置__pos，将__i位置的值插入到__pos处。

那什么叫合适的位置呢？

从__i-1的位置开始遍历，第一个出现逆序对的位置__pos，即：

  • __pos < __i ，且
  • *(__pos-1) <= *__i < *__pos。

当找到这么个位置，需要将[__pos, __i)区间的元素，后移一位，然后将__i位置的元素插入到__pos。为了实现这一步，STL在 __unguarded_linear_insert函数中，边遍历、边把当前位置的元素向后移动。

下面是__unguarded_linear_insert函数的源码分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <typename _RandomAccessIterator, typename _Compare>
void
__unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
  auto __val = std::move(*__last);   // 当前待插入的值 __val
  _RandomAccessIterator __next = __last; 
  --__next;                          // 需要在有序前缀区间 (first, last)中遍历，因此开始遍历的位置需要 --next
    
  /* __comp(__val, __next) 为false时，表示出现逆序，
  *  __next 指向当前遍历位置
  *  __last 用于指向 __next 的上一个位置
  */
  while (__comp(__val, __next))
  {
    /** 下面是将当前遍历位置 __next 存储到 __last ***/
      
    *__last = std::move(*__next);  // 将当前位置的值后移动一位
      
    __last = __next;               //  __last 前移
    --__next;                      //  __next 前移
  } 
 
  /* 以上while循环，相当于将 [__last, __i) 区间的元素，后移动了一位，
   * 现在找到合适位置，此时：*__next <= val && val < *last
   * 因此，将 val 插入到上一个节点位置
   */
  *__last = std::move(__val);
}

__unguarded_linear_insert 为啥能不用检测是否越界？

因为，之所以能进入__unguarded_linear_insert函数，是因为在__insertion_sort函数中有了 __i >= __first。因此在此函数中，再不济，while(__comp(__val, __next))也会在__first后一个位置停下来，最终插入在___first+1处。

免去边界检测，可以实现一定程度上的优化（STL对性能真的是锱铢必较）。

在这，你可能在想这个 __unguarded_partition函数，会存在之前在 __unguarded_partition中出现的BUG吗？

理论上是应该要出BUG的，这也是符合CPP标准，但是从上面的GCC的源码实现可以看出，GCC下不会出现BUG。

下面的代码在MSVC中运行被中止，而GCC下是可以正常运行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <vector>
#include <algorithm>

int main(int argc, char const* argv[]) {
    std::vector<int> vec{1,1};
    
    std::sort(vec.begin(), vec.end(),
              [](const int& lhs, const int& rhs)
              {
                  return lhs <= rhs;
              });

    return 0;
}

因为，在GCC下，会进入__insertion_sort函数的if (__comp(__i, __first))条件分支中，不断地将[__first, __i)区间元素后移动一位，避免了报错。

尽管GCC避免了报错，但实际上却不符合CPP标准。

因此，在书写自定义比较器算法时，要使其符合「严格弱序关系」，代码才具有移植性。

到此，std::sort的整个运行流程大致分析完毕。

什么是严格弱序

严格弱序比较这个概念听起来就比较抽象，生涩难懂，讲明白就更加不容易了。看了多份资料和相关书籍的部分章节，下面就来详细谈谈这个 【严格弱序比较】。谈到这个概念就不得不先讲两个比较重要的概念【小于比较（LessThan comparable）】和【严格弱序（strict weak ordering）】。

小于比较（LessThan comparable）

这里可能有个疑问这么多种比较原则，怎么小于比较就那么重要了？先来回答一下这个问题，对于比较本身而言有：小于，大于，小于等于，大于等于，等于，这个大家都知道。但对于这五种比较可以提炼出一个基础的比较，那就是【小于比较】（当然也可以是大于，这里就以小于为例）其他的比较都可以用小于比较进行等价。

大于：x > y <=> y < x

大于等于：x >= y <=> !(x < y)

小于等于：x <= y <=> !(y < x)

等于：!(x<y) && !(y<x)

严格弱序（strict weak ordering）】

严格弱序的正式定义：如果两个元素具备任何一个元素都不小于另一个元素的性质，那么就视为它们是具备某种程度之等价关系是合理的。公式：!(x<y) && !(y<x), 广义上!op(x,y) && !op(y,x) （op(x,y) 表示比较x和y）。 光看定义需要理解一阵子，不过看了公式应该就比较好理解了，严格弱序就是对等价做了个定义，满足这个条件的既是等价。

严格弱序比较（strick weakly comparable）

前面铺垫了这么多，是时候进入主题了。

所谓严格弱序比较，就是满足【小于比较】和【严格弱序】这两个条件，才能称之为严格弱序比较。

举个反例：如果我们把比较定义为【小于等于】出现什么问题呢？如果x等于y，那么根据等价的定义 !op(x,y) && !op(y,x)，=> !true && !true => false。 明明相等，最后推导出来的结果却是不等，这就错了。

STL 为什么要设计严格弱序

STL为何要给它的用户们设置这样一个关卡，给他们找麻烦呢，但其实细想，这个设计是很绝妙的。

  • 对于sort中排序函数，如果不遵守严格弱序，那么在根据pivot调整元素顺序时，while (__comp(*__first, __pivot)) ++__first; 中++__first会越界。导致程序崩溃。
1
2
3
4
5
6
7
8
9
10
11
12
while (true)
{
    while (__comp(*__first, __pivot))
        ++__first;
    --__last;
    while (__comp(__pivot, *__last))
        --__last;
    if (!(__first < __last))
        return __first;
    std::iter_swap(__first, __last);
    ++__first;
}
  • 对于有序且无重复元素的关联容器（例如，set，map），向里面插入两个相同元素时，如果定义的比较函数不是严格弱序的话（而是 在<= 情况下，返回true），由于stl判断相等是使用的 !Cmp(a,b) && !Cmp(b,a)，那么当a 和b 相等时，stl判断相等会返回false，被认为这两个元素值不同的，这是错误的。所以比较函数需要遵守严格弱序原则，换句话说，永远让比较函数对相等的值返回false。
  • 对于有序且有重复元素的关联容器（例如，multiset，multimap），可能让人产生一种错觉：无重复元素的关联容器是要求严格弱序的，那么有重复元素的关联容器是否可以用小于等于来比较呢？这是错误的。multiset和multimap如果用小于等于来比较，那么容器就会认为值相等的元素不是等价的，这和容器的本意是背道而驰的，它们的本意是值相等 => 被认为是等价的 => 允许插入。被认为是不等价的虽然也可以插入（如下图所示，10A，10B都能插入），但是在调用equal_range获取等价元素（注意这里不是值相等的元素）的范围时候，值相等的元素会不在这个范围内，所以值相等却不等价这是做法是错误的。很多人都认为c++很难，它的难其中一部分原因在于它太过于灵活了，我们可以灵活构造容器，但是我们要考虑这样设计是否合理。

比方说你在进行数据排序的时候，想要写一个自定义的排序方法，你可以重写大于、小于、大于等于 或者是 小于等于，如果你是重写的 >=（非严格弱序）

a >= b , b >= a 通过两个对象交换位置，你可以判断出它们之间的 >= 和 <= 关系，但你无法判断这两个数是否相等，是不是这样的？

但如果你重写的是 >（严格弱序），情况就有所不同了

a > b 结果为 true，则大小已定；

如果结果为false，则可知 a <= b，接着判断 b > a，（操作符不变，因为你就提供了一个操作符，交换比较对象的位置），结果为true，则大小已定，若是结果为false，则结果也很显然，那就是 a == b

严格弱序让你实现了，只要传入一个操作符，你就可以知道两个操作数之间的大小关系、是否相等关系，这是非严格弱序所不能实现的。因为C++有很多地方对相同元素是敏感的，就比如说不允许有重复元素出现的set容器，如果把相同元素识别成不同或者根本识别不出来，那是很不恰当的。

对于一个类型，无论是默认类型，还是自定义的类型的变量，都会经常使用到【比较】。例如，单纯的比较同一个类型的两个变量的大小、set和multiset等容器插入数据时和容器中已有数据做比较来决定是否插入和放入的位置，还有本文的主题在排序（sort）的时的比较。

References:

https://mp.weixin.qq.com/s?__biz=MzkyMjIxMzIxNA==&mid=2247486922&idx=1&sn=5d8336a50d0fe7ebdc0c13e9dc8816cf

https://blog.csdn.net/River_Lethe/article/details/78618788

https://blog.csdn.net/llz62378/article/details/88937139

https://en.wikipedia.org/wiki/Weak_ordering

文章作者: sfc9982
文章链接: https://googles.plus/2022/01/06/c-yan-ge-ruo-xu/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 sfc9982 !
ACM C/C++ 编程 数学
  目录