Vector容器详解

Vector是C++标准模板库(STL)中最常用的序列容器，实现了动态数组的功能。其核心特性包括：

1. 动态扩容：当元素超出当前容量时自动分配更大内存
2. 随机访问：支持$O(1)$时间复杂度的下标访问
3. 连续存储：元素在内存中连续排列

基本操作

#include <vector>
using namespace std;

// 初始化
vector<int> v1;                  // 空向量
vector<int> v2(5, 10);           // 5个元素，每个值为10
vector<int> v3 = {1, 3, 5, 7};   // 初始化列表

// 元素访问
int first = v3[0];               // 下标访问（不检查边界）
int last = v3.back();            // 末尾元素
int val = v3.at(2);              // 带边界检查的访问

// 修改操作
v3.push_back(9);                 // 尾部插入
v3.pop_back();                   // 尾部删除
v3.insert(v3.begin() + 1, 2);    // 指定位置插入

内存管理特性

$$ \text{容量(capacity)} \geq \text{大小(size)} $$

v3.reserve(20);      // 预分配空间（避免多次扩容）
v3.shrink_to_fit();  // 释放多余内存

cout << "Size: " << v3.size();         // 元素数量
cout << "Capacity: " << v3.capacity(); // 实际分配的内存大小

迭代器使用

// 正向遍历
for(auto it = v3.begin(); it != v3.end(); ++it) {
    cout << *it << " ";
}

// 反向遍历
for(auto rit = v3.rbegin(); rit != v3.rend(); ++rit) {
    cout << *rit << " ";
}

// C++11范围遍历
for(int num : v3) {
    cout << num << " ";
}

效率分析

操作	时间复杂度
push_back()	$O(1)$*
insert()	$O(n)$
erase()	$O(n)$
operator[]	$O(1)$

*注：尾部插入平均$O(1)$，扩容时$O(n)$

典型应用场景

1. 替代原始数组
2. 需要动态调整大小的集合
3. 作为其他容器的底层实现

// 二维向量示例
vector<vector<int>> matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
cout << matrix[1][2]; // 输出6

1. 插入/删除中间元素会导致后续元素移动
2. 扩容时迭代器可能失效
3. 频繁插入建议使用reserve()预分配空间