【蓝桥杯冲刺省一，省一看这些就够了-C++版本】蓝桥杯STL模板及相关练习题

蓝桥杯历年省赛真题

点击链接免费加入题单

STL

map及其函数

map<key,value> 提供一对一的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。map 中的第一个值称为关键字(key)，每个关键字只能在 map 中出现一次，第二个称为该关键字的值(value)，可以重复。

// 定义，以 string, int 对为例
#include <map>
map<string, int> mp;     // 底层是红黑树，元素可比较大小，key 的结构体要重载 < 运算// 2- 插入
mp.insert(make_pair("zhs", 18));        // 插入一个键值对，若原先存在该 key，则无法插入和覆盖
mp.insert(pair<string,int>("zhs", 18)); // 插入一个键值对，若原先存在该 key，则无法插入和覆盖
mp["zhs"] = 18;                         // 甚至可以类似数组下标去访问 key 对应的 value，若原先不存在该 key，则创建，若原先存在，则覆盖以前该关键字对应的值
mp.emplace("zhs", 18);                  // 插入效果跟 insert 效果完全一样// 3- 删除
mp.erase(key);     // 删除值为 key 的元素
mp.erase(iter);    // 删除迭代器 iter 指向的元素，例如 mp.erase(mp.begin());
mp.erase(iter1, iter2); // 删除区间 [iter1, iter2) 的所有元素，例如 mp.erase(mp.begin(), mp.end());
mp.clear();        // 清空集合// 3- 求大小
int siz = mp.size();         // 求集合大小
bool flag = mp.empty();      // 集合判空// 4-查询
if(mp.find(key) != mp.end())           // find 函数返回一个指向被查找到元素的迭代器cout << mp[key] << endl;
if(mp.count(key))                // count 返回某个值元素的个数cout << mp[key] << endl;
auto iter = mp.lower_bound(key);   // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
auto iter = mp.upper_bound(key);   // 求 key 的上界，返回大于某个值元素的迭代器// 5-遍历
map<string, int>::iterator iter;             // 正向遍历
for(iter=mp.begin(); iter!=mp.end(); iter++)
{cout << iter->first << " " << iter->second << endl;// 或者cout << (*iter).first << " " << (*iter).second << endl;
}
map<int>::reverse_iterator riter;    // 反向遍历
for(riter=mp.rbegin(); riter!=mp.rend(); riter++)
{// 遍历的同时修改iter->second += 10;cout << iter->first << " " << iter->second << endl;
}
for (auto x : mp){               // C++ 11 auto 遍历cout << x.first << " " << x.second << endl;
}
for (auto& x : mp){               // C++ 11 auto 遍历x.second += 10;   // 遍历并修改cout << x.first << " " << x.second << endl;
}// 6- 求最值
map<string, int>::iterator it = mp.begin();    // 最小值
cout << *it << endl;
map<string, int>::iterator it = mp.end();      // 最大值
cout << *(--it) << endl;/*
1. map 和 set 一样，其中的元素必须支持 < 运算符
2. 在插入时，使用 insert 和 用数组方式去插入，在原先存在要插入的键值时是有区别的，insert不会插入，用数组方式插入则会直接覆盖原先数据
3. map 的迭代器支持 ++、--、==、!=、(*iter).first、 (*iter).second、iter->first、 iter->second 等操作
4. map 的迭代器不支持 +、-、 +=、-= 等算术操作符，也不支持 >、<、>=、<= 等比较操作符
*/

map的插入与遍历

#include<bits/stdc++.h>using namespace std;map<string,int> m;int main(){int n,age;string s;cin >> n;for(int i = 1;i <= n;i++){cin >> s >> age;m[s] = age;}map<string,int>::iterator it;for(it = m.begin();it != m.end();it++){cout << it->first<< " "<< it->second<<endl;}
}

map的查询

