关联式容器
关联式容器是C++标准库提供的一种数据结构，用于存储操作键值对（key-value）。每个键值对都包含一个键和一个关联的值。关联式容器提供了通过键快速查找和访问值的功能。
C++98标准库提供了四种树形结构的关联式容器：set、multiset、map和multimap。
set：set是一个无序集合，存储唯一的元素。内部实现使用红黑树，因此元素是按照特定的顺序进行存储。查找和插入操作的平均时间复杂度为O(log n)。multiset：multiset和set类似，不同之处在于它可以存储重复的元素。map：map是一个键值对的集合，其中的键是唯一的。内部实现也是使用红黑树。查找和插入操作的平均时间复杂度为O(log n)。multimap：multimap和map类似，不同之处在于它可以存储重复的键。
后续C++11又提供了哈希结构的关联式容器，此博客不做讲解。
关联式容器与序列式容器的区别在于元素的顺序。关联式容器内部使用二叉搜索树（如红黑树）实现，因此元素是按照特定的顺序进行存储。而序列式容器内部使用动态数组或链表实现，元素按照插入的顺序进行存储。
pair
在讲解map与set之前，我们要先了解一个类：pair。
pair是一个模板类，封装了两个成员变量first，second，用于存储两个不同类型的值。它被定义在头文件<utility>中。
pair类的定义如下：
template <class T1, class T2> struct pair { T1 first; T2 second; };
pair类有两个模板参数T1和T2，分别表示两个值的类型。
pair类有两个成员变量first和second，分别表示两个值。
pair类的构造函数有多个重载形式，可以根据需要来创建pair对象。其中，最常用的是以下几种：
- pair()：默认构造函数，创建一个
pair对象，默认初始化first和second。 - pair(const T1& x, const T2& y)：构造函数，初始化
first为x，second为y。
pair类还支持拷贝构造函数、移动构造函数和赋值运算符重载，以及比较运算符重载。
使用pair类可以方便地将两个不同类型的值组合在一起，便于传递和操作。例如：
pair<int, string> p1(1, "hello"); cout << p1.first << " " << p1.second << endl; pair<double, char> p2; p2.first = 3.14; p2.second = 'a'; cout << p2.first << " " << p2.second << endl;
输出结果为：
1 hello 3.14 a
另外的，C++还提供了一个函数make_pair用于创建pair对象，需要时直接传入两个参数，分别对应first和second，make_pair内部会自动推演参数类型，返回一个pair对象。
auto p = make_pair("hello world", 10);
此时make_pair就会推演对象的类型为pair<const char*, int>。
因为pair可以存储任意两个不同类型的数据，所以任何需要封装两个变量的地方，都可以使用pair。而我们的key - value结构，就是需要封装两个变量key和value，所以map和set的底层都是使用pair来完成的。
set
set是一种集合容器。它是基于红黑树实现的，它可以存储不重复的元素，并且会自动按照元素的大小进行排序。
下面是一些set的概念和特点：
- 不重复的元素：
set中的元素是不重复的，每个元素只能出现一次。 - 自动排序：
set中的元素会根据元素的大小进行自动排序。默认情况下，set按照升序排列。你也可以通过传入自定义的比较函数来进行降序排序。 - 红黑树实现：
set内部使用红黑树（一种自平衡二叉搜索树）来存储元素。这个数据结构保证了素的快速插入、查找和删除，时间复杂度为O(logn)。 - 迭代器支持：
set提供了迭代器，可以用于遍历集合中的元素。 - 查找和插入的效率高：由于
set是基于红黑树实现，查找和插入操作的平均时间复杂度为O(logn)，效率比较高。 - 元素的值是不可修改的：在
set中，元素的值是不可修改的。如果需要修改元素的值，需要先删除旧的元素，然后插入新的元素。
接下来我们讲解set的接口使用以及注意事项。
模板参数
set的模板如下：
template < class T, class Compare = less<T>> class set;
其有两个模板参数：
T：代表value值的类型
Compare：代表了比较规则的仿函数
也就是说，我们在定义set的时候，可以在模板参数中传入仿函数，用于制定规则：
template <class T> struct comp { bool operator()(const T& t1, const T& t2) const { return T1 > T2; } }; int main() { set<int, comp<int>> s1; return 0; }
其中，s1通过仿函数comp完成了逆序排列，而set的模板参数有缺省值Compare = less<T>，所以set的默认情况是升序排列。
typedef的类型
| 类型 | 含义 | 缺省值 |
key_type |
第一个模板参数T的类型，即value的类型 |
value_type |
第一个模板参数T的类型，即value的类型 |
|
key_compare |
第二个模板参数的类型，即用于比较的仿函数的类型 | less<key_type> |
value_compare |
第二个模板参数的类型，即用于比较的仿函数的类型 | less<value_type> |
由于在set中，key和value是一致的，所以以上表格中，key_type和value_type是一致的，key_compare与value_compare是一致的。
而key_compare与value_compare的缺省值是 less<key_type>，即升序排序的仿函数。
构造函数
默认构造：
explicit set (const key_compare& comp = key_compare());
迭代器区间构造：
template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare());
通过一个迭代器区间来构造set，由于是模板，所以可以是其它容器的迭代器。
迭代器
set的迭代器用法与其它容器一致，就是通过begin和end来进行遍历，或者说使用反向迭代器。值得注意的是容器set的迭代器走中序遍历，得到的是有序的数据。
常规接口
empty：
bool empty() const;
即返回这个set是否为空，如果为空返回true，不为空返回false。
size：
size_type size() const;
返回当前set存储的节点个数。
swap：
void swap (set& x);
交换两个set的根节点指针。
clear：
void clear();
清空当前set。
key_comp 与 value_comp：
key_compare key_comp() const; value_compare value_comp() const;
可以看到，两者的返回类型分别是key_compare 与value_compare ，也就是比较key与value的仿函数，这两个函数的功能就是返回当前比较set的仿函数。
find：
iterator find (const value_type& val) const;
find函数用于查找val值的节点，如果找到了，返回指向val的迭代器；如果没找到，则返回end()处的迭代器。
count：
size_type count (const value_type& val) const;
count函数用于检测set中存在几个val值的节点，但是由于set不可以存在重复的元素，所以这个函数的返回值只有可能是1或0。返回类型为size_type即size_t无符号整型。
特殊接口
lower_bound 与 upper_bound：
iterator lower_bound (const value_type& val) const; iterator upper_bound (const value_type& val) const;
两者都传入一个val值，返回值一个iterator迭代器，它们的功能如下：
lower_bound：返回第一个>=val节点的迭代器
upper_bound：返回第一个>val节点的迭代器
在STL设计中，都是利用左闭右开的区间特性，而迭代器也利用了此特性，我们可以使用lower_bound 与upper_bound配合得到一个一开一闭的迭代器区间，从而进行遍历，删除等等操作。
比如现在我们想遍历一个set中[3, 20]的闭区间，你会如何查找迭代器？
假设我们有一个名为s1的set，看一段代码：
auto it1 = s1.find(3); auto it2 = s2.find(21); while(it1 != it2) { cout << *it1 << endl; ++it1; }
请问这个代码正确吗？
以上代码存在两个问题：
在s1中可能不存在值为3或者21的节点，find有可能是失败的，此时我们就无法遍历到[3， 20]了。
- 由于我们要遍历
[3， 20]，迭代器遵循左闭右开的特性，所以我们找了一个比20大的迭代器21来遍历。但是如果我们的set存储的是float类型的数据，20与21之间可能还会存在其它节点，此时我们可能就会多遍历到其它节点。
因此我们可以利用lower_bound 与upper_bound配合来得到迭代器：
auto it1 = s1.lower_bound(3); auto it2 = s2.upper_bound(21); while(it1 != it2) { cout << *it1 << endl; ++it1; }
以上代码中lower_bound(3)可以得到第一个>=3节点的迭代器，这样就不怕3节点不存在的情况了，如果3存在，此函数得到3，如果不存在，就得到大于3的下一个节点。
而upper_bound(21)则是得到第一个>21节点的迭代器，如果我们存储了float类型的数据，而刚好存储了一个21.0001的数据，那么此时upper_bound(21)就刚刚好返回这个只大21一点点的节点。
通过两者配合，我们就可以得到一个等效的左闭右开迭代器区间，后续方便操作。
erase：
set的erase存在三个重载：
void erase (iterator position);
这个erase用于删除迭代器指向的节点，迭代器必须有效。
void erase (iterator first, iterator last);
这个erase用于删除整个迭代器区间[first, last)，迭代器必须有效。
size_type erase (const value_type& val);
这个erase用于删除val值的节点，val值可以不存在，删除后返回删除节点的个数。在set中，由于不存在重复节点，所以返回值只可能是0或1。
insert：
set的insert也存在三个重载：
iterator insert (iterator position, const value_type& val);
这个重载用于提高插入效率，如果迭代器position位于插入val值的节点之前，那么此次插入val的效率会提高，但是如果迭代器position与插入val节点无关，那么与一般的插入一致。
template <class InputIterator> void insert (InputIterator first, InputIterator last);
这个重载用于插入一整个迭代器区间[first, last)。
pair<iterator,bool> insert (const value_type& val);
这是最常用的插入，其用于直接插入一个val值的节点，但是其返回值比较特别：pair<iterator,bool>
如果原先val存在，此时iterator指向原先的val节点，bool值返回false表示插入失败
如果原先val不存在，此时iterator指向新插入的val节点，bool值返回true表示插入成功
但是函数不能一次性返回两个值，于是把iterator和bool两个值封装进pair中返回。这样我们就既可以得到迭代器，又可以检测是否插入成功了。
multiset
multiset是一个允许存在重复元素的set，其它的效果与set完全一致。
但是有几个接口还是值得注意：
find：
对multiset使用find时，由于一个val可能有多个节点，此时返回中序遍历的第一个节点。
count：
对于set而言，count用于返回某个val值的个数，由于set不能重复，所以这个count接口没有多大意义。而对于multiset才有用，可以检测val的个数。
map
map是一种关联容器，用于存储键-值对（key-value）。map中的每个元素都由一个键和一个与之关联的值组成，键和值可以是任意类型。其将key和value封装进了pair中，所以每一个节点都是一个pair<key, value>。
模板参数
set的模板如下：
template < class Key, class T, class Compare = less<Key> >class map
其有三个模板参数：
Key：代表key值的类型
T：代表value值的类型
Compare：代表了比较规则的仿函数
同样的，map也可以在模板参数中定义仿函数，与set相似。
typedef的类型
| 类型 | 含义 | 缺省值 |
key_type |
第一个模板参数Key的类型，即key的类型 |
|
mapped_type |
第二个模板参数T的类型，即value的类型 |
|
value_type |
将 |
|
|
第二个模板参数的类型，即用于比较的仿函数的类型 |
less<key_type> |
在map中，value的类型是mapped_type，而value_type却是pair<const key_type,mapped_type>的类型，这是值得注意的。
常规接口
由于map的很多接口和set一致，这里就用一张表格概括：
| 函数 | 声明 | 功能 | 注意事项 |
| 迭代器 | begin , end等 | 遍历map | 走中序遍历，得到有序数据 |
| empty | bool empty() const; | 判空 | - |
| size | size_type size() const; | 返回元素个数 | - |
| erase | void erase (iterator position); | 删除迭代器指向的节点 | 迭代器必须有效 |
| size_type erase (const key_type& k); | 删除key值的节点 | key值可以不存在 | |
void erase (iterator first, iterator last); |
删除迭代器区间 |
- |
| swap | void swap (map& x); | 交换两棵树根节点指针 | - |
| clear | void clear(); | 清空map | - |
| key_comp | key_compare key_comp() const; | 得到比较key的仿函数 | - |
| value_comp | value_compare value_comp() const; | 得到比较value的仿函数 | - |
| find | iterator find (const key_type& k); | 得到key位置的迭代器 | 如果没有找到，返回end()等效的迭代器 |
| count | size_type count (const key_type& k) const; | 返回值为key的节点个数 | - |
| lower_bound | iterator lower_bound (const key_type& k); | 返回第一个>=key值节点的迭代器 | - |
| upper_bound | iterator upper_bound (const key_type& k); | 返回第一个>key值节点的迭代器 | - |
特殊接口
insert：
对于map而言，insert的功能其实和set是一致的，但是不一样的是我们需要插入pair<key, value>，所以此处拿出来额外讲解。
重点看到以下insert的重载：
pair<iterator,bool> insert (const value_type& val);
其插入的值val的类型时候value_type，而我们先前说明过，value_type就是pair<key, value>的类型。也就是说，我们要构造出一个pair插入进去。
现在我们有map<string, int>：
pair<iterator,bool> insert (const value_type& val);
现在我们对其进行插入：
- 利用匿名对象插入：
m.insert(pair<string, int>("hello", 100));
以上代码，我们利用pair<string, int>("hello", 100)这种语法构造了一个匿名对象，然后进行插入。
- 利用多参数默认构造的类型转化：
m.insert({ "hello", 100 });
由于pair具有一个多参数的默认构造，具有类型转化的功能，所以我们可以利用隐式类型转化进行传参。而我们有多个参数，所以要把这些参数用{}括起来。
- 利用
make_pair进行插入：
m.insert(make_pair("hello", 100));
即利用make_pair函数，让其自动推导类型构造pair。
operator[ ]：
map还重载了[]，这个重载比较复杂，但是非常有用，我们先看到声明：
mapped_type& operator[] (const key_type& k);
其接收一个key_type类型的参数，也就是接受一个key，然后返回一个mapped_type&，也就是一个value的引用。其功能为：接受一个key值，然后返回这个key对应的value的引用。
其等效于下面的代码：
(*((this->insert(make_pair(k,mapped_type()))).first)).second
现在我们来解读以上代码，我们将其拆解为四个部分：make_pair(k, mapped_type( )) + this->insert( ) + ( ).first + (*( )).second，我们一层层解析。
第一层：
make_pair(k, mapped_type( ))
可以看出，这是在利用参数k，通过make_pair构造一个pair，而这个pair的value使用了mapped_type( )（mapped_type就是value的类型）来调用默认构造。这样我们最后就得到了一个pair<key, value>。
第二层：
this->insert( )
上一层我们构造了一个pair<key, value>，然后它被作为参数，传入到这个insert中，相当于把刚刚构造的节点插入进map中。map的插入后，不论成功与否，都会返回一个pair<iterator, bool>，iterator用于指向key的迭代器，bool用于标识插入是否成功。所以这一层最后得到了一个pair，分别存储了指向key的迭代器和bool。
第三层：
( ).first
上一层中我们得到了pair<iterator, bool>，这一层访问它的first，也就是访问了iterator，所以这一层得到了指向key值的迭代器。
第四层：
(*( )).second
我们上一层拿到了指向key的迭代器，这一层先对迭代器解引用*( )，此时就得到了一个map的节点。而map的节点是pair<key, value>，所以我们解引用得到了一个pair，随后通过( ).second访问pair<key, value>的second，也就是value。最后返回这个value的引用。
所以我们最后得到了key对应的value的引用。那么这有什么用呢？
假设我们有一个map<string, string>类型的字典dict，通过这个来展示operator[ ]的功能：
- 插入一个key值：
dict["left"];
以上语句在dict中插入了一个key = "left"但是没有value的节点 - 插入一对
key - value：dict["left"] = "左边";
由于operator[ ]返回的是对应的引用，因此我们可以直接给返回值赋值，此时我们就插入了一个节点key = "left" - value = "左边" - 修改
key对应的value：dict[“coffe”] = "咖啡";
如果我们的dict原先就存在key = "coffe"的节点，以上代码可以修改这个key的value值
- 得到
key对应的value：cout << dict["coffe"] << endl;
由于我们拿到的是value的引用，我们也可以把它作为一个值赋值给别人或者输出
可以看到，operator[]的功能非常丰富，整体来说还是一个很好用的重载。
multimap
原本的map同一个key只能存在一个value，而multimap则可以存在多个key相同的节点，不过多赘述了。
