STL用法总结（二）（deque,map,set)

4.deque（双端队列）

1.介绍

首尾都可插入和删除的队列为双端队列

#include<deque> //初始化定义 deque<int> dq;

2.方法函数

3.注意

deque可以排序

双端队列排序一般不用，感觉毫无用处，使用其他STL依然可以实现相同功能

//从小到大
 sort(q.begin(), q.end())
 //从大到小排序 
sort(q.begin(), q.end(), greater<int>());
//deque里面的类型需要是int型 
sort(q.begin(), q.end(), greater());//高版本C++才可以用

5.map

1.介绍

映射类似于函数的对应关系，每个x对应一个y，而map是每个键对应一个值。

//头文件 
#include<map>
 //初始化定义 
map<string, string> mp; 
map<string, int> mp; 
map<int, node> mp;//node是结构体类型

map特性：map会按照键的顺序从小到大自动排序，键的类型必须可以比较大小

2.方法函数

查找元素是否存在时，可以使用 ①mp.find() ② mp.count() ③ mp[key] 但是第三种情况，如果不存在对应的key时，会自动创建一个键值对（产生一个额外的键值对空间） 所以为了不增加额外的空间负担，最好使用前两种方法

3.遍历

1.mp.begin()和mp.end()

正向遍历

map<int,int> mp;
 mp[1] = 2; 
mp[2] = 3;
 mp[3] = 4;
 auto it = mp.begin(); 
while(it != mp.end()) { 
cout << it->first << " " << it->second << "\n";
 it ++; }

结果：

1 2 2 3 3 4

2.mp.rbegin()和mp.rend()

用于逆向遍历

map<int,int> mp; 
mp[1] = 2;
 mp[2] = 3;
 mp[3] = 4; 
auto it = mp.rbegin(); 
while(it != mp.rend()) {
 cout << it->first << " " << it->second << "\n"; it ++; }

结果：

3 4 2 3 1 2

也可用智能指针

for(auto i : mp) 
cout << i.first << " " << i.second << endl;//键，值

4.二分查找

二分查找lower_bound()和upper_bound()

map的二分查找以第一个元素（即键为准），对键进行二分查找 返回值为map迭代器类型

include<bits/stdc++.h> using namespace std;
int main() { 
map<int, int> m{{1, 2}, {2, 2}, {1, 2}, {8, 2}, {6, 2}};//有序
 map<int, int>::iterator it1 = m.lower_bound(2);
 cout << it1->first << "\n";//it1->first=2
 map<int, int>::iterator it2 = m.upper_bound(2); 
cout << it2->first << "\n";//it2->first=6 
return 0; }

6.set

1.介绍

set容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且set容器里的元素自动从小到大排序。

即：set里面的元素不重复 且有序

//头文件
#include<set> 
//初始化定义 
set<int> s;

2.遍历

1.迭代器访问

for(set<int>::iterator it = s.begin(); it != s.end(); it++) 
cout << *it << " ";`

2.智能指针

for(auto i : s)
 cout << i << endl;

3.重载<运算符

1.改变set排序规则

set中默认使用less比较器，即从小到大排序。（常用）

set<int> s1; // 默认从小到大排序
 set<int, greater<int> > s2; // 从大到小排序

2.自定义比较规则

set<int, function<bool(int, int)>> s([&](int i, int j){
 return i > j; // 从大到小
 }); 
for(int i = 1; i <= 10; i++)
 s.insert(i); 
for(auto x : s)
 cout << x << " ";