C++ STL 容器:vector

std::vector 是 C++ 中最常用的容器:一块连续内存上的动态数组,支持 O(1) 随机访问和尾部插入,还能自动扩容。学会它,你就告别了 C 里"手动 realloc + 维护 size"的苦日子。

1. 为什么用 vector 而不是数组

• 自动管理内存,push_back 超出容量时自动扩容。
• 自带 size(),不用像 C 数组那样单独记长度。
• 越界访问可用 at() 抛出异常,便于排查。
• 与 STL 算法无缝配合:sort、find、max_element 等。

2. 创建与基本操作

#include <vector>
using namespace std;

vector<int> v1;                 // 空 vector
vector<int> v2(5, 10);          // 5 个 10
vector<int> v3 = {1, 2, 3, 4};  // 初始化列表

v3.push_back(5);                // 尾部追加 → {1,2,3,4,5}
v3.pop_back();                  // 删除尾部 → {1,2,3,4}
v3.insert(v3.begin() + 1, 99);  // 中间插入,较慢
v3.erase(v3.begin() + 2);       // 删除第 3 个元素
int n = v3.size();              // 元素个数
bool empty = v3.empty();        // 是否为空
v3.clear();                     // 清空所有元素

3. 三种遍历方式

// 方式一:下标(需要随机访问时用)
for (size_t i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
}

// 方式二:范围 for(C++11,只读用)
for (int x : v) {
    cout << x << " ";
}

// 方式三:迭代器(通用,所有 STL 容器适用)
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

想在遍历中修改元素,范围 for 写成 for (int& x : v) 即可。

4. size 与 capacity 的区别

size() 是当前元素个数;capacity() 是已分配的内存能装多少个。扩容策略通常是"翻倍",频繁扩容会拷贝已有元素,开销不小:

vector<int> v;
v.reserve(1000);   // 提前预留,避免反复扩容
for (int i = 0; i < 1000; ++i) {
    v.push_back(i);   // 全程零扩容,速度飞快
}

5. 与算法库配合

#include <algorithm>

sort(v.begin(), v.end());                // 升序排序
sort(v.begin(), v.end(), greater<int>()); // 降序

auto it = find(v.begin(), v.end(), 42);
if (it != v.end()) {
    cout << "找到了,下标 " << (it - v.begin());
}

int mx = *max_element(v.begin(), v.end());
int sum = accumulate(v.begin(), v.end(), 0);

6. 避坑指南

💡 动手练习:用 vector 实现"约瑟夫环"或"合并两个有序数组",这两个经典题能让你把插入、删除、遍历、扩容全练一遍。