C++ vector容器详解：动态数组原理与高效使用指南

1. vector容器概述

vector是C++标准模板库(STL)中最常用的序列容器之一，它本质上是一个动态数组，能够根据需要在运行时自动调整大小。作为一名C++开发者，我几乎在每个项目中都会用到vector，因为它完美平衡了性能与易用性。

1.1 核心特性解析

vector的核心特点可以概括为以下几点：

1. 动态扩容机制：与普通数组不同，vector的容量可以自动增长。当现有空间不足以容纳新元素时，vector会自动分配更大的内存空间（通常是当前容量的1.5或2倍），然后将原有元素移动到新空间。

2. 连续内存布局：所有元素存储在连续的内存块中，这使得vector支持随机访问（通过下标操作符[]），访问时间复杂度为O(1)。

3. 高效的尾部操作：在vector末尾添加(push_back)或删除(pop_back)元素的时间复杂度为平摊O(1)，因为不需要移动其他元素。

4. 较低效的中间操作：在vector中间插入或删除元素需要移动后续所有元素，时间复杂度为O(n)。

1.2 底层实现原理

vector的底层通常通过三个指针实现：

• _start：指向内存块起始位置
• _finish：指向最后一个有效元素的下一个位置
• _end_of_storage：指向内存块末尾

这种设计使得size() = _finish - _start，capacity() = _end_of_storage - _start。当_finish == _end_of_storage时，说明需要扩容。

2. vector的基本操作

2.1 构造函数详解

vector提供了多种构造函数，满足不同初始化需求：

cpp复制// 1. 默认构造 - 创建空vector
vector<int> v1;

// 2. 指定大小和初始值 - 创建含10个2的vector
vector<int> v2(10, 2);

// 3. 拷贝构造 - 创建v2的副本
vector<int> v3(v2);

// 4. 迭代器范围构造 - 复制v2的内容
vector<int> v4(v2.begin(), v2.end());

// 5. 列表初始化 (C++11)
vector<int> v5 = {1, 2, 3, 4, 5};

注意：使用迭代器范围构造时，源容器可以是不同类型的容器，只要元素类型兼容即可。例如可以从string构造vector。

2.2 空间管理函数

vector提供了一组函数来管理其容量和大小：

cpp复制vector<int> v(5, 1);  // 5个1

cout << v.size();     // 5 - 当前元素数量
cout << v.capacity(); // 取决于实现，可能>=5

v.reserve(20);        // 预分配空间，避免多次扩容
cout << v.capacity(); // 至少20

v.resize(10);         // 将大小改为10，新增元素默认初始化为0
v.resize(15, -1);     // 大小改为15，新增元素初始化为-1
v.resize(3);          // 缩小到3个元素

cout << v.empty();    // 0 (false) - 检查是否为空

扩容策略：大多数实现采用几何增长策略（如每次扩容为当前容量的1.5或2倍），这使得n次push_back操作的平摊时间复杂度为O(n)。

3. vector的元素访问

3.1 下标访问

vector重载了[]运算符，支持类似数组的访问方式：

cpp复制vector<int> v = {1, 2, 3, 4, 5};

// 随机访问
cout << v[0];    // 1
v[1] = 10;       // 修改元素

// 遍历
for(size_t i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
}

注意：[]运算符不进行边界检查，访问越界会导致未定义行为。如果需要安全访问，可以使用at()成员函数，它在越界时会抛出std::out_of_range异常。

3.2 迭代器访问

vector支持多种迭代器，使得遍历更加灵活：

cpp复制vector<int> v = {1, 2, 3, 4, 5};

