前言
一、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 实现了双向链表，提供了高效的插入和删除操作，尤其适合于元素频繁变动的情况。开发者应根据实际应用的需求，权衡两者的优缺点，选择最合适的容器类型，以实现最优的性能和资源利用。
