关联式容器
在之前的学习中，所学习的容器类型都是序列式容器，其底层是线性数据结构存储的是元素本身
本章所学习的是另一种容器关联式容器，关联就意味着元素与元素之间存在着某种关联；存储的是数据是 <key,value>结构的键值对，接下来学习什么是键值对
键值对
键值对用来表示具有一一对应关系的一种结构，此结构中一般只包括两个成员变量 key和 value；key代表键值， value代表与 key对应的信息；通过结构体pair进行定义
template<class T1,class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() :first(T1()) ,second(T2()) {} pair(const T1&a,const T2&b) :first(a) ,second(b) {} };
一般在进行对pair赋值并插入时，使用其另一种形式make_pair
树状结构关联式容器
根据应用场景的不同，STL实现了两种不同结构的管理式容器：树形结构和哈希结构；树形结构的关联式容器主要有四种： set, multiset, map, multimap。这四种容器都是以平衡搜索树作为底层结构来实现的。接下来对这些容器一一介绍
set
介绍
set是按照一定次序存储元素的
在set中，只存放实值value，但在底层实际存放的是键值对<value,value>；插入元素时只需要插入实值value，不需要构造键值对
元素不可以重复，且不允许修改
元素默认按照小于进行比较
底层由二叉搜索树实现
使用
模板参数列表
T：set中存放的元素的类型是T，既是key也是value
Compare:set中元素默认按照小于进行比较
int main() { set<int>myset; myset.insert(5); myset.insert(5); myset.insert(3); myset.insert(4); myset.insert(1); myset.insert(0); myset.insert(0); for (auto e : myset) { cout << e << " "; } cout << endl; auto pos = find(myset.begin(), myset.end(), 3); myset.erase(pos); for (auto e : myset) { cout << e << " "; } return 0; }
通过运行结果可以发现， set会自动对元素进行排序+去重
multiset
介绍
multiset是按照特定顺序存储元素的容器，元素可以重复
其余的与set一致
使用
int main() { multiset<int>myset; myset.insert(5); myset.insert(5); myset.insert(3); myset.insert(4); myset.insert(1); myset.insert(0); myset.insert(0); for (auto e : myset) { cout << e << " "; } cout << endl; auto pos = find(myset.begin(), myset.end(), 3); myset.erase(pos); for (auto e : myset) { cout << e << " "; } return 0; }
通过结果可以发现，相比于set,multiset只是进行简单的排序，并不会进行去重操作
map
介绍
关联式容器，按照 key的比较次序来存储由键值 key和值 value组成的键值对，通过成员类型 value_type,称为 pair
typedef pair<const key,T>value_type;
键值 key用于排序和标识元素；值 value存储与键值关联的内容；两者的类型可能不同
在内部，map中的元素总是按照键值key进行比较排序的，默认是按照小于进行排序的
map中存放的元素是键值对pair<key,value>
支持下标访问，即可以通过键值key访问与之对应的value
使用
模板参数说明
Key：key的类型 T：value的类型 Compare：比较器，通过key进行比较 int main() { map<string, string>dict; dict.insert(make_pair("east", "东")); dict.insert(make_pair("west", "西")); dict.insert(make_pair("south", "南")); dict.insert(make_pair("north", "北")); for (const auto& e : dict) { cout << e.first << " " << e.second << endl; } return 0; }
multimap
介绍
multimap是按照特定顺序存储键值对pair<key,value>的序列式容器，元素可以重复
其余的与map一致
使用
统计球的次数
int main() { string arr[] = { "篮球","羽毛球","乒乓球","羽毛球","乒乓球","羽毛球"， "羽毛球","乒乓球" }; multimap<string, int>coutmap; for (auto& e : arr) { auto it = coutmap.find(e); if (it == coutmap.end()) { coutmap.insert(make_pair(e, 1)); } else { it->second++; } } for (const auto& e : coutmap) { cout << e.first << " " << e.second << endl; } return 0; }
这里还有另一种方式进行统计，需要使用operator[]，使用之前，先介绍其原理，做到知其然知其所以然
下标访问返回值：
(*((this->insert(make_pair(k,mapped_type()))).first)).second
逐步进行分析：
make_pair(k,mapped_type())，根据键值k和实值类型相同的临时对象mapped_type()创建一个元素
insert(make_pair(k,mapped_type()))，将该元素插入到map中去，这里还需要了解到插入操作会返回一个pair,第一个元素是迭代器，指向插入的新元素或者键值重复的旧元素；第二个元素标识着插入的成功与否
pair<iterator,bool> insert (const value_type& val);
(this->insert(make_pair(k,mapped_type()))).first，取得插入返回 pair中的第一个元素，即迭代器，指向插入的元素
(*((this->insert(make_pair(k,mapped_type()))).first)).second，对迭代器进行解引用，获得一个 map元素，由键值 key和实值 value组成的 pair取得其第二个元素，也就是实值
对上面的代码进行修改
int main() { string arr[] = { "篮球","羽毛球","乒乓球","羽毛球","乒乓球","羽毛球" ，"羽毛球","乒乓球" }; map<string, int>coutmap; for (auto& e : arr) { coutmap[e]++; } for (const auto& e : coutmap) { cout << e.first << " " << e.second << endl; } return 0; }
底层容器
前面的set/multiset/map/multimap有个共同特点：底层都是通过二叉搜索树来实现的，二叉搜索树本身也存在着缺陷，如果插入值不够随机，或者经过某些插入或删除操作导致二叉搜索树失去平衡，造成搜寻效率低的情况，因此set/map的底层结构是对二叉搜索树进行了平衡处理的平衡树来实现的
