Stack

stack 后入先出（LIFO）栈

头文件

#include<stack>

定义

stack<int> s;

函数

函数	功能
q.top()	获取栈顶元素（并不删除）
q.pop()	删除栈顶元素
q.push(x)	向栈中加入元素
q.empty()	判断栈是否为空

Queue

queue 先入先出（FIFO）队列

头文件

#include<queue>

定义

queue<int> q;

函数

函数	功能
q.front()	获取队首元素（并不删除）
q.pop()	删除队首元素
q.push(x)	向队列中加入元素
q.empty()	判断队列是否为空

priority_queue 优先队列

头文件

#include<queue>

定义

priority_queue<int> q; // 队头最大

priority_queue<int,vector<int>,greater<int> > q; 队头最小

函数

函数	功能
q.top()	获取优先队列中最大的元素（并不删除），其时间复杂度为$O(1)$
q.pop()	删除优先队列中最大元素，其时间复杂度为$O(log n)$
q.push(x)	向优先队列中加入元素，其时间复杂度为$O(log n)$
q.empty()	判断优先队列是否为空

Set 与 Multiset

set不允许重复 multiset允许重复
例: set : 1 2 3 4 5 6
multiset : 1 2 2 3 3 3

头文件

#include <set>

定义

multiset<int> s[N];//定义
multiset<int>::iterator it;//迭代器

函数

操作	效果
s.size()	返回当前的元素数量
s.empty ()	判断大小是否为零，等同于$0==size()$，效率更高

操作	效果
count (elem)	返回元素值为$elem$的个数
find(elem)	返回元素值为$elem$的第一个元素，如果没有返回$end()$
lower _bound(elem)	返回元素值$>=elem$的第一个元素位置
upper _bound (elem)	返回元素值$>elem$的第一个元素位置

操作	效果
s.begin()	返回一个随机存取迭代器，指向第一个元素
s.end()	返回一个随机存取迭代器，指向最后一个元素的下一个位置

操作	效果
s.insert(elem)	插入一个$elem$副本，返回新元素位置，无论插入成功与否。
s.erase(elem)	删除与$elem$相等的所有元素，返回被移除的元素个数。
s.erase(pos)	移除迭代器$pos$所指位置元素，无返回值。
s.clear()	移除所有元素，将容器清空

离散化

std::unique

功能：对有序的容器重新排列，将第一次出现的元素从前往后排，其他重复出现的元素依次排在后面
返回值：返回迭代器，迭代器指向的是重复元素的首地址

std::lower_bound

lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了第一个大于等于value 的值。
ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

std::upper_bound

upper_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了第一个大于value 的值。这两个函数为C++ STL内的函数。
ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

std::sort(b + 1, b + cnt + 1);
int *end = std::unique(b + 1, b + cnt + 1);
for(int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, end, a[i]) - b;

本文由落影汐雾原创，采用保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://x.lyxw.xyz/2019/C++_stl/