Vector和list

一、Vector和list的区别——从“它们是什么”到“区别在哪儿”

1. 它们是什么？

• Vector：类似于一排排整齐的书架（数组），存放元素时，元素排成一条线，连续存储。可以很快通过编号（索引）找到任何一项。

• List：像一串珠子，每个珠子知道前后两个珠子（通过指针连接），存储位置不连续。有两种常用链表：单链表和双链表，双链表每个节点都知道前后两个节点。

2. 它们的主要差别

比较点	Vector	List
存储方式	连续内存（数组式）	非连续（链式）
访问元素	支持随机访问（用下标直接取）	需要遍历，逐个走链找到
插入/删除（尾部）	快（摊销时间O(1)）	快（指针操作，无移动元素）
中间插入/删除	复杂（需要移动大量元素，时间O(n)）	方便（只需调整链表指针，时间O(1)）
内存使用	占用连续空间，偶尔会需要重新“扩容”	多占用空间（存指针）
迭代速度	快（缓存友好，占用连续内存）	相对慢（节点散布内存，缓存效率低）

---

二、实际工作中的应用场景——什么时候用Vector，什么时候用list？

场景一：你要频繁随机访问元素——用Vector

• 比如存储一组数据，之后可能会多次访问（查找、排序）

场景二：你需要在中间插入或删除元素——用List

• 比如维护一个任务队列，任务需要频繁插入到中间或删除, 或是在链表头尾操作

场景三：尾部频繁插入删除（比如维护动态数组），用Vector

场景四：需要稳定的元素存储，不频繁改变结构，容器大小变化不大，用Vector

---

三、迭代器会失效的情况——擦亮眼睛，避免“坑”！

1. 什么是迭代器？

• 就像指针一样的东西，用来看“容器”里的元素。比如auto it = vec.begin();，用it可以遍历所有元素。

2. 什么时候迭代器会失效？

Vector的情况

• push_back
  • 增加元素可能会导致容器重新分配（扩容）
  • 这时候所有原有的迭代器都“作废”了（指向的地址变了）
• erase（删除元素）
  • 删除元素后，除非用返回值重启迭代器，否则原迭代器会失效
• resize（调整大小）
  • 改变容器大小也可能导致迭代器失效

List的情况

• 插入和删除操作
  • 不会影响其他迭代器，只要你不删除它们指向的元素，迭代器不会失效

3. 小结——什么情况下失效？

容器类型	会导致迭代器失效的操作	示例
Vector	push_back()（扩容时），erase()，resize()	添加元素导致重分配，删除某元素后继续用旧迭代器
List	一般情况下不会失效，只要不删除迭代器指向的元素	插入、删除元素不会使其他迭代器失效

---

四、通俗点的理解——比喻和总结

比喻：搬家和串珠

• Vector：就像把所有房子（元素）堆在一排（连续内存）里。搬家（扩容）时，可能要找个更大的车（新空间），搬出来所有房子（大量移动元素），旧的地址都不能用了（迭代器失效）

• List：像一串串珠子，每个珠子用线串起来（指针连接）。插入或删除珠子，只要调转指针就行，不会影响其他珠子。

小结一句话

• Vector：“快、连续、随机访问”——适合“读多写少、以访问为主”的场景，但扩容时可能会“搬家”，导致迭器失效。
• List：”链式、插入删除快“——适合“频繁插入删除、顺序存储不变”的场景，不会轻易导致迭代器失效，只要注意不要删除你关心的珠子。