vector — 动态数组

std::vector 是 C++ 最常用的容器，连续内存存储，缓存友好，是绝大多数场景的默认选择。

基本操作

#include <vector>

// 构造
std::vector<int> v1;                    // 空
std::vector<int> v2(5);                 // 5个0
std::vector<int> v3(5, 42);             // 5个42
std::vector<int> v4 = {1, 2, 3, 4, 5}; // 初始化列表
std::vector<int> v5(v4.begin(), v4.end()); // 从迭代器范围

// 访问
v4[0];          // 不检查边界，快
v4.at(0);       // 检查边界，越界抛 std::out_of_range
v4.front();     // 第一个元素
v4.back();      // 最后一个元素
v4.data();      // 底层数组指针（C 接口互操作）

// 修改
v4.push_back(6);           // 尾部追加（可能触发扩容）
v4.emplace_back(7);        // 原地构造（避免拷贝，推荐）
v4.pop_back();             // 删除最后一个
v4.insert(v4.begin(), 0);  // 头部插入（O(n)，慎用）
v4.erase(v4.begin());      // 删除第一个（O(n)）
v4.clear();                // 清空（不释放内存）

// 大小
v4.size();      // 元素数量
v4.capacity();  // 已分配容量
v4.empty();     // 是否为空

内存管理与扩容

// vector 扩容策略（通常是 2x 或 1.5x）
std::vector<int> v;
for (int i = 0; i < 10; ++i) {
    v.push_back(i);
    std::cout << "size=" << v.size()
              << " capacity=" << v.capacity() << "\n";
}
// size=1  capacity=1
// size=2  capacity=2
// size=3  capacity=4
// size=5  capacity=8
// size=9  capacity=16  ← 每次扩容 2x

// 预分配：避免多次扩容
v.reserve(1000);  // 预分配 1000 个元素的空间
// 之后 push_back 不会触发扩容（直到超过 1000）

// 收缩内存
v.shrink_to_fit();  // 释放多余容量（不保证）

// swap 技巧（C++11 前的收缩方法）
std::vector<int>().swap(v);  // 彻底释放内存

扩容时的迭代器失效

std::vector<int> v = {1, 2, 3};
auto it = v.begin();  // 保存迭代器

v.push_back(4);  // 可能触发扩容！
// it 可能已失效！不要再使用 it

// 安全做法：用索引代替迭代器
size_t idx = 0;
v.push_back(4);
auto& elem = v[idx];  // 通过索引访问，始终有效

// 什么操作会使迭代器失效？
// push_back / emplace_back：可能失效（扩容时）
// insert / erase：被操作位置之后的迭代器失效
// clear / resize：所有迭代器失效
// reserve：如果触发扩容，所有迭代器失效

高效使用技巧

// 1. emplace_back vs push_back
struct Point { int x, y; };

std::vector<Point> pts;
pts.push_back({1, 2});        // 构造临时对象，再移动
pts.emplace_back(1, 2);       // 直接在 vector 内构造，零拷贝

// 2. 批量删除（erase-remove 惯用法）
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// v = {1, 3, 4, 5}

// C++20 更简洁
std::erase(v, 2);
std::erase_if(v, [](int x) { return x % 2 == 0; });

// 3. 移动元素而非拷贝
std::vector<std::string> src = {"hello", "world"};
std::vector<std::string> dst;
dst.reserve(src.size());
std::move(src.begin(), src.end(), std::back_inserter(dst));
// src 中的字符串已被移走

// 4. 二维 vector
std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));
matrix[1][2] = 42;

// 更高效的二维数组（连续内存）
std::vector<int> flat(3 * 4, 0);
flat[1 * 4 + 2] = 42;  // matrix[1][2]

vector<bool> 的特殊性

// vector<bool> 是特化版本，每个 bool 只占 1 bit（节省内存）
// 但行为与普通 vector 不同！

std::vector<bool> vb = {true, false, true};
// vb[0] 返回的是代理对象，不是 bool&！
auto ref = vb[0];  // 类型是 vector<bool>::reference，不是 bool&

// 陷阱：不能取地址
// bool* p = &vb[0];  // 编译错误！

// 替代方案
std::vector<char> vc = {1, 0, 1};  // 用 char 代替 bool
std::bitset<64> bs;                 // 固定大小位集合
std::deque<bool> db;                // deque<bool> 没有特化

与 C 接口互操作

// vector 保证内存连续，可以直接传给 C 函数
std::vector<int> v = {1, 2, 3, 4, 5};

// C 函数接口
void c_func(int* arr, size_t n);
c_func(v.data(), v.size());
c_func(&v[0], v.size());  // 等价，但 data() 更安全（空 vector 时）

// 从 C 数组构造
int arr[] = {1, 2, 3};
std::vector<int> v2(arr, arr + 3);
std::vector<int> v3(std::begin(arr), std::end(arr));

关键认知

vector 是默认容器，连续内存对 CPU 缓存极其友好。用 reserve 预分配避免扩容，用 emplace_back 代替 push_back，注意扩容后迭代器失效。vector<bool> 是特化，行为特殊，谨慎使用。