arrays - 使用 STL 列表和向量、链表和数组的优缺点

Question

我想知道 STL:list、STL:vector、数组和链表在基本层面上的区别是什么。

我的理解是，通常，链表允许可增长的列表，插入和删除要容易得多，但直接访问链表中的单个元素需要更长的时间，因为您需要遍历每个元素。

我可能遗漏了许多其他关键差异，因此您也可以指出一些更明显的差异。

比较起来，列表和向量是如何发挥作用的？你什么时候选择一个而不是另一个？

Answer 1

以下是列表和向量之间的一些区别。

1. 插入所需的时间：列表需要恒定的时间才能将元素插入其中，如果向量的容量等于向量中存在的元素数量，则向量内部需要重新定位向量中存在的数据，然后再插入新值。这需要处理器和时间的开销。
2. 访问数据所花费的时间：Vectors 在这方面优于列表。Vector 需要恒定的时间来访问位于中间的元素。其中列表需要遍历列表才能到达所需的元素。
3. 容器占用的内存： vector 的容量和大小不一定相同。向量的容量呈指数增长，消耗的内存比容器实际需要的更多。列表占用存储元素所需的完全相同的内存，因此在分配期间不会分配额外的内存，可以节省内存。