【知识要点】STL

前言部分

STL（Standard Template Library）是C++标准模板库的简称，它是由世界上许多优秀的程序员多年智慧的结晶。STL主要包含三大组件：

1. 1. 容器（Container）：用于管理某类对象的集合，如数组、链表等数据结构

1. 1. 迭代器（Iterator）：提供在对象集合上进行遍历的方法

1. 1. 算法（Algorithm）：包含各种处理集合内元素的函数，如排序、查找等

使用STL可以避免重复造轮子，提高代码可读性和开发效率。但在一些对时间要求极高的场景中，STL有时会成为性能瓶颈，需要谨慎使用。

主要内容目录

容器部分

1. 1. vector动态数组

1. 1. set和multiset集合

1. 1. pair和map映射

1. 1. deque双端队列

1. 1. priority_queue优先队列

算法部分

6. 6. 简单类算法

6. 6. 区间类算法

6. 6. 查找类算法

vector动态数组详解

基本概念

vector被称为动态数组或变长数组，其长度可以根据需要动态改变。在信息学竞赛中，当需要开超大数组又怕爆空间时，vector是一个很好的选择。

构造方法

vector有多种构造方式：

vector<int> v;          // 定义一个长度可变的int数组
vector<int> v[100];     // 定义一个二维数组，第一维固定为100，第二维可变
vector<node> v;         // 存储自定义结构体类型
vector<vector<int>> v;  // 定义一个二维动态数组（注意> >之间要有空格）

常用操作

1. 1. 尾部插入元素：

v.push_back(1);  // 在数组末尾插入1

2. 2. 获取大小和判空：

int size = v.size();  // 返回元素个数
bool isEmpty = v.empty();  // 判断是否为空

3. 3. 访问元素：

// 通过下标访问（从0开始）
for(int i=0; i<v.size(); i++) {
    cout << v[i] << " ";
}

// 通过迭代器访问
for(auto it=v.begin(); it!=v.end(); it++) {
    cout << *it << " ";
}

4. 4. 插入和删除：

v.insert(v.begin()+1, 5);  // 在第二个位置插入5
v.erase(v.begin()+1);      // 删除第二个元素
v.erase(v.begin()+1, v.begin()+3); // 删除第2到第3个元素
v.clear();  // 清空整个vector

应用实例

vector常用于实现图的邻接表存储，相比传统的邻接矩阵可以节省大量空间，特别是对于稀疏图。

set和multiset集合

基本概念

set对应数学中的”集合”概念，内部自动对元素进行排序且保证元素唯一。multiset与set类似，但允许元素重复。

常用操作

1. 1. 插入元素：

set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);  // 集合会自动排序为{1,2,3}

2. 2. 查找元素：

// 方法1：使用find
if(s.find(4) == s.end()) {
    cout << "4不存在";
}

// 方法2：使用count
if(s.count(4) == 0) {
    cout << "4不存在";
}

3. 3. 删除元素：

s.erase(3);  // 删除元素3
s.clear();   // 清空集合

4. 4. 遍历集合：

for(auto it=s.begin(); it!=s.end(); it++) {
    cout << *it << " ";
}

应用场景

set常用于需要去重和自动排序的场景，如统计不同数字的个数、维护有序数据等。

pair和map映射

pair二元组

pair可以看作是一个包含两个元素的简单结构体：

pair<string, int> p;
p = make_pair("Tom", 18);
cout << p.first << " " << p.second;  // 输出 Tom 18

map映射

map提供键值对的存储和查找功能：

map<string, int> score;
score["Alice"] = 90;  // 插入键值对
score["Bob"] = 85;

// 遍历map
for(auto it=score.begin(); it!=score.end(); it++) {
    cout << it->first << ": " << it->second << endl;
}

// 查找元素
if(score.find("Alice") != score.end()) {
    cout << "Alice的成绩是：" << score["Alice"];
}

deque双端队列

基本概念

deque是双端队列，支持在头部和尾部快速插入和删除元素。

常用操作

deque<int> dq;
dq.push_back(1);   // 尾部插入1
dq.push_front(2);  // 头部插入2
int front = dq.front();  // 获取头部元素
int back = dq.back();    // 获取尾部元素
dq.pop_front();    // 删除头部元素
dq.pop_back();     // 删除尾部元素

应用场景

deque常用于实现滑动窗口、单调队列等算法，特别是需要同时在头部和尾部操作的情况。

priority_queue优先队列

基本概念

优先队列底层用堆实现，默认是大根堆（最大元素在顶部）。

常用操作

// 默认大根堆
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
int top = pq.top();  // 获取堆顶元素4
pq.pop();            // 删除堆顶元素

// 小根堆定义
priority_queue<int, vector<int>, greater<int>> min_pq;

应用实例

优先队列常用于需要频繁获取最大或最小元素的场景，如合并果子问题、Dijkstra算法等。

常用算法

排序算法

vector<int> v = {3,1,4,2};
sort(v.begin(), v.end());  // 升序排序
stable_sort(v.begin(), v.end());  // 稳定排序

查找算法

// 在有序数组中查找
auto it = lower_bound(v.begin(), v.end(), 3);  // 第一个≥3的位置
auto it2 = upper_bound(v.begin(), v.end(), 3); // 第一个>3的位置

其他算法

int max_val = max(a, b);  // 返回较大值
int min_val = min(a, b);  // 返回较小值
swap(a, b);  // 交换两个值

综合应用案例

滑动窗口最大值

使用deque实现单调队列，可以在O(n)时间内解决滑动窗口最大值问题：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        // 移除不在窗口内的元素
        if(!dq.empty() && dq.front() == i-k) dq.pop_front();
        // 移除比当前元素小的元素
        while(!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
        dq.push_back(i);
        // 记录当前窗口最大值
        if(i >= k-1) res.push_back(nums[dq.front()]);
    }
    return res;
}

合并果子问题

使用优先队列实现贪心算法：

int mergeFruits(vector<int>& fruits) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int f : fruits) pq.push(f);
    int res = 0;
    while(pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        res += a + b;
        pq.push(a + b);
    }
    return res;
}

练习题推荐

1. 1. 钻石收集者（练习vector使用）

1. 1. 上网统计（练习map和统计）

1. 1. 反片语（练习字符串处理和set使用）

1. 1. 最大K子段和（练习单调队列）

1. 1. 蚯蚓（练习优先队列和单调队列的综合应用）