Chinaunix首页 | 论坛 | 博客
  • 博客访问: 851356
  • 博文数量: 155
  • 博客积分: 4004
  • 博客等级: 中校
  • 技术积分: 2070
  • 用 户 组: 普通用户
  • 注册时间: 2009-07-19 11:37
文章分类

全部博文(155)

文章存档

2014年(3)

2013年(9)

2012年(28)

2011年(20)

2010年(29)

2009年(66)

我的朋友

分类: C/C++

2013-08-02 11:26:37

摘要:std::sort是C++ STL 中最重要的算法之一,可以与for_each算法相提并论,当我们有排序需要时,可能最先想到的就是它。这个算法是一个接口模板,在内部实现可能会根据不现情况使用不同的算法。在使用形式上存在两种方式,一种是使用小于运算符进行比较,一种使用传入的函数对象(仿函数)进行比较。

目录 []

原型声明

下面是 std::sort 的声明语法:

template <class RandomAccessIterator>
        void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
        void sort ( RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp );


从上面的声明我们可以看出来,sort算法要求迭代器是随机迭代器,并且是可写的。如果迭代器不是随机的,那么排序在理论上将变得非常低效;如果迭代器是不可写,那么将无法进行排序,因为排序要求对迭代器指向的元素进行赋值操作。如此 STL sort 算法要求迭代器是可写的随机迭代器。这一点要求使得我们不能在std::set、std::list 等以结点形式存储的容器里。

此外在理论上,sort 算法接受的比较函数是一个“严格偏序”操作,其中最易被忽略的要求 comp(a,a) 不能真,同时还有其它一些要求。大家可以参考: 对偏序的讨论。

sort 不保证相等元素的相对位置保持不变,可能恰好没有变,也可能恰好变了。

使用示例

学习一个函数的使用示例是最直接与明了的,此处提供两类示例,一类是正确的可以工作的示例,另一类是不正确的或行为未定义的示例。

正确的示例

对一个整数的向量进行排序,第一次使用小于操作排序,第二次使用大于操作排序:

#include
#include
#include

std::vector<int> vec;
vec.push_back(5);
vec.push_back(3);
vec.push_back(4);

//使用小于运算符进行比较
std::sort(vec.begin(), vec.end()); //默认行为就是使用小于运算符
//或者手工指定小于运算符
std::sort(vec.begin(), vec.end(), std::less<int>());

//使用大于运算符进行比较
std::sort(vec.begin(), vec.end(), std::greater<int>());
//或者可以自己定义一个大于比较函数

//自定义的函数
static inline my_greater(int a, int b)
{
        return a>b;
}
std::sort(vec.begin(), vec.end(), my_greater);


行为未定义的示例

对非随机迭代器或使用不恰当的比较操作符都可以引起错误,下面进行展示:

#include
#include
#include


std::list<int> vec;
vec.push_back(5);
vec.push_back(3);
vec.push_back(4);

//这个语句将无法编译,原因是迭代器不是随机的
std::sort(vec.begin(), vec.end());

//这个语句的行为是未定义的,原因是 std::greater_equal(a,a) 为真
std::sort(vec.begin(), vec.end(), std::greater_equal<int>());


小结

std::sort 封装了快速排序算法,但它对参数的有自己的要求,在没有太在意的情况下 std::sort 工作得可能很好,也可能不工作,我需要对它的基本原理有个了解。要知道什么是严格偏序,也要知道什么随机迭代器,同时也要知道 std::sort 不是稳定的排序算法,它不保证“相等”元素的相对位置,使用 std::stable_sort 来保证这一点。

zz:

阅读(1558) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~