STL源码剖析(算法)

STL中算法是基于迭代器来实现的。

有了容器中迭代器的实现(对operator*、operator++等的重载)，STL中大部分算法实现就显得很简单了。

先看一例关于find算法的实现:

 template <class InputIterator, class T>

 InputIterator find(InputIterator first, InputIterator last, const T& value) {

     // 直接利用iterator中的operator++、operator*、operator!=实现

     // 默认使用class T的operator!=

     while (first != last && *first != value) ++first;

         return first;

 }

 template <class InputIterator, class Predicate>

 InputIterator find_if(InputIterator first, InputIterator last,

                       Predicate pred) {

     // 能接受一个仿函数 用来指定find的条件

     while (first != last && !pred(*first)) ++first;

         return first;

 }

其它的基本算法实现都差不多，它们一般只是执行单纯的数据移动、线性查找、计数、循环遍历等操作。

比较复杂的算法一般都关于排列、排序之类的，这次只要说说SGI STL中sort()的实现。

SGI STL中的sort()

SGI STL中的排序算法混合了quick sort、heap sort、insert sort三种排序算法。

总体上用的是quick sort，分割到一定深度(2^k < = n)的时候会使用heap sort，

在分割区域元素大小小于阀值(16)时最后执行的是insert sort。

下面是sort()的的基本框架:

 template <class RandomAccessIterator>

 inline void sort(RandomAccessIterator first, RandomAccessIterator last) {

     if (first != last) {

         // 使用quick sort、heap sort排序 直到所有分割区域元素大小都小于阀值 __stl_threshold = 16

         __introsort_loop(first, last, value_type(first), __lg(last - first) * );

        // 最后对其分割区域都执行一次insert sort

         __final_insertion_sort(first, last);

     }

 }

 // 阀值k满足2^k <= n

 template <class Size>

 inline Size __lg(Size n) {

     Size k;

     for (k = ; n > ; n >>= ) ++k;

     return k;

 }

然后看看introsort_loop的实现:

 template <class RandomAccessIterator, class T, class Size>

 void __introsort_loop(RandomAccessIterator first,

                       RandomAccessIterator last, T*,

                       Size depth_limit) {

     while (last - first > __stl_threshold) { // 元素足够少  返回由insert sort处理

         if (depth_limit == ) {  // 分割恶化 采用heap_sort

             partial_sort(first, last, last);  // 实现为heap_sort

             return;

         }

         // 深度

         --depth_limit;

         // key为first middle last的中值

         RandomAccessIterator cut = __unguarded_partition

            (first, last, T(__median(*first, *(first + (last - first)/),

                                *(last - ))));

         // 递归的处理[cut, last)

         __introsort_loop(cut, last, value_type(first), depth_limit);

         // 返回while 继续处理[first, cut)

         last = cut;

     }

 }

巴特西

STL源码剖析(算法)

最新文章

热门文章