【C++第十八章】Map和Set

Map和Set

map和set的介绍

容器分为两种，序列式容器和关联式容器，序列式容器因为底层是线性序列的数据结构，存储的是元素本身，而关联式容器中不单是为了存储数据，还要进行查找，所以存储的是键值对，能够更有效的对数据进行检索。而本篇所介绍的map和set就是关联式容器。

键值对

键值对用来表示具有一一对应的一种结构，该结构一般包含key和value，key表示键值，value表示key对应的数据，比如学生所对应的成绩，单词所对应的中文。

set

set是key模型，它的value就是key，且value唯一，set中的元素不能在容器中修改，可以插入和删除。
set底层是用的红黑树进行维护。
set中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序。
set容器通过key访问单个元素速度通常比unordered_set(哈希)慢，但是set允许根据顺序对子集进行直接迭代(有序)。

insert

  当一个值已经存在时，会返回false，成功插入则会返回true。

erase

  erase接收迭代器时，如果迭代器没有找到该数，就会报错，但是erase接收具体的值时，没有该数会正常运行，并且erase返回的是size_t告诉我们删除了几个数。

lower_bound和upper_bound

  用于寻找迭代器区间，可以配合erase使用。

equal_range

  equal_range会返回一个pair，first返回>=val的迭代器，second返回>val的迭代器

count

  count可以查看当前值存在的数量，在set中可用于看该值在不在容器中，而multiset可用于统计数量。

multiset

  允许有重复的值插入set中，在底层存储的是<value,value>，对于搜索树来说，重复数据插入左边或者右边都可以，红黑树会进行平衡，当有多个值时，find会返回中序的第一个val。

  equal_range也可以在这里使用，multiset可以存储重复数据，而equal_range可以指定删除一样的数据。

map

map的用法与set基本一致，不过map是kv模型，其中map的key是键值对中key的类型，T是键值对中value的类型。
在map内部中，key与value通过成员类型value_type绑定在一起，取别名为pair，并且不想自己的key被修改。
map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但是map允许根据顺序对元素进行直接迭代。
map支持下标访问，在方括号中放入key，能找到对应的value。map底层为红黑树。

  我们写的时候不需要加上const，因为在pair中有一个copy，它既是构造也是拷贝构造，能够自动推导类型，然后初始化成const版本。

  我们可以用多种方法进行插入，make_pair是一个函数模板，能自动推导类型，所以可以简化使用。

  当我们使用范围for时，可以加上引用防止拷贝构造过大的消耗(比如string拷贝会进行深拷贝，消耗会更大)，map的first不能修改，second可以修改。

  在map中统计次数可以用下面两种方法，第一种用++的方式统计

  第二种则是用方括号直接++，在方括号中加上key即可。

  原理在于方括号是一个具有复合功能的函数

  我们根据官网map的operator[]返回值来讲解，可以发现，方括号是insert实现的，insert的first是一个迭代器，指向一个新插入的数据，如果该数据已经存在，那么会转而指向已经存在的数据，insert的second在插入成功时返回true，否则返回false。

  在方括号中，如果value是int类型，那么第一次插入时value就返回0，insert的返回值是一个pair，pair的first是一个迭代器，迭代器解引用出来就是k-value的pair，而k-value的first就是key，second就是value，所以得出，countMap[str]++第一次插入，value为0，它再返回迭代器，迭代器取到的second也就是value，当我们++时，value也会++。

  multimap不支持方括号，因为有多个相同数据时，它不知道该返回哪一个。