常用c++ STL 汇总

常用STL：

vector

变长数组，倍增的思想
初始化：

//初始化
vector<int> a;
vector<int> a(n);
vector<int> a[n];
vector<int> a(n, 0);//长度为n，值为0

操作：

size() //返回元素个数
empty() //返回是否为空
clear() //清空
front()/back() //返回第一个/最后一个元素
push_back()/pop_back() //在尾端插入元素/删除元素
begin()/end()  //迭代器
[] //随机访问

遍历：

for(int i = 0; i < a.size(); ++ i)
for(vector<int>::iterator/*auto*/ i = a.begin(); i != a.end(); ++ i)
for(auto x : a)

黑科技：
- 支持比较运算，按字典序比较

pair

二元组
初始化：

pair<T, T> p;
pair<T, pair<T, T>> p;
p = make_pair(a, b);
p = {a, b};
p.first/p.second //第一个元素/第二个元素

黑科技：
- 也支持比较运算
- 以first为第一关键字，以second为第二关键字

string

字符串
初始化：

string a = "adfb";
a += "adf";
a += 'c';

操作：

size()/length() //返回字符串长度
empty() //返回是否为空
clear() //清空
substr() //求子串
a.substr(st, len) //从下标st开始长度为len的子串
a.substr(st) //从st开始到结尾的子串
c_str() //返回字符串地址
//printf()无法输出string，但是可以printf("%s", a.c_str);

queue

队列
初始化：同数组
操作：

size()
empty()
push() //想队尾插入元素
pop() //弹出队头元素
front() //返回队头元素
back() //返回队尾元素
//队列没有clear()函数

priority_queue

优先队列（堆）
初始化：

priority_queue<int> heap; //堆默认为大根堆
heap.push(-x); //将数反号实现小根堆
priority_queue<int, vector<int>, greater<int> > heap //直接定义小根堆

操作：

push() //插入一个元素
top() //返回堆顶元素
pop() //弹出堆顶元素

stack

栈
初始化：同数组
操作：

size()
empty()
push() //向栈顶插入元素
top() //返回栈顶元素
pop() //弹出栈顶元素

deque

双端队列
初始化：
操作：

size()
empty()
clear()
front()
back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
//操作多效率低

set

集合：无重复元素
基于平衡二叉树
操作：

size()
empty()
clear()
insert() //插入一个数
find() // 查找一个数
count() //返回某个数的个数
erase() //输入一个数x，删除所有x；输入一个迭代器，删除这个迭代器
lower_bound() //返回大于等于x的最小的数的迭代器
upper_bound() //返回大于x的最小的数的迭代器
//增删查改时间复杂度为log(n)

multiset
- 可以有重复元素
- 操作：同set
以下unoder 都不支持排序有关操作，因为是无序的，不支持lower_bound/upper_bound ，但是增删改查的时间复杂度为O(1)，不支持迭代器的加减
unordered_set
unordered_multiset

map
- map
  - 基于平衡二叉树
  - 元素是pair
- multimap
  - 操作：
```
insert() //插入的数是一个pair
erase() //输入的参数是pair或者迭代器
find()

map<string, int> a;
a["adf"] = 1; //支持随机插入/访问,时间复杂度为log(n)
lower_bound()/upper_bound()
//增删查改时间复杂度为log(n)
```
- 以下unoder 都不支持排序有关操作，因为是无序的，不支持lower_bound/upper_bound ，但是增删改查的时间复杂度为O(1)，不支持迭代器的加减
- unordered_map
- unordered_multimap

bitset

压位
- bool 类型位一个字节，8位
- 如：压位将bool 占用内存压缩1/8，使bool类型只占一个二进制位
- bitset 相当于一个二进制数组，数组里存0/1，一个数组元素占1个二进制位
初始化：

bitset<10000> s;

操作：

~, &, |, ^
>>, <<
==, !=
[]
count() //返回有多少1
any() //判断是否至少有一个1
none() //判断是否全为0
set() //把所有位置成1
set(k, v) //将第k位变成v
reset() //把所有位变成0
flip() //等价于~
flip(k) //把第k位取反

MoiLip

常用c++ STL 汇总

常用STL：

vector

pair

string

queue

stack

deque

set

map

bitset