C++ 竞赛训练营第一课：STL 核心容器之 vector 详解（竞赛向）

一、课程导航 🚀

1. 🎯 竞赛视角：为什么 vector 是竞赛 “万能容器”？
2. 📚 vector 核心特性与底层原理（竞赛优化关键）
3. 🔧 竞赛高频操作：构造、增删查改与高效遍历
4. ⚡ 竞赛优化技巧：内存预分配、避免冗余拷贝
5. 📝 真题实战：vector 在竞赛题中的典型应用
6. ❌ 竞赛避坑指南：常见错误与性能陷阱
7. 🔖 下节预告：STL 核心容器之 stack 与 queue（栈与队列的竞赛用法）

二、核心知识点与竞赛实战

🎯 1. 竞赛视角：为什么 vector 是竞赛 “万能容器”？

在算法竞赛中，vector 是使用频率最高的 STL 容器，没有之一，核心原因的是它完美平衡了灵活性、效率与易用性，适配竞赛场景的核心需求：

• 动态扩容：无需提前确定大小，适配题目中不确定数据量（如输入规模未知）；

• 随机访问：O(1) 时间复杂度访问任意元素，远超 list 等链表容器；

• 连续内存：缓存命中率高，遍历速度快，适合排序、二分等竞赛高频操作；

• 接口简洁：与数组用法兼容，学习成本低，能快速上手刷题；

• 功能强大：支持排序、查找、反转等高频算法操作，配合 ` 拉满。

竞赛场景适配：线段树、前缀和、模拟题、贪心题、动态规划题等几乎所有竞赛题型都能用到 vector，是竞赛选手的 “必备工具”。

📚 2. vector 核心特性与底层原理（竞赛优化关键）

2.1 底层结构

vector 底层是动态数组，存储在连续内存空间，内部维护三个核心指针：

• begin()：指向数组首元素；

• end()：指向数组尾元素的下一个位置；

• capacity()：当前分配的内存能容纳的元素个数（区别于 size()：实际存储的元素个数）。

2.2 动态扩容机制（竞赛避坑重点）

• 扩容规则：当 size() == capacity() 时，触发扩容，通常是翻倍扩容（如从 4→8→16→...）；

• 扩容过程：分配新内存 → 拷贝旧元素 → 释放旧内存；

• 竞赛影响：频繁扩容会导致时间开销增大（拷贝元素的 O(n) 时间），需提前优化。

2.3 核心区别（竞赛选型关键）

容器	随机访问	插入删除（中间）	扩容开销	适用场景
vector	O(1)	O(n)	低（翻倍）	大多数竞赛场景（存储、遍历、排序）
array	O(1)	不支持	无	固定大小数据（如矩阵）
list	O(n)	O(1)	无	频繁插入删除（竞赛极少用）

🔧 3. 竞赛高频操作：构造、增删查改与高效遍历

3.1 核心构造方式（竞赛常用）

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

int main() {
    // 1. 空vector（最常用）
    vector<int> v1; // 修正：补充模板参数<int>

    // 2. 初始化n个元素，默认值0（竞赛中快速初始化数组）
    int n = 5;
    vector<int> v2(n, 0); // 修正：补充模板参数<int>，初始化5个0
    cout << "v2: ";
    for (int x : v2) cout << x << " "; // 输出：0 0 0 0 0
    cout << endl;

    // 3. 用已有数组/vector初始化（快速拷贝）
    int a[] = {1,2,3,4};
    vector<int> v3(a, a+4); // 修正：补充模板参数<int>，从数组a[0]到a[3]初始化
    cout << "v3: ";
    for (int x : v3) cout << x << " "; // 输出：1 2 3 4
    cout << endl;

    vector<int> v4(v3.begin(), v3.end()); // 拷贝v3的所有元素
    cout << "v4: ";
    for (int x : v4) cout << x << " "; // 输出：1 2 3 4
    cout << endl;

    // 4. 初始化n个元素，值为x（竞赛中初始化特殊值）
    int x = -1;
    vector<int> v5(n, x); // 初始化5个-1
    cout << "v5: ";
    for (int x : v5) cout << x << " "; // 输出：-1 -1 -1 -1 -1
    cout << endl;

    return 0;
}

3.2 增删查改（竞赛高频接口）

3.2.1 增加元素（重点掌握 push_back 与 emplace_back）

• push_back(x)：在尾部添加元素 x（拷贝构造，O (1) amortized，均摊时间复杂度）；

• emplace_back(x)：在尾部直接构造元素 x（直接构造，无拷贝，比 push_back 更快，C++11+）；

• 竞赛建议：优先用 emplace_back 提升效率，尤其存储结构体 / 对象时。

3.2.2 删除元素（竞赛常用 pop_back 与 erase）

• pop_back()：删除尾部元素（O (1)，无扩容，竞赛高频）；

• erase(pos)：删除指定位置 pos 的元素（O (n)，后续元素前移，尽量少用）；

• erase(l, r)：删除区间 [l, r) 的元素（O (n)，如 v.erase(v.begin()+2, v.begin()+5) 删除第 3-5 个元素）；

• 竞赛技巧：如需删除中间元素，可先将目标元素与尾部元素交换，再 pop_back（O (1) 操作）。

3.2.3 查找与修改（竞赛高效用法）

• 随机访问：v[i] 或 v.at(i)（竞赛中优先用 v[i]，O (1)，无越界检查，更快）；

• 查找元素：配合 的find函数（O(n)），如find(v.begin(), v.end(), x)`；

