Chinaunix首页 | 论坛 | 博客
  • 博客访问: 359381
  • 博文数量: 60
  • 博客积分: 15
  • 博客等级: 民兵
  • 技术积分: 1138
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-20 16:18
个人简介

最多140个字

文章分类

全部博文(60)

文章存档

2016年(1)

2015年(34)

2014年(25)

分类: C/C++

2015-12-13 13:41:13

//sort函数源码:

template 
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
                 _LessThanComparable); if (__first != __last) { //如果待排序序列非空;
    //进行introsort排序,其中__lg函数用于控制最大分割层数;
    __introsort_loop(__first, __last,
                     __VALUE_TYPE(__first),
                     __lg(__last - __first) * 2);
    __final_insertion_sort(__first, __last);//对序列进行插入排序;
  }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

//__lg函数源码:

//找出2^k<=n的最大值k;
template 
inline _Size __lg(_Size __n) {
  _Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

//__introsort_loop函数源码:

const int __stl_threshold = 16; //全局变量;
template 
//_Tp为待排序元素类型, __depth_limit为最多允许分割的层数;
void __introsort_loop(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Tp*,
                      _Size __depth_limit)
{ while (__last - __first > __stl_threshold) {//如果待排序元素个数大于阀值; if (__depth_limit == 0) {//如果允许分割层数为0;
      partial_sort(__first, __last, __last);//对[first,last)进行堆排序; return;
    }
    --__depth_limit;//分割层数减1;
    //__median函数用于选择一个枢轴,然后进行一次分割操作,其中cut为"右半段"的第一个元素;
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1))));
    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);//对"右半段"进行__introsort排序;
    __last = __cut;//继续while循环,对由[first,last)表示的"左半段"进行introsort;
  }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

//__unguarded_paririon函数源码:

template 
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
                                        _RandomAccessIter __last, 
                                        _Tp __pivot) //分割函数;
{ while (true) { while (*__first < __pivot)//如果first指向的元素小于枢轴;
      ++__first;
    --__last; while (__pivot < *__last)//如果枢轴小于last指向的元素;
      --__last; if (!(__first < __last))//如果first和last迭代器交错,first为右半段第一个元素; return __first;
    iter_swap(__first, __last);//firtst和last指向的元素交换;
    ++__first;
  }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

//partial_sort函数源码:

template 
inline void partial_sort(_RandomAccessIter __first,
                         _RandomAccessIter __middle,
                         _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
                 _LessThanComparable);
  __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
}

template 
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
                    _RandomAccessIter __last, _Tp*) {
  make_heap(__first, __middle);//建立大顶堆;
  //分割[middle,last)为[first,last)的"右半段"; for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) 
      __pop_heap(__first, __middle, __i, _Tp(*__i),
                 __DISTANCE_TYPE(__first));
  sort_heap(__first, __middle);//对[first,middle)区间(即左半段)进行堆排序;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

// __final_insertion_sort函数源码:

//进行插入排序;
void __final_insertion_sort(_RandomAccessIter __first, 
                            _RandomAccessIter __last) { if (__last - __first > __stl_threshold) {
    __insertion_sort(__first, __first + __stl_threshold);
    __unguarded_insertion_sort(__first + __stl_threshold, __last);
  } else __insertion_sort(__first, __last);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

//__insertion_sort函数源码:

template 
void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    __linear_insert(__first, __i, __VALUE_TYPE(__first));
}

template 
inline void __linear_insert(_RandomAccessIter __first, 
                            _RandomAccessIter __last, _Tp*) {
  _Tp __val = *__last; if (__val < *__first) {
    copy_backward(__first, __last, __last + 1);
    *__first = __val;
  } else __unguarded_linear_insert(__last, __val);
}

template 
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
  _RandomAccessIter __next = __last;
  --__next; while (__val < *__next) {
    *__last = *__next;
    __last = __next;
    --__next;
  }
  *__last = __val;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

//__unguarded_insertion_sort函数源码:

template 
inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
                                _RandomAccessIter __last) {
  __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
}
template 
void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
                                    _RandomAccessIter __last, _Tp*) { for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    __unguarded_linear_insert(__i, _Tp(*__i));
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

//参考文献《STL源码剖析》

阅读(3594) | 评论(0) | 转发(0) |
0

上一篇:First Bad Version

下一篇:本博客停止更新

给主人留下些什么吧!~~