ACM CSP竞赛笔记（九）——容器与STL库的使用

完整板子可以去资源看，我设置的0积分应该是免费的，如果拿不到可以B站私我。

容器

顺序容器：通过位置来访存元素

容器适配器：集成了基本容器的容器

关联容器：字典，用于表达键值对关系

无序容器：哈希表

Vector

vector初始化长度后，填充不可以用push_back()，否则只是往后加，必须用vec[i]填充。

如果没有初始化长度才可以用push_back（）.

vector开在main外面。

二维vector

矩形二维vector

可变长一维数组的拼接 与 创建 遍历

这里例子每一行是i的大小递增。

如果要求任意长度，可以用resize()，再push_back进vec4中。

对Vector的遍历

一种是

Resize 操作 例题

带初始值的resize，将行数扩到4，第四行是全0的大小为4的vector

std::vector<std::vector<int>> matrix(3, std::vector<int>(3, 0)); // 初始为 3×3

// 将行数扩容到 4，新增的第4行是一个包含 4 个元素且全为 0 的 vector
matrix.resize(4, std::vector<int>(4, 0));

不带初始值的resize，将行数扩到4，第四行是null，在使用的时候必须对列resize。

std::vector<std::vector<int>> matrix(3, std::vector<int>(3, 0)); // 初始为 3×3

// ❌ 危险操作：行数变成了 4，但第 4 行（matrix[3]）里面没有分配任何空间！
matrix.resize(4);

P3613

https://www.luogu.com.cn/problem/P3613

​

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

int main(){
int n,q;
cin>>n>>q;
store.resize(n+1);
int p,i,j,k;
for(int v=0;v<q;v++){
cin>>p;
if(p==1){
cin>>i>>j>>k;
if(store[i].size()<=j){store[i].resize(j+1);}
store[i][j]=k;
}else{
cin>>i>>j;
cout<<store[i][j]<<endl;
}
}
return 0;
}

List

​

List的遍历

实际上直接for(auto x:lst)即可。

​

List的查找

找第一个/找所有的val都可以

​

可以直接用algorithm的函数

find(begin,end,val)

​

List的删除

删除单个节点

erase(find(10))

删除所有节点

remove(10)

List的插入

在后面插入 push_back

在前面插入 push_front

在i之前插入

L.insert(i,100)

在i之后插入

auto i=find(5) i++ L.insert(i,1000)

​

翻转链表

List与Vector的转换

1. Vector转List

std::vector<int> myVec = {1, 2, 3, 4};
// 利用迭代器范围直接构造 list
std::list<int> myList(myVec.begin(), myVec.end());

2. List转Vector

这是最直接的方法。std::vector 提供了一个接受迭代器范围的构造函数，可以直接接收 std::list 的头尾迭代器进行初始化：

std::list<int> myList = {5, 6, 7, 8};
// 利用迭代器范围直接构造 vector
std::vector<int> myVec(myList.begin(), myList.end());

应用

快排回去

List排序很慢

std::list<int> myList = {…}; // 假设包含大量无序数据

// 1. 将 list 转换为 vector
std::vector<int> tempVec(myList.begin(), myList.end());

// 2. 对 vector 进行高效排序
std::sort(tempVec.begin(), tempVec.end());

// 3. 将排好序的数据拷贝回 list
10myList.assign(tempVec.begin(), tempVec.end());

队列

入队

头往后

​

出队

尾巴往前移

​

环形队列

​

STL队列 queue

​

STL双端队列 deque

​

单调队列（找各区间最大值）

维护一个时间窗口，先检查队头是否过期，如果过期就弹出，然后检查队尾如果比当前小就弹出，然后入队。

​

优先队列

栈

​

STL栈

​

前中后缀表达式

​

中缀转前缀

​

中缀转后缀

​

前后缀表达式的计算

前缀表达式的计算

前缀从右往左压入栈，遇到运算符弹栈计算。

​

后缀表达式的计算

后缀从左往右压入栈，遇到运算发弹栈计算。注意顺序是次栈顶<运算>栈顶。

​

练习 P1449

https://www.luogu.com.cn/problem/P1449

​

#include <iostream>
#include <stack>
#include <string>
using namespace std;
//
int main() {
string s;
getline(cin, s);
stack<long long> st;
string num = "";
for (char c : s) {
//第一个可能是数字也可能是负号，要完整接受一个多位数字：先通过一次性收集齐“.”前的字符，然后一次stod变成数字
if (isdigit(c)) {
num += c;
}
else if (c == '.') {//如果遇到是.就std
st.push(stoll(num));
num.clear();//输入完要清空
}
else if (c == '@') {
break;
}
else {
long long op2 = st.top(); st.pop();
long long op1 = st.top(); st.pop();

if (c == '+') {
//cout << op1 <<"+"<< op2 <<"="<<op1+op2 << endl;
st.push(op1 + op2);

}
else if (c == '-') {
//cout << op1 << "-" << op2 << "=" << op1 – op2 << endl;
st.push(op1 – op2);

}
else if (c == '*') {
//cout << op1 << "*" << op2 << "=" << op1 * op2 << endl;
st.push(op1 * op2);

}
else {
//cout << op1 << "/" << op2 << "=" << op1 / op2 << endl;
st.push(op1 / op2);

}
}

}
cout << st.top() << endl;
}