• 排序：sort(v.begin(), v.end())（O (n log n)，竞赛排序首选，支持自定义比较器）；

• 反转：reverse(v.begin(), v.end())（O (n)，竞赛中反转数组常用）。

3.3 高效遍历方式（竞赛速度优先）

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // 1. 普通for循环（最快，竞赛首选）
    cout << "普通for循环遍历：";
    for (int i = 0; i < v.size(); ++i) { // 修正：补全循环条件i < v.size()
        cout << v[i] << " "; // 修正：输出v[i]
    }
    cout << endl;

    // 2. 范围for循环（简洁，速度接近普通for）
    cout << "范围for循环遍历：";
    for (auto x : v) { // auto自动推导类型为int
        cout << x << " "; // 修正：补全输出语句
    }
    cout << endl;

    // 3. 迭代器遍历（兼容所有容器，竞赛中少用，除非必要）
    cout << "迭代器遍历：";
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) { // 修正：迭代器完整定义
        cout << *it << " "; // 修正：解引用迭代器输出值
    }
    cout << endl;

    return 0;
}

⚡ 4. 竞赛优化技巧：内存预分配、避免冗余拷贝

竞赛中，vector 的效率直接影响程序是否超时，以下优化技巧是竞赛必备：

4.1 内存预分配（避免频繁扩容）

• 核心函数：reserve(n)（预留 n 个元素的内存，不改变 size，仅改变 capacity）；

• 适用场景：已知数据量范围（如题目说明 n≤1e5），提前预分配内存，避免扩容拷贝；

• 示例：

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

int main() {
    // 修正：补充vector模板参数<int>
    vector<int> v;

    // 预分配1e5个元素的内存空间（避免后续push_back时频繁扩容）
    v.reserve(100000); // 1e5即100000，代码中建议直接写数值或用const定义

    // 修正：循环条件i < 100000（1e5是数值，不能直接写在代码中当常量）
    for (int i = 0; i < 100000; ++i) {
        v.push_back(i);
    }

    // 验证：输出vector的大小和容量
    cout << "vector大小：" << v.size() << endl; // 100000
    cout << "vector容量：" << v.capacity() << endl; // 100000（与预分配一致）
    return 0;
}

4.2 避免冗余拷贝（竞赛性能关键）

• 用 emplace_back 替代 push_back（构造元素时无拷贝）；

• 传递参数时用引用（const vector v），避免值传递导致的 O (n) 拷贝；

• 清空容器用 clear() 而非重新构造（clear() 仅置空 size，不释放 capacity，后续使用无需重新扩容）。

4.3 其他优化细节

• 用 shrink_to_fit() 释放多余内存（仅在容器不再添加元素时使用，如处理完所有数据后）；

• 避免用 v.size() 作为循环条件（每次调用需计算，可缓存到变量）：

int len = v.size(); // 缓存size

for (int i = 0; i < len; ++i) { ... }

📝 5. 真题实战：vector 在竞赛题中的典型应用

例题 1：基础应用 —— 数组去重（竞赛高频预处理）

