使用标准库std::sort函数进行排序

std的sort方法接受两个迭代器begin和end。通过迭代器来抽象元素的访问,隐藏内部实现。

这是一个简单的例子:

std::list<int> list {
    0,
    4,
    2,
    1,
    3,
};

std::sort(list.begin(), list.end());

结果就是list被排序了,至于使用了什么排序算法,我们并不需要关心。实际上标准库会通过元素的数量来决定使用什么算法,基于Introspective Sorting(内省式排序)。
它是一种混合式的排序算法:

  • 在数据量很大时采用正常的快速排序,此时效率为O(logN)。

  • 一旦分段后的数据量小于某个阈值,就改用插入排序,因为此时这个分段是基本有序的,这时效率可达O(N)。

  • 在递归过程中,如果递归层次过深,分割行为有恶化倾向时,它能够自动侦测出来,使用堆排序来处理,在此情况下,使其效率维持在堆排序的O(N logN),但这又比一开始使用堆排序好。

默认情况下排序是升序排序,既结果从小到大,我们可以通过使用std::equal_to、std::not_equal_to、std::greater、std::less、std::greater_equal和std::less_equal来控制排序。

以上是通过标准库内置的一些方式来控制排序,且适用于元素已实现了自定义比较(Compare)的要求。

比较 (Compare) 是一些标准库设施针对用户提供的函数对象类型所期待的一组要求。

对满足比较 (Compare) 的类型的对象运用函数调用操作的返回值,当按语境转换成 bool 时,若此类型所引入的严格弱序关系中,该调用的第一实参先于第二实参,则生成 true,否则生成 false。

与任何二元谓词 (BinaryPredicate) 相同,不允许该表达式的求值通过解引用的迭代器调用非 const 函数。

用人话来说就是,Compare必须提供出对比结果。

看一个例子:

struct Test {
    int i;
}

std::list<Test> list {
    new Test(2),
    new Test(1),
    new Test(4),
    new Test(3),
    new Test(5),
};

std::sort(list.begin(), list.end(), [=] (const Test& test1, const Test& test2) -> bool {
    return test1.i < test2.i;
});

这个例子提供了一个Compare,通过lambda来提供自定义的对比函数,返回值必须是bool,否则将不满足对比函数的要求。

通过以上三种方式可以看出,标准库的sort函数可以很方便的为使用者提供标准对比和自定义对比。如果元素自己已实现operator<,则只需要使用标准库内置的对比函数即可,但是大部分情况其实并不会涉及到元素的排序,仅在临时情况下需要列表有序,所以我个人倾向于通过lambda提供Compare函数来完成列表的排序。

std::sort
知无涯之std::sort源码剖析

发表评论

电子邮件地址不会被公开。 必填项已用*标注