vector扩容
ector 是 C++ 标准模板库（STL）中的一个非常重要的容器，用于存储一个动态数组。它的底层实现通常包括三个主要部分：一个连续的存储空间、一个指向这个存储空间起始位置的迭代器（或指针）、以及一个记录当前vector中元素个数的计数器。下面详细解释这些组成部分：
- 连续的存储空间：
vector使用连续的内存空间来存储元素，这意味着它可以快速地通过索引来访问元素（时间复杂度为O(1)）。- 当
vector的元素数量增加并超出其当前分配的存储容量时，它会重新分配一个更大的连续内存块，并将旧数据复制（或移动）到这个新的内存块中。这个过程称为“扩容”。
- 迭代器或指针：
vector通常通过一个迭代器（在内部实现中可能是一个简单的指针）来访问其元素。这个迭代器指向vector的第一个元素（或第一个元素之前的位置，如果vector为空）。- 通过这个迭代器，可以遍历
vector中的所有元素，或者访问特定位置的元素。
- 元素计数器：
vector还维护一个计数器，用于记录当前存储在vector中的元素数量。这个计数器与vector的容量（即其分配的内存大小）不同。容量是vector可以存储的最大元素数量，而元素计数器是当前实际存储的元素数量。
- 扩容策略：
- 当
vector需要增加新元素而当前容量不足时，它会执行扩容操作。扩容的具体策略（如扩容多少倍）在不同的实现中可能有所不同，但常见的做法是将容量加倍或增加固定的大小（如增加当前容量的50%）。 - 扩容是一个相对昂贵的操作，因为它涉及到内存的重新分配和数据的复制（或移动）。因此，频繁地向
vector添加元素可能会导致性能问题。
- 当
- 其他特性和成员函数：
vector提供了丰富的成员函数来支持各种操作，如push_back（在vector末尾添加一个元素）、pop_back（移除vector末尾的元素）、insert（在指定位置插入一个或多个元素）、erase（移除指定位置的元素）等。- 它还提供了迭代器访问接口，允许使用范围for循环等现代C++特性来遍历
vector。
- 扩容策略：
- 每次扩一个：如果
vector每次在需要扩容时都只增加一个元素的存储空间，那么在最坏的情况下（即每次添加都导致扩容），push_back的时间复杂度将接近O(n^2)，因为每次添加元素都可能需要复制或移动所有已存在的元素。 - 扩两倍：在实际应用中，更常见的策略是每次将容量加倍。这种策略下，
push_back操作的平均时间复杂度可以降低到接近O(1)，尽管在最坏的情况下（即每次添加都恰好导致扩容）仍然是O(n)。但由于扩容间隔较长，平均下来每次操作的时间成本较低。
- 每次扩一个：如果
- 平均时间复杂度的计算：
- 假设初始容量为
c，每次扩容都将容量加倍。那么，在第一次扩容之前，可以进行c次push_back操作而不需要重新分配内存。第一次扩容后，容量变为2c，接下来可以进行c次额外的push_back操作。这个过程会不断重复，每次扩容后都能支持额外的c次操作，直到达到某个总的操作次数N。 - 假设进行了
k次扩容操作，那么总的操作次数N可以表示为N = c + c + c + ... + c + (剩余的操作次数)，其中加号前的每个c代表一次扩容前可以进行的操作次数，而最后一项“剩余的操作次数”可能小于c。 - 注意到，每次扩容都伴随着一次内存分配和数据复制（或移动），这些操作的时间复杂度是O(n)，其中
n是扩容前vector中的元素数量。但由于扩容次数k与总操作次数N成对数关系（k = log2(N/c + 1)，假设初始容量c为常数），因此平均每次push_back操作的时间复杂度可以视为O(1)的常数因子乘以对数因子，即O(log N)。但在日常讨论中，我们常说其平均时间复杂度接近O(1)，因为对数因子增长非常缓慢，对于大多数实际应用场景来说，可以认为其影响是“平均”的且可忽略的。
- 假设初始容量为