题目描述：给定一个整数数组，删除重复元素，保持元素顺序不变，输出去重后的数组。

解法（vector + 双指针）：

#include <iostream>
#include <vector>   // 修正：正确包含vector头文件（原代码写了#include >）
using namespace std;

int main() {
    // 修正：vector定义补充<int>和赋值符号
    vector<int> v = {1,2,2,3,3,3,4};

    if (v.empty()) return 0;

    int idx = 0;
    // 修正：循环条件补充i < v.size()（原代码i ++i错误）
    for (int i = 1; i < v.size(); ++i) {
        if (v[i] != v[idx]) {
            v[++idx] = v[i];
        }
    }

    v.resize(idx + 1); // 截断多余元素，只保留去重后的结果

    // 修正：输出流符号<<（原代码写反成<）
    for (auto x : v) cout << x << " "; 
    cout << endl; // 补充换行，输出更整洁

    return 0;
}

核心思路：利用 vector 的随机访问特性，双指针原地去重，时间 O (n)，空间 O (1)（不考虑输出）。

例题 2：进阶应用 —— 动态数组模拟栈（竞赛灵活适配）

题目描述：实现一个栈，支持 push、pop、top 操作，无需提前确定栈大小。

解法（vector 模拟）：

#include <iostream>
#include <vector>   // 修正：正确包含vector头文件（原代码写了#include >）
using namespace std;

// 修正：补充vector模板参数<int>，定义全局栈容器
vector<int> stk;

void push(int x) {
    stk.emplace_back(x); // 尾部添加元素（模拟栈push）
}

void pop() {
    if (!stk.empty()) stk.pop_back(); // 尾部删除元素（模拟栈pop）
}

int top() {
    return stk.back(); // 访问尾部元素（模拟栈top）
}

int main() {
    push(1); push(2); push(3);
    
    // 修正：输出语句语法错误（原代码cout <() <3）
    cout << top() << endl; // 输出3
    
    pop();
    
    cout << top() << endl; // 输出2
    
    return 0;
}

竞赛优势：vector 模拟栈比手写数组更灵活，无需处理栈满扩容问题，代码简洁。

❌ 6. 竞赛避坑指南：常见错误与性能陷阱

6.1 常见错误

• 越界访问：v[i] 无越界检查，竞赛中需确保 i 如循环条件用 i i 1，避免 size=0 时出错）；

• 未判空访问：调用 v.back()、v.pop_back() 前需检查 !v.empty()；

• 混淆 size() 与 capacity()：size() 是实际元素个数，capacity() 是内存容量，不可用 capacity() 遍历。

6.2 性能陷阱

• 频繁扩容：未预分配内存时，大量 push_back 会导致多次扩容，时间开销激增（如 1e5 次 push_back 可能触发 17 次扩容）；

• 冗余拷贝：值传递 vector（如 void func(vector<int> v)），每次调用拷贝 O (n) 元素，需改为引用传递；

• 滥用 erase：中间位置 erase 是 O (n) 操作，竞赛中尽量用 “交换 + pop_back” 替代。

🔖 7. 下节预告：STL 核心容器之 stack 与 queue（竞赛用法）

核心内容前瞻

1. stack（栈）：

• • 竞赛核心用法：后进先出（LIFO）特性、括号匹配、单调栈（竞赛高频难点）；

• • 关键接口：push()、pop()、top()、empty()；

• • 真题实战：有效的括号、每日温度（单调栈经典题）。

1. queue（队列）：

• • 竞赛核心用法：先进先出（FIFO）特性、BFS（广度优先搜索）标配；

• • 关键接口：push()、pop()、front()、back()、empty()；

• • 真题实战：二叉树的层序遍历、滑动窗口最大值（队列优化）。

1. 竞赛对比：stack 与 queue 的适用场景、与 vector 的选型技巧。

预习建议

1. 回顾 vector 的动态数组特性，对比栈 / 队列的限制（无随机访问）；
2. 提前了解 BFS 算法的基本思路（queue 是 BFS 的核心工具）；
3. 思考：为什么竞赛中用 stack 模拟递归能避免栈溢出？

下节课，我们将聚焦栈与队列的竞赛核心用法，尤其是单调栈、BFS 等高频考点，带你攻克 STL 容器的第二关！