STL 学习笔记

· · 算法·理论

part 0：前言（必读）

本文章是在学习 STL 算法和容器后写的，如果有缺少的容器或函数，请评论区指正。

本文为 c++ 环境，编译选项为 -std=c++14 -O2。

火车头：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    return 0;
}

配套题单为：877299

本文目前共约13k字。

part 1：容器

STL 库拥有很多好用的容器，通用的定义方法是：

容器类型 < 数据类型 > 名称;

其中数据类型可以是 int、long long 之类的普通类型，也可以是其他的 STL，比如：

vector < pair < pair < int,int >,int > > a;

通用的迭代器（必读）

容器类型 < 数据类型 >::iterator it;//定义
//对于普通类型
for(it = a.begin();it != a.end();it++){
    cout << *it << ' ';
}
//也可以
for(auto x : a){
    cout << x << ' ';
}
//对于map
for(it = mp.begin();it != mp.end();it++){
    cout << it->first << ' ' << it->second >> '\n';
}
//也可以
for(auto x : mp){
    cout << it.first << ' ' << it.second >> '\n';
}

序列式容器

vector

简介

vector 是动态数组，支持随机访问，尾部插入效率高。

基本定义

vector < int > a;//定义一个空的vector
vector < int > a(arr);//用数组初始化
vector < int > a(n);//长度为n，初始值为0
vector < int > a(n,x);//长度为n，初始值为x

常用操作

::::info[我的代码]

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int a[1000005];
deque < int > q;
int n,m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++){
        while(!q.empty() && a[q.back()] > a[i]) q.pop_back();
        q.push_back(i);
        if(i >= m){
            while(!q.empty() && q.front() <= i - m) q.pop_front();
            cout << a[q.front()] << ' ';
        }
    }
    cout << '\n';
    while(!q.empty()) q.pop_front();
    for(int i = 1;i <= n;i++){
        while(!q.empty() && a[q.back()] < a[i]) q.pop_back();
        q.push_back(i);
        if(i >= m){
            while(!q.empty() && q.front() <= i - m) q.pop_front();
            cout << a[q.front()] << ' ';
        }
    }
    return 0;
}

::::

list

简介

list 是一个双向链表容器，支持任意位置的高效插入和删除操作，但不支持随机访问。

基本定义

list < int > a;//定义一个空的list
list < int > a(arr);//用数组初始化
list < int > a(n);// 长度为n，初始值为0
list < int > a(n,x);//长度为n，初始值为x
list < int > a(begin,end);// 用迭代器范围初始化

常用操作

