STL算法之sort
STL算的中的sort接受两个RandomAcceddIterators(随机存取迭代器)。STL的所有关系型容器都拥有自动排序功能(底层采用RB-tree),所有不需要用到sort算法。至于序列式容器stack,queue和priority-queue都有特别的出入口,不允许用户对元素排序。剩下的vector、deque和list,前两者的迭代器满足要求适合用sort算法。而list的迭代器属于BidirectionalIterators,不适合sort算法。如果要对list排序,可以使用它自己通过的成员函数sort()算法。
SGI STL的sort算法,数据量大时采用QuickSort,分段递归排序。一旦分段后的数据量小于某个门槛,为避免QuickSort的递归调用带来过大的额外负荷,就改用Insertion Sort。如果递归层次过深,还会改用Heap Sort。SGI将使用快排与插入排序的分割线设为16。
RW STL的sort算法,数据大的时候用QuickSort,小的时候用Insertion Sort。
下面是SGI STL sort的源码:
// 版本一
// 千萬注意:sort()只適用於 RandomAccessIterator
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first != last) {
__introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
__final_insertion_sort(first, last);
}
}
// 版本一
// 注意,本函式內的許多迭代器運算動作,都只適用於RandomAccess Iterators.
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
RandomAccessIterator last, T*,
Size depth_limit) {
// 以下,__stl_threshold 是個全域常數,稍早定義為 const int 16。
while (last - first > __stl_threshold) {
if (depth_limit == 0) { // 至此,切割惡化
partial_sort(first, last, last); // 改用 heapsort
return;
}
--depth_limit;
// 以下是 median-of-three partition,選擇一個夠好的樞軸並決定切割點。
// 切割點將落在迭代器 cut 身上。
RandomAccessIterator cut = __unguarded_partition
(first, last, T(__median(*first, *(first + (last - first)/2),
*(last - 1))));
// 對右半段遞迴進行 sort.
__introsort_loop(cut, last, value_type(first), depth_limit);
last = cut;
// 現在回到while 迴圈,準備對左半段遞迴進行 sort.
// 這種寫法可讀性較差,效率並沒有比較好。
// RW STL 採用一般教科書寫法(直觀地對左半段和右半段遞迴),較易閱讀。
}
}
template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
if (last - first > __stl_threshold) {
__insertion_sort(first, first + __stl_threshold);
__unguarded_insertion_sort(first + __stl_threshold, last);
}
else
__insertion_sort(first, last);
}
template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first == last) return;
for (RandomAccessIterator i = first + 1; i != last; ++i) // 外迴圈
__linear_insert(first, i, value_type(first)); // first,i形成一個子範圍
}
// 版本一
template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
RandomAccessIterator last, T*) {
T value = *last; // 記錄尾元素
if (value < *first) { // 尾比頭還小(那就別一個個比較了,一次做完…)
copy_backward(first, last, last + 1); // 將整個範圍向右遞移一個位置
*first = value; // 令頭元素等於原先的尾元素值
}
else
__unguarded_linear_insert(last, value);
}
// 版本一
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
RandomAccessIterator next = last;
--next;
// insertion sort 的內迴圈
// 注意,一旦不出現逆轉對(inversion),迴圈就可以結束了。
while (value < *next) { // 逆轉對(inversion)存在
*last = *next; // 轉正
last = next; // 調整迭代器
--next; // 前進一個位置
}
*last = value;
}
// 版本一
template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
__unguarded_insertion_sort_aux(first, last, value_type(first));
}
template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
RandomAccessIterator last, T*) {
for (RandomAccessIterator i = first; i != last; ++i)
__unguarded_linear_insert(i, T(*i));
}
分享到:
相关推荐
简单举例普通数组、vector、对象排序 ,列举了默认排序、自定义排序,在自定义排序函数注释部分 点明了容易出问题的地方
对于C++的STL的双向链表,排序算法有的模板并没有实现,因此给出来,大家参考。
STL将算法库分成4组: 1)非修改式序列操作,find()、for_each()等; 2)修改式序列操作,transform()、random_shuffle()、copy等; 3)排序和相关操作,sort()等; 4)通用数字运算。 ........
为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...
在STL的泛型算法中有4类基本的算法: 1)变序型队列算法: 可以改变容器内的数据; 2)非变序型队列算法:处理容器内的数据而不改变他们; 3)排序值算法:包涵对容器中的值进行排序和合并的算法,还有二叉搜索算法 ,4)...
为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...
第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 21.4 邻近查找容器元素adjacent_find 287 21.5 范围查找...
为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...
非常实用的STL容器讲解学习,内容全,讲解详细 包括Vector、Vector、String、Deque、sort、set、map,绝对有用!!
STL(Standard TemplateLibrary),即标准模板库,从根本上说,STL是一些“容器”的集合,这些...算法(Algorithms):各种常用算法,如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templat
为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...
例如,由于STL的sort()函数是完全通用的,你可以用它来操作几乎任何数据集合,包括链表,容器和数组; STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多...
6.1.5 stl算法的一般形式 292 6.2 算法的泛化过程 294 6.3 数值算法 [stl_numeric.h] 298 6.3.1 运用实例 298 6.3.2 accumulate 299 6.3.3 adjacent_difference 300 6.3.4 inner_product 301 6.3.5 partial_...
STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念,但这种分离确实使得STL变得非常通用。例如,由于STL的sort()函数是完全通用的,你可以用它来操作几乎任何数据集合,包括链表,容器和数组。
STL
全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)
6.1.5 STL算法的一般形式 292 6.2 算法的泛化过程 294 6.3 数值算法 [stl_numeric.h] 298 6.3.1 运用实例 298 6.3.2 accumulate 299 6.3.3 adjacent_difference 300 6.3.4 inner_product 301 6.3.5 partial_...
STL介绍 3 1、STL简介 3 2、算法 3 3、容器 3 4、迭代器 4 5、使用注意 4 一、stack 堆栈 5 成员函数: 5 实例程序: 5 二、queue 队列 6 成员函数: 6 实例程序: 6 三、Priority Queues 优先队列 7 成员函数: 7 ...
stl库在C++的使用,以vector为例子建立的一段代码,使用了sort(),find()的泛型算法,以及使用了random中的概率分布
例如find可以用来在容器中查找某特定值的元素,for_each可以用来将函数应用到容器元素之上,sort用于对容器中的元素排序。 8;迭代器(iterators)STL重要组成部分,每个容器都有自己的迭代器,只有容器才可以进行...