📮 STL 常用容器

简记

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位取反

⛓ string

📋 简介： string (opens new window)是 C++ 风格的字符串，而 string 本质上是一个类

1. string 和 char * 区别：
   • char * 是一个指针
   • string 是一个类，类内部封装了 char *，管理这个字符串，是一个 char * 型的容器
2. 特点：
   • string 类内部封装了很多成员方法。例如：查找 find()，拷贝 copy()，删除 delete()，替换 replace()，插入 insert()
   • string管理 char *所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

在这里不对两者的区别进行深入讲解，只讲解 string 的基本操作，起到方便查询的作用。

📝 头文件与创建：

#include <string>
// 创建
string s1 = "hello world!";	// 最常用
string s2(s1);
string s3(9, 'a');	// s3 = "aaaaaaaaa"

➰ 示例1：string 综合使用

#include <iostream>
#include <string>
using namespace std;
/* 示例1 - string综合使用 */
void example()
{
	// 1.创建 
	string s1 = "hello world, my name is [haha | heihei | hehe]. Let's go!";
	// 2.添加数据 
	s1 += " Where you go?";
	// 3.遍历/输出 
	  // 法一：直接法
	cout << s1 << endl;
	  // 法二：遍历法
	for (int i = 0; i < s1.length(); i ++ ) cout << s1[i];
	cout << endl; 
	// out: hello world, my name is [haha | heihei | hehe]. Let's go! Where you go?
	// 4.大小
	cout << s1.size() << endl;	// out: 71 等价于 s1.length()
	cout << s1.empty() << endl;	// out: 0  (代表不是空字符串)
	// 5.查找和获取
	int i1 = s1.find('[');	// 查找s1中字符'['所在的位置 存在则返回其索引，若不存在则返回 s1.npos
	int i2 = s1.find(']');
	string s2 = s1.substr(i1 + 1, i2 - (i1 + 1));	// 获取s1中的子串，从下标 i1+1 开始，共获取 i2-(i1+1) 个字符 
	// s2 = haha | heihei | hehe
	int i3 = s1.find("@qq.com", 10);	// 从s1中的下标10之后开始查找子符串 "@qq.com"
	if (i3 == s1.npos) {
		cout << "不存在@qq.com" << endl;
	} else {
		cout << "存在@qq.com" << endl;
	} // out: 不存在@qq.com
}

⛓ vector

📋 简介：

Vector 译为向量，是一个封装了动态大小数组的顺序容器。直白地说，向量是一个能够存放任意指定类型 、任意大小 的数组 。

它包含一些特性：

• 顺序序列：容器 vector<type> v 中的元素是线性顺序存放的，支持随机访问 v[i]
• 动态数组：支持快速直接访问，也提供了在末尾快速插入 push_back() 和删除末尾元素 pop_back() 的操作

TIP

Vector 类似于数据结构中的顺序表 (opens new window)，但与之不同的是，Vector 已经封装好了，你只管使用它就行，不需要考虑空间不足的情况。

📝 头文件与创建：

#include <vector>  
...
vector<int> v;
vector<string> v2;
vector<int> v0(10, 5);	// 10个5，即 v0 = {5,5,5,5,5,5,5,5,5,5}
vector<int> v1(v0);		// 深拷贝

📗 函数与功能：

函数	功能
v.push_back(elem)	在数组的最后添加一个元素 elem
v.pop_back()	去掉数组的最后一个数据
v.front()	得到数组的第一个单元的引用
v.back()	得到数组的最后一个单元的引用
v.at(i)	得到编号位置 i 的数据，与 v[i] 等价
v.begin()	返回指向 v 第一个元素的迭代器
v.end()	返回指向 v 最后一个元素的下一个位置的迭代器
v.size()	容器 v 的大小
v.empty()	判断容器是否为空
v.clear()	清空容器
v.erase(i)	删除 v 中下标为 i 的元素
v.erase(v.begin(),v.end())	效果等价于 v.clear()
v.swap(v0)	与另一个 vector<> v0 交换数据

➰ 示例1：vector 综合使用

