SGI STL序列式容器list中的sort算法.pdf

mwjsolar的专栏
欢迎大家光临我的博客小站
SGI STL序列式容器list中的sort算法
分类: STL 2013-08-18 17:20 90人阅读评论(0) 收藏举报
STLC++算法list
essIterator,list容器属于bidirectional Iterator,因此STL的list容器提供了专有
的sort算法,是一个以非递归形式的merge sort,虽然研究多时,无奈本人算法功底不济,本文权当抛砖引玉,望
各路高手指点。
代码:
1. template <class _Tp, class _Alloc>
2. template <class _StrictWeakOrdering>
3. void list<_Tp, _Alloc>::sort(_StrictWeakOrdering p)
4. {
5. // Do nothing if the list has length 0 or 1.
6. if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
7. // 保存下层merge返回的结果
8. list<_Tp, _Alloc> __carry;
9. // 模拟merge sort使用的堆栈,保存部分有序的list
10. // 64应该写作sizeof(size_type) * 8,即最大的递归调用层次。
11. list<_Tp, _Alloc> __counter[64];
12. // 指示堆栈层次
13. int __fill = 0;
14. while (!empty()) {
15. // 将begin处的元素从list取下,insert到carry中
16. ((), *this, begin());
17. int __i = 0;
18. // 模拟递归时对下层的返回结果进行merge,并将结果交给carry
19. while(__i < __fill && !__counter[__i].empty()) {
20. __counter[__i].merge(__carry, p);
21. (__counter[__i++]);
22. }
23. // carry将结果保存到堆栈
24. (__counter[__i]);
25. // 更新递归层次
1
26. if (__i == __fill) ++__fill;
27. }
28.
29. // 逐级获取结果
30. for (int __i = 1; __i < __fill; ++__i)
31. __counter[__i].merge(__counter[__i-1], p);
32. // 保存最终结果
33. swap(__counter[__fill-1]);
34. }
35. } 再免费赠送一个正常merge sort的C实现:)
1. void merge(int