vector容量增长策略是什么 分析resize和reserve的性能影响

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 vec;
vec.resize(10); // 创建一个包含10个元素的vector，每个元素的值为0
vec.resize(15, 5); // 创建一个包含15个元素的vector，前10个元素的值不变，后5个元素的值为5

reserve主要用于预先分配vector的空间，避免在后续插入元素时频繁扩容。reserve不会改变vector的元素个数，只是改变capacity。

例如：

std::vector 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 
#include 
#include 

template 
class MyAllocator : public std::allocator {
public:
    using typename std::allocator::pointer;
    using typename std::allocator::size_type;

    MyAllocator() noexcept {}
    template  MyAllocator(const MyAllocator&) noexcept {}

    pointer allocate(size_type n) {
        std::cout << "Allocating " << n << " elements" << std::endl;
        return std::allocator::allocate(n);
    }

    void deallocate(pointer p, size_type n) {
        std::cout << "Deallocating " << n << " elements" << std::endl;
        std::allocator::deallocate(p, n);
    }
};

int main() {
    std::vector> 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类来实现类似的效果。