代码随想录八股训练营第三十四天| C++

前言

一、vector和list的区别？

1.1.存储方式：

1.2.随机访问：

1.3.插入和删除操作：

1.4.内存使用：

1.5.容量和大小：

1.6.迭代器类型：

1.7.用途：

二、vector 底层原理和扩容过程？

2.1.底层原理：

2.2. 扩容过程：

总结

---

前言

在C++ 编程中，选择合适的数据结构对于优化程序性能和资源使用至关重要。标准模板库（STL）提供了多种容器，其中 vector 和 list 是两种常用的序列容器，它们各自具有独特的特性和适用场景。了解这些容器的内部机制和性能特点，可以帮助开发者根据具体需求做出更合理的选择。

一、vector和list的区别？

在 C++ 中，vector 和 list 都是标准模板库（STL）中的序列容器，用于存储元素集合。它们的主要区别如下：

1.1.存储方式：

• vector 是一个动态数组，它在内存中连续存储元素。这意味着元素在内存中是紧密排列的，类似于数组。
• list 是一个双向链表，每个元素由一个节点表示，节点之间通过指针连接。这种结构使得 list 在插入和删除操作中更加灵活。

1.2.随机访问：

• vector 支持随机访问，即可以通过下标直接访问任何元素，访问时间复杂度为 O(1)。
• list 不支持随机访问，访问特定元素需要从头或尾开始遍历，直到到达所需元素，访问时间复杂度为 O(n)。

1.3.插入和删除操作：

• vector 在插入和删除元素时，如果需要移动内存中的元素来保持连续性，可能会有较高的开销。特别是当容器大小需要增长时，可能需要分配新的内存并复制现有元素。
• list 在插入和删除元素时，只需要调整节点之间的指针，不需要移动其他元素，因此在这些操作上通常比 vector 更高效。

1.4.内存使用：

• vector 通常在内存使用上更紧凑，因为它是一个连续的存储块。
• list 由于每个元素都需要额外的空间来存储指针（至少两个指针，指向前一个和后一个元素），因此内存使用上不如 vector 紧凑。

1.5.容量和大小：

• vector 维护了 size（当前元素数量）和 capacity（容器能够容纳的最大元素数量）两个概念。当 size 达到 capacity 时，vector 会进行扩容操作。
• list 没有 capacity 的概念，它可以根据需要动态增长，不需要像 vector 那样进行扩容。

1.6.迭代器类型：

• vector 的迭代器支持随机访问，可以进行复杂的迭代操作，如 std::sort。
• list 的迭代器是双向迭代器，只能进行顺序访问，不支持随机访问。

1.7.用途：

• vector 适合于需要频繁随机访问元素的场景，如数值计算、游戏开发中的动态数组等。
• list 适合于需要频繁插入和删除元素的场景，如实现算法中的链表结构、维护一个有序的元素集合等。

---

二、vector 底层原理和扩容过程？

在 C++ 中，std::vector 是一种序列容器，它封装了动态大小的数组。以下是 std::vector 的一些底层原理和扩容过程：

2.1.底层原理：

• 动态数组：vector 内部使用一个连续的内存块来存储元素，这个内存块的大小可以通过 capacity() 方法获取。

• 迭代器：vector 提供了随机访问迭代器，这意味着你可以像使用普通数组一样通过下标访问元素。

• 内存管理：vector 负责管理其内部数组的内存分配和释放。当元素被添加到 vector 时，它会检查当前的容量是否足够。如果不够，它会进行扩容。

• 构造和析构：vector 会为每个元素调用构造函数，当元素被移除或 vector 被销毁时，会调用析构函数。

2.2. 扩容过程：

• 容量检查：当你尝试添加元素到 vector 时，如果当前 vector 的 size 等于 capacity，vector 需要扩容。

• 分配新内存：vector 会分配一个新的内存块，通常这个新内存块的大小是当前容量的两倍，或者按照某个特定的增长策略。

• 复制元素：vector 会使用拷贝或移动构造函数将现有元素从旧内存块复制到新内存块。

• 释放旧内存：一旦所有元素都被成功复制到新内存块，vector 会释放旧内存块。

• 更新迭代器和指针：由于内存块的地址发生了变化，所有指向旧内存块的迭代器和指针都会失效。因此，任何在扩容前获取的迭代器都需要在扩容后重新获取。

• 性能考虑：扩容是一个昂贵的操作，因为它涉及到分配新内存、复制元素和释放旧内存。因此，频繁的扩容可能会导致性能问题。

• 手动控制：可以通过调用 reserve() 方法来手动设置 vector 的容量，这样可以减少在添加元素时进行的扩容次数。

• 缩减容量：如果不再需要 vector 的额外容量，可以调用 shrink_to_fit() 方法来请求减少 vector 的内存使用，但这不保证容量会减少，因为标准库实现可能会忽略这个请求。

---

总结

vector 和 list 作为 C++ STL 中的两种序列容器，它们在数据存储、访问方式、操作效率等方面有着显著的差异。vector 提供了类似动态数组的功能，支持快速的随机访问，适合于需要频繁访问元素的场景。而 list 实现了双向链表，提供了高效的插入和删除操作，尤其适合于元素频繁变动的情况。开发者应根据实际应用的需求，权衡两者的优缺点，选择最合适的容器类型，以实现最优的性能和资源利用。