#include<bits/stdc++.h>
using namespace std;
map<string,string> ma;
pair<string,string> p;
int main(){int m,n,a;string s,t,str;set<string,string>::iterator it;cin >> n >> m;for(int i=1;i<=n;i++){cin >> s >> t;p.first = s;p.second = t;ma.insert(p);} for(int i=1;i<=m;i++){cin >> a>> str;if(a==1){if(ma.find(str)!=ma.end()){cout << ma[str];}else{cout << "NO";}}if(a==2){if(str <= (ma.begin()->first)){cout<<"NO";}else{auto it = ma.lower_bound(str);it--;cout<< it->second;}}if(a==3){if(str >= ((--ma.end())->first)){cout<<"NO";}else{auto it = ma.upper_bound(str);cout<<it->second;}}cout << endl; }
}

set及其函数

set 的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入、删除、查找等操作，就像一个集合。所有的操作的都是严格在 $O (l o g n)$ 时间之内完成，效率非常高。 set 和 multiset 的区别是：set插入的元素不能相同，但是 multiset 可以相同。

// 1- 定义
#include <set>
set<int> s;     // 元素必须可比较大小，元素类型必须要支持 < 运算，结构体需要重载 <// 2- 插入
s.insert(key);    // 插入// 3- 删除
s.erase(key);     // 删除值为 key 的元素
s.erase(iter);    // 删除迭代器 iter 指向的元素，例如 s.erase(s.begin());
s.erase(iter1, iter2); // 删除区间 [iter1, iter2) 的所有元素，例如 s.erase(s.begin(), s.end());
s.clear();        // 清空集合// 4- 求大小
int siz = s.size();         // 求集合大小
bool flag = s.empty();      // 集合判空// 5-查询
if(s.find(key) != s.end())           // find 函数返回一个指向被查找到元素的迭代器cout << "exist" << endl;
if(s.count(key) == 1)               // count 返回某个值元素的个数cout << "exist" << endl;set<int>::iterator iter = s.lower_bound(key);   // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
set<int>::iterator iter = s.upper_bound(key);   // 求 key 的上界，返回大于某个值元素的迭代器// auto 类型推断关键字 在NOI 系列比赛中也可以使用了
auto iter = s.lower_bound(key);   // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
auto iter = s.upper_bound(key);   // 求 key 的上界，返回大于某个值元素的迭代器// 6-遍历
set<int>::iterator iter;             // 正向遍历
for(iter=s.begin(); iter!=s.end(); iter++)
{cout<<*iter<<endl;
}
set<int>::reverse_iterator riter;    // 反向遍历，不重要
for(riter=s.rbegin(); riter!=s.rend(); riter++)
{cout<<*riter<<endl;
}// 7- 求最值
set<int>::iterator it = s.begin();    // 最小值
cout << *it << endl;
set<int>::iterator it = s.end();      // 最大值
cout << *(--it) << endl;/*
注意：
1. set 和优先队列一样，其中的元素必须支持 < 运算符
2. set 的迭代器支持 ++、--、==、!=、*iter 等操作
3. set 的迭代器不支持 +、-、 +=、-= 等算术操作符，也不支持 >、<、>=、<= 等比较操作符
*/

set的插入与遍历

#include<bits/stdc++.h>
using namespace std;
int main(){set<int> s;//set可以自动去重和排序，默认升序 int n,t;cin >> n;for(int i=1;i<=n;i++){cin >> t;s.insert(t);//set没有push_back操作 }set<int>::iterator it;//set需要使用迭代器遍历数据 for(it=s.begin();it!=s.end();it++){//set支持双向迭代器 cout << *it << " ";}
}

set的查询