#include <vector>
#include <iostream>
#include <string>
using namespace std;
/* 示例1 - vector综合使用 */
void example() {
  // 1.创建
  vector<int> v1;       // 默认
  vector<int> v2(v1);  // 拷贝构造
  vector<int> v3(10, 3);	// 长度为10，每个元素为3 
  // 2.添加数据
  v1.push_back(10);
  v1.push_back(20);
  v1.push_back(15);
  v1.push_back(5);
  // 3.遍历
    // 方法1 
  for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
    cout << *it << "  ";
  }
    // 方法2
  for (int i = 0; i < v1.size(); i ++ ) cout << v1[i] << " ";
  // out: 10 20 15 5
  // 4.大小和交换
  cout << v1.size() << endl; 
  // out: 4
  v1.swap(v3);		// v1 = (3 3 3 3 3 3 3 3 3 3)
  if ( v1.empty() ) {
    cout << "v1为空" << endl;
  } else {
    cout << "v1不为空" << endl;
  } 
  // out: v1不为空
  // 5.清空和删除
  v1.clear();           // s = ()            // s.clear();效果相等于s.erase(s.begin(), s.end());
  v1.swap(v3);          // s = (10 20 15 5)
  v1.erase(v1.begin()); // s = (20 15 5)
  v1.pop_back();		// s = (20 15)
  // 6.查找和统计
  cout << v1.front();	// out: 20
  cout << v1.back();	// out: 15
  // 7.支持比较运算，按字典排序 
  vector<int> v4(4, 3), v5(3, 4);
  if (v4 < v5) puts("v4 < v5"); 
}

➰ 示例2：vector + sort() 排序

#include <iostream>
#include <vector>
#include <algorithm>  // sort()函数
using namespace std;
/* 示例2 - 常用类型排序 */
// 从大到小排序 
int fun1(int val1, int val2)
{
	return val1 > val2;
}
// 示例 
void example1()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(15);
	v.push_back(25);
	v.push_back(5);
	v.push_back(100);
	v.push_back(35);
	v.push_back(0);
	// 默认插入顺序 
	for (int i = 0; i < v.size(); i ++ ) cout << v[i] << " ";
	cout << endl;
	// out: 20 15 25 5 100 35 0
	// sort()默认从小到大排序
	sort(v.begin(), v.end());		 
	for (int i = 0; i < v.size(); i ++ ) cout << v[i] << " ";
	cout << endl;
	// out: 0 5 15 20 25 35 100
	// 通过回调函数fun1()改变成从大到小排序
	sort(v.begin(), v.end(), fun1);	 
	for (int i = 0; i < v.size(); i ++ ) cout << v[i] << " ";
	cout << endl;
	// out: 100 35 25 20 15 5 0
}
/* 示例2 - 自定义类型排序 */
// 类
class User {
public:
	string str1;
	string str2;
	int i1;
	int i2;
	string name;
	int id;
public:
	User(int id, string name)
	{
		this->id = id;
		this->name = name;
	}
	User(int id, string name, int i1, int i2)
	{
		this->id = id;
		this->name = name;
		this->i1 = i1;
		this->i2 = i2;
	}
	void print() {
		cout << this->id << " "
			 << this->name << " "
			 << this->i1 << " "
			 << this->i2 << endl;
	}
};
// 排序函数
int fun2(const User &u1, const User &u2)
{
	return u1.name > u2.name; 
} 
int fun3(const User &u1, const User &u2)
{
	if (u1.i1 == u2.i1) return u1.i2 > u2.i2;	// i2由大到小
	return u1.i1 < u2.i1;	// i1由小到大 
} 
// 示例 
void example2()
{
	vector<User> v;
	User u1(1, "adxs", 154, 210);
	User u2(2, "cxds", 154, 195);
	User u3(3, "asdx", 154, 212);
	User u4(4, "gdfd", 134, 223);
	User u5(5, "sws", 148, 190);
	User u6(6, "saws", 114, 342);
	v.push_back(u1);
	v.push_back(u2);
	v.push_back(u3);
	v.push_back(u4);
	v.push_back(u5);
	v.push_back(u6);
	
	// 默认插入顺序 
	for (int i = 0; i < v.size(); i ++ ) v[i].print();
	cout << endl;
	/* out:
	1 adxs 154 210
	2 cxds 154 195
	3 asdx 154 212
	4 gdfd 134 223
	5 sws 148 190
	6 saws 114 342
	*/
	// 按User.name排序，如果想按其他关键字排序，可以在fun2()里进行合适自身的修改 
	sort(v.begin(), v.end(), fun2);
	for (int i = 0; i < v.size(); i ++ ) v[i].print();
	cout << endl;
	/* out:
	5 sws 148 190
	6 saws 114 342
	4 gdfd 134 223
	2 cxds 154 195
	3 asdx 154 212
	1 adxs 154 210
	*/
	// 按User.i1优先排序，i1若相等则排序i2
	sort(v.begin(), v.end(), fun3);
	for (int i = 0; i < v.size(); i ++ ) v[i].print();
	cout << endl;
	/* out:
	6 saws 114 342
	4 gdfd 134 223
	5 sws 148 190
	3 asdx 154 212
	1 adxs 154 210
	2 cxds 154 195
	*/
}

