C++ 中 Vector 和 List 的区别

在本文中，您将学习 C++ 中 Vector 和 List 的区别。但在讨论区别之前，您必须了解 Vector 和 List。

C++ 中的 Vector 是什么？

在 C++ 中，vector 是一个类似动态数组的容器，可以存储相同数据类型的元素的集合。与数组不同，vector 可以在运行时增长或缩小。Vector 是 C++ Standard Template Library (STL) 的一部分，包含在 <vector> 头文件中。

C++ 中 vector 的一些用途

• 存储元素集合： Vector 可以存储相同数据类型的元素集合，例如 整数、浮点数 或 字符串。
• 动态调整容器大小： Vector 可以在运行时增长或缩小，这使得它们在您不知道集合大小或者集合大小在运行时可能发生变化时非常有用。
• 快速随机访问： Vector 中的元素存储在连续的内存位置，因此可以使用它们的索引在常数时间内访问元素。
• 高效内存分配： Vector 高效地分配内存，可以以最小的开销在 vector 的末尾添加或删除元素。
• 与其他库的互操作性： Vector 是 C++ 标准模板库 的一部分，这意味着它们可以与其他 STL 容器、算法和迭代器一起使用。

语法

声明 vector 的基本语法

我们还可以通过将整数参数传递给相应的构造函数来指定 vector 的初始大小

C++ 中的 List 是什么？

在 C++ 中，list 是一个容器，它存储元素的集合，类似于 vector 或 array。但是，与 vector 和 array 不同，list 实现为 双向链表，其中每个元素都链接到列表中的前一个和后一个元素。它允许在列表的任何位置高效地插入和删除元素，但代价是与 vector 或 array 相比，随机访问元素的速度较慢。List 高效地分配内存，因为每个元素都存储为一个单独的节点，并且可以动态调整大小而无需连续内存分配。

Vector 和 List 之间的关键区别

Vector 和 list 都是容器类，允许用户存储元素的集合，它们之间存在一些区别，如下所示

• 实现： Vector 实现为 动态数组，这意味着元素存储在 连续的内存位置。相比之下，List 实现为 双向链表，意味着元素不存储在连续的内存位置，而是通过指针链接。
• 访问元素： 由于 vector 将其元素存储在连续的内存位置，因此它们允许使用 [] 运算符 进行元素的随机访问。另一方面，List 不允许随机访问，需要遍历列表来访问元素。
• 插入和删除： 在 vector 中插入和删除元素如果是在 vector 的中间或前面进行，可能会很昂贵，因为它需要移动插入或删除点之后的所有元素。相比之下，在 list 中插入和删除元素相对便宜，它们只需要更新相邻元素的指针。
• 内存分配： Vector 通常实现为连续数组，这意味着它们为所有元素分配一个内存块。另一方面，List 通常实现为链式 list，这意味着它们为每个元素分配单独的内存块。这会影响性能，因为内存的分配和释放可能很昂贵。
• 迭代器： Vector 和 List 都支持迭代器，但迭代器的行为不同。Vector 迭代器 的行为类似于指向 vector 中元素的 指针，它们支持随机访问（即，您可以直接访问 vector 中的任何元素）。另一方面，List 迭代器 的行为类似于指向链表中节点的指针，它们支持双向访问（即，您可以沿两个方向遍历列表，但不能通过索引直接访问元素）。
• 内存开销： Vector 的内存开销比 list 大，因为它们需要存储额外的信息，例如 vector 的容量和大小，而 list 不需要这些信息。
• 缓存性能： 由于其连续的内存布局，vector 通常比 list 具有更好的缓存性能，因为相邻元素更有可能存储在同一个缓存行中，从而减少缓存未命中并提高性能。相比之下，由于 list 实现为带有指针的节点，list 中的每个元素可能存储在内存中的不同位置，这可能导致更多的缓存未命中和更慢的性能。
• 排序： Vector 可以使用 <algorithm> 头文件 中的 sort() 函数 进行排序，该函数使用快速排序算法的变体，而 list 没有内置的排序函数，需要使用自定义比较器函数手动排序。
• 复制： 复制 vector 包括将 vector 中的所有元素复制到新的内存块，而复制 list 包括将节点及其指针复制到新的 list。这可能会根据 list 的大小和内存分配器的效率而产生不同的性能特征。

示例

演示 vector 和 list 之间差异的基本 C++ 代码片段

输出

Time taken by vector for insertion:  33ms
Time taken by list for insertion: 131ms
Time taken by vector for random access: 0ms
Time taken by list for random access: 3163ms
Time taken by vector for sorting: 346ms
Time taken by list for sorting: 704ms

说明

此代码创建一个 vector 和一个 list，并使用 push_back() 将 100 万个元素 插入到每个容器中。之后，它在每个容器中随机访问 1000 个元素，并测量每个操作所花费的时间。最后，它使用 sort() 函数 对 vector 中的元素进行排序，并使用 sort() 成员函数 对 list 中的元素进行排序，并测量每个操作所花费的时间。

此代码的结果将取决于执行它的特定机器和环境，但总的来说，它应该能够说明 vector 和 list 在不同类型操作下的性能差异。