总序

（1）只有vector、string、deque是可以用sort（默认从小到大，如果要改优先级则加cmp作为第三个参数），而set和map是用红黑树实现（自动排序）。
（2）只有vector和string能直接对迭代器加减某个数，如str.begin()+3——但注意起始advance(it,num)可以实现将迭代器it向后移动num位，如果num是负数则是向前移动；
注意string要用头文件< string >（和头文件<string.h>不一样）。
（3）C++11的unordered_set去重但不排序（如果不去重则用multiset），unordered_map不按key排序（速度比map快很多）。
（4）如果遇到一些不熟悉的stl，可以直接查询c++的官方文档，如map的count，里面有解释也有对应的栗子。

1.vector

（1）动态数组，方便动态扩容，方便的变量初始化(int类型默认初始化为0，bool默认初始化为false)。
（2）可以用来实现邻接表（结点数太多的图）。
（3）有些场合需要根据一些条件把部分数据输出在同一行，数据中间用空格隔开。由于输出数据的个数不确定，为了更方便地处理最后一个满足条件的数据后面不输出额外的空格，可以先用vector记录所有需要输出的数据，然后一次性输出。

头文件

#include<vector>
using namespace std;

  
 

  
1
  
2
 

定义

//typename可以是基本数据类型/其它标准STL容器/自定义结构体
vector<typename>name;
vector<int>v1;

vector<vector<int> >v2;//两个维度都是动态（数组）的
vector<int> vi[100];//每个vi[i]都是一个vector容器

  
 

  
1
  
2
  
3
  
4
  
5
  
6
 

元素访问

//1.下标访问
v[i];//和v.begin()+i是等价的
//2.迭代器访问
vector<typename>::iterator it;
auto it;//另一种迭代器简易定义方法
for(auto it=v.begin();it!=v.end();it++)
	cout<<*it;
for(int i=0;i<5;i++)
	printf("%d ",*(it+i));
//只有vector和string的迭代器it可以进行算术运算进行访问元素。

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

注意要支持C++11才能使用上面的auto这种写法。

常用函数

使用场景

• 元素个数不确定
• 用于实现邻接表存储图

2.set

内部自动有序且不含重复元素的集合

头文件

#include<set>
using namespace std;

  
 

  
1
  
2
 

定义

set<typename> name;

  
 

  
1
 

元素访问

for(auto it=v.begin();it!=v.end();it++)
	cout<<*it;

  
 

  
1
  
2
 

常用函数

使用场景

• 自动去重并按升序排序

扩展

• 需要元素不唯一，使用multiset
• 需要元素不排序，unordered_set（内部以散列代替了set内部的红黑树）

3.string

