`
xitonga
  • 浏览: 579608 次
文章分类
社区版块
存档分类
最新评论

STL算法之sort

 
阅读更多

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));
}


分享到:
评论

相关推荐

    STL 1.算法之1.1Sort用法 及注意事项

    简单举例普通数组、vector、对象排序 ,列举了默认排序、自定义排序,在自定义排序函数注释部分 点明了容易出问题的地方

    STL双向链表list的sort

    对于C++的STL的双向链表,排序算法有的模板并没有实现,因此给出来,大家参考。

    STL算法详解与汇总

    STL将算法库分成4组: 1)非修改式序列操作,find()、for_each()等; 2)修改式序列操作,transform()、random_shuffle()、copy等; 3)排序和相关操作,sort()等; 4)通用数字运算。 ........

    30分钟掌握stl

    为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...

    stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)

    在STL的泛型算法中有4类基本的算法: 1)变序型队列算法: 可以改变容器内的数据; 2)非变序型队列算法:处理容器内的数据而不改变他们; 3)排序值算法:包涵对容器中的值进行排序和合并的算法,还有二叉搜索算法 ,4)...

    30分钟学会STL.doc

    为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...

    C++ STL开发技术导引(第5章)

    第四篇 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轻松入门 很基础性的文章(译文)

    为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...

    STL容器 内容全,讲解详细 包括Vector、Deque、sort、set、map等

    非常实用的STL容器讲解学习,内容全,讲解详细 包括Vector、Vector、String、Deque、sort、set、map,绝对有用!!

    C++STL讲解 PPT版本

    STL(Standard TemplateLibrary),即标准模板库,从根本上说,STL是一些“容器”的集合,这些...算法(Algorithms):各种常用算法,如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templat

    三十分钟掌握STL doc文档

    为了和其他组件相区别,在本书中STL算法以后接一对圆括弧的方式表示,例如sort()。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个...

    C++标准的STL介绍

    例如,由于STL的sort()函数是完全通用的,你可以用它来操作几乎任何数据集合,包括链表,容器和数组; STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多...

    STL源码剖析.pdg

    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变得非常通用。例如,由于STL的sort()函数是完全通用的,你可以用它来操作几乎任何数据集合,包括链表,容器和数组。

    STL应用——第一天课程sort.pptx

    STL

    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介绍 3 1、STL简介 3 2、算法 3 3、容器 3 4、迭代器 4 5、使用注意 4 一、stack 堆栈 5 成员函数: 5 实例程序: 5 二、queue 队列 6 成员函数: 6 实例程序: 6 三、Priority Queues 优先队列 7 成员函数: 7 ...

    C++stl的运用

    stl库在C++的使用,以vector为例子建立的一段代码,使用了sort(),find()的泛型算法,以及使用了random中的概率分布

    STL入门快速入门教程-----学习C++

    例如find可以用来在容器中查找某特定值的元素,for_each可以用来将函数应用到容器元素之上,sort用于对容器中的元素排序。 8;迭代器(iterators)STL重要组成部分,每个容器都有自己的迭代器,只有容器才可以进行...

Global site tag (gtag.js) - Google Analytics