第2章 vector 容器详解

vector（动态数组）是 STL 中最常用的序列式容器，底层基于连续的内存空间实现，支持随机访问，可动态调整大小，兼顾了数组的高效访问和链表的灵活扩容，是日常开发和算法题中使用频率最高的容器之一，与关联式容器（set、map）形成互补。

---

🎯 本章学习目标

学完本章，你将能够：

1. 理解 vector 的底层结构（连续内存 + 动态扩容）
2. 熟练使用 vector 的定义、插入、删除、访问等基本操作
3. 掌握 vector 三种遍历方式（下标、迭代器、范围 for）
4. 理解 vector 的扩容机制及其性能影响
5. 区分 size 和 capacity 的概念
6. 掌握 reserve 和 resize 的区别与使用场景
7. 了解 vector 迭代器失效的几种情况
8. 根据场景判断是否应该使用 vector
9. 熟练使用 vector 配合 algorithm 库进行排序、查找等操作

---

🗺️ 本章知识图谱

vector 动态数组
├── 核心特性
│   ├── 连续内存空间
│   ├── 随机访问 O(1)
│   ├── 动态扩容（默认2倍）
│   └── 尾插高效、中间插入低效
├── 基本用法
│   ├── 定义与初始化
│   ├── 插入操作（push_back、insert）
│   ├── 删除操作（pop_back、erase、clear）
│   ├── 访问元素（[]、at、迭代器）
│   └── 遍历方式（三种）
├── 进阶原理
│   ├── 扩容机制
│   ├── size vs capacity
│   ├── reserve 与 resize
│   └── 迭代器失效
├── 与其他容器对比
│   ├── vs list
│   ├── vs deque
│   └── vs set/map
└── 适用场景与选型

---

一、vector 核心特性

🍎 生活比喻：vector 就像一辆公交车——车厢里的座位是连续排列的（连续内存），你可以直接走到第 5 个座位（随机访问 O(1)），但如果要在中间加座位，后面的人都得往后挪（中间插入 O(n)）。人太多坐不下时，司机会换一辆更大的公交车（扩容）。

1. 存储结构：连续内存空间，与普通数组类似，但支持动态扩容（自动分配更大的内存，拷贝原有数据）；
2. 访问效率：支持随机访问（通过下标访问），时间复杂度 O(1)，远高于 list、set 等容器；
3. 插入删除：尾部插入/删除效率极高（O(1)），中间插入/删除效率较低（需移动后续元素，O(n)）；
4. 灵活性：可动态调整大小，无需手动管理内存，支持各种算法（排序、查找等）。

vector 与 set、map 的核心区别：vector 是「序列式容器」，按插入顺序存储，不自动去重、不排序；set、map 是「关联式容器」，按关键字存储，支持去重、排序和快速查找。

🔥 高频考点：vector 的随机访问特性、尾插 O(1)、中间插入 O(n)，这些时间复杂度经常出现在选择题中。

---

二、vector 基础用法（完整代码）

#include <iostream>
#include <vector>  // vector的头文件
#include <algorithm>  // 用于排序等算法
using namespace std;

