开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> STL总结篇（参考自《算法竞赛入门经典》） -> 正文阅读

[C++知识库]STL总结篇（参考自《算法竞赛入门经典》）

STL指的是C++的标准模板库，它包括一些算法和容器，这篇文章将会总结一些常用的STL（参考自《算法竞赛入门经典》）

排序与检索
不定长数组：vector
集合：set
映射：map
栈，队列与优先队列
测试STL（略）
应用

1.排序与检索

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

int a[]={10,0,2,5,6,7};

int main(){
    sort(a,a+6);
    for(int i=0;i<6;i++) cout<<a[i];
    return 0;
}

//0256710

sort使用数组元素默认的大小比较运算符进行排序，只有在需要按照特殊依据进行排序时才需要传入额外的比较函数。

sort数组的默认排序顺序是从小到大的，可以自定义一个compare函数来改变排序方式，也可以通过C++中的比较函数less,greater，这样就不需要我们自己家重新写比较函数了。

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

int a[]={10,0,2,5,6,7};

int cmp(int a,int b){
    return a>b;
}//从大到小

int main(){
    sort(a,a+6,cmp);
    //sort(a,a+6,greater<int>());
    //sort(a,a+6,less<int>());
    for(int i=0;i<6;i++) cout<<a[i]<<" ";
    return 0;
}

//10 7 6 5 2 0

