13 选 list 还是 vector？C++ STL list 扩容 / 迭代器失效问题 + 模拟实现，对比后再做选择

1  list 类

1.1 底层数据结构--双向循环链表

环形结构‌：

• 链表的头尾通过一个‌不存储数据的哨兵节点‌连接形成环形

• 哨兵节点的 next 指向第一个实际节点

• 哨兵节点的 prev 指向最后一个实际节点

• 最后一个节点的 next 指向哨兵节点

• 第一个节点的 prev 指向哨兵节点

1.2 构造函数的底层行为--都先创建一个哨兵位节点

void empty_init(){_head = new Node;//new自定义类型，自定义类型会调用默认构造函数创建哨兵位节点_head->_prev = _head;//前驱指针指向自己_head->_next = _head;//后驱指针指向自己_size = 0;}list() {empty_init();}

1.3 list iterator的使用

只支持顺序遍历，不支持随机访问---地址加偏移量来访问因为底层结构是链式的，一个一个节点分开的。

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.4 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无 效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入 时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭 代器，其他迭代器不会受到影响。

void TestListIterator1(){ int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };  list l(array, array+sizeof(array)/sizeof(array[0]));  auto it = l.begin();  while (it != l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值  l.erase(it);   ++it; }}// 改正void TestListIterator(){ int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };  list l(array, array+sizeof(array)/sizeof(array[0]));  auto it = l.begin();  while (it != l.end())  {   l.erase(it++);   // it = l.erase(it);  }}

1.5 list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下：

vector list 底层结构 动态顺序表，一段连续空间 ,物理和逻辑上都是连续的 带头结点的双向循环链表，逻辑上连续，物理上不连续 随机访问 支持随机访问，访问某个元素效率O(1)，地址加偏移量直接访问。 不支持随机访问，访问某个元素效率O(N)，只能从头节点开始遍历查找 插入和删除 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) 空间利用率 底层为连续空间，不容易造成内存碎片，空间利用 率高，缓存利用率高 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 迭代器 原生态指针，指针类型 对原生态指针(节点指针)进行封装 迭代器失效 在插入元素时，要给所有的迭代器重新赋值，因为 插入元素有可能会导致重新扩容，致使原来迭代器 失效，删除时，当前迭代器需要重新赋值否则会失 效 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 使用场景 需要高效存储，支持随机访问，不关心插入删除效 率 大量插入和删除操作，不关心 随机访问2

 2 list的使用和简单模拟实现gitee链接：

c++基础/c++List(链表)/Project1/List.h · 坤坤/c++入门代码及笔记 - 码云 - 开源中国