栈 (stack) 先进后出（第一个进最后一个出）
定义： stack < typename > name, 如stack< int > st;
| 函数 | 注释 |
|---|---|
| push(x) | 将x入栈 |
| pop() | 将栈顶元素出栈 |
| top() | 获取栈顶元素 |
| empty() | 判断栈内是否为空，true为空，false为非空 |
| size() | 获取栈内元素个数 |
| 上述函数时间复杂度均为O(1） |
队列 (queue） 先进先出（第一个进最后一个出）
定义： queue < typename > name, 如queue< int > st;
| 函数 | 注释 |
|---|---|
| push(x) | 将x入队 |
| pop() | 将队首元素出队 |
| front() | 获取队首元素 |
| back() | 获取队尾元素 |
| empty() | 判断队内是否为空，true为空，false为非空 |
| size() | 获取队内元素个数 |
优先队列 (priority_queue)
与队列不同的是，优先级最大的元素永远在最上面（队首）
比如可以快速获得最大值与最小值
定义：priority_queue<int, vector< int >, less< int > > q1; 获取最大值
priority_queue<int, vector< int >, greater< int > > q1; 获取最小值
也可以用结构体定义排序
top() 用来获取优先级最高的元素
优先队列没有back() 操作，且不会去重
其余函数与队列一样
动态数组 (vector) 长度可以根据需要自动改变的数组
定义：vector < typename > name; typename可以为任何基本数据类型，如int, double, char, …
定义完可进行初始化，如 vector< int > v{2,1,3,5,3};
访问方式：
-
通过下标访问
vector< int > v{2,1,3,5,3};
for(int i=0;i<v.size();i++)
cout<<v[i]<<" "; -
通过迭代器访问
vector< int > v{2,1,3,5,3};
for(auto it=mp.begin();it!=mp.end();it++)
cout<<*it<<" ";
| 函数 | 注释 |
|---|---|
| push_back(x) | vector后面添加一个元素x |
| pop_back() | 删除vector的尾元素 |
| size() | 获取vector内元素个数 |
| back() | 获取队尾元素 |
| insert(it,x) | vector的任意迭代器it处插入一个x |
| erase() | 删除单个或一个区间内所有元素 |
| clear() | 删除所有元素 |
二维vector
定义：vector< vector< typename > > name;
vector表示内层vector, vector< vector > 表示外层vector，即二维vector
访问元素时可以使用两个下标，如 v[i][j] = 1
集合 (set)，特点为自动去重，自动排序，可以快速查找
定义：set< typename > name;
set只能通过迭代器访问，方式与vector类似
set< int > s{2,1,3,5,3};
for(auto it=s.begin();it!=s.end();it++)
cout<<*it<<" ";
| 函数 | 注释 |
|---|---|
| insert(x) | 将x插入set中 |
| find(x) | 返回set中对应值为x的迭代器，否则返回end() |
| erase(first, last) | 删除一个区间内所有元素 |
| clear() | 删除所有元素 |
| lower_bound(x) | 返回首个大于等于x的元素，若不存在返回end() |
| upper_bound(x) | 返回首个大于x的元素，若不存在返回end() |
| erase(first, last) | 删除一个区间内所有元素 |
| size() | 获取set中元素个数 |
| empty() | 判断set是否为空，1空0不空 |
| count(x) | 判断x元素是否存在，1存在0不存在 |
映射 (map) 由一个基本类型映射到另一个基本类型
定义：map<key, value> mp;
例子：map<string, int> mp;
访问方式：
-
通过键访问，注意键是唯一的
map<string, int> mp;
mp[“a”]++;
mp[“b”]++;
mp[“a”]++;
cout<<mp[“a”]<<" "<<mp[“b”]; // 2 1 -
通过迭代器访问
for(auto it=mp.begin();it!=mp.end();it++)
cout<first<<" "<second<<endl;
it->first访问键，it->second访问值
注意map会以键从小到大自动排序
| 函数 | 注释 |
|---|---|
| size() | 获取map映射的个数 |
| find(key) | 返回键为key的映射的迭代器 |
| erase(it) | 删除单个元素的迭代器 |
| erase(key) | 删除单个元素映射的键 |
| clear(x) | 删除map中所有元素 |
unordered_map的元素没有顺序
map与set都可用count来判断元素是否存在