1.序列式容器与关联式容器
序列式容器
定义：以线性的序列存储数据，数据按照顺序插入，两个数据位置没有紧密关系，即使交换了也不会影响
eg：数组，链表，栈，队列通常用于按照顺序访问和存储数据
关联式容器
定义：基于键值对（pair）的容器，顺序按照键的顺序，两个数据位置关系紧密，交换数据位置会出问题
eg：哈希表，红黑树
通常用于快速查找，插入，删除
2.key类型关联式容器的使用场景
key类型的特点是：只需要存储唯一一种数据，且key值唯一
eg：小区停车场里面的车库杆，识别业主车牌号，若录入了数据库就准入，否则不准入。
这种情况我们只需要存储一种数据，就是车牌号
3.key-value类型关联式容器的使用场景
key-value的特点是：需要两种数据一一对应，key值唯一，value不唯一
eg：商场的停车场，停车时不仅需要存储车牌号，还要同时记录当前时间点，也就是一个车牌号对应一个时间点。也就是两种数据一一对应
4.set的使用
set是无冗余的，key值唯一。multiset允许数据冗余，key值不唯一
（1）set的模板参数构成
一共有三个模板参数，第一个T是set存的数据的类型，第二个Compare是需要支持比较仿函数（默认为less升序），第三个Alloc是空间配置器，一般来说我们只需要传第一个模板参数。
使用时记得包含头文件
（2）set的性能
set是由二叉平衡搜索树实现的，所以增删查的效率是logN。而迭代器的遍历是中序遍历，所以他的数据也是有序的
（3）set的构造函数与迭代器
这里的控制仿函数构造，我们传递了greater仿函数，使set中数据变成了降序
他的迭代器是双向迭代器
对于反向的，他会降序输出数据
因为正向迭代器是按照中序遍历树，从而实现迭代器++移动到下一个大于等于当前数据的位置。而反向迭代器的起始位置就是升序排序的最后一个数据位置，进行++操作，实际上相当于正向迭代器的--，从而可以反过来遍历数据
（4）set的增删查
1.insert
2.find与erase
erase有三种参数形式，第一种是单迭代器，第二种是单数据值，第三种是迭代器区间
注意：
删除数据值在multiset（支持键值冗余的set表）中会直接删除所有等于该值的数据，并返回删除掉的数据的个数find只有一种查找方式，就是直接查找数据
但是我们有库的查找，有set的查找，我们应该使用哪个find更好？
库中的查找是BF暴力查找，而我们set的find是搜索树的查找，效率在logN。很明显set的find效率更好。
不过如果仅仅是判断是否存在，而不需要获取数据的迭代器，那么我们可以用count来实现
O（1）时间复杂度的查找
！！！：先查找再删除需要注意判断是否查找成功
这里的1数据是不存在的，所以迭代器是非法的，我们传递一个非法的迭代器给erase去执行删除操作会报错。正确的做法是先判断是否查找成功，成功再执行删除操作
（5）lower_bound与upper_bound
假如我们需要删除一段特定区间，我们可以使用erase的迭代器区间删除的方式去删除数据，但是我们如何获取特定的区间的边界迭代器？
我们可以使用lower_bound与upper_bound来查找边界迭代器
lower_bound:查找大于等于x的第一个迭代器，相当于（>=）
upper_bound：查找大于x的第一个迭代器，相当于（>）
比如我们需要删除区间为1-10的数据的3-6的值，那么我们用lower_bound查找3，用upper_bound查找6，这样子删除区间就知道了，接下来利用erase删除即可
5.map的使用
map不允许key值冗余，multimap允许key值冗余
由于map是键值对（key-value）形式的，所以我们引入一个新的类pair，该类包含两个数据
一个是key，一个是value。
pair<const key, T>:引入他有个好处，就是对map的迭代器解引用可以根据需求访问key/value。如果不引入在解引用时会出问题，因为解引用不能返回两个值
接下来我们利用insert来体现pair的用法：
直接用一个花括号表示一个键值对，多个键值对需要用花括号整个包住
以及迭代器遍历的时候我们不再使用解引用符号访问数据，而是用->
因为pair没有被实现流插入和流提取，所以我们需要分别访问pair的key和value，利用->
其实it->first应该是：it->->first 也就是，it.operator->()->first
5.1operator[]
operator[]实际上是复用insert实现的
map的insert返回值有个特别之处，正常的insert只要返回是否插入成功的判断就行，也就是bool类型的数据，但是map的insert返回的是pair类型数据。
这里我们看到对于单数据插入，返回的是pair<iterator,bool>。若插入成功，返回新插入的数据的迭代器，以及true。若插入失败，返回map中key等于待插入数据key的数据的迭代器
下面我们举例说明
（1）插入成功
这里我们没有哈密瓜这个键值，所以插入成功，观察it1迭代器，我们发现返回的迭代器就是新插入的数据迭代器，且返回的是true
（2）插入失败
由于已经存在西瓜这个键，所以插入失败，观察it2迭代器，我们发现迭代器指向的是数量为1的西瓜，也就是map中的数据的迭代器
利用insert实现operator[]
由于这里只是写了对应代码，没有放到自定义命名空间，所以会有些报错。
operator[ ]的目的是通过传递key给[ ]然后访问到key对应的value，并可以实现修改操作
所以我们的返回值是key对应的位置迭代器的value值的引用
插入分两种情况：
其一：插入成功，返回的pair中包含新插入的数据的迭代器
其二：插入失败，返回的pair中包含map原本就存在的对应的key的迭代器
我们发现，无论如何，p中都包含key的迭代器，而我们要的就是key对应的迭代器的value值
也就是p.first->second（p.first是key对应的迭代器，它指向pair<key,value>类型）
operator[]的多种用处
