std::sort的坑

std::sort的使用姿势不对会导致程序 core 掉

std::sort默认是升序排序, 我们也可以自定义比较函数来控制升序还是降序, 或者使用less<T> / greater<T>, 而且使用 sort 排序的区间必须是可以使用随机迭代器随机访问的, 例如 map set 这类无序的容器, 就不能使用sort, 而且排序中的元素互换是通过内存的 copy, 所以容器中存储的元素太过于庞大时, 代价变高, 像std::list也不能使用, 内存的 copy 会改变其next指针

(吐槽: 一直觉得这个随机的翻译不太好有歧义, Random Access的这个 random 翻译出任意的意思不是更容易理解么

std::sort 是一个在绝大数情况下都能达到极限性能的排序算法
他在元素数量和递归深度上都有优化, 当递归深度过深时会使用堆排序, 而当元素数量小于限定值时, 会使用插入排序

std::sort 在内部定义一个 enum _S_threshold = 16(不同环境可能不同), 当容器元素数量小于 Sthreshold, 使用的插入排序, 大于该值时使用快速排序

(根据快排的特性, 当分段值小于 Sthreshold 时, 也会改用插入排序)

而另外一个变量 __depth_limit控制了递归深度, 每次递归该值自减, 当其值为 0 时, 认为已经达到了一个很深的递归深度, 比较危险了, 开始使用堆排序

坑点

当我们使用自定义的比较函数的时候, 就需要注意了, 当比较两个相等的值时, 永远要返回false

– Effective STL

因为在 sort 进行快排的过程中, 会认为容器中一定会有两个元素的比较值返回false, 而当两元素比较返回true的时候就会继续快排的过程, 继续扫描容器, 将小于基准数的元素放一边, 大于基准数的放一边, 而我们自定义的比较函数如果没有返回 false的情况, 就会一直扫描, 导致越界

0%