答案

std::vector和std::list是两种不同的STL容器，具有不同的实现和行为。

• std::vector实现了动态数组，元素在内存中连续存储。按索引快速访问（O(1)），在末尾快速添加（摊销O(1)），在中间插入和删除的成本较高（O(n)），因为元素需要移动。
• std::list是一个双向链表。随机访问较慢（O(n)），在列表的任何位置进行插入和删除的速度较快（O(1)），内存开销较大（每个元素有两个指针）以及频繁的分配/回收。

选择时机：

• 如果不需要在中间频繁插入/删除，几乎总是使用std::vector。
• 仅在需要在任意位置进行插入/删除且数据量很大时，std::list才是合理的选择，因为移动vector的元素代价太高。
• 对于较小的集合，即使需要在中间添加，std::vector因数据的局部性往往也更快。

示例：

std::vector<int> v;
v.push_back(1);
v[0] = 2; // 按索引快速访问

std::list<int> l;
l.push_back(1);
// l[0] = 2; // 错误：std::list没有按索引访问的功能！

有陷阱的问题

"为什么在现代C++项目中几乎没有使用std::list，尽管在频繁在集合中间插入时理论上具有优势？"

答案： 因为在实践中，由于大量的小分配、数据局部性的丧失（缓存友好性）、结构的庞大以及对某些操作的糟糕支持（std::list在大列表中也低效，由于分配和回收的时间损失，缓存失效的减速常常抵消了渐近性上的优势）。此外，现代处理器非常敏感于缓存局部性，因此即使在处理大量数据时，std::vector在实际情况下通常也更快。

由于对主题细节缺乏了解而导致的实际错误示例

---

故事

在实时系统中选择std::list来存储事件队列，以便在任意位置频繁删除。结果系统由于频繁访问堆和数据在内存中的差的局部化而变慢10倍。

---

故事

在图形处理器中将邻接数组存储为std::list以便插入。这造成了内存使用量的剧烈增长并且L1/L2缓存的退化，而且并没有获得实质上的速度好处。

---

故事

在报表生成服务中，每个报表是由Linked List对象组装而成。在压力测试中，服务开始“变慢”，而分析显示在处理列表时分配的开销是瓶颈。转而使用vector后，结果提高了几个数量级。