跳到主要内容

信奥赛常用 STL 容器与函数讲义

一、STL 简介​

STL（Standard Template Library）是 C++ 标准库的重要组成部分，包含 容器（Container）、算法（Algorithm）、迭代器（Iterator） 三大核心组件。
本章重点介绍竞赛中常用的容器及其操作。

二、常用容器分类​

容器类型数据结构特点典型应用场景
vector动态数组随机访问快，尾部增删高效动态数组、栈
deque双端队列头尾增删高效队列、双端操作
list双向链表中间插入/删除高效频繁修改的序列
stack栈后进先出（LIFO）深度优先搜索（DFS）
queue队列先进先出（FIFO）广度优先搜索（BFS）
priority_queue堆自动排序，顶部元素最大/最小最短路径、贪心算法
map红黑树有序键值对，查找复杂度 O(log n)字典、动态排序
unordered_map哈希表无序键值对，平均 O(1) 查找快速查找、计数

三、常用容器详解​

1. vector - 动态数组​

特点：动态扩容的数组，随机访问O(1)，尾部操作高效

基本操作​

函数功能时间复杂度
push_back(x)尾部插入元素 xO(1)（均摊）
pop_back()删除尾部元素O(1)
operator[]随机访问元素O(1)
size()返回元素个数O(1)
clear()清空所有元素O(n)

示例代码​

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

int main() {
    // 创建与初始化
    vector<int> v1 = {7, 3, 5};  // 初始化列表
    vector<int> v2(5, 0);         // 5个0: {0,0,0,0,0}
    
    // 关键操作
    v1.push_back(9);      // {7,3,5,9}
    v1.pop_back();        // {7,3,5}
    v1.insert(v1.begin() + 1, 8); // {7,8,3,5}
    cout<<v1.size();  //3
    
    // 遍历方式
    // 1. 下标遍历
    for(int i = 0; i < v1.size(); i++) {
        cout << v1[i] << " ";
    }
    
    // 2. 迭代器遍历
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << " ";
    }
    
    // 3. 范围for循环
    for(int num : v1) {
        cout << num << " ";
    }
    return 0;
}

内存变化示意图：

初始：[7][3][5]
push_back(9)后：[7][3][5][9] 
pop_back()后： [7][3][5]
insert(8)后： [7][8][3][5]

2. queue - 队列​

特点：FIFO（先进先出）数据结构

基本操作​

函数功能时间复杂度
push(x)入队O(1)
pop()出队O(1)
front()访问队首元素O(1)
back()访问队尾元素O(1)
empty()判断是否为空O(1)

示例代码​

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

int main() {
    queue<int> q;
    
    // 入队操作
    q.push(1);
    q.push(2);
    q.push(3);  // 队列：队首←1-2-3←队尾
    
    cout << "队首元素: " << q.front() << endl; // 1
    cout << "队尾元素: " << q.back() << endl;  // 3
    
    q.pop();  // 移除1
    cout << "弹出后队首: " << q.front(); // 2
    cout << "队列大小: " << q.size();    // 2
    return 0;
}

3. stack - 栈​

特点：LIFO（后进先出）数据结构

基本操作​

函数功能时间复杂度
push(x)压栈O(1)
pop()弹栈O(1)
top()访问栈顶元素O(1)
empty()判断是否为空O(1)

示例代码​

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

int main() {
    stack<int> s;
    
    s.push(1);  // 栈底 ← 1
    s.push(2);  // 栈底 ← 1 ← 2 ←栈顶
    s.push(3);  // 栈底 ← 1 ← 2 ← 3 ←栈顶
    
    cout << "栈顶元素: " << s.top() << endl; // 3
    s.pop();    // 移除3
    cout << "新栈顶: " << s.top();         // 2
    return 0;
}

4. unordered_map - 哈希表​

特点：键值对存储，O(1)平均查找复杂度

基本操作​

函数功能时间复杂度（平均）
insert({k,v})插入键值对O(1)
erase(k)删除键 kO(1)
find(k)查找键 kO(1)
operator[]访问或插入键 kO(1)

示例代码​

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

int main() {
    unordered_map<string, int> scoreMap;
    
    // 插入数据
    scoreMap["Alice"] = 90;
    scoreMap["Bob"] = 85;
    scoreMap.insert({"Charlie", 92});
    
    // 查找与访问
    if(scoreMap.find("Bob") != scoreMap.end()) {
        cout << "Bob's score: " << scoreMap["Bob"] << endl; // 85
    }
    
    // 遍历
    for(auto& pair : scoreMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    // 删除元素
    scoreMap.erase("Alice");
    return 0;
}

四、容器性能对比​

容器时间复杂度典型应用场景
vector随机访问O(1)动态数组、邻接表存储图
尾部操作O(1)
中间插入O(n)
queue入队/出队O(1)BFS广度优先搜索
stack入栈/出栈O(1)DFS深度优先搜索、表达式求值
unordered_map查找/插入O(1)哈希计数、快速索引
set查找/插入O(log n)有序数据去重、二分查找需求

五、竞赛常用技巧​

  1. 优先队列模拟堆

    priority_queue<int> pq; // 默认大根堆
    pq.push(3); pq.push(1); pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出：3 2 1
        pq.pop();
    }

  2. 哈希表计数

    unordered_map<int, int> count;
    for (int x : {1, 2, 1, 3}) {
        count[x]++; // 统计频率
    }

  3. 双指针遍历 vector

    vector<int> v = {1, 2, 3, 4};
    for (int i = 0, j = v.size()-1; i < j; i++, j--) {
        swap(v[i], v[j]); // 反转数组
    }

  4. sort排序

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

    int main() {
        vector<int> nums = {4, 2, 7, 1, 5};
        
        // 升序排序
        sort(nums.begin(), nums.end()); // {1,2,4,5,7}
        
        // 降序排序
        sort(nums.begin(), nums.end(), greater<int>()); // {7,5,4,2,1}
        
        // 自定义排序（按绝对值）
        vector<int> nums2 = {-3, 2, -5, 1};
        sort(nums2.begin(), nums2.end(), [](int a, int b) {
            return abs(a) < abs(b);
        }); // {1,2,-3,-5}
        return 0;
    }

六、易错点与最佳实践​

1. vector越界访问​

vector<int> v(3);
// cout << v[5];  // 未定义行为！
// 正确做法：先检查大小或使用at()
if(v.size() > 5) cout << v[5];

2. queue/stack判空​

while(!q.empty()) {  // 必须判空！
    q.pop();
}

3.unordered_map查找优化​

// 避免直接访问不存在的键
if (map.count(key)) {  // 先检查存在性
    value = map[key];
}

七、总结​

  • 动态数组选 vector：需要随机访问或尾部操作时。
  • 先进先出用 queue：BFS、滑动窗口等场景。
  • 后进先出用 stack：DFS、括号匹配等问题。
  • 快速查找用 unordered_map：需要 O(1) 查找的场景。
  • 有序映射用 map：需要按键排序的场景。

*学习笔记​

暂没有学习笔记，快来抢first blood ！