⛓ pair

📋 简介： pair 是由两个类型组合成的一对值。类比一下，就像直角坐标系的坐标$(x, y)$，$x$ 表示横坐标值、$y$ 表示纵坐标值。那么相应的，创建 pair<type1, type2> p(type1_value, type2_value) ，其中 p.first 代表第一个类型的值 type1_value ， p.second 代表第二个类型的值 type2_value 。

📗 函数与功能：

属性	功能
p.first	获取pair对组的第一个元素
p.second	获取pair对组的第二个元素

➰ 示例1：pair 综合使用

#include <string>  
#include <iostream>
#include <utility>	// pair 需要包含的头文件。但其实如果包含了<iostream>文件，那么可以不用包含该文件
using namespace std;
/* 示例1 - pair综合使用 */
void example() {
	pair<int, int> p1(1, 2);
	pair<int, int> p2;
	p2 = make_pair(1, 2);
	cout << (p1 >= p2);	// out: 1
	// pair 是可以嵌套使用的，就像下面这样，p3.second 又是一个 pair 类型
	pair<int, pair<int, string> > p3(1, {2,"zhangsal"});
	pair<int, pair<int, string> > p4(1, {2,"zhangsan"});
	// 按字典序比较大小，
	// 如果 p3.first == p4.first 那么比较 second
	// 如果 p3.second.first == p4.second.first 那么比较 second.second
	// 最后 p3.second.second < p4.second.second 因为最后一个字符 'l' < 'n'
	cout << (p3 >= p4);	// out: 0
	
	cout << p4.first << " " << p4.second.first << " " << p4.second.second;	// out: 1 2 zhangsan
}

🎯 拓展：

1. 事实上，pair 是由结构体 struct 实现的

⛓ list

📋 简介：

前面我们了解了 vector 是逻辑和物理结构都连续的顺序容器，所以可以把 vecotr 当作数组/顺序表来操作，可以进行随机存取访问。

list 也是顺序容器，但不同的是， list 中的元素在逻辑上连续，但物理存储上并不一定连续，所以无法进行随机存取 [i] 操作，属于链表，按顺序访问元素。另外，list 支持双向操作，即可以在链表头部 l.begin() 和尾部 l.end() 进行删除 l.pop_xxx() / 插入 l.push_xxx(elem) 操作。

📝 头文件：

#include <list>  

📗 函数与功能：

函数	功能
l.push_back(elem)	在链表的最后添加一个元素 elem
l.pop_back()	去掉链表的最后一个数据
l.push_front(elem)	在链表的头部之前添加一个元素 elem
l.pop_front()	去掉链表的第一个数据
l.front()	得到链表的第一个单元的引用
l.back()	得到链表的最后一个单元的引用
l.begin()	返回指向 l 第一个元素的迭代器
l.end()	返回指向 l 最后一个元素的下一个位置的迭代器
l.insert(l.begin(), elem)	在链表的头部之前添加一个元素 elem
l.insert(l.begin(), n, elem)	在链表的头部之前添加 n 个元素 elem
l.insert(l.begin(),l0.begin(),l0.end())	在链表的头部之前添加 l0 的所有元素
l.size()	链表 l 的大小
l.empty()	判断链表是否为空
l.clear()	清空链表
l.erase(l.begin())	删除 l 中第一个元素
l.erase(l.begin(),l.end())	效果等价于 l.clear()
l.swap(l0)	与另一个 list<> l0 交换数据
l.merge(l0)	将 l0 合并到 l 中，合并后 l0 为空