单调栈（下一个比自己大的元素 NGE问题）

​

​

牛只能看到之前比自己高的牛，比如53214 对于5号牛，只能看到5.对于4号牛能看到532，是一个单调递减栈。每次只需要pop调比自己矮的牛，那么s.size()就是能看到的数量了。

​

Map 字典（增删改查 且有不重复唯一键 带值去重）

不支持随机访问，必须用it迭代器

​

会对key建立索引。

如果是自定义类型的key，必须实现<

基本用法

​

​

find返回的是迭代器，如果是尾后迭代器就是没找到。

遍历的时候需要用i->first ->second输出元素。

练习

T424396

https://www.luogu.com.cn/problem/T424596

​

P1918

https://www.luogu.com.cn/problem/P1918

Set（增删改查 且本身就是可作为索引 唯一 去重）

不支持随机访问 必须用it迭代。

​

注意，set是有序的，是可以建立索引和遍历的。集合是无序的。

注意，set的插入是insert。

​

set的遍历

输出是有序的 这里插入10 15 11但是输出是唯一且有序的 7 8 10 11 15.

​

练习

带重复的第k小整数，但是要求不重复的顺序。最核心的痛点就是去重。

​

注意，set不支持随机访问，必须顺序遍历

//迭代器不可以跳变，只能一个个叠加上去。
auto it=s.begin();
for(int i=0;i<k-1;i++){
it++;
}

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

set<int> s;
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
s.insert(temp);
}
if(k > s.size()){
cout << "NO RESULT" << endl;
return 0;
}
//迭代器不可以跳变，只能一个个叠加上去。
auto it=s.begin();
for(int i=0;i<k-1;i++){
it++;
}
cout<<*it<<endl;
}

set和Map的upper_bound和lower_bound

当查找基于红黑树实现的容器，比如set和map，都可以用bound函数找到第一个满足大于这个值/小于这个值的值。

P5250

https://www.luogu.com.cn/problem/P5250

​

正确解法：利用 lower_bound

std::set 内部是红黑树，支持 O(log⁡N)的查找。我们可以利用 s.lower_bound(val)：

• 它会返回第一个 大于等于 val 的元素的迭代器。

策略：

找第一个大于等于val的迭代器

auto it_high=s.lower_bound(val)

然后就可以用

*(–it_high)

表达后一个

*(++it_high)

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

set<int> s;
//vector<int> vec;
int main(){
int m;
cin>>m;
for(int i=0;i<m;i++){
int op=0;
cin>>op;
if(op==1){
int val=0;
cin>>val;
auto it=s.find(val);
if(it==s.end()){//如果没招到
s.insert(val);
}else{
cout<<"Already Exist"<<endl;
}
}else if(op==2){
int val=0;
cin>>val;
auto it=s.find(val);
if(s.empty()){
cout<<"Empty"<<endl;
}else if(it!=s.end()){
s.erase(val);
cout<<val<<endl;
}else{//如果找不到长度一样的，就找最小的 直接上二分
auto it_high=s.lower_bound(val);//去找第一个满足大于val的迭代器
int chose=0;
if(it_high==s.end()){//如果所有的都不满足，说明都太短了
chose=*(–it_high);
}else if(it_high==s.begin()){//所有的都大于，都太长了
chose=*it_high;
}else{
int v_high=*it_high;
int v_low=*(–it_high);

if(v_high-val<val-v_low){//更近就选更近的，一样就选短的
chose=v_high;
}else{
chose=v_low;
}

}
s.erase(chose);
cout<<chose<<endl;
}

}
}
}

哈希（超大范围的不重复统计）不咋考

一般都需要offset偏移量

​

需要将一个大范围压缩到一个小范围时，比如key1的值是-1亿，key4是一亿，就需要映射到小桶中。因为数组不能开1e7的桶。

​

Unordered_Map和Unordered_Set

​

​​

​

 排序sort()

正序

sort(num.begin(), num.end());

逆序

// rbegin() 指向最后一个元素，rend() 指向第一个元素的前一个位置
sort(num.rbegin(), num.rend());

自定义类型使用sort()

​

如果 cmp(a, b) 返回 true，sort 就认为 a 应该排在 b 的前面。

如果 cmp(a, b) 返回 false，sort 就认为 a 应该排在 b 的后面（或者顺序不变）。

第二关键词排序

// 比较函数：优先按时间升序；时间相同时，按原始编号(idx)升序
bool cmp(const Node& a, const Node& b) {
if (a.t != b.t) return a.t < b.t;
return a.idx < b.idx;
}

​

精度限制输出

cout << fixed << setprecision(10) << ans << endl;

清空/初始化 Memset

对象、多少、大小sizeof

memset(arr, 0, sizeof(arr)); // 将整个数组的每个字节设为0