algorithm头文件中的sort可以给任意对象排序，排序对象可以存在一个普通数组里（sort(a,a+n)）也可以存在vector里（使用sort(v.begin(),v.end()调用）包括内置类型和自定义类型，前提是类型定义了“<”运算符。排序之后可以用lower_bound查找大于或者等于x的第一个位置。待排序、待查找的元素可以放在数组里，也可以放在vector里。

（还有一个unique函数课一删除有序数组中的重复元素）

2.不定长数组：vector

vector就是个不定长数组，不仅如此，它把一些常用的操作封装在了vector类型内部。

例如，我们假设a是一个vector，vector<int> a;

读取大小：a.size();

改变大小：a.resize();

向尾部添加元素：a.push_back();

删除最后一个元素：a.pop_back();

清空：a.clear();

测试是否为空：a.empty();

vector可以直接赋值，也可以作为函数的参数或者返回值，而无需像传递数组那样另外用一个变量指定元素个数。

vector<int>a;
for(int i=0;i<10;++i){a.push_back(i);}
//
int a[6]={1,2,3,4,5,6};
vector<int>b;
vector<int>c(a,a+4);
for(vector<int>::iterator it=c.begin();it<c.end();++it)
{
	b.push_back(*it);
}
// 
int a[6]={1,2,3,4,5,6};
vector<int>b(a,a+4);
for(vector<int>::iterator it=b.begin();it!=b.end();it++){cout<<*it<<"  ";}

3.集合：set

集合和映射是两个常用的容器。set就是数学上的集合——每个元素最多只出现一次，和sort一样，自定义类型也可以构造set。定义在头文件<set>里。

返回set容器第一个元素的迭代器? begin()

返回一个指向当前set末尾元素的下一位置的迭代器.?end()

删除set容器中的所有的元素? clear()

判断set容器是否为空? empty()

返回当前set容器中的元素个数? size()

插入操作? intser()

查找set中某个键值出现的次数? count()

返回给定值值的定位器，若没找到则返回end()? find()

lower_bound(key_value) ，返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于等于key_value的定位器

int main(){
     set<int> s;
     s.insert(1);
     s.insert(2);
     s.insert(3);
     s.insert(1);
     cout <<s.size()<<endl;
     cout <<s.max_size()<<endl;
     cout <<*s.begin()<<endl;
     cout <<*s.end()<<endl; 
     s.clear();
     if(s.empty()){
         cout<<"set为空"<<endl;
     }
     return 0;
}

4.映射：map

map就是从键（key）到值（value）的映射。定义在头文件<map>里。

例如我们可以用一个map<string,int>month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。

map与set二者都支持insert、find、remove、count等等操作，并且可以按照从小到大的顺序循环遍历其中的元素，map还提供了[]运算符，这让map可以像数组一样进行使用。

注意：没有良好的代码设计，是很难发挥出如map这种STL的优势的，如果没有想到相应的好的思路就很难使用map简化代码。


map<int,string> mp;
mp.insert(pair<int,string>(123,lvshun));

iter = mapStudent.find("123");
 
if(iter != mapStudent.end())
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Do not Find"<<endl

5.栈，队列与优先队列

栈

栈即是符合后进先出规则的数据结构，有push和pop两种操作，push是将元素压入栈顶，而pop则是从栈顶将元素弹出。

栈定义在头文件<stack>中，可以用stack<int> s的方式来声明一个栈。

?push() 元素入栈

pop() 元素出栈

top() 取栈顶元素（但不删除）

队列

队列是符合先进先出原则的。

STL队列定义在头文件<queue>中，可以用queue<int> s;的方式声明一个队列。

push() 元素入队

pop() 元素出队

front() 取队首元素（但不删除）

优先队列

优先队列是一种抽象的数据类型，行为有些像队列，但先进队列的额元素不是先进队列的元素，而是队列中优先级最高的元素，这样就可以允许类似于“急诊病人插队”这样的事情发生。

与队列一样也定义在<queue>头文件里，用priority_queue<int> pq; 来声明。

这个pq是iyige越小的整数优先级越低的优先队列，由于出队元素并不是最先进队的元素，出队的方法变为了top()；

自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只需要能比较大小即可。（我们不难想到前面所述的sort）

在一些特殊的情况下，需要使用自定义方式比较优先级。

对于一些常见的优先队列，STL提供了更为简单的定义方法，例如越小的整数优先级越大的优先队列可以写成priority_queue<int,vector<int,greater<int> > pq;注意最后两个>>最好不要写在一起，有些编译器会认为是“>>”运算符。

7.应用

原题链接：

J - Ginger的牧场 | SDUT OnlineJudge

这是一道校选拔赛题，二分图板子，注意要使用map映射。


#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
int e[N],h[N],ne[N],idx;
vector<int> cows;
unmap(string,int) mp;
//int cow,cow_m;
int n,m,q;
int match[N];
bool st[N];
//
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            if(match[j]==0||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
signed main(){
    IOS;
    cin>>n>>m>>q;
    mem(h,-1);
    idx=0;
    while(q--){
        string a,b;
        cin>>a>>b;
        if(!mp.count(a)){
            mp[a]=++idx;
            cows.pb(mp[a]);
        }
        if(!mp.count(b)) mp[b]=++idx;
        add(mp[a],mp[b]);
    }
    int res=0;
    for(auto cow :cows){
        mem(st,false);
        if(find(cow)) res++;
    }
    cout<<res<<endl;
}
//made by shun 20220714

Problem - I - Codeforces

使用堆栈模拟

/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 11*/

#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=2e6+5;
//
int n;
string s;
int pre[N];
//
signed main(){
    IOS;
    
    cin>>n;
    cin>>s;
    stack<int> a;
    mem(pre,0);
    int len = s.size();
    for(int i=0;i<len;i++){
        if(s[i]>='0'&&s[i]<='9'){
            int x=0;
            while(s[i]>='0'&&s[i]<='9'){
                x=x*10+s[i]-'0';
                i++;
            }
            i--;
            if(a.empty()) a.push(x);
            else{
                pre[x]=a.top();
                a.push(x);
            }
        }
        else if(s[i]==')') a.pop();
    }
    for(int i=1;i<n;i++){
        cout<<pre[i]<<' ';
    }
    cout<<pre[n]<<endl;
}
//made by shun 20220714

（后续再更新几个好题找不到了。。）