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

简介:

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容器死循环喵~(虽然这个操作本来就是非法的)

复制代码
 1 int main()
 2 {
 3     list<int> ls;
 4     ls.insert(ls.begin(), 0);
 5     ls.insert(ls.begin(), 1);
 6     ls.erase(ls.end());
 7     for(list<int>::iterator it=ls.begin(); it!=ls.end(); ++it)
 8         printf("it -> %d\n", *it);
 9     return 0;
10 }
复制代码

  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()
复制代码
 1     void sort(_StrictWeakOrdering __comp)
 2     {
 3         // Do nothing if the list has length 0 or 1.
 4         if (_M_node._M_data->_M_next != _M_node._M_data &&
 5                 (_M_node._M_data->_M_next)->_M_next != _M_node._M_data)
 6         {
 7             list<_Tp, _Alloc> __carry;
 8             list<_Tp, _Alloc> __counter[64];
 9             int __fill = 0;
10             while (!empty())
11             {
12                 __carry.splice(__carry.begin(), *this, begin());   //个位加一
13                 int __i = 0;
14                 while(__i < __fill && !__counter[__i].empty())
15                 {
16                     __counter[__i].merge(__carry, __comp);
17                     __carry.swap(__counter[__i++]);
18                 }
19                 __carry.swap(__counter[__i]);
20                 if (__i == __fill) ++__fill;
21             }
22 
23             for (int __i = 1; __i < __fill; ++__i)
24                 __counter[__i].merge(__counter[__i-1], __comp);
25             swap(__counter[__fill-1]);
26         }
27     }
复制代码

  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中已创建的结点先用着,然后采用”多退少补“的原则喵~



相关文章
|
10天前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
14 0
|
10月前
|
存储 算法 C++
4.1 C++ STL 动态链表容器
List和SList都是C++ STL中的容器,都是基于双向链表实现的,可以存储可重复元素的特点。其中,List内部的节点结构包含两个指针一个指向前一个节点,一个指向后一个节点,而SList只有一个指针指向后一个节点,因此相对来说更节省存储空间,但不支持反向遍历,同时也没有List的排序功能。双向链表的数据元素可以通过链表指针串接成逻辑意义上的线性表,不同于采用线性表顺序存储结构的`Vector`和`Deque`容器,双向链表中任一位置的元素,查找,插入和删除,都具有高效的常数阶算法时间复杂度O(1).
33 0
|
存储 编译器 C++
c++基础知识——STL之链表
c++基础知识——STL之链表
350 0
|
存储 算法 C++
STL设计之链表设计,分块分组件分析,迭代器设计思路
STL设计之链表设计,分块分组件分析,迭代器设计思路
STL设计之链表设计,分块分组件分析,迭代器设计思路
|
移动开发 算法 C++
[leetcode] 432. 全 O(1) 的数据结构 | STL 双向链表&哈希
我们可以维护一个链表,这个链表是一个双向的,把这个链表维护成从头节点到尾节点是单调递增的,然后我们就可以很好的通过头尾返回出现次数最多(尾部)和出现次数最小的字符串(头部) 在这个链表里面,我们存入两个部分,用 pair 做在一起,第一部分是存放 string 的 unorderedset 容器 keys,用来放置字符串,然后我们用第二部分来标识这个字符串出现的次数 count 对于一个给定的字符串,如果不用遍历的防止获取他的位置,那还能怎么做呢?
87 0
[leetcode] 432. 全 O(1) 的数据结构 | STL 双向链表&哈希