c++_list
目录
一.c++ _list库 的结构 和 介绍
二.list的使用
编辑
三 list的迭代器失效
四.list 和 vector 对比
一.c++ _list库 的结构 和 介绍
我直接用浏览器翻译的：
cplusplus.com/reference/list/list/?kw=list
std:: list
template < class T, class Alloc = allocator<T> > class list;
列表是序列容器，允许对序列中任意位置的恒定时间插入和擦除操作，以及双向迭代。
列表容器实现为双向链表;双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置。排序在内部通过与指向其前面的元素的链接和指向其后元素的链接的每个元素的关联来保持。
它们与 forward_list 非常相似：主要区别在于 forward_list 对象是单链表，因此它们只能向前迭代，以换取更小、更高效。
与其他基本标准序列容器（array、vector 和 deque）相比，列表在容器中已经获得迭代器的任何位置插入、提取和移动元素时通常表现更好，因此在密集使用这些的算法（如排序算法）中也表现更好。
与这些其他序列容器相比，列表s 和 forward_lists 的主要缺点是它们无法通过其位置直接访问元素;例如，要访问列表中的第六个元素，必须从已知位置（如开头或结尾）迭代到该位置，这需要在这些位置之间的距离内花费线性时间。它们还会消耗一些额外的内存来保持与每个元素关联的链接信息（对于大型小尺寸元素列表来说，这可能是一个重要因素）。
二.list的使用
其常用构造为：
2.1 list iterator的使用
他的迭代器是一种双向迭代器 无法和 其他的随机迭代器(vector的迭代器) 一样随机访问元素
begin 返回第一个元素的迭代器
end 返回最后一个元素下一个位置的迭代器
2.2 list capacity
empty 判空
size 大小
其他函数可以自行查询 我就不发了
<list> - C++ Reference
2.3 list element access
2.4 list modifiers
三 list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无
效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入
时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是 指向被删除节点的迭
代器，其他迭代器不会受到影响
四.list 和 vector 对比
| vector | list | |
| 底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元 素效率O(N) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间 复杂度为O(N)，插入时有可能需要增容，增容： 开辟新空间，拷贝元素，释放旧空间，导致效率更 低 | 任意位置插入和删除效率高， 不需要搬移元素，时间复杂度 为O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用 率高，缓存利用率高 | 底层节点动态开辟，小节点容 易造成内存碎片，空间利用率 低，缓存利用率低 |
| 迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进行 封装 |
| 迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为 插入元素有可能会导致重新扩容，致使原来迭代器 失效，删除时，当前迭代器需要重新赋值否则会失 效 | 插入元素不会导致迭代器失 效，删除元素时，只会导致当 前迭代器失效，其他迭代器不 受影响 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效 率 | 大量插入和删除操作，不关心 随机访问 |