前言
map、set、multimap、multiset是C++ STL中的四种关联容器，它们内部都使用了红黑树这种高效的平衡检索二叉树来存储数据。它们的区别和用法如下：
map是一种键值对容器，它可以根据键来快速查找、插入和删除值，它的键是唯一的，不能重复。
multimap也是一种键值对容器，但它允许键重复，也就是说一个键可以对应多个值。
set是一种只存储值的容器，它可以快速查找、插入和删除值，它的值是唯一的，不能重复。在底层实际存放的是由<value, value>构成的键值对。(排序+去重）
multiset也是一种只存储值的容器，但它允许值重复，也就是说一个容器中可以有多个相同的值。
这四种容器都可以保证元素按照一定的顺序排列，通常是按照键或者值的升序排列。如果想要改变排序规则，可以自定义比较函数或者比较类。
这四种容器的时间复杂度如下：
- 插入：O(log n)
- 查找：O(log n)
- 删除：O(log n)
如果想要更高效的时间复杂度，可以使用哈希表实现的unordered_map, unordered_set, unordered_multimap, unordered_multiset(后期介绍）。它们的时间复杂度如下：
插入：O(1)期望，O(n)最坏
查找：O(1)期望，O(n)最坏
删除：O(1)期望，O(n)最坏
但是哈希表实现的容器不能保证元素有序，并且需要提供合适的哈希函数和相等判断函数。
那什么是键值对呢？
键值对实际也是一个类，类里面对key和value数据进行了封装，key表示关键码，value表示与之对应的值，下面是SGI对于pair键值对结构体的定义：
struct pair{}有两个构造函数，一个是无参的利用T1和T2类型的默认构造函数初始化出来的键值对，一个是T1和T2作为参数的构造函数。
另外pair还重载了两个运算符，用于键值对的等于和小于比较，小于比较时，优先比较first，如果first恰好满足x<y，则返回true。如果first之间相等，则比较失败返回false。如果first是x>y，那就继续比较second。
为了方便构造键值对，pair又另写了成员函数make_pair()，这个函数其实也是调用了构造函数，但在构造键值对的时候，省下我们自己去传T1和T2的类型了。
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()), second(T2()) {} pair(const T1& a, const T2& b) : first(a), second(b) {} template <class T1, class T2> inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) { return x.first == y.first && x.second == y.second; } template <class T1, class T2> inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) { return x.first < y.first || (!(y.first < x.first) && x.second < y.second); } template <class T1, class T2> inline pair<T1, T2> make_pair(const T1& x, const T2& y) { return pair<T1, T2>(x, y); }
set、multiset的使用
1. set
set是一种只存储值的容器，它可以快速查找、插入和删除值，它的值是唯一的，不能重复。
set内部使用红黑树这种高效的平衡检索二叉树来存储数据，因此它可以保证元素按照一定的顺序排列，通常是按照值的升序排列。
set的时间复杂度为O(log n)，其中n是set中元素的个数。
所以set的特点是：不允许元素被修改，不允许元素有重复，那么它的作用就是排序+去重
set的使用方法如下：
要使用set，需要添加set头文件，即#include<set>。除此之外，还需要在头文件下面加上一句：“using namespace std;”。
set的定义：可以使用set<类型> 变量名;来定义一个空的set对象，也可以使用set<类型> 变量名(初始值);来定义一个带有初始值的set对象。例如：
set<int> s1; // 定义一个空的set对象，存储int类型的元素
set<string> s2({"hello", "world"}); // 定义一个带有初始值的set对象，存储string类型的元素
set的插入：可以使用insert()方法来向set中插入一个元素，该方法返回一个pair对象，其中第一个元素是一个指向插入位置的迭代器，第二个元素是一个布尔值，表示插入是否成功。如果插入的元素已经存在于set中，则插入失败。例如：
s1.insert(1); // 向s1中插入1
s1.insert(2); // 向s1中插入2
auto p = s1.insert(2); // 再次向s1中插入2
cout << *p.first << " " << p.second << endl; // 输出 2 0，表示插入失败
set的删除：可以使用erase()方法来从set中删除一个元素或者一个范围内的元素，该方法返回一个整数，表示删除了多少个元素。如果删除的元素不存在于set中，则返回0。例如：
s2.erase("hello"); // 从s2中删除"hello"
s2.erase("hi"); // 从s2中删除"hi"
cout << s2.erase("world") << endl; // 输出 1，表示删除成功
cout << s2.erase("hi") << endl; // 输出 0，表示删除失败
set的查找：可以使用find()方法来查找set中是否存在某个元素，该方法返回一个指向找到元素的迭代器，如果没有找到，则返回end()。也可以使用count()方法来统计set中某个元素出现的次数，该方法返回一个整数，表示出现的次数。由于set中不允许重复元素，所以该方法只能返回0或者1。例如：
auto it = s1.find(1); // 查找s1中是否有1
if (it != s1.end()) cout << *it << endl; // 如果找到了，则输出1
cout << s1.count(2) << endl; // 输出 1，表示s1中有2
cout << s1.count(3) << endl; // 输出 0，表示s1中没有3
set的遍历：可以使用迭代器来遍历set中的所有元素，也可以使用范围for循环来遍历。由于set是有序的，所以遍历时会按照从小到大或者从大到小（取决于比较函数）的顺序输出元素。例如：
for (auto it = s1.begin(); it != s1.end(); ++it) cout << *it << " "; // 使用迭代器遍历s1，并输出每个元素
for (auto x : s2) cout << x << " "; // 使用范围for循环遍历s2，并输出每个元素
代码示例：
#include <iostream> #include <set> using namespace std; int main() { set<int> s1; // 定义一个空的set对象，存储int类型的元素 set<string> s2({"hello", "world"}); // 定义一个带有初始值的set对象，存储string类型的元素 s1.insert(1); // 向s1中插入1 s1.insert(2); // 向s1中插入2 auto p = s1.insert(2); // 再次向s1中插入2 cout << *p.first << " " << p.second << endl; // 输出 2 0，表示插入失败 s2.erase("hello"); // 从s2中删除"hello" s2.erase("hi"); // 从s2中删除"hi" cout << s2.erase("world") << endl; // 输出 1，表示删除成功 cout << s2.erase("hi") << endl; // 输出 0，表示删除失败 auto it = s1.find(1); // 查找s1中是否有1 if (it != s1.end()) cout << *it << endl; // 如果找到了，则输出1 cout << s1.count(2) << endl; // 输出 1，表示s1中有2 cout << s1.count(3) << endl; // 输出 0，表示s1中没有3 for (auto it = s1.begin(); it != s1.end(); ++it) cout << *it << " "; // 使用迭代器遍历s1，并输出每个元素 cout << endl; for (auto x : s2) cout << x << " "; // 使用范围for循环遍历s2，并输出每个元素 cout << endl; return 0; }
2. multiset
multiset是一种只存储值的容器，它可以快速查找、插入和删除值，它允许值重复，也就是说一个容器中可以有多个相同的值。
multiset内部使用红黑树这种高效的平衡检索二叉树来存储数据，因此它可以保证元素按照一定的顺序排列，通常是按照值的升序排列。
multiset的时间复杂度为O(log n)，其中n是multiset中元素的个数。
multiset相比于set，它可以存在重复的元素
multiset的使用方法和set基本相同：
要使用multiset，需要添加set头文件，即#include<set>。除此之外，还需要在头文件下面加上一句：“using namespace std;”。
multiset的定义：可以使用multiset<类型> 变量名;来定义一个空的multiset对象，也可以使用multiset<类型> 变量名(初始值);来定义一个带有初始值的multiset对象。也可以指定一个比较函数对象来自定义元素的排序规则。例如：
multiset<int> ms1; // 定义一个空的multiset对象，存储int类型的元素，按照默认的升序排列
multiset<string> ms2({"hello", "world"}); // 定义一个带有初始值的multiset对象，存储string类型的元素，按照默认的升序排列
multiset<int, greater<int>> ms3; // 定义一个空的multiset对象，存储int类型的元素，按照降序排列
multiset的插入：可以使用insert()方法或者emplace()方法（C++11）来向multiset中插入一个元素，这两个方法都返回一个指向插入位置的迭代器。如果插入的元素已经存在于multiset中，则插入到已有元素之后。也可以使用emplace_hint()方法（C++11）来向multiset中插入一个元素，并提供一个提示位置作为参数，该方法返回一个指向插入位置的迭代器。如果提示位置是正确的或者接近正确的，则该方法比insert()或者emplace()更高效。例如：
ms1.insert(1); // 向ms1中插入1
ms1.insert(2); // 向ms1中插入2
ms1.insert(2); // 再次向ms1中插入2
auto it = ms1.insert(3); // 向ms1中插入3，并获取插入位置
cout << *it << endl; // 输出 3
ms2.emplace("hi"); // 向ms2中原位构造"hi"
ms2.emplace_hint(ms2.begin(), "bye"); // 向ms2中原位构造"bye"，并提供一个提示位置
multiset的删除：可以使用erase()方法来从multiset中删除一个元素或者一个范围内的元素，该方法返回一个整数，表示删除了多少个元素。如果删除的元素不存在于multiset中，则返回0。也可以使用clear()方法来清空multiset中的所有元素。例如：
ms2.erase("hello"); // 从ms2中删除"hello"
ms2.erase("hi"); // 从ms2中删除"hi"
cout << ms2.erase("world") << endl; // 输出 1，表示删除成功
cout << ms2.erase("hi") << endl; // 输出 0，表示删除失败
ms2.clear(); // 清空ms2中的所有元素
multiset的查找：可以使用find()方法来查找multiset中是否存在某个元素，该方法返回一个指向找到元素的迭代器，如果没有找到，则返回end()。也可以使用count()方法来统计multiset中某个元素出现的次数，该方法返回一个整数，表示出现的次数。还可以使用lower_bound()方法和upper_bound()方法来获取某个元素在multiset中的边界位置，或者使用equal_range()方法来获取某个元素在multiset中的范围。例如：
auto it = ms1.find(1); // 查找ms1中是否有1
if (it != ms1.end()) cout << *it << endl; // 如果找到了，则输出1
cout << ms1.count(2) << endl; // 输出 2，表示ms1中有两个2
cout << ms1.count(3) << endl; // 输出 1，表示ms1中有一个3
auto lb = ms1.lower_bound(2); // 获取2在ms1中的下界位置
auto ub = ms1.upper_bound(2); // 获取2在ms1中的上界位置
cout << *lb << " " << *ub << endl; // 输出 2 3
auto p = ms1.equal_range(2); // 获取2在ms1中的范围
cout << *p.first << " " << *p.second << endl; // 输出 2 3
multiset的遍历：可以使用迭代器来遍历multiset中的所有元素，也可以使用范围for循环来遍历。由于multiset是有序的，所以遍历时会按照从小到大或者从大到小（取决于比较函数）的顺序输出元素。例如：
for (auto it = ms3.begin(); it != ms3.end(); ++it) cout << *it << " "; // 使用迭代器遍历ms3，并输出每个元素
for (auto x : ms3) cout << x << " "; // 使用范围for循环遍历ms3，并输出每个元素
代码示例：
#include <iostream> #include <set> using namespace std; int main() { multiset<int> ms1; // 定义一个空的multiset对象，存储int类型的元素，按照默认的升序排列 multiset<string> ms2({"hello", "world"}); // 定义一个带有初始值的multiset对象，存储string类型的元素，按照默认的升序排列 multiset<int, greater<int>> ms3; // 定义一个空的multiset对象，存储int类型的元素，按照降序排列 ms1.insert(1); // 向ms1中插入1 ms1.insert(2); // 向ms1中插入2 ms1.insert(2); // 再次向ms1中插入2 auto it = ms1.insert(3); // 向ms1中插入3，并获取插入位置 cout << *it << endl; // 输出 3 ms2.emplace("hi"); // 向ms2中原位构造"hi" ms2.emplace_hint(ms2.begin(), "bye"); // 向ms2中原位构造"bye"，并提供一个提示位置 ms2.erase("hello"); // 从ms2中删除"hello" ms2.erase("hi"); // 从ms2中删除"hi" cout << ms2.erase("world") << endl; // 输出 1，表示删除成功 cout << ms2.erase("hi") << endl; // 输出 0，表示删除失败 ms2.clear(); // 清空ms2中所有元素 auto it = ms1.find(1); // 查找ms1中是否有1 if (it != ms1.end()) cout << *it << endl; // 如果找到了，则输出1 cout << ms1.count(2) << endl; // 输出 2，表示s有两个个 cout << s.count(3) << endl; // 输出 0 表示s没有 auto lb = s.lower_bound(4); auto ub = s.upper_bound(6); cout<<*lb<<" "<<*ub<<endl; auto p=s.equal_range(5); cout<<*p.first<<" "<<*p.second<<endl;
3. 什么时候应该使用multiset而不是set
先看看二者有什么区别:
- multiset允许元素重复，而set不允许元素重复
- multiset的插入操作总是成功，而set的插入操作可能失败，如果插入的元素已经存在于set中。
- multiset的count()方法可能返回大于1的值，而set的count()方法只能返回0或者1。
- set的作用：排序+去重，所以
- 当你需要存储一些可以重复的元素，并且需要按照一定的顺序来访问它们时，你可以使用multiset。例如，你可以使用multiset来存储一些词汇，并且按照字典序来遍历它们，同时也可以统计每个词汇出现的次数。
- 当你需要对一些元素进行合并或者分割操作时，你可以使用multiset。例如，你可以使用multiset来实现一个优先队列，每次从multiset中取出最小或者最大的元素，并且可以将两个或者多个元素合并成一个新的元素再插入到multiset中。
- 当你需要使用一些set不提供的功能时，你可以使用multiset。例如，你可以使用multiset的extract()方法和merge()方法来将一个multiset中的结点转移到另一个multiset中，而不需要重新分配内存或者复制元素。
map、multimap的使用
1.map
map存储的是key和value组成的键值对元素结构体，在比较时按照key来进行比较，下面源码我们可以看到key依旧是不允许被修改的，但其对应的value是可以被修改的。
map中比较时比较的是key类型，但我们可以通过key找到value，这里多说一句，无论是map还是set，他们的迭代器走的都是中序的顺序。
map的使用
先说说两个注意点：
map的迭代器访问这里有讲究，由于其迭代器指向的是由key和value组成的键值对，那* it该获得哪个key和value的哪个值呢？set的迭代器指向的就只有key，所以* it直接返回key值即可。
对于map来说，*it拿到的是pair的对象，所以我们还需要再加一个.操作符才能访问pair对象里面的first和second值，但这样写起来有点麻烦，所以map的迭代器也重载了→操作符，→重载的函数会返回迭代器指向对象的地址，所以还应该再加个→访问first或second才对，但是编译器在这里做了优化，省略了一个箭头。
在map这里，如果我们用语法糖遍历map时，最好采用const引用，因为map中存的是键值对pair，不用引用就会发生赋值，会调用pair的赋值重载函数，代价比较大，为了提升效率建议采用const引用。（语法糖遍历拿到的值其实就是*it，在map这里就是pair对象，键值对）
另外一种非常骚的操作就是利用map的[ ]来统计次数，在了解了insert的返回值之后，再来理解map的[ ]调用成本就会低很多了，实际上[ ]带来的作用包括插入，查找，修改的功能，直接一个[ ]运算符重载包揽map的三个重要功能。
对于map和set在插入后都会返回一个键值对:
键值对的first是迭代器，其指向的是新插入键值对，若新插入键值对的key已经存在，则返回已经存在的key对应的键值对的迭代器，这是first的变化规则。
键值对的second是bool值，如果插入的key已经存在，则bool为false，否则bool为true
map的使用方法如下：
要使用map，需要添加map头文件，即#include<map>。除此之外，还需要在头文件下面加上一句：“using namespace std;”。
map的定义：可以使用map<键类型, 值类型> 变量名;来定义一个空的map对象，也可以使用map<键类型, 值类型> 变量名(初始值);来定义一个带有初始值的map对象。也可以指定一个比较函数对象来自定义键的排序规则。例如：
map<int, string> m1; // 定义一个空的map对象，存储int类型的键和string类型的值，按照默认的升序排列
map<int, string> m2({{1, "one"}, {2, "two"}}); // 定义一个带有初始值的map对象，存储int类型的键和string类型的值，按照默认的升序排列
map<int, string, greater<int>> m3; // 定义一个空的map对象，存储int类型的键和string类型的值，按照降序排列
map的插入：可以使用insert()方法或者emplace()方法（C++11）来向map中插入一个键值对，这两个方法都返回一个pair对象，其中first是一个指向插入位置的迭代器，second是一个布尔值，表示插入是否成功。如果插入的键已经存在于map中，则插入失败。也可以使用emplace_hint()方法（C++11）来向map中插入一个键值对，并提供一个提示位置作为参数，该方法返回一个指向插入位置的迭代器。如果提示位置是正确的或者接近正确的，则该方法比insert()或者emplace()更高效。还可以使用下标运算符[]或者at()方法来向map中插入或修改一个键值对，但这两种方式有所不同：下标运算符如果键不存在，则会创建一个新的键值对并返回默认值；而at()方法如果键不存在，则会抛出异常。例如：
m1.insert(pair<int, string>(1, "one")); // 向m1中插入{1, "one"}
m1.insert(make_pair(2, "two")); // 向m1中插入{2, "two"}
auto p = m1.insert({3, "three"}); // 向m1中插入{3, "three"}，并获取返回值
cout << p.first->first << " " << p.first->second << endl; // 输出 3 three
cout << p.second << endl; // 输出 true
p = m1.insert({3, "san"}); // 尝试向m1中插入{3, "san"}
cout << p.second << endl; // 输出 false
m2.emplace(3, "three"); // 向m2中原位构造{3, "three"}
m2.emplace_hint(m2.begin(), 4, "four"); // 向m2中原位构造{4, "four"}，并提供一个提示位置
m3[5] = "five"; // 向m3中插入或修改{5, "five"}
m3[6] = "six"; // 向m3中插入或修改{6, "six"}
cout << m3[7] << endl; // 输出 空字符串，并向m3中插入{7, ""}
cout << m3.at(8) << endl; // 抛出异常，并不会向m3中插入{8, ""}
map的删除：可以使用erase()方法来从map中删除一个键值对或者一个范围内的键值对，该方法返回一个整数，表示删除了多少个键值对。如果删除的键不存在于map中，则返回0。也可以使用clear()方法来清空map中的所有键值对。例如：
m1.erase(1); // 从m1中删除键为1的键值对
cout << m1.erase(4) << endl; // 输出 0，表示删除失败
auto it = m1.begin(); // 获取m1的起始迭代器
it++; // it指向第二个元素
m1.erase(it); // 从m1中删除it所指向的元素
it = m1.begin(); // 重新获取m1的起始迭代器
auto it2 = m1.end(); // 获取m1的结束迭代器
it2--; // it2指向最后一个元素
m1.erase(it, it2); // 从m1中删除[it, it2)范围内的元素
m2.clear(); // 清空m2中所有元素
map的查找：可以使用find()方法来查找map中是否存在某个键，并返回一个指向该键所在位置的迭代器，如果没有找到，则返回end()。也可以使用count()方法来统计map中某个键出现的次数，该方法返回一个整数，表示出现的次数（只能是0或者1）。还可以使用lower_bound()方法和upper_bound()方法来获取某个键在map中的边界位置，或者使用equal_range()方法来获取某个键在map中的范围。例如：
auto it = m2.find(3); // 查找m2中是否有键为3的元素
if (it != m2.end()) cout << it->first << " " << it->second << endl; // 如果找到了，则输出 3 three
cout << m2.count(4) << endl; // 输出 1，表示m2中有键为4的元素
cout << m2.count(5) << endl; // 输出 0，表示m2中没有键为5的元素
auto lb = m3.lower_bound(5); // 获取5在m3中的下界位置
auto ub = m3.upper_bound(5); // 获取5在m3中的上界位置
cout << lb->first << " " << lb->second << endl; // 输出 5 five
cout << ub->first << " " << ub->second << endl; // 输出 6 six
auto p = m3.equal_range(6); // 获取6在m3中的范围
cout << p.first->first << " " << p.first->second << endl; // 输出 6 six
cout << p.second->first << " " << p.second->second << endl; // 输出 7 空字符串
代码示例：
#include <iostream> #include <map> using namespace std; int main() { map<int, string> m1; // 定义一个空的map对象，存储int类型的键和string类型的值，按照默认的升序排列 map<int, string> m2({{1, "one"}, {2, "two"}}); // 定义一个带有初始值的map对象，存储int类型的键和string类型的值，按照默认的升序排列 map<int, string, greater<int>> m3; // 定义一个空的map对象，存储int类型的键和string类型的值，按照降序排列 m1.insert(pair<int, string>(1, "one")); // 向m1中插入{1, "one"} m1.insert(make_pair(2, "two")); // 向m1中插入{2, "two"}); // 向m1中插入{2, "two"} auto p = m1.insert({3, "three"}); // 向m1中插入{3, "three"}，并获取返回值 cout << p.first->first << " " << p.first->second << endl; // 输出 3 three cout << p.second << endl; // 输出 true p = m1.insert({3, "san"}); // 尝试向m1中插入{3, "san"} cout << p.second << endl; // 输出 false m2.emplace(3, "three"); // 向m2中原位构造{3, "three"} m2.emplace_hint(m2.begin(), 4, "four"); // 向m2中原位构造{4, "four"}，并提供一个提示位置 m3[5] = "five"; // 向m3中插入或修改{5, "five"} m3[6] = "six"; // 向m3中插入或修改{6, "six"} cout << m3[7] << endl; // 输出 空字符串，并向m3中插入{7, ""} cout << m3.at(8) << endl; // 抛出异常，并不会向m3中插入{8, ""} m1.erase(1); // 从m1中删除键为1的键值对 cout << m1.erase(4) << endl; // 输出 0，表示删除失败 auto it = m1.begin(); // 获取m1的起始迭代器 it++; // it指向第二个元素 m1.erase(it); // 从m1中删除it所指向的元素 it = m1.begin(); // 重新获取m1的起始迭代器 auto it2 = m1.end(); // 获取m1的结束迭代器 it2--; // it2指向最后一个元素 m1.erase(it, it2); // 从m1中删除[it, it2)范围内的元素 m2.clear(); // 清空m2中所有元素 auto it = m2.find(3); // 查找m2中是否有键为3的元素 if (it != m2.end()) cout << it->first << " " << it->second << endl; // 如果找到了，则输出 3 three cout << m2.count(4) << endl; // 输出 1，表示m2中有键为4的元素 cout << m2.count(5) << endl; // 输出 0，表示m2中没有键为5的元素 auto lb = m3.lower_bound(5); // 获取5在m3中的下界位置 auto ub = m3.upper_bound(5); // 获取5在m3中的上界位置 cout << lb->first << " " << lb->second << endl; // 输出 5 five cout << ub->first << " " << ub->second << endl; // 输出 6 six auto p = m3.equal_range(6); // 获取6在m3中的范围 cout << p.first->first << " " << p.first->second << endl; // 输出 6 six cout << p.second->first << " " << p.second->second << endl; // 输出 7 空字符串 }
2.multimap
- multimap允许键重复，而map不允许键重复，所以multimap是没有[ ]的。
- multimap的插入操作总是成功，而map的插入操作可能失败，如果插入的键已经存在于map中。
multimap和map的其他用法和特点基本相同，都是基于红黑树实现的有序关联容器。
3.什么时候应该使用multimap而不是map
一般来说，应该使用multimap而不是map的情况是：
当需要存储多个具有相同键的键值对时，例如一个人的多个电话号码，一个词的多个同义词等。
当不需要修改键值对的值时，因为multimap不支持使用下标运算符或者at()方法来修改值。
当不需要按照键的顺序遍历键值对时，因为multimap的迭代器可能会跳跃地访问相同键的元素。
最后两个OJ题作为练习
