@toc

一：关联式容器

• 容器分类：

序列式容器：初阶阶段中学习过 STL 中的部分容器，如：vector、list、deque 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身

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

二：键值对

• 概念：

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表键值，value 表示与 key 对应的信息

• SGI-STL 中关于键值对的定义：

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){}};

三：set

1. set 的介绍

1. set 是按照一定次序存储元素的容器

2. 在 set 中，元素的 value 也标识它(value 就是 key，类型为 T)，并且每个 value 必须是唯一的。set 中的元素不能在容器中修改(元素总是 const)，但是可以从容器中插入或删除它们。

3. 在内部，set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。

5. set 在底层是用二叉搜索树(红黑树)实现的

2. set 的使用

set 的模板参数列表：

T: set 中存放元素的类型，实际在底层存储<value, value>的键值对。Compare：set 中元素默认按照小于来比较 Alloc：set 中元素空间的管理方式，使用 STL 提供的空间配置器管理

3. set 的使用举例

#include <set>void TestSet(){// 用数组array中的元素构造setint array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };set<int> s(array, array+sizeof(array)/sizeof(array));cout << s.size() << endl;// 正向打印set中的元素，从打印结果中可以看出：set可去重for (auto& e : s)cout << e << " ";cout << endl;// 使用迭代器逆向打印set中的元素for (auto it = s.rbegin(); it != s.rend(); ++it)cout << *it << " ";cout << endl;// set中值为3的元素出现了几次cout << s.count(3) << endl;}

• C++中的 multiset

1. multiset 容器与 set 容器实现和接口基本一致，唯一区别就是，multiset 允许键值冗余，即 multiset 容器当中存储的元素是可以重复的

2. 注意：对于 find 来说 multiset 返回底层搜索树中序的第一个键值为 key 的元素的迭代器

四： map

一：map 的介绍

1. map 是关联容器，它按照特定的次序(按照 key 来比较)存储由键值 key 和值 value 组合而成的元素。

2. 在 map 中，键值 key 通常用于排序和惟一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair:typedef pair value_type;

3. 在内部，map 中的元素总是按照键值 key 进行比较排序的。

4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代(即对 map 中的元素进行迭代时，可以得到一个有序的序列)。

5. map 支持下标访问符，即在[]中放入 key，就可以找到与 key 对应的 value。

6. map 通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

二：map 的使用

• map 的模板参数说明:

• 

key: 键值对中 key 的类型 T： 键值对中 value 的类型 Compare: 比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器注意：在使用 map 时，需要包含头文件。

三：总结

1. map 中的的元素是键值对

2. map 中的 key 是唯一的，并且不能修改

3. 默认按照小于的方式对 key 进行比较

4. map 中的元素如果用迭代器去遍历，可以得到一个有序的序列

5. map 的底层为平衡搜索树(红黑树)，查找效率比较高

6. 支持[]操作符，operator[]中实际进行插入查找。

四：multimap

multimap 容器与 map 容器的底层实现以及成员函数的接口都是基本一致，区别是 multimap 允许键值冗余，即 multimap 容器当中存储的元素是可以重复的

• 注意:

对于 find 来说 multimap 返回底层搜索树中序的第一个键值为 key 的元素的迭代器

由于 multimap 容器允许键值冗余，调用[运算符重载函数时，应该返回键值为 key 的哪一个元素的 value 的引用存在歧义，因此在 multimap 容器当中没有实现[ ]运算符重载函数

五：有关 oj 题

• 前 K 个高频单词：（题目链接）

• 

• 代码：

class Solution {public:    vector<string> topKFrequent(vector<string>& words, int k) {          //sort不稳定,堆排序也一样          //用两个map来排序          map<string,int> countMap;          for(auto& e: words)          {              countMap[e]++;          }
          multimap<int,string,greater<int>> Map; //必须要用multimap，不然出现次数相同的string会被抵消掉          for(auto& e:countMap )          {              Map.insert(make_pair(e.second,e.first));          }          auto it = Map.begin();          vector<string> v;          while(k--)          {               v.push_back(it->second);               it++;          }          return v;    }};

• 思路：

1. 用一个 map 按字典序排字符串，并且记录出现次数

2. 再用一个 multimap 来排序出现次数，并且记录字符串

3. 利用迭代器来输出前 k 大的数

• 注意：

4. 不能使用 sort 和堆来排序，因为不稳定

5. 注意第二个 map 必须要用 multimap，不然出现次数相同的 string 会被抵消掉

6. multimap<int,string,greater<int>> Map; ，注意是 greater<int>

总结：

1. 当你只需要查找信息是否存在时，用 set。

2. 当你需要利用当前信息去查看与之关联的信息时，用 map.

• 博主同款刷题网站

很多小伙伴为了刷题发愁今天为大家推荐一款刷题神奇哦：刷题面试神器牛客各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题 应有尽有，赶快来装备自己吧！助你面试稳操胜券，solo 全场面试官