c++ 中的容器 vector、deque 和 list 的区别

0. 表格汇总：

容器	存储结构	随机访问性能	中间插入/删除性能	两端插入/删除性能	内存管理特点	迭代器类型	适用场景
vector	连续存储的动态数组	$O(1)$	$O(n)$（需要移动元素）	末尾：$O(1)$，头部：$O(n)$	空间不足时重新分配并复制元素	随机访问迭代器	频繁随机访问，插入/删除在末尾
deque	分段连续存储	$O(1)$（稍逊于 vector）	$O(n)$（优于 vector）	$O(1)$	以块为单位分配内存，空间扩展更稳定	随机访问迭代器	两端高效插入/删除，需一定随机访问
list	双向链表，节点存储元素及前后指针	$O(n)$（需遍历）	$O(1)$（仅需修改指针）	$O(1)$	元素节点单独分配，可能碎片化	双向迭代器	频繁中间插入/删除，不依赖随机访问

1. 存储结构：
   • vector：
     • 是一个动态数组，元素在内存中是连续存储的。这使得它可以像数组一样支持快速的随机访问，通过下标访问元素的时间复杂度为 $O(1)$。例如，对于一个 std::vector<int> v;，使用 v[2] 可以快速访问第三个元素（索引从 0 开始）。
   • deque（双端队列）：
     • 数据在内存中是分段连续存储的，对用户而言逻辑上是连续的。它也支持随机访问，不过效率比 vector 稍低，但仍为 $O(1)$。例如，对于 std::deque<int> d;，可以使用 d[3] 来访问第四个元素。
   • list（双向链表）：
     • 是一个双向链表，每个元素存储在一个节点中，节点包含数据和指向前一个及后一个节点的指针。这导致它不能直接根据下标进行随机访问，访问元素需要从头部或尾部开始遍历，时间复杂度为 $O(n)$，其中 n 是元素的个数。
2. 插入和删除元素的性能：
   • vector：
     • 在末尾插入和删除元素通常比较快，时间复杂度为 $O(1)$，但当元素数量达到容器的容量时，插入元素会触发扩容操作，需要重新分配内存和复制元素，性能开销较大。在中间插入或删除元素时，需要移动其后的元素，时间复杂度为 $O(n)$。例如，v.insert(v.begin() + 2, 5); 会将元素 5 插入到 v 的第三个位置，其后的元素会向后移动。
   • deque：
     • 在两端插入和删除元素都非常快，时间复杂度为 $O(1)$。在中间插入或删除元素时，性能比 vector 好，因为不需要移动大量元素，但仍然比 list 慢，时间复杂度为 $O(n)$。例如，d.push_front(1); 和 d.push_back(2); 分别在 deque 的前端和后端插入元素。
   • list：
     • 在任何位置插入和删除元素都很快，只要有指向该位置的迭代器，时间复杂度为 $O(1)$，因为只需要修改前后节点的指针，不涉及元素的移动。例如，对于 std::list<int> l;，使用 l.insert(l.begin(), 3); 插入元素 3 时，只需调整指针。
3. 内存管理：
   • vector：
     • 当空间不足时，会分配一个更大的连续内存空间，将原元素复制过去，释放原空间。这可能导致性能开销和内存浪费（预留但未使用的空间）。例如，当 v 的元素数量超过其容量时，会重新分配更大的内存空间。
   • deque：
     • 以块为单位分配内存，当需要更多空间时，会分配新的块，不需要像 vector 那样大规模复制元素，因此在空间扩展时相对更稳定。
   • list：
     • 每个元素节点单独分配内存，插入元素时为新节点分配内存，不会出现 vector 那样的整体复制和重新分配问题，但可能导致内存碎片化，因为节点是分散存储的。
4. 迭代器特性：
   • vector：
     • 迭代器是随机访问迭代器，可以进行加、减操作，支持 operator[]。在插入或删除元素时，可能导致迭代器失效，特别是在扩容时，迭代器和指针、引用都可能失效。
   • deque：
     • 迭代器是随机访问迭代器，但在中间插入或删除元素时，部分迭代器可能失效，因为存储是分段的。
   • list：
     • 迭代器是双向迭代器，只能进行前后移动，不支持 operator[]。在插入或删除元素时，只有被操作元素的迭代器失效，其他迭代器不受影响。
5. 适用场景：
   • vector：
     • 适合需要频繁随机访问元素，并且元素的插入和删除操作主要在末尾进行的场景。例如，存储一组学生成绩，经常根据索引查询成绩，成绩的添加和删除多在末尾。
   • deque：
     • 适用于需要在两端高效插入和删除元素，同时也需要一定程度随机访问能力的情况。例如，实现一个双端操作的队列，或者一个窗口滑动的数据结构。
   • list：
     • 适用于需要频繁在容器中间插入和删除元素，对随机访问性能要求不高的情况。例如，实现一个文本编辑器中的文本行存储，频繁插入和删除行操作。