11.1关联容器概述

关联容器有map和set两大类，map是关键字和值得映射，set是关键字的简单集合，它们分别有对应的multi(允许关键字重复）,unordered版本（无序容器 ），有序容器使用比较函数来比较关键字，从而使元素顺序存储，所以相等元素也是连续存放的，而无序容器使用关键字的==运算符和一个hash <key_type>类型的对象来组织元素

---

11.2关联容器对关键字的要求

关联容器不支持顺序容器的有关位置方面的操作，对于有序容器而言，标准库使用关键字类型的<运算符来比较两个关键字，在集合类型，关键字类型就是元素类型；在映射类型，关键字类型是元素的第一部分的类型。替代<的函数必须在关键字类型上定义一个严格弱序。

函数必须满足如下基本性质：

• 任意两个关键字不能同时“小于等于”对方
• 关系具有传递性
• 如果存在两个关键字，任何一个都不”小于等于”对方，则称它们是等价的。等价性也必须具备传递性。
  使用形式如下：
  set<string,decltype(compare)*> set_ex(compare);
  decltype来获得一个函数指针类型时，必须加上一个*来指示使用一个给定的函数类型的指针

---

tips:
可以使用列表初始化返回值，如返回类型是pair<int,int>,可以return {1,1};

11.3关联容器操作

关联容器的类型别名：
key_type:容器的关键字类型
mapped_type:每个关键字关联的类型；只适用于map
value_type:对于set和key_type相同，对于map，为pair<const key_type,mapped_type>

---

11.3.1 关联容器迭代器

当解引用一个关联容器迭代器时，会得到一个类型为value_type的之的引用，不能修改关键成员的值。set的iterator和const_iterator都只允许只读

11.3.2 关联容器算法

通常不对关联容器使用算法，因为它们的关键字都是const,故只能用于只读算法，使用关联容器定义的find方法比泛型要快

11.3.3 检测insert的返回值

对于不允许关键字重复的关联容器，insert(v)返回一个pair类型，pair的first成员是指向给定元素的迭代器，second成员是一个表示是否插入成功的bool值。
insert(p,v)表示从p开始搜索新元素应该存储的位置,返回指向给定元素的迭代器。
对于允许关键字重复的关联容器，insert(v)返回指向给定元素的迭代器

11.3.4 map的下标操作

map和unordered_map提供下标运算符和一个对应的at函数，使用下标运算符，返回类型是mapped_type，如果关键字不在map中，会为它创建一个元素插入到map中，关联值将进行值初始化，at函数当关键字不在容器中，会抛出Out of range异常

11.3.5 访问元素

lower_bound(k)：返回第一个不小于k的元素的迭代器
upper_bound(k)：返回第一个大于k元素的迭代器
equal_range(k): 返回一个迭代器pair,表示等于关键字k的元素范围，若k不在，返回两个end()

11.4 无序容器

无序关联容器在存储上使用哈希函数和关键字 类型的==运算符，使用链地址法来解决哈希冲突，同时额外提供了哈希策略来重组容器。

无序容器对关键字类型的要求：
使用一个hash<key_type>类型的对象来生成每个元素的哈希值。标准库提供了内置类型包含其对应的指针提供了hash模板，而且也包括string，
使用形式如下：

using DS_set unordered_set<string ,decltype(hash)*,decltype(equal)*>;
DS_set set_ex(bucket_count,hash,equal);