C++ STL 容器 vector 的动态扩容策略
C++ STL 容器 vector 的动态扩容策略
一、vector 简介
在 C++ 标准模板库（STL）中，vector 是一种非常常用的序列式容器。它能够像数组一样，高效地存储一系列相同类型的元素，并且支持随机访问，即可以通过下标 [] 快速访问容器中的任意元素。与普通数组相比，vector 更为灵活，它能够动态地管理内存，在运行时根据需要自动调整大小。这得益于其背后的动态扩容策略。
vector 的定义位于 <vector> 头文件中，其基本的声明方式如下：
#include <vector>
std::vector<int> v; // 声明一个存储 int 类型的 vector
二、内存管理基础
在深入探讨 vector 的动态扩容策略之前，我们先来回顾一下 C++ 中的内存管理相关知识。
（一）栈内存与堆内存
- 栈内存：栈是一种后进先出（LIFO）的数据结构，用于存储局部变量、函数参数等。栈内存的分配和释放由编译器自动管理，速度非常快。例如：
void func() {
int a = 10; // a 存储在栈内存中
}
当函数 func 结束时，变量 a 所占用的栈内存会自动被释放。
- 堆内存：堆是一块供程序动态分配内存的区域，其生命周期由程序员手动控制。在 C++ 中，通过
new关键字来分配堆内存，通过delete关键字来释放堆内存。例如：
int* ptr = new int(20); // 在堆上分配一个 int 类型的内存空间，并将其地址赋给 ptr
delete ptr; // 释放 ptr 所指向的堆内存
使用堆内存的优点是可以根据程序的运行时需求动态分配内存大小，但缺点是需要手动管理内存的释放，否则容易导致内存泄漏。
（二）连续内存与非连续内存
- 连续内存：连续内存意味着多个数据元素在内存地址上是紧密相邻的。例如数组，其元素在内存中是顺序排列的，这样的布局使得通过偏移量可以快速地访问任意元素，具有很高的访问效率。例如：
int arr[5] = {1, 2, 3, 4, 5};
// arr[0] 的地址假设为 0x1000，那么 arr[1] 的地址为 0x1004（假设 int 类型占 4 个字节）
- 非连续内存：非连续内存则是指数据元素在内存中的地址是分散的，它们通过指针等方式相互关联。例如链表，每个节点在内存中可能分布在不同的位置，通过指针来连接这些节点。虽然链表在插入和删除元素时具有较高的灵活性，但随机访问的效率较低，因为需要通过指针逐步遍历才能找到目标元素。
三、vector 的内存布局
vector 在内存中采用连续存储的方式，这一点与数组类似，但它又具备动态管理内存的能力。vector 内部主要包含三个指针：
_Myfirst：指向容器中第一个元素的内存地址。_Mylast：指向容器中最后一个元素之后的内存地址。_Myend：指向容器所能容纳的最大元素数量之后的内存地址，即当前已分配内存的末尾。
下面是一个简单示意 vector 内存布局的代码示例：
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3};
// 获取 vector 内部指针
auto first = &v[0];
auto last = first + v.size();
auto end = &v[0] + v.capacity();
std::cout << "First element address: " << first << std::endl;
std::cout << "Last element (after) address: " << last << std::endl;
std::cout << "End of allocated memory address: " << end << std::endl;
return 0;
}
在上述代码中，通过获取 vector 第一个元素的地址，并结合 size() 和 capacity() 方法，模拟出了 vector 内部三个指针所指向的位置。
vector 的大小（size）指的是当前容器中实际存储的元素个数，而容量（capacity）则表示当前已分配内存空间所能容纳的最大元素个数。例如，当 vector 的大小为 5 时，它实际存储了 5 个元素；而如果容量为 10，那么在不进行扩容的情况下，最多还能再存储 5 个元素。
四、动态扩容触发条件
vector 的动态扩容机制是在其内部元素数量（size）达到当前容量（capacity）时触发的。当这种情况发生时，vector 需要重新分配一块更大的内存空间，将原有的元素复制到新的内存空间中，并释放旧的内存空间。
下面通过一个简单的代码示例来观察动态扩容的触发：
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
for (int i = 0; i < 10; ++i) {
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
v.push_back(i);
}
return 0;
}
在上述代码中，通过循环向 vector 中插入元素，并在每次插入前输出 vector 的大小和容量。可以观察到，随着元素的不断插入，当 size 达到 capacity 时，capacity 会发生变化，即触发了动态扩容。
五、动态扩容策略
不同的 C++ 标准库实现对于 vector 的动态扩容策略可能会略有不同，但常见的策略是将当前容量翻倍。例如，当 vector 的容量为 4，且已经存储了 4 个元素时，再次插入一个元素就会触发扩容，此时新的容量可能会变为 8。
下面是一个模拟 vector 动态扩容翻倍策略的简单实现：
#include <iostream>
#include <memory>
template <typename T>
class MyVector {
private:
T* data;
size_t size_;
size_t capacity_;
public:
MyVector() : size_(0), capacity_(1) {
data = new T[capacity_];
}
~MyVector() {
delete[] data;
}
void push_back(const T& value) {
if (size_ == capacity_) {
capacity_ *= 2;
T* newData = new T[capacity_];
for (size_t i = 0; i < size_; ++i) {
newData[i] = data[i];
}
delete[] data;
data = newData;
}
data[size_++] = value;
}
T& operator[](size_t index) {
return data[index];
}
size_t size() const {
return size_;
}
size_t capacity() const {
return capacity_;
}
};
int main() {
MyVector<int> v;
for (int i = 0; i < 10; ++i) {
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
v.push_back(i);
}
return 0;
}
在上述代码中，MyVector 类模拟了 vector 的基本功能，包括动态扩容。当 size_ 等于 capacity_ 时，将 capacity_ 翻倍，并重新分配内存，复制原有的元素。
六、扩容带来的性能影响
虽然 vector 的动态扩容机制为其使用带来了很大的灵活性，但扩容操作本身会带来一定的性能开销。
（一）内存分配与释放开销
每次扩容时，都需要重新分配一块更大的内存空间，并释放原来的内存空间。内存分配和释放操作通常由操作系统的内存管理模块来完成，这些操作需要与操作系统内核进行交互，具有较高的时间复杂度。例如，在一些操作系统中，内存分配可能涉及到查找合适的空闲内存块、更新内存管理数据结构等操作。
（二）元素复制开销
除了内存分配和释放，还需要将原有的元素从旧的内存空间复制到新的内存空间。对于简单的数据类型（如 int、double 等），复制操作相对较快，因为它们只需要进行简单的字节拷贝。但对于复杂的数据类型（如自定义类对象），复制操作可能会涉及到调用类的拷贝构造函数，这可能会执行一些复杂的初始化逻辑，从而导致性能下降。
例如，假设有一个包含大量自定义类对象的 vector：
class MyClass {
public:
int data[1000];
MyClass() {
for (int i = 0; i < 1000; ++i) {
data[i] = i;
}
}
MyClass(const MyClass& other) {
for (int i = 0; i < 1000; ++i) {
data[i] = other.data[i];
}
}
};
int main() {
std::vector<MyClass> v;
for (int i = 0; i < 100; ++i) {
v.push_back(MyClass());
}
return 0;
}
在上述代码中，每次 vector 扩容时，都需要对 MyClass 对象进行复制，由于 MyClass 对象内部有较大的数组，复制操作会比较耗时。
（三）迭代器失效问题
动态扩容还会导致 vector 的迭代器失效。因为扩容时 vector 的内存地址发生了变化，原来指向旧内存空间的迭代器不再有效。例如：
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 可能触发扩容
// 此时 it 失效，使用 it 会导致未定义行为
std::cout << *it << std::endl;
return 0;
}
在上述代码中，当 push_back 操作可能触发扩容后，原来的迭代器 it 就失效了。如果继续使用 it，会导致未定义行为，可能引发程序崩溃等问题。
七、优化策略
为了减少 vector 动态扩容带来的性能影响，可以采取以下一些优化策略。
（一）预先分配足够的容量
通过 reserve 方法，可以预先分配足够的容量，避免在插入元素过程中频繁触发扩容。例如：
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
v.reserve(100); // 预先分配容纳 100 个元素的容量
for (int i = 0; i < 100; ++i) {
v.push_back(i);
}
return 0;
}
在上述代码中，通过 reserve(100) 预先分配了足够的容量，使得在插入 100 个元素的过程中不会触发扩容，从而提高了性能。
（二）使用 emplace_back 代替 push_back
push_back 方法在插入元素时，会先创建一个临时对象，然后将其复制或移动到 vector 中。而 emplace_back 方法则是直接在 vector 的末尾构造对象，避免了临时对象的创建和复制（或移动）操作，从而提高了性能。例如：
#include <iostream>
#include <vector>
#include <string>
class MyClass {
public:
std::string data;
MyClass(const std::string& str) : data(str) {
std::cout << "Constructor: " << data << std::endl;
}
MyClass(const MyClass& other) : data(other.data) {
std::cout << "Copy Constructor: " << data << std::endl;
}
};
int main() {
std::vector<MyClass> v;
v.emplace_back("Hello"); // 直接在 vector 末尾构造对象
// v.push_back(MyClass("Hello")); // 先创建临时对象，再复制或移动
return 0;
}
在上述代码中，emplace_back 直接在 vector 末尾构造 MyClass 对象，避免了 push_back 可能带来的临时对象创建和复制操作。
（三）批量插入元素
相比于逐个插入元素，批量插入元素可以减少扩容的次数。例如，使用 insert 方法一次性插入多个元素：
#include <iostream>
#include <vector>
#include <initializer_list>
int main() {
std::vector<int> v = {1, 2, 3};
std::initializer_list<int> list = {4, 5, 6};
v.insert(v.end(), list.begin(), list.end());
return 0;
}
在上述代码中，通过 insert 方法一次性插入了多个元素，相比于逐个调用 push_back，减少了扩容的次数，从而提高了性能。
八、总结
vector 作为 C++ STL 中常用的容器，其动态扩容策略在提供灵活性的同时，也带来了一定的性能开销。了解 vector 的内存布局、动态扩容触发条件和策略，以及其对性能的影响，并采取相应的优化策略，能够帮助我们在使用 vector 时编写更高效的代码。在实际应用中，需要根据具体的需求和场景，合理地选择和使用 vector，以达到性能和功能的平衡。同时，对于不同的 C++ 标准库实现，vector 的动态扩容策略可能会有所差异，在编写跨平台代码时需要注意兼容性问题。