std::sort 宕机源码分析

作者: v子午线v | 来源:发表于2021-09-23 17:47 被阅读0次

一次公司项目代码引发了宕机，源于std::sort。相似代码贴在下面。由于std::sort 第三个参数写的不对造成的。

源码：

using Vec = std::vector<std::pair<int, int>>;
void print_elem(const Vec& vec, const std::string& str)
{
    std::stringstream oss;
    for (const auto& item : vec)
    {
        oss << "(" << item.first << "--" << item.second << ")";
    }
    std::cout << str << oss.str() << std::endl;
}
Vec getVec(uint32_t size)
{
    Vec vec;
    for (uint32_t i = 0; i < size; i++)
    {
        vec.emplace_back(i, rand() % 2 + 1);
    }
     print_elem(vec, "origin: ");
    std::sort(vec.begin(), vec.end(),
              [&vec](const std::pair<int, int>& lhs, const std::pair<int, int>& rhs)
              {
                  print_elem(vec, "sort: ");
                  return lhs.second >= rhs.second;
              });
     return vec;
}
 int main()
{
    srand(time(NULL));
    const Vec vec = getVec(17);
    return 0;
}

编译：g++ sort.cpp -g -o sort，执行

[cn@sort] ./sort.o 
origin: (0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)

......

sort: (15-2)(14-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (15-2)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
free(): invalid pointer
已放弃 (核心已转储)

最开始存放的元素是：(0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)

调用std::sort 之后，在中间的过程中出现了非法元素：273-0

(273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)

生成了core文件，使用 gdb调试一下

[cn@sort] gdb -c core --se sort.o
Reading symbols from sort.o...
[New LWP 340173]
Core was generated by `./sort.o'.
Program terminated with signal SIGABRT, Aborted.
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50  ../sysdeps/unix/sysv/linux/raise.c: 没有那个文件或目录.
(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007fc877d18859 in __GI_abort () at abort.c:79
#2  0x00007fc877d833ee in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7fc877ead285 "%s\n")
    at ../sysdeps/posix/libc_fatal.c:155
#3  0x00007fc877d8b47c in malloc_printerr (str=str@entry=0x7fc877eab4ae "free(): invalid pointer") at malloc.c:5347
#4  0x00007fc877d8ccac in _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:4173
#5  0x000055a8ec33cdf8 in __gnu_cxx::new_allocator<std::pair<int, int> >::deallocate (this=0x7ffc51d279e0, 
    __p=0x55a8edd28000) at /usr/include/c++/9/ext/new_allocator.h:128
#6  0x000055a8ec33c59a in std::allocator_traits<std::allocator<std::pair<int, int> > >::deallocate (__a=..., 
    __p=0x55a8edd28000, __n=32) at /usr/include/c++/9/bits/alloc_traits.h:470
#7  0x000055a8ec33bc3a in std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::_M_deallocate (
    this=0x7ffc51d279e0, __p=0x55a8edd28000, __n=32) at /usr/include/c++/9/bits/stl_vector.h:351
#8  0x000055a8ec33b420 in std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::~_Vector_base (
    this=0x7ffc51d279e0, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:332
#9  0x000055a8ec33b475 in std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::~vector (
    this=0x7ffc51d279e0, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:680
#10 0x000055a8ec339c9d in main () at sort.cpp:30
(gdb) f 5
#5  0x000055a8ec33cdf8 in __gnu_cxx::new_allocator<std::pair<int, int> >::deallocate (this=0x7ffc51d279e0, 
    __p=0x55a8edd28000) at /usr/include/c++/9/ext/new_allocator.h:128
128     ::operator delete(__p);
(gdb) f 4
#4  0x00007fc877d8ccac in _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:4173
4173    malloc.c: 没有那个文件或目录.
(gdb) f 3
#3  0x00007fc877d8b47c in malloc_printerr (str=str@entry=0x7fc877eab4ae "free(): invalid pointer") at malloc.c:5347
5347    in malloc.c
(gdb) f 2
#2  0x00007fc877d833ee in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7fc877ead285 "%s\n")
    at ../sysdeps/posix/libc_fatal.c:155
155 ../sysdeps/posix/libc_fatal.c: 没有那个文件或目录.
(gdb) f 1
#1  0x00007fc877d18859 in __GI_abort () at abort.c:79
79  abort.c: 没有那个文件或目录.

最后发现是 delete 的时候宕机-----在 std::sort 排序过程中将 vector 写坏了。

下面再来看看 std::sort 都干了些啥？

std::sort 排序思想

当元素的数量超过 _S_threshold(16) 的时候，采用QuickSort 的方式;
- 为了避免递归调用 __introsort_loop 层数过深，采用 HeapSort 的方式
- __depth_limit 由 std::__lg(__last - __first) * 2 计算而来
最后采用 InsertSort 来实现。

// /usr/include/c++/9/bits/stl_algo.h
template <typename _RandomAccessIterator, typename _Compare>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    // ...
    std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}

template <typename _RandomAccessIterator, typename _Compare>
inline void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    if (__first != __last)
    {
        // 首先调用__introsort_loop 进行内部排序-快速排序、堆排序，完成局部有序
        std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2, __comp);
        // 最后调用插入排序-完全有序
        std::__final_insertion_sort(__first, __last, __comp);
    }
}

// 其中的 std::__lg(__n)  控制分割恶化； 找出 2^k <= n, 如： n=100 时, k=6; n=10,k=3
size lg(size n)
{
    size k = 0;
    for (k = 0; n > 1; n >>= 1) ++k;
    return k;
}

QuickSort

排序思想：将待排序的数据元素序列中选取一个数据元素为基准，通过一趟扫描把待排序的元素分成两个部分，一部分元素关键字都小于或等于基准元素关键字，而另一部分元素关键字都大于或等于基准元素关键字。对各部分数据再进行不断的划分，直至整个序列都有序为止

1）选中待排序列中的第一个元素为基准，复制到 r[0],然后将该位置置空。设置两个指针， low-指向第一个数据元素， high-指向最后一个元素
2）从后向前扫描，若 r[high] 大于或等于基准关键字，则 high 向前移动一个位置。直到 r[high] 小于基准关键字，此时 r[high] 与 r[low0] 交换
3）从前向后扫描，若 r[low] 小于或等于基准关键字，则 low 向后移动一个位置。直到 r[low ] 大于于基准关键字，此时 r[low] 与 r[high] 交换
4）一直重复 2）和 3），直到 low == high 时，令 r[low] = [0], 以 r[low] 为基准将待排序划分为前后两个序列
5）重复 2）3）4），通过不断的划分，一直到各部分只有一个数据。整个序列排序完成

quick_sort.png

空间复杂度：最好- O(log2N), 最坏- O(N)

时间复杂度：平均复杂度- O(NLog2N) O(n²)

稳定性：不稳定

__introsort_loop

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Size, typename _Compare>
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
{
    while (__last - __first > int(_S_threshold))
    {
        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;
    }
}

/// This is a helper function...
template <typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    // 先找到中间位置，然后取三个位置的中值赋给__first
    _RandomAccessIterator __mid = __first + (__last - __first) / 2;
    // 然后取三个位置的中值赋给__first
    std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, __comp);
    // 对 __first, __last 进行分割，并返回分割点__cut, 使 [__first, __cut] 中间的元素不大于pivot, [__cut, last] 中间的元素不小于__cut
    return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}


/// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template <typename _Iterator, typename _Compare>
void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
{ // 此函数希望在 a, b, c 三个数中找到一个中值，并放在result中
    if (__comp(__a, __b))
    {
        if (__comp(__b, __c))
            std::iter_swap(__result, __b);    // a < b < c
        else if (__comp(__a, __c))
            std::iter_swap(__result, __c);    // a < c < b
        else
            std::iter_swap(__result, __a);    // c < a < b
    }
    else if (__comp(__a, __c))
        std::iter_swap(__result, __a);    // b <= a < c
    else if (__comp(__b, __c))
        std::iter_swap(__result, __c);    // b <= c <= a
    else
        std::iter_swap(__result, __b);    // c <= b <= a
}

/// This is a helper function...
template <typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
{
    // 对 __first, __last 进行分割，并返回分割点__cut, 使 [__first, __cut] 中间的元素不大于pivot, [__cut, last] 中间的元素不小于__cut
    while (true)
    {
        while (__comp(__first, __pivot))  // __first < __pivot 当 __first >= __pivot 跳出循环
            ++__first;
        --__last;
        while (__comp(__pivot, __last))       // __pivot <  __last 当 __pivot >=  __last 跳出循环
            --__last;
        if (!(__first < __last))          // __first >= __last 表示 first 和 last 相遇了，结束循环
            return __first;                   // 返回分割点的位置
        std::iter_swap(__first, __last);   // 不满足分割要求，交换大小值， 此时：__first >= __pivot >= __last
        ++__first;
    }
}

__unguarded 前缀的函数表示 函数没有越界检测

HeapSort

建堆过程--大顶堆

将待排序的数据构成一课完全二叉树，从最后一个非叶子节点 N/2 开始，检查该节点是否满足大顶堆要求
- r[i] 的关键字是否大于等于其左右孩子的关键字的值，若不满足，则将 r[i] 与 r[2i] 、 r[2i+1] 中的较大者交换
采用以上方式继续调整其他非叶子节点。如果与 r[i] 交换的时非叶子节点，交换后可能不符合堆的定义，还需要对与 r[i]交换的孩子节点继续调整，使得该节点为根的完全二叉树仍然满足大顶堆的要求
继续重复以上步骤，直到对根节点调整完成

heapSort.gif

堆排序

将堆顶元素 r[1] 与最后一个节点 r[n] 交换
输出该叶子节点对应的数据元素并使其离堆
将序列按找建堆的方法调整为大顶堆
重复以上步骤，直到所有数元素有序输出

时间复杂度：平均时间复杂度 O(nLog2N)

空间复杂度：O(1) 仅仅需要提供一个供交换的辅助存储空间

稳定性：不稳定

__partial_sort

template <typename _RandomAccessIterator, typename _Compare>
inline void __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
{
    // 建堆
    std::__heap_select(__first, __middle, __last, __comp);
    // 排序
    std::__sort_heap(__first, __middle, __comp);
}

/// This is a helper function for the sort routines.
template <typename _RandomAccessIterator, typename _Compare>
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
{
    std::__make_heap(__first, __middle, __comp);
    for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
        if (__comp(__i, __first))
            std::__pop_heap(__first, __middle, __i, __comp);
}

InsertSort

插入排序基本思路：将待排序的数据元素插入到已经排好的有序表中，得到一个新的有序表

1）将第1个数据元素看作一个已排好的有序表

2）将第 i (2 <= i <=n) 个数据元素关键字 Ki 一次与前面数据元素的关键字进行比较，将所有关键字大与 Ki 的数据元素一次后移一个位置，直到某个数据元素 Kj 的关键字小于或等于Ki，然后将第i个数据元素插入到关键 Kj 元素后面，完成第 i 个数据元素的插入

3）经过n - 1 次插入操作后，所有元素数据构成一个关键字有序的序列

insertionSort.gif

空间复杂度：O（1）

时间复杂度 O(n^2)

稳定性：稳定

__final_insertion_sort

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    // 数据量超过 _S_threshold(16) 
    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);
}

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    if (__first == __last)
        return;

    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    {
        if (__comp(__i, __first))
        {   // 如果 *i < *first, 则将 [first, i] 区间的元素向后一定一个位置，然后将 i 位置的元素移动到first
            typename iterator_traits<_RandomAccessIterator>::value_type __val = _GLIBCXX_MOVE(*__i);
            _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
            *__first = _GLIBCXX_MOVE(__val);
        }
        else
        {
            // 如果 *i >= *first 则需要在(first, i) 区间找合适的位置插入
            std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
        }
    }
}

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
inline void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
        std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
}

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
    typename iterator_traits<_RandomAccessIterator>::value_type __val  = _GLIBCXX_MOVE(*__last);
    _RandomAccessIterator                                       __next = __last;
    --__next;
    while (__comp(__val, __next))
    {
        *__last = _GLIBCXX_MOVE(*__next);   // 将当前位置的数值后移一位， 然后next 一直前移
        __last  = __next;
        --__next;
    }
    *__last = _GLIBCXX_MOVE(__val); // 此时所有的元素均已经完成了前移，此时的 last 就是合适的位置
}

不稳定性

struct Entry
{
    Entry(uint32_t id) : user_id(id) {}

    uint32_t user_id = 0;
    uint32_t score   = 0;
};

bool cmp(const Entry& lhs, const Entry& rhs)
{
    return lhs.score > rhs.score;
}

void print_ele(const std::vector<Entry>& vec)
{
    std::stringstream oss;
    for (const auto& item : vec)
    {
        oss << "(" << item.user_id << "-" << item.score << ")";
    }
    std::cout << "element: " << oss.str() << std::endl;
}

int main()
{
    std::vector<Entry> vec;

    for (uint32_t idx = 0; idx < 20; idx++)
    {
        Entry entry(idx);
        entry.score = 1000;
        vec.emplace_back(std::move(entry));
    }

    vec[5].score = 111111;
    vec[6].score = 111111;
    print_ele(vec);
    std::sort(vec.begin(), vec.end(), cmp);
    print_ele(vec);
    std::sort(vec.begin(), vec.end(), cmp);
    print_ele(vec);
    return 0;
}

/*
[cn@build] ./sort/sort
element: (0-1000)(1-1000)(2-1000)(3-1000)(4-1000)(5-111111)(6-111111)(7-1000)(8-1000)(9-1000)(10-1000)(11-1000)(12-1000)(13-1000)(14-1000)(15-1000)(16-1000)(17-1000)(18-1000)(19-1000)
element: (5-111111)(6-111111)(10-1000)(19-1000)(18-1000)(17-1000)(16-1000)(15-1000)(14-1000)(13-1000)(12-1000)(11-1000)(0-1000)(9-1000)(8-1000)(7-1000)(4-1000)(3-1000)(2-1000)(1-1000)
element: (6-111111)(5-111111)(1-1000)(2-1000)(3-1000)(4-1000)(7-1000)(8-1000)(9-1000)(0-1000)(11-1000)(12-1000)(13-1000)(14-1000)(15-1000)(16-1000)(17-1000)(18-1000)(19-1000)(10-1000)
*/

解决方案

// 将排序准则优化
 bool cmp(const Entry& lhs, const Entry& rhs)
 {
     if (lhs.score != rhs.score)
         return lhs.score > rhs.score;
     return lhs.user_id < rhs.user_id;
 }

排序准则

---摘自《C++标准库》7.7 
- 1、必须是非对称的
    对operator < 而言，如果 x < y 为true，那么 y < x 为false;        
    对判断式(predicate) op() 而言, 如果op(x, y) 为true， 那么op(y, x) 为false。

- 2、必须是可传递性的
    对operator < 而言，如果 x < y 为true 且 y < z 为true， 那么 x < z 为true
    对判断式(predicate) op() 而言, 如果op(x, y) 为true 且 op(y, z) 为true， 那么 op(x, z) 为true

- 3、必须自反的
    对operator < 而言，x < x 永远为false;  
    对判断式(predicate) op() 而言, op(x, x) 永远为false。

- 4、必须有等效传递性
    如果 a 等于 b 且 b 等于 c，那么a必然等于 c
    对操作符 <, 若 !(a < b) && !(b < a)为true且 !(b < c) && !(c < b) 为true，那么!(a < c) && !(a < b) 也为true
    对于判断是 op(), 如果op(a,b)、op(b,a)、op(b,c)和op(c,b) 都为false， 那么op(a,c)、op(c,a)也为false

这就意味着：必须区分less 和equal， 一个像operator <= 这样的准则并不满足条件

std::sort 宕机源码分析

std::sort 排序思想

QuickSort

__introsort_loop

HeapSort

建堆过程--大顶堆

堆排序

__partial_sort

InsertSort

__final_insertion_sort

不稳定性

解决方案

排序准则

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读