101 std::vector（动态数组容器）
作者Lou Xiao, deepseek创建时间2025-04-02 17:04:54更新时间2025-04-02 17:04:54
版本：C++11 及以上
1. 概述
std::vector 是 C++标准库中的动态数组容器，属于序列容器（Sequence Container）。
特点：
- 动态扩容：自动管理内存，支持高效随机访问（O(1)）。
- 连续存储：元素在内存中连续存放，兼容 C 风格数组操作（如
data()）。 - 类型安全：模板类，支持任意类型（需满足可拷贝/可移动）。
2. 基本操作
2.1 头文件
2.2 声明与初始化
| 方法 | 示例 | 说明 |
|---|
| 默认构造 | vector<int> v1; | 空容器 |
| 指定大小 | vector<int> v2(5); | 5 个默认初始化的元素（int() 即 0） |
| 指定大小和初值 | vector<int> v3(5, 42); | 5 个值为 42 的元素 |
| 列表初始化 | vector<int> v4 = {1, 2, 3}; | C++11 引入 |
| 拷贝构造 | vector<int> v5(v4); | 深拷贝 |
| 迭代器范围 | vector<int> v6(v4.begin(), v4.end()); | 支持其他容器的迭代器 |
2.3 元素访问
| 方法 | 示例 | 说明 |
|---|
operator[] | v[0] = 10; | 不检查越界（更快） |
at() | v.at(0) = 10; | 检查越界（抛出 std::out_of_range） |
front() | int x = v.front(); | 首元素 |
back() | int y = v.back(); | 末元素 |
data() | int* p = v.data(); | 返回底层数组指针（C 风格兼容） |
3. 容量管理
3.1 容量查询
| 方法 | 说明 |
|---|
size() | 当前元素数量 |
capacity() | 当前分配的内存可容纳的元素数（≥ size()） |
empty() | 是否为空 |
3.2 调整容量
| 方法 | 说明 |
|---|
reserve(n) | 预分配至少 n 个元素的空间（避免频繁扩容） |
shrink_to_fit() | 请求释放多余容量（非强制） |
resize(n) | 调整 size()，新增元素默认初始化 |
resize(n, val) | 调整 size()，新增元素初始化为 val |
4. 修改操作
4.1 添加元素
| 方法 | 示例 | 时间复杂度 | 说明 |
|---|
push_back() | v.push_back(10); | 均摊 O(1) | 尾部插入 |
emplace_back() | v.emplace_back(10); | 均摊 O(1) | 直接构造（C++11 起，避免拷贝） |
insert() | v.insert(v.begin(), 42); | O(n) | 指定位置插入 |
emplace() | v.emplace(v.begin(), 42); | O(n) | 直接构造到指定位置 |
4.2 删除元素
| 方法 | 示例 | 时间复杂度 | 说明 |
|---|
pop_back() | v.pop_back(); | O(1) | 删除尾部元素 |
erase() | v.erase(v.begin()); | O(n) | 删除指定位置或区间 |
clear() | v.clear(); | O(n) | 清空容器（不释放内存） |
5. 迭代器与遍历
5.1 迭代器类型
| 迭代器 | 示例 |
|---|
begin()/end() | for (auto it = v.begin(); it != v.end(); ++it) |
cbegin()/cend() | 常量迭代器（C++11 起） |
rbegin()/rend() | 反向迭代器 |
5.2 遍历方式
| 1 |
// 1. 范围 for 循环（C++11 起） |
| 2 |
for (const auto& x : v) { ... } |
| 3 |
|
| 4 |
// 2. 下标遍历 |
| 5 |
for (size_t i = 0; i < v.size(); ++i) { ... } |
| 6 |
|
| 7 |
// 3. 迭代器遍历 |
| 8 |
for (auto it = v.begin(); it != v.end(); ++it) { ... } |
6. 其他特性
6.1 移动语义（C++11）
std::vector 支持移动构造和移动赋值，避免深拷贝：
cpp
vector<int> v1 = {1, 2, 3};
vector<int> v2 = std::move(v1); // v1 变为空
6.2 异常安全性
- 基本操作提供强异常保证（如
push_back 失败时容器状态不变）。
6.3 与 C 数组互操作
| 1 |
int arr[] = {1, 2, 3}; |
| 2 |
vector<int> v(arr, arr + 3); // 通过指针范围构造 |
| 3 |
|
| 4 |
// vector 转 C 数组 |
| 5 |
int* p = v.data(); |
7. 性能分析
| 操作 | 时间复杂度 |
|---|
| 随机访问 | O(1) |
| 尾部插入/删除 | 均摊 O(1) |
| 头部或中间插入/删除 | O(n) |
| 扩容 | O(n)（分配新内存 + 拷贝） |
8. 最佳实践
- 预分配空间：已知大小时用
reserve() 减少扩容开销。 - 优先用
emplace_back：避免临时对象拷贝（尤其对复杂类型）。 - 避免频繁插入/删除中间元素：如需高频操作，考虑
std::list 或 std::deque。
9. 完整示例
| 1 |
#include <vector> |
| 2 |
#include <iostream> |
| 3 |
|
| 4 |
int main() { |
| 5 |
std::vector<int> v = {1, 2, 3}; |
| 6 |
v.reserve(10); // 预分配空间 |
| 7 |
v.emplace_back(4); // 直接构造 |
| 8 |
|
| 9 |
for (const auto& x : v) { |
| 10 |
std::cout << x << " "; // 输出: 1 2 3 4 |
| 11 |
} |
| 12 |
} |
附：与类似容器的对比
| 容器 | 特点 |
|---|
std::array | 固定大小，栈上分配 |
std::deque | 双端队列，支持高效头尾插入 |
std::list | 双向链表，支持 O(1) 任意位置插入 |
附录：std::vector 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|
push_back | 在末尾添加元素 | void push_back(const T& value); | std::vector<int> v; v.push_back(42); | 元素会被拷贝或移动到容器末尾，可能导致扩容。 |
emplace_back | 直接在末尾构造元素（避免拷贝） | template<class... Args> void emplace_back(Args&&... args); | std::vector<std::string> v; v.emplace_back("Hello", 3); | 更高效，直接在容器内存中构造元素（C++11 引入）。 |
size | 返回元素数量 | size_type size() const noexcept; | std::vector<int> v{1, 2}; std::cout << v.size(); // 输出 2 | 时间复杂度 O(1)。 |
capacity | 返回当前分配的存储容量 | size_type capacity() const noexcept; | std::vector<int> v; v.reserve(100); std::cout << v.capacity(); // 输出 100 | 容量 ≥ size()，扩容策略由实现决定。 |
reserve | 预分配存储空间 | void reserve(size_type new_cap); | std::vector<int> v; v.reserve(100); | 避免多次扩容，但不会改变 size()。 |
operator[] | 通过下标访问元素（无边界检查） | reference operator[](size_type pos); | std::vector<int> v{1, 2}; std::cout << v[1]; // 输出 2 | 越界行为未定义（通常崩溃）。 |
at | 通过下标访问元素（有边界检查） | reference at(size_type pos); | std::vector<int> v{1, 2}; std::cout << v.at(1); // 输出 2 | 越界抛出 std::out_of_range 异常。 |
front | 访问第一个元素 | reference front(); | std::vector<int> v{1, 2}; std::cout << v.front(); // 输出 1 | 空容器调用此方法行为未定义。 |
back | 访问最后一个元素 | reference back(); | std::vector<int> v{1, 2}; std::cout << v.back(); // 输出 2 | 空容器调用此方法行为未定义。 |
clear | 清空所有元素 | void clear() noexcept; | std::vector<int> v{1, 2}; v.clear(); // v.size() == 0 | 不释放内存（capacity() 不变）。 |
insert | 在指定位置插入元素 | iterator insert(const_iterator pos, const T& value); | std::vector<int> v{1, 3}; v.insert(v.begin() + 1, 2); // v = {1, 2, 3} | 可能导致迭代器失效，时间复杂度 O(n)。 |
emplace | 在指定位置直接构造元素 | template<class... Args> iterator emplace(const_iterator pos, Args&&... args); | std::vector<std::string> v{"a", "c"}; v.emplace(v.begin() + 1, "b"); | 避免拷贝，效率高于 insert（C++11 引入）。 |
erase | 删除指定位置的元素 | iterator erase(const_iterator pos); | std::vector<int> v{1, 2, 3}; v.erase(v.begin() + 1); // v = {1, 3} | 返回指向下一个元素的迭代器，时间复杂度 O(n)。 |
pop_back | 删除末尾元素 | void pop_back(); | std::vector<int> v{1, 2}; v.pop_back(); // v = {1} | 空容器调用此方法行为未定义。 |
resize | 调整容器大小 | void resize(size_type count, T value = T()); | std::vector<int> v{1, 2}; v.resize(4, 0); // v = {1, 2, 0, 0} | 若 count > size()，填充默认值或指定值；否则截断。 |
swap | 交换两个容器的内容 | void swap(std::vector& other) noexcept; | std::vector<int> v1{1, 2}, v2{3}; v1.swap(v2); // v1 = {3}, v2 = {1, 2} | 高效（仅交换指针），不影响迭代器（指向原元素）。 |
data | 返回指向底层数组的指针 | T* data() noexcept; | std::vector<int> v{1, 2}; int* p = v.data(); // p[0] = 1 | 可用于与 C 风格 API 交互。 |
关键说明：
- 迭代器失效：多数修改操作（如
push_back、insert、erase）可能导致迭代器失效。 - 时间复杂度：
- 随机访问（[]、at）：O(1)
- 插入/删除中间元素：O(n)
- 末尾插入/删除（push_back/pop_back）：平均 O(1) - 异常安全：基本操作提供强异常保证（如
push_back 失败时容器状态不变）。