C++ map和set
C++参考文献：cplusplus.com - The C++ Resources Network
目录
一、序列式容器和关联式容器
二、set系列
（1）set类的介绍
（2）set的构造和迭代器
（3）set的接口
1.insert编辑
2.find和erase
3.lower_bound和upper_bound
（4）set和multiset的差异
三、map系列
（1）map类的介绍
（2）pair类型介绍
（3）map的接口
1.insert
2.erase
3.operator[]
（4)multimap和map的差别
一、序列式容器和关联式容器
前面我们已经接触过STL中的部分容器如:string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered map/unordered set系列。本章节讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。
二、set系列
（1）set类的介绍
set的声明如下图，T就是set底层关键字的类型set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
一般情况下，我们都不需要传后两个模版参数。set底层是用红黑树实现，增删查效率是O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。因为STL库实现的接口相似度高，我们就不一一展示，挑选重要的来理解学习。
（2）set的构造和迭代器
迭代器是一个双向迭代器。
set支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序;支持迭代器就意味着支持范围for，set的iterator和const iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
（3）set的接口
1.insert
set的insert不支持插入相同的值。当然不管是不是const迭代器都不支持修改。
说明默认的insert作用就是去重和升序。如果我们想要变成降序的话，我们就需要增加仿函数这个参数。
对于列表值的插入，类似下图。
接着我们也观看一下构造中的列表初始化。下图是先构造了个临时对象，然后再拷贝构造出strset。
2.find和erase
find返回值是迭代器，成功返回要找的迭代器，返回失败返回end的迭代器。
而erase删除提供传迭代器，传数据，还可以传迭代器区间。
这时候会有疑问，为什么第二个返回值不是bool而是size_type呢？这是为了兼容multiset，这里是删除成功返回1删除失败返回0，在multiset中，删除几个返回多少。
我们通过一些例子去熟悉掌握这些接口。例如我们想把set中的最小值删除，这里因为默认是升序，我们删除begin迭代器即可。
例如我们如果要实现输入一个值然后删除。
例如直接查找在利用迭代器删除x。
这里erase后迭代器肯定失效。第一种是野指针，第二种是在替换法后当前位置的迭代器意义改变，也称为迭代器失效。
3.lower_bound和upper_bound
lower_bound返回大于等于val位置的迭代器，upper_bound则是返回大于val位置的迭代器
这个有什么作用呢？假如我们需要删除一段区间的值，而删除一段区间需要左闭右开，这个时候我们就可以用上面两个接口来获得区间。
int main()
{set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); for (auto e : myset){cout << e << " ";}cout << endl;auto itlow = myset.lower_bound(30);auto itup = myset.upper_bound(60);myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}这样我们就能够删除30到60之间的值。
（4）set和multiset的差异
multiset和set的使用基本完全类似，:要区别点在于multiset支持值冗余，insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
相比set不同的是，multiset是排序，但是不去重。
而find相比set也不同，不同的是，x可能会存在多个，find查找中序的第一个。
count则会返回multiset中x的个数。
erase则会删除所有的x。
三、map系列
（1）map类的介绍
map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的 。
（2）pair类型介绍
我们先来了解一下map的插入，在了解插入之前我们需要去了解pair，因为插入的参数涉及到这个类型。
底层大概就是这样，对比我们能够知晓，first就是Key而second就是value。
typedef pair<const Key, T> value_type;
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 U, class V>pair(const pair<U, V>& pr) : first(pr.first), second(pr.second){}
};所以我们在map中使用insert需要使用到pair。
（3）map的接口
1.insert
我们先前提到的pair就是我们在insert的时候所要使用到的，对于insert我们有多种形式insert。
第一种就是我们定义一个有名的pair对象，然后插入pair对象。
第二种我们可以插入一个匿名的pair对象。
第三种我们可以借用函数模板make_pair来插入，make_pair它会自己推导出后面的类型，返回一个pair对象。
C++11后提支持多参数隐式类型转换后，我们就有了第四种方法insert。
在遍历map的时候，与其他容器也有所不同，map没有重载流插入和流提取，我们了解了pair的结构后我们需要去解引用后再调用first或者second。
在之前的学习中，我们能够知晓迭代器不止重载了operator*还重载了operator->。刚好我们存储的对象是结构，这样我们就可以采用箭头。
所以在map中我们常用箭头来取对应的数据。我们要注意map中可以修改value，但不可以修改key。
2.erase
erase还是只跟key有关，即使你map中没有key也不会报错。
3.operator[]
我们先来实现一个统计水果出现的次数。思路就是利用find和iterator修改功能，统计水果出现的次数。
但是实际上在map中不使用这种方式来实现，直接通过一行代码就可以搞定。
这是怎么做到的呢？那我们需要来学习了解一下operator[]。
这个接口提供了插入，查找和修改的功能。我们再回去观看一下insert。
我们能够发现这里其实有两个pair。
我们重点要理解insert的返回值中的迭代器是什么意思呢？
所以返回的迭代器要么是新插入节点的迭代器，要么是插入失败map里面和插入key相等的迭代器。bool则是根据插入成功失败返回的。总结来说，insert如果插入成功返回的是pair<新插入值所在的迭代器，true>，插入失败则是pair<已经存在的跟key相同值的迭代器，false>，所以insert不仅有插入的功能，还有查找的功能。insert插入失败时充当了查找的功能，因为这一点，insert可以用来实现operator[]。
mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}我们把operator[]内部实现大概的代码拿出来研究一下。能够得出：1、如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储mapped_type值的引用，那么我们可以通过引用修改返映射值。所以[]具备了插入+修改功能。2、如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找+修改的功能。
（4)multimap和map的差别
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。