map和set容器

目录

1. 关联式容器

2. 键值对

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

3.1 set容器

3.2 map容器

---

1. 关联式容器

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

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

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中存储的是真正的键值对，set中只放  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 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

---