int main(){ stack < int > s; s.push(10); s.push(20); s.push(30); cout << "栈顶元素: " << s.top() << '\n'; cout << "栈大小: " << s.size() << '\n'; s.pop(); cout << "栈顶元素: " << s.top() << '\n'; while(!s.empty()){//遍历 cout << s.top() << ' '; s.pop(); } return 0; }

#### **底层容器要求**
`stack` 是容器适配器，底层容器需要支持以下操作：  
`push_back()`  
`pop_back()`  
`back()`  
默认使用 `deque`，不过可以指定底层容器为 `vector` 或 `list`：
```cpp
stack < int,vector < int > > s;//底层容器为vector
stack < int,list < int > > s;//底层容器为list

题目

B3614 【模板】栈

queue

简介

queue 是一种 先进先出（FIFO, First In First Out） 的容器适配器，只能在队尾插入元素，在队头删除元素。它默认基于 deque 实现，也可以指定底层容器（如 list）。

基本定义

queue < int > q1;//定义空队列，元素类型为int，默认底层容器是deque
//用list作为底层容器
queue < int,list < int > > q2;

常用操作

int main() { queue < int > q; q.push(10); q.push(20); q.push(30); cout << "队头元素: " << q.front() << '\n'; cout << "队尾元素: " << q.back() << '\n'; cout << "队列大小: " << q.size() << '\n'; q.pop(); cout << "队头元素: " << q.front() << '\n'; while(!q.empty()){ cout << q.front() << ' '; q.pop(); } return 0; }

#### **底层容器要求**
`queue` 是容器适配器，底层容器需要支持以下操作：  
`push_back()`  
`pop_front()`  
`front()`  
`back()`  
默认使用 `deque`，也可以指定 `list`：
```cpp
queue < int,list < int > > q;//底层容器为list

题目

B3616 【模板】队列

priority_queue

简介

priority_queue 是优先队列，每次出队的元素都是当前队列中优先级最高的元素（默认最大值优先）。它的底层默认使用堆实现，并且是一种容器适配器，可以基于 vector 或 deque 作为底层容器。

基本定义

//默认：最大堆（降序）
priority_queue < int > pq1;
//自定义比较器，最小堆（升序）
priority_queue < int,vector < int >, greater < int > > pq2;
//使用list不能作为底层容器（需要随机访问迭代器）

常用操作

-push(val)：将元素 val 插入队列，并自动调整堆结构

int main(){ priority_queue < int > pq;//默认大顶堆 pq.push(30); pq.push(10); pq.push(50); pq.push(20); cout << "队头元素: " << pq.top() << '\n'; pq.pop(); cout << "队头元素: " << pq.top() << '\n'; cout << "队列大小: " << pq.size() << '\n'; while(!pq.empty()){ cout << pq.top() << ' '; pq.pop(); } return 0; }

#### 自定义比较器
如果存储的是自定义类型，可以自己写比较器：
```cpp
struct Person{
    string name;
    int age;
};

bool cmp(Person a,Person b){
    return a.age < b.age;
}

priority_queue < Person,vector < Person >,cmp > pq;

底层容器要求

priority_queue 底层容器需要支持随机访问迭代器，并且支持以下操作：
push_back()
pop_back()
随机访问（如 vector、deque）
默认使用 vector 作为底层容器。

part 2：算法

set 等关联式容器中已经封装了 lower_bound 等函数（像 s.lower_bound(x) 这样），这样调用的时间复杂度是 O(\log_2 n) 的。 ::::

string 能动态分配空间，这使得我们可以直接使用 cin 来输入，但其速度较慢。

string 的加法运算符可以直接拼接两个字符串或一个字符串和一个字符。string 重载了比较运算符，按字典序比较，所以我们可以直接调用 sort 对字符串进行排序。

声明

string 的定义方法十分简单，为 string s。

转 char 数组

string 转 char 数组的方式很简单，只要用一个函数 s.c_str() 就可以解决。

printf("%s",s);//编译错误
printf("%s",s.c_str());//能够正确输出

长度

很多函数都可以返回 string 的长度，如下：

printf("%zu",s.size());//我用这个
printf("%zu",s.length());//有人用这个
printf("%zu",strlen(s.c_str()));//绝对的整活，还慢

::::info[复杂度] 第三种写法是 O(n) 的，前两种都是 O(1) 的。 :::: ::::warning[返回值] 这几种函数的返回值都是 size_t 或 unsigned long 类型。因此，这些返回值不支持直接与负数比较或运算，需要时要进行强制类型转换。 ::::

查找

find(s,pos) 函数可以用来查找字符串中 s 在 pos（含）之后第一次出现的位置（若不传参给 pos 则默认为 0）。如果没有出现，则返回 string::npos（一般是 -1，但类型仍为 size_t/unsigned long）。 示例：

string s = "IAKIOI",s1 = "OI",s2 = "I";
int pos = 4;
s.find("I");//返回0
s.find("a");//返回string::npos
s.find(s1)//返回4
s.find(s2,pos);//返回5

截取

substr(pos,len) 函数的参数返回从 pos 位置开始截取最多 len 个字符组成的字符串（如果从 pos 开始的后缀长度不足 len 则截取到末尾）。

示例：

string s = "IAKIOI", t = "OI";
s.substr(3,3);//返回IOI
t.substr(1,3);//返回I

插入/删除

insert(pos,cnt,s1) 和 insert(pos,s2) 是插入函数。它们分别表示在 pos 处连续插入 cnt 次字符串 s1 和插入字符串 s2。

erase(pos,cnt) 函数将字符串 pos 位置开始（含）的 cnt 个字符删除（若不传参给 cnt 则删去 pos 位置及以后的所有字符）。

示例：

string s = "IAKIOI",t = " IOI";
char ch = '!';
s.erase(3);//s = "IAK"
s.insert(3,t);//s = "IAKIOI"
s.insert(7,3,ch);//s = "IAKIOI!!!"

替换

replace(pos,cnt,s1) 和 replace(l,r,s2) 是替换函数。它们分别表示从 pos 位置开始 cnt 个字符的子串替换为 s1 以及将以 l 开始（含），r 结束（不含）的子串替换为 s2，其中 l 和 r 均为迭代器。

示例：

string s = "IOI";
s.replace(1,2,"");//s = "I"
s.replace(s.begin(),s.begin() + 1,"NOI");//s = "NOI"

例题

P5734 【深基6.例6】文字处理软件