int main() {
    // 1. 定义vector（多种方式）
    vector<int> v1;  // 空vector，默认初始容量
    vector<int> v2(5, 0);  // 容量为5，所有元素初始化为0
    vector<int> v3(v2.begin(), v2.end());  // 拷贝v2的所有元素
    vector<int> v4 = {1, 2, 3, 4, 5};  // 初始化列表（C++11及以上）
    
    // 2. 插入元素
    v1.push_back(1);  // 尾部插入（推荐，效率高）
    v1.push_back(2);
    v1.insert(v1.begin() + 1, 3);  // 中间插入（在索引1的位置插入3）
    // 此时v1：[1, 3, 2]
    
    // 3. 访问元素（三种方式）
    cout << "通过下标访问v1[1]：" << v1[1] << endl;  // 输出：3（无越界检查）
    cout << "通过at访问v1[2]：" << v1.at(2) << endl;  // 输出：2（有越界检查，越界抛异常）
    cout << "通过迭代器访问：";
    for (auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;  // 输出：1 3 2
    
    // 4. 修改元素
    v1[0] = 10;  // 下标修改
    v1.at(2) = 20;  // at修改
    // 此时v1：[10, 3, 20]
    
    // 5. 删除元素
    v1.pop_back();  // 尾部删除（效率高）
    v1.erase(v1.begin() + 1);  // 中间删除（删除索引1的元素）
    // 此时v1：[10]
    
    // 6. 常用操作
    cout << "\nvector大小（元素个数）：" << v1.size() << endl;  // 输出：1
    cout << "vector容量（可存储元素个数）：" << v1.capacity() << endl;  // 容量 >= 大小
    v1.resize(3, 0);  // 调整大小为3，新增元素初始化为0（此时v1：[10, 0, 0]）
    if (v1.empty()) {
        cout << "vector为空" << endl;
    } else {
        cout << "vector非空" << endl;
    }
    
    // 7. 排序（需包含<algorithm>头文件）
    vector<int> v5 = {3, 1, 4, 1, 5};
    sort(v5.begin(), v5.end());  // 升序排序
    cout << "\n排序后v5：";
    for (auto x : v5) {
        cout << x << " ";
    }
    cout << endl;  // 输出：1 1 3 4 5
    
    // 8. 清空与释放内存
    v5.clear();  // 清空元素（大小变为0，容量不变）
    vector<int>().swap(v5);  // 释放多余容量（容量变为0）
    
    return 0;
}

💡 小技巧：遍历 vector 推荐使用范围 for（for (auto x : v)），简洁又安全；如果需要修改元素，用引用 for (auto& x : v)。

---

三、vector 的扩容机制

vector 的底层是连续内存，当插入元素导致容量不足时，会自动扩容，扩容规则通常是：每次扩容为当前容量的 2 倍（不同编译器可能略有差异）。

扩容过程：

1. 分配一块新的、容量为当前 2 倍的内存；
2. 将原有内存中的所有元素拷贝到新内存；
3. 释放原有内存；
4. 将 vector 的指针指向新内存。

⚠️ 易错点：扩容过程涉及元素的拷贝，对于自定义类型（尤其是大对象），扩容的开销很大。频繁扩容会严重影响性能。

💡 小技巧：若已知元素数量，可提前预留容量，避免频繁扩容：

vector<int> v;
v.reserve(100);  // 提前预留100个元素的容量，避免频繁扩容

🔥 高频考点：reserve 只改变 capacity（容量），不改变 size（元素个数）；resize 既改变 size，也可能改变 capacity。

---

四、vector 与其他容器对比

容器类型	容器类别	核心特点	随机访问	尾插效率	中间插入效率	适用场景
vector	序列式	连续内存、动态扩容	✅ O(1)	✅ O(1)（均摊）	❌ O(n)	频繁访问、尾部插入删除、需要排序
list	序列式	双向链表、不连续内存	❌	✅ O(1)	✅ O(1)	频繁中间插入删除、不需要随机访问
deque	序列式	分段连续、双端高效	✅ O(1)	✅ O(1)	⚠️ O(n)	头尾都需要高效操作
set	关联式	红黑树、值为key、去重有序	❌	-	O(log n)	去重、有序查找、不需要 key-value
map	关联式	红黑树、key-value 映射	❌	-	O(log n)	关键字映射、通过 key 找 value

---

五、常见误区与注意事项

⚠️ 易错点 1：下标访问越界。vector 的 [] 操作符无越界检查，访问超出 size 的下标会导致未定义行为（可能崩溃，也可能读到垃圾值）。建议用 at() 访问，它有越界检查，越界会抛出异常。

⚠️ 易错点 2：混淆 size 和 capacity。size 是当前元素个数，capacity 是当前可存储的最大元素个数，永远满足 size <= capacity。

⚠️ 易错点 3：中间插入删除效率低。vector 中间插入/删除会移动后续所有元素，数据量较大时性能很差，这种场景应该用 list。

⚠️ 易错点 4：清空不释放内存。clear() 仅清空元素（size=0），capacity 不变。要释放多余容量，需用 vector<int>().swap(v) 技巧。

⚠️ 易错点 5：迭代器失效。vector 扩容后，原有迭代器会全部失效（因为指向了已释放的旧内存）。扩容后必须重新获取迭代器。此外，中间插入/删除也会导致插入点之后的迭代器失效。

---

六、适用场景总结

1. 频繁通过下标访问元素（如：数组遍历、随机访问）；
2. 主要在尾部进行插入/删除操作（如：收集数据、拼接数组）；
3. 需要对元素进行排序、查找等算法操作（与 algorithm 配合使用）；
4. 数据量不大，或可提前预估数据量（避免频繁扩容）。

vector 是 STL 中最基础、最常用的容器，与 set、map、stack 等容器配合使用，可覆盖绝大多数开发场景。

---

七、🔖 本章小结

vector 是最常用的序列式容器：连续内存带来 O(1) 随机访问与良好的缓存局部性，尾插均摊 O(1)；代价是中间插入删除为 O(n)，且扩容时会重新分配内存并拷贝元素，导致迭代器全部失效。默认场景选 vector 通常不会错；当插删主要发生在头部时改用 deque，发生在中间且频繁时改用 list。

八、📝 实战练习

练习题 1（选择题）

题目： vector 的底层存储结构是？

A. 双向链表 B. 连续内存的动态数组 C. 红黑树 D. 哈希表

🔑 点击查看答案与解析

答案： B

**解析：**vector 底层是连续内存的动态数组，支持随机访问。A 是 list 的底层结构，C 是 set/map 的底层结构，D 是 unordered_set/unordered_map 的底层结构。

---

练习题 2（判断题）

题目： vector 的 push_back 操作时间复杂度一定是 O(1)（ ）

🔑 点击查看答案与解析

答案： 错误

解析：push_back 的均摊时间复杂度是 O(1)，但当容量不足需要扩容时，这一次插入的时间复杂度是 O(n)（需要拷贝所有元素）。不过因为扩容频率很低（每次容量翻倍），平均下来每次操作还是 O(1)。

---

练习题 3（选择题）

题目： 以下关于 vector 的 size() 和 capacity() 的说法，正确的是？

A. size() 一定等于 capacity() B. size() 一定大于 capacity() C. size() 一定小于等于 capacity() D. size() 和 capacity() 没有关系

🔑 点击查看答案与解析

答案： C

**解析：**size() 是当前元素个数，capacity() 是当前分配的内存能容纳的元素个数。vector 会预留一些额外空间以应对未来的插入，因此 size() <= capacity() 永远成立。

---

练习题 4（程序阅读题）

题目： 阅读以下代码，写出输出结果：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    for (int i = 1; i <= 5; i++) {
        v.push_back(i);
    }
    v.insert(v.begin() + 2, 10);
    v.erase(v.begin() + 1);
    cout << v[2] << endl;
    return 0;
}