// 1. 正向迭代器
for(auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

// 2. 反向迭代器
for(auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " ";
}

// 3. 基于范围的for循环 (C++11)
for(int num : v) {
    cout << num << " ";
}

// 4. 常量迭代器 (避免意外修改)
for(auto cit = v.cbegin(); cit != v.cend(); ++cit) {
    cout << *cit << " ";
}

迭代器类型：

• iterator：可读写迭代器
• const_iterator：只读迭代器
• reverse_iterator：反向迭代器
• const_reverse_iterator：只读反向迭代器

4. vector的增删操作

4.1 尾部操作

尾部操作是vector最高效的修改操作：

cpp复制vector<int> v;

// 尾部插入
v.push_back(1);
v.push_back(2);
v.push_back(3);

// 尾部删除
v.pop_back();  // 删除3
v.pop_back();  // 删除2

// C++11引入的更高效插入方式
v.emplace_back(4);  // 直接在尾部构造元素，避免拷贝

4.2 任意位置操作

在vector中间插入或删除元素需要移动后续元素：

cpp复制vector<int> v = {1, 2, 3, 4, 5};

// 在第二个位置插入10
v.insert(v.begin() + 1, 10);  // v: 1,10,2,3,4,5

// 在第三个位置插入3个-1
v.insert(v.begin() + 2, 3, -1); // v: 1,10,-1,-1,-1,2,3,4,5

// 删除第三个元素
v.erase(v.begin() + 2);  // v: 1,10,-1,-1,2,3,4,5

// 删除范围 [begin+1, begin+4)
v.erase(v.begin() + 1, v.begin() + 4); // v: 1,2,3,4,5

性能考虑：中间插入/删除操作的时间复杂度为O(n)，因为需要移动后续所有元素。如果需要频繁在序列中间操作，考虑使用list或deque。

4.3 查找操作

vector本身没有find成员函数，但可以使用算法库中的find：

cpp复制#include <algorithm>

vector<int> v = {1, 2, 3, 4, 5};

// 查找值为3的元素
auto it = find(v.begin(), v.end(), 3);

if(it != v.end()) {
    cout << "Found at position: " << it - v.begin();
    v.erase(it);  // 删除找到的元素
} else {
    cout << "Not found";
}

对于有序vector，可以使用binary_search等算法实现更高效的O(log n)查找。

5. vector的高级特性

5.1 迭代器失效问题

迭代器失效是vector使用中最容易出错的问题之一，主要发生在以下场景：

扩容导致的失效：

cpp复制vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 可能导致扩容
// it可能失效，不能再使用

删除导致的失效：

cpp复制vector<int> v = {1, 2, 3, 4};
auto it = v.begin() + 1;
v.erase(it);     // 删除元素2
// it已失效，但it+1可能仍然有效(实现依赖)

解决方案：

1. 在修改操作后重新获取迭代器
2. 使用erase的返回值更新迭代器：

cpp复制it = v.erase(it);  // erase返回下一个有效迭代器

5.2 容量管理技巧

shrink_to_fit (C++11)：

cpp复制vector<int> v(1000);
v.resize(10);
v.shrink_to_fit();  // 请求释放未使用的内存

swap技巧：

cpp复制vector<int> v(1000);
v.resize(10);
vector<int>(v).swap(v);  // 创建一个临时副本并交换

reserve优化：

cpp复制vector<int> v;
v.reserve(1000);  // 预分配空间，避免多次扩容
for(int i = 0; i < 1000; ++i) {
    v.push_back(i);
}

5.3 自定义分配器

vector允许指定自定义内存分配器：

cpp复制#include <memory>

vector<int, MyAllocator<int>> v;

这在特殊场景（如嵌入式系统）中很有用，可以实现内存池等优化策略。

6. vector的性能优化

6.1 避免不必要的拷贝

使用emplace_back代替push_back：

cpp复制vector<pair<int, string>> v;
v.emplace_back(1, "test");  // 直接构造，避免临时对象

使用移动语义(C++11)：

cpp复制vector<string> v;
string s = "large string";
v.push_back(std::move(s));  // 移动而非拷贝

6.2 批量操作优化

使用assign进行批量赋值：

cpp复制vector<int> v;
v.assign(100, 1);  // 100个1，比循环push_back高效

使用insert范围版本：

cpp复制vector<int> v1, v2;
// ...填充v2...
v1.insert(v1.end(), v2.begin(), v2.end());  // 批量插入

6.3 选择合适的数据结构

虽然vector很强大，但并非所有场景都适用：

• 需要频繁在头部插入/删除：考虑deque
• 需要频繁在中间插入/删除：考虑list
• 元素非常大且需要稳定引用：考虑list或deque

7. vector与其他容器的比较

7.1 vector vs array

7.2 vector vs deque

7.3 vector vs list

在实际开发中，我通常会优先考虑vector，除非有明确的理由选择其他容器。vector的连续内存特性使其对CPU缓存更友好，在现代处理器架构上往往能提供最佳的实际性能。