map和set容器

目录

1. 关联式容器

2. 键值对

3. 树形结构的关联式容器

3.1 set容器

3.2 map容器

1. 关联式容器

vector、list、string、deque等容器都称为序列式容器，因为其底层原理都是线性的数据结构，里面存储的是元素本身，那么什么是关联式容器？和序列式容器的区别又在哪里？

关联式容器也是用来存储数据的，与序列式容器不同的是，里面存储的是<key，value>结构的键值对，在数据检索时比序列式容器的效率更高。

2. 键值对

用来表示一一对应关系的一种结构，该结构只包含了两个成员变量key和value，key表示键值，value表示与key所对应的信息，比如英汉互译的字典，找到一个英语单词必定存在一个与之对应的翻译，每个单词和翻译之间是一一对应的。

3. 树形结构的关联式容器

STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器

3.1 set容器

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。
3. set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
4. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
5. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序子集进行直接迭代。
6. set在底层是用二叉搜索树(红黑树)实现的

注意事项：

1.  与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放  value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：log2n
7. set中的元素是不允许修改，因为键值是不可以被修改的
8. set中的底层使用二叉搜索树(红黑树)来实现

set的各类操作：

1. insert

 插入一个值

 插入一个区间

 在指定位置插入一个值

 我们也可以发现set是默认进行升序排序

2.erase

 删除指定位置

 删除已存在的数

 删除一个区间

 3. count和find

 找出set中有多少个键值为val的值

虽然我们插入了两个5，但结果只有一个5，因为set会去重，因此count的结果只能是1/0 

 在set容器中找寻目标值，如果目标值存在则返回其迭代器，如果不存在则返回end()

需要判断find的返回值，如果不等于end()，则说明找到了

 4. empty和size

3.2 map容器

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型
3. value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
4. 在内部，map中的元素总是按照键值key进行比较排序的。
5. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
6. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
7. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

map的各类操作：

1. insert

 我们可以发现map的插入的是一个pair类型

那么我们有几种实现pair的方法：

插入还有第二种方法：

通过介绍我们可以发现，如果键值key在map中存在时，则会返回其键值对应的value的引用，

如果key在map中不存在时，则会以该键值插入进map

 2.erase

删除指定位置的元素

 删除指定值

删除指定值会返回删除的个数，又因为map中每个key值是独立的，因此返回值只能是0/1,但如果是multimap值可以超过1

删除区间 

 3. find和count

我们可以发现当查找成功会返回该键值所在的迭代器，如果不存在则会返回end()

因此当我们获得迭代器时，我们需要判断一下

 查询当前容器有多少个键值是key的数据，但由于在map中key值是独立的，因此count的结果只能是0 / 1