Skip to Main Content
C++程序设计语言(第4部分:标准库)(原书第4版)
book

C++程序设计语言(第4部分:标准库)(原书第4版)

by 本贾尼 斯特劳斯特鲁普
August 2021
Intermediate to advanced content levelIntermediate to advanced
450 pages
6h 57m
Chinese
Pearson
Content preview from C++程序设计语言(第4部分:标准库)(原书第4版)

32.6 排序和搜索

排序和已排序序列中的搜索是非常基础的操作,而程序员对这两个操作的需求可能有很大的差异。默认的比较操作是<运算符,值a和b的相等性通过!(a<b)&&!(b<a)来判定,而不是使用运算符==。

除了“普通排序”外,还有其他很多版本:

sort()算法要求随机访问迭代器(见33.1.2节)。

对is_sorted_until(),不要理会它的名字,它其实返回一个迭代器,而不是一个bool。

标准库list(见31.3节)并不提供随机访问迭代器,因此只能用特殊的list操作(见31.4.2节)来排序list,或者先将list的元素拷贝到一个vector中,排序这个vector,然后再将元素拷回list:

基础的sort()很高效(平均时间复杂性N*log(N))。如果需要一个稳定排序算法,可使用stable_sort(),这是一个N*log(N)*log(N)时间的算法,当系统有足够的额外内存时,可缩短为N*log(N)。函数get_temporary_buffer()可以用来获取额外内存(见34.6节)。stable_sort()可以保证相等元素的相对顺序,sort()则不能保证。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Java并发编程实战

Java并发编程实战

Brian Goetz, Tim Peierls
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普
Go程序设计语言

Go程序设计语言

艾伦A. A.多诺万, 布莱恩W. 柯尼汉
可编程网络自动化

可编程网络自动化

Jason Edelman, Scott S. Lowe, Matt Oswalt

Publisher Resources

ISBN: 9787111544395