两个STL容器，std::vector和std::list，似乎提供了非常相似的功能。据我所知，唯一的区别是std::list为向量提供 O(1) 修改时间和 O(n) 时间用于读取，反之亦然。忽略效率，还有其他区别吗？提议的副本似乎侧重于效率，而我想知道内存差异如何在语义差异中表现出来(例如 std：：list 的拼接能力)？
List 的每个元素具有(大得多)更大的内存占用量，并且与向量相比，缓存一致性更少(即使忽略较大的元素大小)。这意味着它将更多地依赖于缓存行获取和内存读取速度，这通常是您的性能瓶颈，而不是最初用于列表/矢量比较的假设"一个元素的读/写"。
作为病理学示例，考虑 16int的向量与 16int的列表。第一个有一个包含 16 个整数的单个缓存行，可以在 1 个缓存行提取中执行任何操作，其中第二个具有：
- 一个内存分配块开销(16 字节)
- 一个指向前一个块的指针(8 个字节)
- 一个指向下一个块的指针(8 字节)
- 一个整数(4 字节)
在每个分配的单位中。使用上面猜测的大小，这使其约为 36 字节，四舍五入为 40(由于对齐原因)，可能为 48(由于 malloc 的内部对齐原因)。在理想情况下，这将加载 12 个完整缓存行，在最坏的情况下加载 32 个缓存行。
鉴于您的性能瓶颈是缓存，将所有内容都放在 1 或 2 个缓存行中而不是 12-32种方式胜过列表的理论优势。
总结一下到目前为止我在评论和答案中看到的内容，以下是lists 优于vectors的优缺点：
- 几乎所有领域的性能都差得多
vector不支持的拼接功能- 更少的缓存一致性，意味着更多地依赖内存读取
- 列表中的项目大小较大。
- 布尔值和包装器的
vector和list问题 非常感谢所有的帮助！