➰ 示例1：list 综合使用

#include <iostream>
#include <list>
using namespace std;
/* 示例1 - list综合使用 */
void example()
{
	// 1.创建 
	list<int> l;
	list<int> l0(5,1);	// l0 = {1,1,1,1,1}
	// 2.添加数据 
	l.insert(l.begin(), 10, 3);
	l.push_back(8);
	l.push_front(15);
	// 3.遍历 
	for (list<int>::iterator it = l.begin(); it != l.end(); it ++ ) 
		cout << *it << " ";
	cout << endl;
	// out: 15 3 3 3 3 3 3 3 3 3 3 8
	// 4.大小和交换
	cout << l.size() << endl;	// out: 12
	l.swap(l0);	// l = {1,1,1,1,1}
	// 5.清空和删除
	l.clear();	// l = {}
	l.erase(l.begin(), l.end());	// 相当于 l.clear() 
	if ( l.empty() ) {
		cout << "l为空" << endl;
	} else {
		cout << "l不为空" << endl;
	} // out: l为空
	l.swap(l0);		// l = {15 3 3 3 3 3 3 3 3 3 3 8}
	l.pop_back();	// l = {15 3 3 3 3 3 3 3 3 3 3}
	l.pop_front();	// l = {3 3 3 3 3 3 3 3 3 3}
	// 6.合并
	list<int> l2;
	l2.push_back(11);
	l2.push_back(18);
	l2.push_back(2);	// l2 = {11,18,2}
	l.merge(l2);		// l = {3 3 3 3 3 3 3 3 3 3 11 18 2}，l2 = {} 
	// 7.查看
	cout << l.front() << endl;	// out: 3
	cout << l.back() << endl;	// out: 2
}

⛓ queue

📋 简介：

queue 是数据结构的队列在 C++ 中的实现。与 vector 和 list 相比，queue 只能在有两个操作： q.push() 和 q.pop()，push 的一端称为队尾，pop 的一端称为队头。

queue 就像超市里结账的队伍一样，队头第一个人结完账就离开队伍，新加入结账队伍的人排到队尾，井然有序。

📝 头文件：

#include <queue>  

📗 函数与功能：

函数	功能
q.push(elem)	入队，在队尾添加一个元素 elem
q.pop()	出队，删除队头元素
q.front()	返回队头元素
q.back()	返回队尾元素
q.size()	队列 queue<type> q 的大小
q.empty()	判断队列是否为空

➰ 示例1：queue 综合使用

#include <iostream>
#include <queue>
#include <string>
using namespace std;
/* 示例1 - queue综合使用 */
void example()
{
	// 1.创建 
	queue<string> q;
	// 2.添加数据 
	q.push("小明");
	q.push("张三");
	q.push("小红");
	// 3.遍历
	// queue 只能通过移除元素的方式顺便遍历元素 
	while ( !q.empty() )
	{
		cout << q.front() << " ";
		q.pop();
	} // out: 小明 张三 小红   // q = {}
	// 4.大小
	q.push("小东");
	q.push("李明");
	cout << q.size() << endl;	// out: 2
	cout << q.front() << endl;	// out: 小东
	cout << q.back() << endl;	// out: 李明 
}

⛓ deque

📋 简介： deque 在 queue 的基础上进一步放宽了限制，允许在队头和队尾进行删除或插入操作，称为双端队列，操作与 list 非常接近。

📝 头文件：

#include <deque>  

📗 函数与功能：

函数	功能
d.push_front(elem)	入队，在队头添加一个元素 elem
d.push_back(elem)	入队，在队尾添加一个元素 elem
d.pop_front()	出队，删除队头元素
d.pop_back()	出队，删除队尾元素
d.front()	返回队头元素
d.back()	返回队尾元素
d.size()	队列 deque<type> d 的大小
d.empty()	判断队列是否为空

➰ 示例1：deque 综合使用

