vector容量增长策略通常采用倍增方式以减少内存分配次数，提升性能。1.倍增策略通过每次将容量翻倍，使内存分配次数从o(n)降至o(log n)，降低时间开销；2.resize改变元素个数并可能触发扩容，reserve仅提升容量以避免频繁分配；3.选择上，需初始化元素个数用resize，预分配空间用reserve；4.自定义策略可通过实现allocator或自定义vector类完成，但需权衡空间与性能。合理使用resize和reserve并理解其机制，有助于编写高效c++代码。
Vector容量增长策略关乎性能，简单来说，就是它在空间不够用的时候，怎么分配新的空间。理解它，能帮你写出更高效的代码，避免不必要的性能损耗。
Vector容量增长策略通常是成倍增长，比如每次容量翻倍。这种策略在大多数情况下比较均衡，能避免频繁的内存分配。但具体实现会因编译器和标准库版本而异。
resize和reserve是两个关键的函数，它们分别影响着vector的size（实际元素个数）和capacity（可容纳元素总数）。
resize会改变vector的size，如果新的size大于capacity，会自动触发扩容。这会涉及内存分配和元素拷贝，开销较大。reserve只改变capacity，不影响size。如果你预先知道vector需要存储多少个元素，使用reserve可以避免多次扩容，显著提升性能。
为什么vector要采用倍增策略，而不是每次增加固定大小？
倍增策略是时间复杂度和空间复杂度之间的一种折衷。
假设我们每次增加固定大小的容量，比如每次增加1个元素的大小。如果我们要存储n个元素，那么需要进行n次内存分配。每次分配的开销虽然小，但频繁的分配会累积成很大的开销。
而倍增策略，比如每次容量翻倍。如果要存储n个元素，那么最多需要进行log2(n)次内存分配。虽然每次分配的空间可能比较大，但分配次数大大减少，总体的平均时间复杂度是O(n)。
从空间利用率来看，倍增策略可能会浪费一些空间。因为最后一次分配的空间可能远大于实际需要的空间。但相比于频繁分配带来的时间开销，这种空间上的浪费通常是可以接受的。
当然，在某些特定场景下，固定大小增长可能更合适。比如，我们确切知道vector需要存储多少个元素，并且这个数量非常大。这时，可以预先分配足够的空间，避免倍增策略带来的空间浪费。
resize和reserve的具体使用场景是什么？如何选择？
resize主要用于初始化vector，或者在vector已经存在一些元素的情况下，改变vector的元素个数。resize可以接受一个可选的参数，用于指定新增加的元素的初始值。
例如：
std::vector<int> vec; vec.resize(10); // 创建一个包含10个元素的vector，每个元素的值为0 vec.resize(15, 5); // 创建一个包含15个元素的vector，前10个元素的值不变，后5个元素的值为5
reserve主要用于预先分配vector的空间，避免在后续插入元素时频繁扩容。reserve不会改变vector的元素个数，只是改变capacity。
例如：
std::vector<int> vec; vec.reserve(100); // 预先分配100个元素的空间，但vector仍然是空的 for (int i = 0; i < 100; ++i) { vec.push_back(i); // 插入元素，不会触发扩容 }
选择resize还是reserve，关键在于你是否需要改变vector的元素个数，以及是否知道vector需要存储多少个元素。
如果你需要改变vector的元素个数，并且需要指定新增加的元素的初始值，那么使用resize。如果你只是想预先分配空间，避免频繁扩容，那么使用reserve。
通常情况下，如果可以预先知道vector需要存储多少个元素，那么优先使用reserve。这可以显著提升性能。
如何自定义vector的容量增长策略？
C++标准库并没有直接提供自定义vector容量增长策略的接口。但是，我们可以通过一些间接的方式来实现类似的效果。
一种方式是自定义allocator。allocator负责vector的内存分配和释放。通过自定义allocator，我们可以控制vector的内存分配行为，从而间接控制容量增长策略。
例如：
#include <iostream> #include <vector> #include <memory> template <typename T> class MyAllocator : public std::allocator<T> { public: using typename std::allocator<T>::pointer; using typename std::allocator<T>::size_type; MyAllocator() noexcept {} template <typename U> MyAllocator(const MyAllocator<U>&) noexcept {} pointer allocate(size_type n) { std::cout << "Allocating " << n << " elements" << std::endl; return std::allocator<T>::allocate(n); } void deallocate(pointer p, size_type n) { std::cout << "Deallocating " << n << " elements" << std::endl; std::allocator<T>::deallocate(p, n); } }; int main() { std::vector<int, MyAllocator<int>> vec; vec.reserve(10); for (int i = 0; i < 10; ++i) { vec.push_back(i); } return 0; }
另一种方式是自己实现一个类似的vector类。在这个类中，我们可以完全控制容量增长策略。
这种方式比较复杂，需要自己处理内存分配、元素拷贝等细节。但它可以提供最大的灵活性。
需要注意的是，自定义容量增长策略需要谨慎。不合理的策略可能会导致性能下降。
总而言之，理解vector的容量增长策略，并合理使用resize和reserve，是编写高性能C++代码的关键。虽然C++标准库没有直接提供自定义容量增长策略的接口，但我们可以通过自定义allocator或者自己实现vector类来实现类似的效果。
