已关闭。此问题需要details or clarity。当前不接受答案。
**想要改进此问题吗？**通过editing this post添加详细信息并阐明问题。
11天前关闭。
Improve this question
我最近参加了两次面试，两次我都说向量是因为我的常识告诉我，因为访问堆上的内存比较慢。然而，链表和向量都是在堆上存储元素的。面试官似乎对我的答案不满意，即使我答对了。
有谁能给予我一个教科书式的答案来回答这两个面试问题吗？
什么东西迭代更快，在什么东西上创建新元素更快？向量还是链表？为什么？
为什么访问元素或在向量上创建新元素更快？
1条答案
按热度按时间xeufq47z1#
在大多数体系结构中，缓存局部性确保了向量是迭代最快的，而链表在每一步都需要间接寻址。（1）时间。插入到向量取决于你想插入的位置和向量的内部实现方式。假设是普通的c++实现，在不超过 * 容量的情况下插入到向量的末尾是O（1），但是这是一个很慢的（O（n））操作，因为重新分配意味着复制/移动。对于插入到中间，没有比手动复制/移动元素（通常是O（n）个元素）更快的算法，这样的实现也很慢。
向量插入的性能取决于您是否可以将增长的成本分摊到多个插入上。在
std::vector<>的情况下，这种增长可以很好地分摊，因此如果您进行批处理（许多元素），那么您将经历几乎恒定的插入时间。出于实时目的，您不能在逐个调用地测量插入时间时分摊;那么它的时间复杂度是O（n）。