#include <iostream>
#include <deque>
#include <string>
using namespace std;
/* 示例1 - deque综合使用 */
void example()
{
	// 1.创建 
	deque<string> d;
	// 2.添加数据 
	d.push_front("小明");
	d.push_back("张三");
	d.push_front("小红");
	d.push_front("小东");
	d.push_back("李明");
	// 3.遍历
	for (deque<string>::iterator it = d.begin(); it != d.end(); it ++ )
		cout << *it << " ";
	// out: 小东 小红 小明 张三 李明
	// 4.大小
	cout << d.size() << endl;	// out: 5
	cout << d.front() << endl;	// out: 小东
	cout << d.back() << endl;	// out: 李明 
	d.clear();	// 清空元素 
}

⛓ stack

📋 简介：

stack 与 queue 都是操作受限的线性表，不同的是，stack 只允许在其中一端进行删除和插入操作，可以操作的一端称为栈顶，不能操作的一端称为栈底，这种结构称为栈。

stack 栈就像死胡同一样，先开进来的车 $car_1$ 遇到巷底无法前进，而后来的车 $car_2$ 从巷口开进来，导致 $car_1$ 无法动弹，此时只能让 $car_2$ 先出去。这就是栈的经典特性——LIFO(Last In First Out, 后进先出)，相应的，队列的经典特性——FIFO(First In First Out, 先进先出)。

📝 头文件：

#include <stack>  

📗 函数与功能：

函数	功能
s.push(elem)	入栈，在栈顶添加一个元素 elem
s.pop()	出栈，删除栈顶元素
s.top()	返回栈顶元素
s.size()	队列 stack<type> s 的大小
s.empty()	判断队列是否为空

➰ 示例1：stack 综合使用

#include <iostream>
#include <stack>
#include <string>
using namespace std;
/* 示例1 - stack综合使用 */
void example()
{
	// 1.创建 
	stack<string> s;
	// 2.添加数据 
	s.push("小明");
	s.push("张三");
	s.push("小红");
	// 3.遍历
	// stack 只能通过移除元素的方式顺便遍历元素，LIFO—后进先出 
	while ( !s.empty() )
	{
		cout << s.top() << " ";	// 拿到栈顶元素 
		s.pop();
	} // out: 小红 张三 小明   // q = {}
	// 4.大小
	s.push("小东");
	s.push("李明");
	cout << s.size() << endl;	// out: 2
}

⛓ set

📋 简介： set 是一个集合容器，所有元素都会在插入时自动被排序，动态维护有序序列

1. 本质：set/multiset属于关联式容器，底层结构是用**平衡二叉树(红黑树)**实现。
2. set和multiset区别：
   • set 不可以插入重复数据，而multiset 可以
   • set 插入数据的同时会返回插入结果，表示插入是否成功
   • multiset 不会检测数据，因此可以插入重复数据

📝 头文件与创建：

#include <set>  
// 创建
set<int> s;  // int类型元素集合
set<char> s1; // char类型元素集合
set<User> s2; // 自定义类型class User{...}元素集合

📗 函数与功能：

函数	功能
s.insert(elem)	插入一个元素 elem
s.begin()	返回指向 set 集合第一个元素的迭代器
s.end()	返回指向 set 集合最后一个元素的下一个位置的迭代器
s.size()	集合 set 的大小
s.empty()	是否为空集合
s.clear()	清空集合
s.erase(elem)	删除集合中的 elem 元素
s.erase(s.begin(),s.end())	效果等价于 s.clear()
s.swap(s0)	和集合 set<same_type> s 相同类型的集合 set<same_type> s0 交换数据
s.count(elem)	统计元素 elem 在集合中的个数，因为 set 是不包含重复数据的，因此这里只返回 0 或者 1
s.find(elem)	查找元素 elem ，若查找成功，返回成功位置的迭代器；若查找失败，返回 s.end()

➰ 示例1：set 综合使用

