副标题#e#
0 媒介: STL,为什么你必需把握
对付措施员来说,数据布局是必修的一门课。从查找到排序,从链表到二叉树,险些所有的算法和道理都需要领略,领略不了也要死记硬背下来。幸运的是这些理论都已经较量成熟,算法也根基牢靠下来,不需要你再去花操心思去思量其算法道理,也不消再去验证其精确性。不外,等你开始应用计较机语言来事情的时候,你会发明,面临差异的需求你需要一次又一次去用代码反复实现这些已经成熟的算法,并且会一次又一次陷入一些由于本身疏忽而发生的bug中。这时,你想找一种东西,已经帮你实现这些成果,你想怎么用就怎么用,同时不影响机能。你需要的就是STL, 尺度模板库!
西方有句谚语:不要反复发现轮子!
STL险些封装了所有的数据布局中的算法,从链表到行列,从向量到仓库,对hash到二叉树,从搜索到排序,从增加到删除……可以说,假如你领略了STL,你会发明你已不消拘泥于算法自己,从而站在巨人的肩膀上去思量更高级的应用。
排序是最遍及的算法之一,本文具体先容了STL中差异排序算法的用法和区别。
1 STL提供的Sort 算法
C++之所以获得这么多人的喜欢,是因为它既具有面向工具的观念,又保持了C语言高效的特点。STL 排序算法同样需要保持高效。因此,对付差异的需求,STL提供的差异的函数,差异的函数,实现的算法又不尽沟通。
1.1 所有sort算法先容
所有的sort算法的参数都需要输入一个范畴,[begin, end)。这里利用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator), 也就是说可以随时机见的迭代器,如:it+n什么的。(partition 和stable_partition 除外)
假如你需要本身界说较量函数,你可以把你界说好的仿函数(functor)作为参数传入。每种算法都支持传入较量函数。以下是所有STL sort算法函数的名字列表:
| 函数名 | 成果描写 |
| sort | 对给定区间所有元素举办排序 |
| stable_sort | 对给定区间所有元素举办不变排序 |
| partial_sort | 对给定区间所有元素部门排序 |
| partial_sort_copy | 对给定区间复制并排序 |
| nth_element | 找出给定区间的某个位置对应的元素 |
| is_sorted | 判定一个区间是否已经排好序 |
| partition | 使得切合某个条件的元素放在前面 |
| stable_partition | 相对不变的使得切合某个条件的元素放在前面 |
个中nth_element 是最不易领略的,实际上,这个函数是用来找出第几个。譬喻:找出包括7个元素的数组中排在中间谁人数的值,此时,我大概不体贴前面,也不体贴后头,我只体贴排在第四位的元素值是几多。
#p#副标题#e#
1.2 sort 中的较量函数
当你需要凭据某种特定方法举办排序时,你需要给sort指定较量函数,不然措施会自动提供应你一个较量函数。
vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于挪用
sort(vect.begin(), vect.end(), less<int>() );
上述例子中系统本身为sort提供了less仿函数。在STL中还提供了其他仿函数,以下是仿函数列表:
| 名称 | 成果描写 |
| equal_to | 相等 |
| not_equal_to | 不相等 |
| less | 小于 |
| greater | 大于 |
| less_equal | 小于便是 |
| greater_equal | 大于便是 |
需要留意的是,这些函数不是都能合用于你的sort算法,如何选择,抉择于你的应用。别的,不能直接写入仿函数的名字,而是要写其重载的()函数:
less<int>()
greater<int>()
当你的容器中元素时一些尺度范例(int float char)可能string时,你可以直接利用这些函数模板。但假如你时本身界说的范例可能你需要凭据其他方法排序,你可以有两种要领来到达结果:一种是本身写较量函数。另一种是重载范例的'<‘操纵赋。
#p#分页标题#e#
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
class myclass {
public:
myclass(int a, int b):first(a), second(b){}
int first;
int second;
bool operator < (const myclass &m)const {
return first < m.first;
}
};
bool less_second(const myclass & m1, const myclass & m2) {
return m1.second < m2.second;
}
int main() {
vector< myclass > vect;
for(int i = 0 ; i < 10 ; i ++){
myclass my(10-i, i*3);
vect.push_back(my);
}
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
sort(vect.begin(), vect.end());
cout<<"after sorted by first:"<<endl;
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
cout<<"after sorted by second:"<<endl;
sort(vect.begin(), vect.end(), less_second);
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
return 0 ;
}
知道其输出功效是什么了吧:
(10,0)1.3 sort 的不变性
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
after sorted by first:
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
after sorted by second:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
你发明有sort和stable_sort,尚有 partition 和stable_partition, 感想奇怪吧。个中的区别是,带有stable的函数可担保相等元素的原内情对序次在排序后保持稳定。或者你会问,既然相等,你还管他相对位置呢,也分不清楚谁是谁了?这里需要弄清楚一个问题,这里的相等,是指你提供的函数暗示两个元素相等,并不必然是一摸一样的元素。
譬喻,假如你写一个较量函数:
bool less_len(const string &str1, const string &str2)
{
return str1.length() < str2.length();
}
此时,"apple" 和 "winter" 就是相等的,假如在"apple" 呈此刻"winter"前面,用带stable的函数排序后,他们的序次必然稳定,假如你利用的是不带"stable"的函数排序,那么排序完后,"Winter"有大概在"apple"的前面。
1.4 全排序
全排序即把所给定范畴所有的元素凭据巨细干系顺序分列。用于全排序的函数有
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
在第1,3种形式中,sort 和 stable_sort都没有指定较量函数,系统会默认利用operator< 对区间[first,last)内的所有元素举办排序, 因此,假如你利用的范例义军已经重载了operator<函数,那么你可以省心了。第2, 4种形式,你可以随意指定较量函数,应用更为机动一些。来看看实际应用:
班上有10个学生,我想知道他们的后果排名。
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;
class student{
public:
student(const string &a, int b):name(a), score(b){}
string name;
int score;
bool operator < (const student &m)const {
return score< m.score;
}
};
int main() {
vector< student> vect;
student st1("Tom", 74);
vect.push_back(st1);
st1.name="Jimy";
st1.score=56;
vect.push_back(st1);
st1.name="Mary";
st1.score=92;
vect.push_back(st1);
st1.name="Jessy";
st1.score=85;
vect.push_back(st1);
st1.name="Jone";
st1.score=56;
vect.push_back(st1);
st1.name="Bush";
st1.score=52;
vect.push_back(st1);
st1.name="Winter";
st1.score=77;
vect.push_back(st1);
st1.name="Andyer";
st1.score=63;
vect.push_back(st1);
st1.name="Lily";
st1.score=76;
vect.push_back(st1);
st1.name="Maryia";
st1.score=89;
vect.push_back(st1);
cout<<"------before sort..."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
stable_sort(vect.begin(), vect.end(),less<student>());
cout <<"-----after sort ...."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
return 0 ;
}
其输出是:
#p#分页标题#e#
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Lily: 76
Winter: 77
Jessy: 85
Maryia: 89
Mary: 92
sort回收的是成熟的"快速排序算法"(今朝大部门STL版本已经不是回收简朴的快速排序,而是团结内插排序算法)。注1,可以担保很好的平均机能、巨大度为n*log(n),由于纯真的快速排序在理论上有最差的环境,机能很低,其算法巨大度为n*n,但今朝大部门的STL版本都已经在这方面做了优化,因此你可以安心利用。stable_sort回收的是"合并排序",分配足够内存是,其算法巨大度为n*log(n), 不然其巨大度为n*log(n)*log(n),其利益是会保持相等元素之间的相对位置在排序前后保持一致。
1.5 局部排序
局部排序其实是为了淘汰不须要的操纵而提供的排序方法。其函数原型为:
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator,
class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
领略了sort 和stable_sort后,再来领略partial_sort 就较量容易了。先看看其用途: 班上有10个学生,我想知道分数最低的5名是哪些人。假如没有partial_sort,你就需要用sort把所有人排好序,然后再取前5个。此刻你只需要对分数最低5名排序,把上面的措施做如下修改:
stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());
输出功效为:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Lily: 76
Maryia: 89
这样的长处知道了吗?当数据量小的时候大概看不出优势,假如是100万学生,我想找分数最少的5小我私家……
partial_sort回收的堆排序(heapsort),它在任何环境下的巨大度都是n*log(n). 假如你但愿用partial_sort来实现全排序,你只要让middle=last就可以了。
#p#分页标题#e#
partial_sort_copy其实是copy和partial_sort的组合。被排序(被复制)的数量是[first, last)和[result_first, result_last)中区间较小的谁人。假如[result_first, result_last)区间大于[first, last)区间,那么partial_sort相当于copy和sort的组合。
1.6 nth_element 指定元素排序
nth_element一个容易看懂但表明较量贫苦的排序。用例子说会更利便:
班上有10个学生,我想知道分数排在倒数第4名的学生。
假如要满意上述需求,可以用sort排好序,然后取第4位(因为是由小到大排), 更智慧的伴侣会用partial_sort, 只排前4位,然后获得第4位。其实这是你照旧挥霍,因为前两位你基础没有须要排序,此时,你就需要nth_element:
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);
对付上述实例需求,你只需要按下面要求修改1.4中的措施:
stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());
运行功效为:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jone: 56
Bush: 52
Jimy: 56
Andyer: 63
Jessy: 85
Mary: 92
Winter: 77
Tom: 74
Lily: 76
Maryia: 89
第四个是谁?Andyer,这个晦气的家伙。为什么是begin()+3而不是+4? 我开始写这篇文章的时候也没有在意,厥后在ilovevc 的提醒下,发明白这个问题。begin()是第一个,begin()+1是第二个,… begin()+3虽然就是第四个了。
1.7 partition 和stable_partition
仿佛这两个函数并不是用来排序的,’分类’算法,会越发贴切一些。partition就是把一个区间中的元素凭据某个条件分成两类。其函数原型为:
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);
看看应用吧:班上10个学生,计较所有没有合格(低于60分)的学生。你只需要凭据下面名目替换1.4中的措施:
stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));
其输出功效为:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jimy: 56
Jone: 56
Bush: 52
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
瞥见了吗,Jimy,Jone, Bush(难怪说美国总统较量笨
)都没有合格。并且利用的是stable_partition, 元素之间的相对序次是没有变.
2 Sort 和容器
STL中尺度容器主要vector, list, deque, string, set, multiset, map, multimay, 个中set, multiset, map, multimap都是以树布局的方法存储其元素具体内容请参看:进修STL map, STL set之数据布局基本. 因此在这些容器中,元素一直是有序的。
这些容器的迭代器范例并不是随机型迭代器,因此,上述的那些排序函数,对付这些容器是不行用的。上述sort函数对付下列容器是可用的:
vector
string
deque
假如你本身界说的容器也支持随机型迭代器,那么利用排序算法是没有任何问题的。
#p#分页标题#e#
对付list容器,list自带一个sort成员函数list::sort(). 它和算法函数中的sort差不多,可是list::sort是基于指针的方法排序,也就是说,所有的数据移动和较量都是此用指针的方法实现,因此排序后的迭代器一直保持有效(vector中sort后的迭代器会失效).
3 选择符合的排序函数
为什么要选择符合的排序函数?大概你并不体贴效率(这里的效率指的是措施运行时间), 可能说你的数据量很小, 因此你以为随便用哪个函数都无关紧急。
其实否则,纵然你不体贴效率,假如你选择符合的排序函数,你会让你的代码更容易让人大白,你会让你的代码更有扩充性,逐渐养成一个精采的习惯,很重要吧
。
假如你以前有用过C语言中的qsort, 想知道qsort和他们的较量,那我汇报你,qsort和sort是一样的,因为他们回收的都是快速排序。从效率上看,以下几种sort算法的是一个排序,效率由高到低(耗时由小变大):
partion
stable_partition
nth_element
partial_sort
sort
stable_sort
记得,以前翻译过Effective STL的文章,个中对如何选择排序函数总结的很好:
若需对vector, string, deque, 或 array容器举办全排序,你可选择sort或stable_sort;
若只需对vector, string, deque, 或 array容器中取得top n的元素,部门排序partial_sort是首选.
若对付vector, string, deque, 或array容器,你需要找到第n个位置的元素可能你需要获得top n且不干系top n中的内部顺序,nth_element是最抱负的;
若你需要从尺度序列容器可能array中把满意某个条件可能不满意某个条件的元素分隔,你最好利用partition或stable_partition;
若利用的list容器,你可以直接利用partition和stable_partition算法,你可以利用list::sort取代sort和stable_sort排序。若你需要获得partial_sort或nth_element的排序结果,你必需间接利用。正如上面先容的有几种方法可以选择。
总之记着一句话: 假如你想节省时间,不要走弯路, 也不要走多余的路!
4 小结
接头技能就像个无底洞,常常容易由一点可以引申别的无数个技能点。因此需要从全局的角度来调查问题,就像调查STL中的sort算法一样。其实在STL尚有make_heap, sort_heap等排序算法。本文章没有提到。本文以实例的方法,表明白STL中排序算法的特性,并总结了在实际环境下应如何选择符合的算法。