🔑 点击查看答案与解析

答案： 3

解析：

• 初始 push_back 后 v = [1, 2, 3, 4, 5]
• v.insert(v.begin() + 2, 10) 在索引 2 的位置（元素 3 前面）插入 10，v 变为 [1, 2, 10, 3, 4, 5]
• v.erase(v.begin() + 1) 删除索引 1 处的元素（即 2），v 变为 [1, 10, 3, 4, 5]
• v[2] 即索引为 2 的元素，值为 3

---

练习题 5（多选题）

题目： 以下哪个场景下，已有的迭代器仍然有效？（多选）

A. push_back 导致扩容 B. 在尾后删除元素（pop_back），指向第一个元素的迭代器 C. 在中间插入元素，插入点之前的迭代器 D. 在中间删除元素，被删除位置之前的迭代器

🔑 点击查看答案与解析

答案： B、C、D

解析：

• A：扩容会重新分配内存，所有迭代器全部失效（A 错误）
• B：pop_back 仅使指向尾元素的迭代器失效，指向第一个元素的迭代器始终有效（B 正确）
• C：未触发扩容的普通中间插入，C++ 标准明确保证插入点之前的迭代器仍然有效，仅插入点及之后的迭代器失效（C 正确）
• D：中间删除只会使被删除位置及之后的迭代器失效，被删除位置之前的迭代器仍然有效（指向的元素没变）（D 正确）

因此 B、C、D 三项在标准层面均为正确陈述；A 才是唯一使"前面的迭代器"失效的情形。