#include <set>      // 包含头文件
#include <iostream>
using namespace std;
// 示例1
void example() {
  // 1.创建
  set<int> s;       // 默认
  set<int> s2(s1);  // 拷贝构造
  // 2.插入数据(set会自动升序排序，并只包含一次重复的数据)
  s.insert(10);
  s.insert(20);
  s.insert(15);
  pair<set<int>::iterator, bool> res = s.insert(15);
  if (res.second) cout << "插入成功" << endl;
  else cout << "插入失败" << endl;  
  // out: 插入失败
  s.insert(5);
  // 3.遍历
  for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it << "  ";
  } 
  // out: 5  10  15  20
  // 4.大小和交换
  cout << s.size() << endl; 
  // out: 4
  s.swap(s2);
  if ( s.empty() ) {
    cout << "s为空" << endl;
  } else {
    cout << "s不为空" << endl;
  } 
  // out: s为空
  // 5.清空和删除
  s.clear();          // s= ()            // s.clear();效果相等于s.erase(s.begin(), s.end());
  s.swap(s2);         // s = (5 10 15 20)
  s.erase(s.begin()); // s = (10 15 20)
  s.erase(15);        // s = (10 20)
  // 6. 查找和统计
  s.count(10);        // 对于set容器而言，s.count() = 0 or 1
  set<int>::iterator pos = s.find(10);  // 如果找到元素10，返回其所在位置的迭代器；如果没有找到，则返回s.end()
}

➰ 示例2：set 排序规则修改

/* 示例2 - 内置类型排序规则修改 */
// 设置set容器对内置类型int的降序排序
class compareSet {
public:
	bool operator() (int v1, int v2) {
		return v1 > v2;
	}
};
// 演示主函数
void example1() {
  // 1.创建，创建时就指定排序规则 compareSet
  set<int, compareSet> s;
  // 2.插入数据
  s.insert(10);
  s.insert(20);
  s.insert(15);
  s.insert(40);
  s.insert(25);
  s.insert(50);
  s.insert(18);
  // 3.输出
  for (set<int, compareSet>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it << "  ";
  } 
  // out: 50  40  25  20  18  15  10
}

/* 示例2 - 自定义类型排序规则修改 */
// 用户类 
class User
{
public:
	string name; int age; float height; // 姓名，年龄，身高
	User(string name, int age, float height) {
		this->name = name;
		this->age = age;
		this->height = height;
	};
};
// 设置set容器对自定义类型User的排序规则(按照年龄从大到小排序)
class compareUser {
public:
	bool operator() (const User &u1, const User &u2) {
		return u1.age > u2.age;
	}
};
// 演示主函数
void example2() {
	// 存放用户的容器，创建时就指定排序规则 compareUser
	set<User, compareUser> s;
	// 添加用户
	User u1("刘备", 35 , 175);
	User u2("曹操", 45 , 180);
	User u3("孙权", 40 , 170);
	User u4("赵云", 25 , 190);
	User u5("张飞", 35 , 160);
	User u6("关羽", 35 , 200);
	s.insert(u1);
	s.insert(u2);
	s.insert(u3);
	s.insert(u4);
	s.insert(u5);
	s.insert(u6);
	// 输出 
	for (set<User, compareUser>::iterator it = s.begin(); it != s.end(); it++) {
		cout << "姓名：" << it->name << "  年龄：" << it->age << "  身高：" << it->height << endl;
	}
  /* out:
  姓名：曹操  年龄：45  身高：180
  姓名：孙权  年龄：40  身高：170
  姓名：刘备  年龄：35  身高：175
  姓名：赵云  年龄：25  身高：190
  */
}

⛓ map

📋 简介：

• map 中所有元素都是 pair
• pair 中第一个元素为 key（键值），起到索引作用，第二个元素为 value（实值）
• 所有元素都会根据元素的键值自动排序

1. 本质：map / multimap 属于关联式容器，底层结构是用二叉树实现。
2. 优点：可以根据 key 值快速找到 value 值
3. map / multimap 区别：
   • map 不允许容器中有重复 key 值元素
   • multimap 允许容器中有重复 key 值元素

📝 头文件与创建：

#include <map>
// 创建
map<int, int> m;

📗 函数与功能： 函数 功能

➰ 示例1：map 综合演示

