vector

std::vector 是 C++ 标准库中最常用的顺序容器之一，可以理解为“可自动扩容的动态数组”。

它的元素在内存中连续存储，因此支持高效的随机访问（下标访问），并且对 CPU 缓存友好。在工程实践中，如果没有特殊理由，vector 往往是首选容器。

头文件与基本特征

使用 vector 时，需要包含头文件：

#include <vector>

vector 的常见特征如下：

特征	说明
底层结构	动态连续数组
内存布局	连续存储
随机访问	支持，O(1)
尾部插入	均摊 O(1)
中间插入删除	通常 O(n)，可能搬移元素
迭代器失效	扩容、插删时可能失效

基本用法

#include <vector>

int main() {
	std::vector<int> nums;

	nums.push_back(10);
	nums.push_back(20);
	nums.push_back(30);

	return 0;
}

访问与遍历

#include <iostream>
#include <vector>

int main() {
	std::vector<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);

	for (std::vector<int>::size_type i = 0; i < nums.size(); ++i) {
		std::cout << nums[i] << ' ';
	}
	std::cout << '\n';

	for (std::vector<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
		std::cout << *it << ' ';
	}
	std::cout << '\n';

	return 0;
}

operator[] 不做越界检查，at() 会做边界检查（越界会抛异常）。

常用成员函数

函数	作用
begin() / end()	获取首元素和尾后迭代器
size()	当前元素个数
capacity()	当前容量
empty()	判断是否为空
push_back()	尾部插入元素
pop_back()	删除尾元素
insert()	在指定位置插入
erase()	删除指定位置或区间
clear()	清空元素（容量通常不变）
resize()	调整元素个数
reserve()	预留容量，减少扩容次数

扩容与容量

vector 在空间不够时会重新分配更大的连续内存，再把原元素搬过去。这会带来两点影响：

1. 扩容当次可能开销较大。
2. 旧内存上的指针、引用、迭代器可能失效。

可以用 reserve() 预先申请容量，降低多次扩容成本：

#include <vector>

int main() {
	std::vector<int> nums;
	nums.reserve(1000);

	for (int i = 0; i < 1000; ++i) {
		nums.push_back(i);
	}

	return 0;
}

插入与删除示例

#include <vector>

int main() {
	std::vector<int> nums;
	nums.push_back(1);
	nums.push_back(3);
	nums.push_back(4);

	std::vector<int>::iterator it = nums.begin();
	++it;
	nums.insert(it, 2);  // 1 2 3 4

	it = nums.begin();
	it += 2;
	nums.erase(it);      // 删除 3，结果 1 2 4

	return 0;
}

使用注意

1. 中间位置频繁插删通常不适合 vector。
2. 保存了迭代器或指针时，要特别注意扩容后的失效问题。
3. 需要大量尾插时，优先考虑先 reserve()。
4. 想要栈结构，可直接用 vector + push_back/pop_back，或者使用适配器 stack。

何时优先选择 vector

1. 需要按下标随机访问元素。
2. 主要是尾部追加，较少中间插删。
3. 希望获得良好的遍历性能和缓存局部性。