STL源码——序列式容器list

1. list即链表

优点:插入、移除方便

缺点:查找不方便,每次都需要从头开始查

slist是单向链表

我们常说的list表示环状双向链表

2. list节点结构

STL源码——序列式容器list

3. 将头结点设为尾端的一个空白节点

STL源码——序列式容器list

STL源码——序列式容器list

STL源码——序列式容器list

可以将这个空白节点称为Flag节点

4.向list插入一个元素

STL源码——序列式容器list

其实是插入在迭代器所在位置之前那个位置

5. erase

原理:将要移除的那个节点的前节点和后节点链接起来,然后删除迭代器指向的那个节点。返回指向原迭代器指向结点的后一个结点的那个迭代器

STL源码——序列式容器list

6. clear()

原理:

先找出头结点,然后遍历链表内所有节点,逐个删除

STL源码——序列式容器list

7.  remove

移除指定数值的元素

原理:遍历链表,找出数值元素,erase

STL源码——序列式容器list

8. splice

将两个list接合

原理:利用transfer

STL源码——序列式容器list

9、 merge

注意,merge之前一定要递增排序才可以正确使用

10. reverse

原理:如果链表为空或者链表只有一个节点,那么不做修改

其他情况,使用transfer,依次将后面一个元素放到指定迭代器之前完成翻转。

STL源码——序列式容器list

11.sort

list有自己专门的sort函数,所以一定要使用自己的

原理:利用快速排序(个人觉得不是),将每个元素都单独存放,最后将这些元素再merge合在一起即可

STL源码——序列式容器list