#include <map>    // 包含头文件
#include <iostream>
// 示例1 
void example() {
	// 1.创建
	map<int, int> m;
	map<int, int> m2(m);	// 拷贝构造 
	map<int, int> m3;	// 赋值
	m3 = m2; 
	// 2.插入元素
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(4, 40));
	m.insert(pair<int, int>(4, 42));
	m.insert(pair<int, int>(3, 30));
	m.insert(pair<int, int>(6, 60));
	// 3.遍历 
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key: " << (*it).first << "  value: " << (*it).second << endl;
	}
	/* out:
	key: 1  value: 10
	key: 2  value: 20
	key: 3  value: 30
	key: 4  value: 40
	key: 5  value: 50
	key: 6  value: 60
	*/
	// 4.大小和交换
	if (m.empty()) { cout << "m为空" << endl; }
	else { cout << "m不为空，大小为：" << m.size() << endl; }
	// out: m不为空，大小为：6
	m.swap(m2);					// 交换后，  m = ()
	m.insert(make_pair(4,45));	// m = (<4,45>)
	// 5. 插入和删除 
	m.clear();			// m = ()	等价于 m.erase(m.begin(), m.end());
	m.swap(m2);			// m = (<1,10>, <2,20>, <3,30>, <4,40>, <5,50>, <6,60>)
	m.erase(2);			// m = (<1,10>, <3,30>, <4,40>, <5,50>, <6,60>)	删除key=2的元素 
	m.erase(m.begin());	// m = (<3,30>, <4,40>, <5,50>, <6,60>)
	// 6.查找和统计
	m.count(2);			// 对于map容器而言，返回 0 or 1
	map<int, int>::iterator res = m.find(3);	// 找到则返回元素所在位置迭代器，未找到则返回m.end() 
	if (res != m.end()) cout << "找到元素：key = " << res->first << "  value = " << res->second << endl;
	else cout << "没找到元素" << endl;
	// out: 找到元素：key = 3  value = 30
}

➰ 示例2：map 排序规则修改

/* 示例2 - 内置类型排序规则修改 */ 
// 设置map容器对内置类型int的降序排序
class compareMap {
public:
	bool operator() (int v1, int v2) {
		return v1 > v2;
	}
};
// 演示主函数 
void example1() {
	// 1.创建
	map<int, int, compareMap> m;
	// 2.插入元素
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(4, 40));
	m.insert(pair<int, int>(4, 42));
	m.insert(pair<int, int>(3, 30));
	m.insert(pair<int, int>(6, 60));
	// 3.遍历 
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key: " << (*it).first << "  value: " << (*it).second << endl;
	}
	/* out:
	key: 6  value: 60
	key: 5  value: 50
	key: 4  value: 40
	key: 3  value: 30
	key: 2  value: 20
	key: 1  value: 10
	*/
}

/* 示例2 - 自定义类型排序规则修改 */
// 用户类 
class User
{
public:
	string name; int age; float height; // 姓名，年龄，身高 
	User(string name, int age, float height) {
		this->name = name;
		this->age = age;
		this->height = height;
	};
};
// 设置容器对自定义类型User的排序规则(按照年龄从大到小排序)，因此Key唯一值为年龄User.age  
class compareUser {
public:
	bool operator() (const User &u1, const User &u2) {
		return u1.age > u2.age;
	}
};
// 演示主函数
void example2() {
	// 存放用户的容器，创建时就指定排序规则 compareUser，指定Key唯一值为年龄User.age 
	map<User, string, compareUser> m;
	// 添加用户
	User u1("刘备", 35 , 175);
	User u2("曹操", 45 , 180);
	User u3("孙权", 40 , 170);
	User u4("赵云", 25 , 190);
	User u5("张飞", 35 , 160);
	User u6("关羽", 35 , 200);
	m.insert(make_pair(u1, "良君"));
	m.insert(make_pair(u2, "霸气"));
	m.insert(make_pair(u3, "十万"));
	m.insert(make_pair(u4, "银枪"));
	m.insert(make_pair(u5, "断阳桥"));	// 年龄和u1冲突，插入失败 
	m.insert(make_pair(u6, "斩华雄"));	// 年龄和u1冲突，插入失败 
	// 输出 
	for (map<User, string, compareUser>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "Value值：" << it->second 
		     << "  Key值：姓名-" << it->first.name 
			 << "  年龄-" << it->first.age 
			 << "  身高-" << it->first.height << endl;
	}
	/* out:
	Value值：霸气  Key值：姓名-曹操  年龄-45  身高-180
	Value值：十万  Key值：姓名-孙权  年龄-40  身高-170
	Value值：良君  Key值：姓名-刘备  年龄-35  身高-175
	Value值：银枪  Key值：姓名-赵云  年龄-25  身高-190
	*/
}