字符串，可以替换为C语言版本的字符数组(str.c_str()😉

头文件&定义

#include<string>
using namespace std;
string str;

  
 

  
1
  
2
  
3
 

内容访问

///1.下标访问
str[i]
//2.输出输出只能用cin和cout，除非转化为字符数组
//3.迭代器访问

  
 

  
1
  
2
  
3
  
4
 

常用函数

4.map

将任何基本类型映射到任何基本类型（包括STL容器）
可以用于hash散列（当元素个数比较多时，不适合用数组散列，就用map）
（1）需要建立字符（或字符串）与整数之间映射的题；
（2）判断大整数或其他类型数据是否存在的题目，可以将map当bool数组使用。

头文件及定义

#include<map>
using namespace std;
map<typename1,typename2> mp;

  
 

  
1
  
2
  
3
 

元素访问

//1.下标
mp['c']    mp[0]   mp["key"]
//2.迭代器
for(auto it=mp.begin();it!=mp.end();it++)
	cout<<it->first<<" "<<it->second;

  
 

  
1
  
2
  
3
  
4
  
5
 

常用函数

使用场景

• 散列表
• 其他映射
  扩展
• 多映射，即一个key对应多个value，使用mutimap
• undered_map可以替代map,内部实现使用散列代替了map内部的红黑树实现，用于处理只映射而不需要按key来排序的需求，速度快。

5.queue

队列，先进先出的容器，常用语广度优先遍历BFS

头文件及定义

#include<queue>
using namespace std;
queue<typename>name;

  
 

  
1
  
2
  
3
 

常用函数

使用场景

• BFS
  另外，需要注意使用front(),back(),pop()函数前，必须判断是否为空队列（empty函数）
  扩展
• deque(double end queue,双端队列)首位皆可插入和删除u
• priority_queue,使用堆实现的默认将当前队列最大元素置于队首的容器

6.priority_queue

优先队列，默认情况下是将队列中最大元素置于队首，优先级可以自定义。每次进行push().pop()操作，底层的数据结构堆（heap）都会随时调整调整，使优先级最高的元素永远在队首。

头文件&定义

#include<queue>
using namespace std;
priority_queue<typename> name;

  
 

  
1
  
2
  
3
 

常用函数

优先级设定

基本数据类型(int ,double,char)默认数字大或字典序大的优先级高。

priority_queue<int,vector<int>,greater<int>> q;

  
 

  
1
 

• greater表示这个数字越小，优先级越高
• less表示数字越大，优先级越高（默认情况）
  vector表示底层数据堆(heap)的容器
  结构体优先级设置

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2);
		return f1.price>f2.price;
	}
}f1,f2,f3;
int main(){
	priority_queue<fruit> q;
	f1.name="桃子";
	f.price=3;
	f1.name="梨子";
	f.price=4;
	f1.name="苹果";
	f.price=1;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<<q.top().name<<" "<<q.top().price<<endl;
	return 0;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

使用场景

（1）priority_queue可以解决一些贪心问题，也可以用于dijkstra算法的顶点选择（优化）中（因为优先队列的本质是堆）。
（2）注意使用top函数之前判断队列是否为空（empty()函数）。

7.stack

栈，先今后出

头文件及定义

#include <stack>
using namespace std;
stack<typename> name;

  
 

  
1
  
2
  
3
 

常用函数

使用场景

递归模拟，防止递归深度过深，DFS模拟

8.pair

**头文件及使用

#include<utility>//或者偷懒用头文件<map>，因为map包含了utility
using namespace std;
//map实现中设计pair，使用map时自动添加了该头文件

pair<typename1,typename2> name;
paif<string,int> p("hahahah",7);
make_pair("haha",4);
cout<<p.first<<" "<<p.second;

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

（1）用来代替二元结构体及其构造函数，省时。
（2）作为map的键值对来进行插入。如下栗子：

map<string,int>mp;
mp.insert(make_pair("guoguo",1));
mp.insert(pair<string,int>("guoguo2",2);
for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
	cout<<it->first <<" "<<it->second<<endl;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
 

9.algorithm常用函数

algorithm头文件下的常用函数有max()、min()、abs()（这个abs的x必须是整数），浮点数的绝对值要用math头文件的fabs()。
swap(x,y)交换x和y变量的值。
reverse(x,y)将数组指针/容器的迭代器在[it,it2)之间的元素进行反转。
利用#include< algorithm >头文件的next_permutation()函数。

#include <iostream>
#include <algorithm>
using namespace std;
int sum=0;
int main()
{
	int a[6]={1,2,3}; 
	do{
		for(int i=0;i<3;i++)
			cout<<a[i];
		cout<<endl;
		sum++;
	}while(next_permutation(a,a+3));
	cout<<sum;
	system("pause");
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

（1）使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false，这样会方便退出循环；
（2）使用do…while语句而不使用while语句是因为序列1 2 3本身也需要输出，而如果用while语句会直接跳到下一个序列（1 3 2）再输出（即少了一个1 2 3）。

关于lower_bound和upper_bound就复习下这个：https://andyguo.blog.csdn.net/article/details/112369996。
最后一个是

（$）sort函数排序：

（1）基本数据类型数组/string型
如对int/double/char型数组排序，或对string字符串排序——sort(s.begin(),s.end());
（2）结构体数组
sort排序默认是从小到大，如果要从大到小排序：(注意functional的头文件)：

#include<algorithm>
#include<functional>
int a[100000];
sort(a,a+n,greater<int>());
//或者
int cmp(int a,int b){return a>b;}
sort(a,a+n,cmp);

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

符号重载的node结构体作为set的元素自动排序（按频率cnt降序，如cnt同则编号升序）
注意运算符重载在结构体中的写法：

struct node{
	int value,cnt;
	bool operator<(const node &a)const{
		return (cnt!=a.cnt)?cnt>a.cnt:value<a.value;
		//第一优先级:频率降次  第二优先级:编号
	}
};

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

（3）容器的排序
只有vector、string、deque是可以使用sort，而set、map是用红黑树实现，内部的元素自动排序了，所以不用sort。

附各容器操作：

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/104069065