根据 Bjarne Stroustrup在他的Going Native 2012 主题演讲中的幻灯片，a 中的插入和删除在现代硬件上非常低效：std::list
矢量节拍列表海量用于插入和删除
如果这确实是真的，还剩下什么用例std::list？那不应该弃用吗？
问问题
2334 次
5 回答
24
向量和列表解决不同的问题。List 保证迭代器在您插入和删除其他元素时永远不会失效。Vector 不做这样的保证。
它不仅仅与性能有关。所以答案是否定的。不应弃用列表。
编辑除此之外，C++ 的设计目的不仅仅是在“现代硬件”上工作。它旨在用于比这更广泛的硬件。我是金融行业的程序员，我使用 C++，但其他领域，如嵌入式设备、可编程控制器、心肺机和无数其他领域也同样重要。C++ 语言的设计不应仅仅考虑某些领域的需求和某些类别的硬件的性能。仅仅因为我可能不使用列表并不意味着它应该从语言中被弃用。
于 2012-12-08T17:11:27.147 回答
8
向量是否优于列表还取决于元素的类型。例如，对于int元素，向量确实非常快，因为大多数数据都适合 CPU 缓存，并且 SIMD 指令可用于数据复制。所以向量的 O(n) 复杂度没有太大影响。
但是对于较大的数据类型，复制不会转换为流操作，而是必须从各处获取数据呢？此外，没有大型 CPU 缓存并且可能还缺少 SIMD 指令的硬件呢？C++ 不仅用于现代台式机和工作站机器。弃用 std::list 是不可能的。
Stroustrup 在该演示文稿中所说的是，在您为数据选择 std::list 之前，您应该确保它是适合您特定情况的正确选择。换句话说，基准和配置文件。它绝对不是说你应该总是选择 std::vector。
于 2012-12-08T17:24:44.307 回答
3
不，尤其是不基于一个特定的图表。在某些情况下，列表会比向量表现更好。见：http ://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/
正如其他人所提到的，这忽略了非性能差异。
Bjarne 在那次谈话中的观点不是你不应该使用列表。正是人们对 list 的性能做出了太多的假设，结果往往证明是错误的。他只是在证明向量应该始终是您的默认首选容器类型的立场，除非您确实发现需要列表的性能或其他语义特征。
于 2012-12-08T17:09:38.570 回答
0
std::list是一个双端队列，它有push_front()和pop_front()。它仍然具有这样的利基角色，尽管它可能不是双端队列的最佳选择。
链表与树数据结构有关。两者都包含链接。如果我们弃用std::list，那么基于树的容器呢？
于 2021-11-09T14:18:59.093 回答
-1
当然不是。std::list 是一种不同的数据结构。比较不同的数据结构可以很好地说明其属性、优点或缺点。但每种数据结构都有其优势。
于 2012-12-08T17:15:42.077 回答