#include<bits/stdc++.h>
using namespace std;
int n, m, c, x;
set<int>a;
set <int, greater<int>> b;
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {int t;cin >> t;a.insert(t);b.insert(t);}for (int i = 1; i <= m; i++) {cin >> c >> x;if (c == 1) {if (a.find(x) != a.end())cout << x << "\n";else cout << "NO\n";}if (c == 2) {set<int>::iterator it;it = b.upper_bound(x);//二分查找，找第一个大于x的数的地址if (it != b.end()) {cout << *it << "\n";} else cout << "NO\n";}if (c == 3) {set<int>::iterator it;it = a.upper_bound(x);if (it != a.end()) {cout << *it << "\n";} else cout << "NO\n";}}
}

priority_queue优先队列

因为堆的作用主要是用来获取最大/最小值，类似队列的取最值操作，因此堆有一个别名叫优先队列。在 STL 中提供了"优先队列“的模板，即 priority_queue。关于优先队列具体的应用会在二叉堆与对顶堆中详细讲解。

常见使用

#include <queue>
using namespace std;
// using std::priority_queue;
priority_queue<int> q;    // 定义一个空的优先队列，默认是大根堆void test()
{int x = 5;q.push(x);       // 将 5 插入堆，这时堆顶是 5q.push(3);       // 将 3 插入堆，这时堆顶是 5q.push(2*x);     // 将 10 插入堆，这时堆顶是 10int k = q.top(); // 取堆顶元素，应该是 10q.pop();         // 删除堆顶元素，删除了 10，这时堆顶为 5int s = q.size();// 求堆中元素个数，应为 2// 清空优先队列的一种方法while(!q.empty())q.pop();// 清空优先队列的第二种方法q = priority_queue<int>();
}

实现小根堆

// 大根堆改成小根堆，其中 vector<Type> 为内部存储容器，greater<Type> 为比较方式
priority_queue<Type,vector<Type>,greater<Type>> q; // 常为 int 类型
priority_queue<int,vector<int>,greater<int>> q;

优先队列与结构体重载运算符

// 只能用于大根堆的结构体
struct node{int val;string info;...// 大根堆，重载小于运算符bool operator <(const node& other) const {return val < other.val;}
};
// 定义一个大根堆（默认）
priority_queue<node> q;// 只能用于小根堆的结构体
struct node{int val;string info;...// 小根堆，重载大于运算符bool operator >(const node& other) const {return val > other.val;}
};
// 定义一个小根堆（默认）
priority_queue<node,vector<node>,greater<node>> q;

pair

将两个变量成对组合打包在一起的数据类型，可以理解为C++内置的保存两个元素(类型可以自定义)的结构体常见的应用就是保存坐标等
pair 支持比较运算符。其比较规则是:先比较第一个元素，如果第一个元素值相等，再比较第二个元素。

pair<int,int> pos;
pos.first = 1;
pos.second = 1; 
a = make_pair(1,1);
a = pair<int,int>(1,1);

vector及其函数

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

vector插入

#include<bits/stdc++.h>
using namespace std;
int a[15];
int main(){int n,x,y;cin >> n ;for(int i=1;i<=n;i++){cin >> a[i];}cin >> x >> y;vector<int> v(a+1,a+n+1);v.insert(v.begin()+x-1,y);for(int i=0;i<v.size();i++){cout << v[i] << endl;}
}

vector遍历

#include<bits/stdc++.h>
using namespace std;
vector<int> a[100100];
int n,m,i,j,x,y; 
int main(){cin >> n>> m;for(i=1;i<=m;i++){cin>> x>> y;a[x-1].push_back(y);//这里使用a[x]也是可以的}for(i=0;i<n;i++){cout << a[i].size();sort(a[i].begin(),a[i].end());//对每一个向量排序for(j=0;j<a[i].size();j++){cout << " "<<a[i][j];} cout<< endl;}return 0;
}

vector排序

#include<bits/stdc++.h>
using namespace std;
vector<int> a[1005];//定义向量数组
int main(){int n,c,x;cin >> n;for(int i=1;i<=n;i++){cin >> c;for(int j=1;j<=c;j++){cin>> x;a[i].push_back(x);}sort(a[i].begin(),a[i].end());}sort(a+1,a+n+1);for(int i=1;i<=n;i++){for(int j=0;j<a[i].size();j++){cout << a[i][j]<< " ";}cout << endl;} 
}