C++ 常用容器：栈、优先队列、map、set 与 bitset

stack：栈

stack<int> stk; // 栈的定义，括号内为数据类型

stk.empty()  //  当栈内为空，返回true
stk.top()  // 返回栈顶元素
stk.push()  // 将括号内的元素压入栈中
stk.pop()  //  将栈顶元素弹出

//www.starrycoding.com/problem/38
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
using ll = long long;
ll a[N];

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	stack<int> stk;    
	int pos = 1;
	for(int i = 1;i <= n;++i)
	{
		while(pos <= n && ( stk.empty() || stk.top() != i ) ) stk.push(a[pos++]);
		
		if(stk.top() == i)stk.pop();
		else
		{
			cout << "No" << '\n';
			return 0;
		}
	}
	cout << "Yes" << '\n';
}

priority_queue：优先队列

priority_queue<ll> pq  //优先队列的定义，括号内为参数类型,默认是大根堆
pq.top()  //返回优先队列的顶部元素
pq.pop()  //弹出优先队列的顶部元素
pq.push()  //将括号内的元素压入优先队列
    
priority_queue<ll,vector<ll>,greater<ll> > pq  //换为小根堆，从大到小

另一种切换为小根堆的方法：
struct cmp{
    bool operator()(const ll &u, const ll & v)const
    {
        return u > v;
    }
}
priority_queue<ll,vector<ll>,greater<ll> > pq

//www.starrycoding.com/problem/58
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
using ll = long long;
ll a[N];

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int q;cin >> q;
	priority_queue<ll> pq;
	ll sum = 0;
	while(q--)
	{
		int n;cin >> n;
		if(n == 1) 
		{
			ll x;cin >> x;
			pq.push(x);
			sum+=x;
		}
		else if(!pq.empty())
		{
			sum -= pq.top();
			pq.pop();
		}
	}
	cout << sum << '\n';
}

map：键值映射

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin >> T;
	
	map<string, int> mp;
	vector<string> v;
	while(T--)
	{
		map<string, int> mp;
		vector<string> v;
		int n;cin >> n;
		for(int i = 1;i <= n;++i)
		{
			string s;cin >> s;
			if(mp.count(s)) mp[s]++;
			else{
				v.push_back(s);
				mp[s] = 1;
			}
		}
		for(auto &i : v) cout << i << ' ' << mp[i] << '\n';
	}
}

set：去重集合

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	set<ll> st;
	ll n;cin >> n;
	for(int i = 1;i <= n;++i)
	{
		ll x;cin >> x;
		st.insert(x);
	}
	for(auto &i : st) cout << i << ' ';
}

bitset：位集合

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e3+9, M = 5e5+9;
ll a[N];

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n;cin >> n;
	bitset<M> bt;
	bt[0] = 1;
	for(int i= 1;i <= n;++i)cin >> a[i];
	
	for(int i = 1;i <= n;++i)
	{
		bt |= (bt << a[i]);
	}
	cout << bt.count() << '\n';
}