STL源码学习——Lists(链表)-阿里云开发者社区

STL源码学习——Lists(链表)

2014-09-23 1587

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

STL源码学习——Lists(链表)

　　今天突然想起来看看开源项目，找了找最后决定好好看看经典的STL喵~
　　和STL里的代码比起来我突然觉得以前写的代码也太不规范了喵，估计很多ACMer都一样吧喵。

　　先从简单的看、先挑了一发list的源码来看。总结如下：

　　　　欢迎大家一起讨论喵~

　　1 ：list是用双向循环链表实现的，就是说 list.end()+1 == list.begin()
　　2 ：list中有一个关键结点，这个结点是 list.end()
　　3 ：在看了list中的erase函数后，发现这个函数没有对end()结点进行特殊处理，所以很遗憾list在erase(end)后就会出现一些意想不到的情况，比如以下代码会让list容器死循环喵~（虽然这个操作本来就是非法的）

 
    
  
int main()
{
   list<int> ls;
   ls.insert(ls.begin(), 0);
   ls.insert(ls.begin(), 1);
   ls.erase(ls.end());
   for(list<int>::iterator it=ls.begin(); it!=ls.end(); ++it)
       printf("it -> %d\n", *it);
   return 0;
} 
    
  

　　4 ：erase(it)之后会返回应该在原先it位置的元素。同样erase(end)后返回值是不对的。（erase(end)后的返回值为begin喵~）

　　5 ：erase()函数并未检测传入参数是否是本身这个list的。所以如果你有两个list：L1、L2，你这样写也是对的喵~

L1.erase( L2.begin() );

　　6 ：list里居然自己实现了sort算法喵，而且时间复杂度O(n*lg n)、空间复杂度O(1)。以前并没有仔细想list的排序问题，一直很单纯的以为list排序很慢。今天看了一发源码才知道原来链表排序也可以这么优越喵~

　　这里，《STL源码剖析》中采用的如下解释：解释为快速排序。

　　大致说一下算法喵：这里采用的是归并排序算法的思想。
　　先将0、1两元素排序，再将2、3两元素排序。
　　接下来就是排序前4个元素，
　　然后，同上前8、16、32 ... 个元素
　　具体实现用了64个桶，每个依编号存放2^n个元素。然后就像二进制加法一样，每次对个位进行加一操作，通过进位过程可将排好序的桶进行合并了喵。
由于链表的特殊性，无须另开空间存放元素，只需将原来的结点移动位置即可喵~

list::sort() 
    
  
   void sort(_StrictWeakOrdering __comp)
   {
       // Do nothing if the list has length 0 or 1.
       if (_M_node._M_data->_M_next != _M_node._M_data &&
               (_M_node._M_data->_M_next)->_M_next != _M_node._M_data)
       {
           list<_Tp, _Alloc> __carry;
           list<_Tp, _Alloc> __counter[64];
           int __fill = 0;
           while (!empty())
           {
               __carry.splice(__carry.begin(), *this, begin());   //个位加一
               int __i = 0;
               while(__i < __fill && !__counter[__i].empty())
               {
                   __counter[__i].merge(__carry, __comp);
                   __carry.swap(__counter[__i++]);
               }
               __carry.swap(__counter[__i]);
               if (__i == __fill) ++__fill;
           }

           for (int __i = 1; __i < __fill; ++__i)
               __counter[__i].merge(__counter[__i-1], __comp);
           swap(__counter[__fill-1]);
       }
   } 
    
  

　　7 ：关于resize()我以前一直以为list会存放一个size_val，结果它木有存，resize的复杂度是线性的。所以如果size比较大的话，还是少resize()为好喵。

当然现在也可以理解为什么没有存放size_val了喵，因为存在这个时间复杂度为O(1)的insert函数。

 
        void 
        insert( iterator pos, input_iterator start, input_iterator end );

　　8 ：“operator=” list里这个函数比我想像的要聪明喵。
　　我以为它会先erase(begin(), end())，然后再一个一个的加进去。
　　结果它是先将就目标list中已创建的结点先用着，然后采用”多退少补“的原则喵~

STL源码学习——Lists(链表)

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

STL源码学习——Lists(链表)

热门文章

最新文章

相关电子书