---

练习题 6（编程题）

题目： 输入 n 个整数，将它们存入 vector 中，然后输出排序后的结果（从小到大），并去重（即相同的数只输出一次）。

**输入格式：**第一行一个整数 n，第二行 n 个整数。 **输出格式：**一行，排序去重后的整数，用空格隔开。

样例输入：

7
3 1 4 1 5 9 2

样例输出：

1 2 3 4 5 9

🔑 点击查看答案与解析

参考代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    // 先排序
    sort(v.begin(), v.end());
    
    // 再去重：unique 将重复元素移到末尾，返回去重后的末尾迭代器
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());  // 删除末尾的重复元素
    
    // 输出结果
    for (int i = 0; i < v.size(); i++) {
        if (i > 0) cout << " ";
        cout << v[i];
    }
    cout << endl;
    
    return 0;
}

**解析：**这道题考查 vector 配合 algorithm 库的使用。sort 排序后，unique 函数会将相邻的重复元素移到 vector 末尾，返回去重部分的结束位置，最后用 erase 删除多余元素即可。这是 vector 排序去重的经典套路。

---

练习题 7（编程题）

题目： 实现一个函数，判断一个 vector 中是否存在重复元素。如果存在重复，返回 true，否则返回 false。

函数原型：bool hasDuplicate(vector<int>& v)

🔑 点击查看答案与解析

参考代码（方法一：排序法）：

#include <vector>
#include <algorithm>
using namespace std;

bool hasDuplicate(vector<int>& v) {
    sort(v.begin(), v.end());
    for (int i = 1; i < v.size(); i++) {
        if (v[i] == v[i - 1]) {
            return true;
        }
    }
    return false;
}

参考代码（方法二：用 set 去重对比）：

#include <vector>
#include <set>
using namespace std;

bool hasDuplicate(vector<int>& v) {
    set<int> s(v.begin(), v.end());
    return s.size() != v.size();
}

解析：

• 方法一：先排序，再遍历检查相邻元素是否相等。时间复杂度 O(n log n)，空间复杂度 O(1)（不计排序栈空间）。
• 方法二：利用 set 自动去重的特性，如果 set 的大小小于 vector 的大小，说明有重复。时间复杂度 O(n log n)，空间复杂度 O(n)。

两种方法都可以，方法一空间效率高，方法二代码简洁。

---

九、📊 考点总结表

知识点	重要程度	出题形式	易错点
vector 底层结构（连续内存）	⭐⭐⭐⭐⭐	选择题、判断题	与 list 混淆
随机访问 O(1)	⭐⭐⭐⭐⭐	选择题	认为所有容器都能随机访问
尾插均摊 O(1)	⭐⭐⭐⭐	选择题	误以为一定是 O(1)
中间插入/删除 O(n)	⭐⭐⭐⭐	选择题	与 list 混淆
size vs capacity	⭐⭐⭐⭐	选择题、判断题	分不清两者关系
扩容机制（2倍）	⭐⭐⭐	选择题、判断题	不知道扩容会拷贝元素
reserve vs resize	⭐⭐⭐	选择题	reserve 不改变 size
迭代器失效	⭐⭐⭐	选择题、判断题	不知道哪些操作会失效
排序 + 去重套路	⭐⭐⭐⭐	编程题	unique 后忘记 erase
[] 与 at 的区别	⭐⭐⭐	选择题、判断题	at 有越界检查

---

⭐ 必背速记卡

┌──────────────────────────────────────┐
│  vector 必背速记卡                    │
├──────────────────────────────────────┤
│  1. 底层是连续内存的动态数组           │
│  2. 随机访问 O(1)，尾插均摊 O(1)      │
│  3. 中间插入删除 O(n)，需移动元素      │
│  4. 扩容默认 2 倍，会拷贝所有元素      │
│  5. size <= capacity，前者是元素数     │
│  6. reserve 只扩容量，resize 改大小    │
│  7. [] 无越界检查，at() 有越界检查     │
│  8. 扩容后所有迭代器失效               │
│  9. clear 只清元素，不释放内存         │
│  10. 排序去重：sort + unique + erase  │
└──────────────────────────────────────┘