本文主要是介绍C++ STL系列容器（六）：树形结构的关联式容器（map、set、multimap、multiset），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
引言
1. 关联式容器
我们已经了解过STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列（即每个数据元素都只有一个直接前驱和一个直接后继）的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key,value>结构的键值对，在数据检索时比序列式容器效率更高。
2. 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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){}
};树形结构的关联式容器
根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
一、set
- set是按照一定次序存储元素的容器，默认按照小于来比较。
- set中插入元素时，只需要插入value即可，不需要构造键值对。
- set中的元素不可以重复(因此可以使用set进行去重)。
- set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- set在底层是用二叉搜索树(红黑树)实现的。
1. set的模板参数列表
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type > class set;T: set中存放元素的类型，实际在底层存储<value,value>的键值对。
Compare：set中元素默认按照小于来比较。
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。
2. set常见接口的使用
详情请参照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(int));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;
}
这里用array数组构造（迭代器区间构造）set对象,使用set的迭代器遍历set中的元素，得到升序序列。由此看出，set中的元素默认按照小于来比较且元素不重复。
二、multiset
- multiset是按照一定次序存储元素的容器，默认按照小于来比较。
- multiset中插入元素时，只需要插入value即可，不需要构造键值对。
- multiset中的元素可以重复(与set的区别)。
- multiset中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- multiset在底层是用二叉搜索树(红黑树)实现的。
1. multiset的模板参数列表
template < class T, // multiset::key_type/value_type
class Compare = less<T>, // multiset::key_compare/value_compare
class Alloc = allocator<T> // multiset::allocator_type
> class multiset;multiset与set的参数列表相同。
2. multiset常见接口的使用
multiset常见接口的使用与set相同，详情请参照multiset文档。
#include <set>
int main()
{int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };// 注意：multiset在底层实际存储的是<int, int>的键值对multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));for (auto& e : s)cout << e << " ";cout << endl;return 0;
}
迭代器遍历multiset中的元素，同样得到升序序列。由此看出，multiset中的元素可重复。
三、map
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。
- 在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair（ typedef pair value_type;）。
- 在内部，map中的元素总是按照键值key进行比较排序的。
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
1. map的模板参数列表
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T>> // map::allocator_type
> class map;key： 键值对中key的类型。
T： 键值对中value的类型 Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比 较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)。
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。
2. map常见接口的使用
它的构造函数、迭代器都与之前的容器没有太大区别，详情请参照map文档。
map的容量与元素访问
map的operator[]重载跟之前容器有些不同，它会在内部调用map的insert函数。
mapped_type& operator[](const key_type& k) {return (*((this->insert(make_pair(k, mapped_type()))).first)).second;
}再看一下insert函数的声明。
pair<iterator,bool> insert (const value_type& val);insert函数会返回插入元素的迭代器位置和元素是否存在的bool值构成的pair对象，在operator[]函数中，会先让map对象调用insert函数插入键值k和value的默认值（为value类型的默认构造函数生成的临时对象）所构成的pair对象。
其中(this->insert(make_pair(k, mapped_type()))).first)，就是获取插入后的迭代器位置，之后再进行解引用，得到对应pair对象，最后.second获得key所对应的value值。
当key存在时，插入失败。获取key所在pair对象的迭代器，解引用后为key所对应的value。
当key不存在时，插入成功。获取新插入pair对象的迭代器，解引用后为默认value。
所以，map的operator[]能够实现查找，修改，插入三个功能。
修改操作
接口使用
void TestMap()
{map<string, string> m;// 向map中插入元素的方式：// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对m.insert(pair<string, string>("peach", "桃子"));// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对m.insert(make_pair("banan", "香蕉"));// 借用operator[]向map中插入元素/*operator[]的原理是：用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回*/// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果m["apple"] = "苹果";// key不存在时抛异常//m.at("waterme") = "水蜜桃";cout << m.size() << endl;// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列for (auto& e : m)cout << e.first << "--->" << e.second << endl;cout << endl;// map中的键值对key一定是唯一的，如果key存在将插入失败auto ret = m.insert(make_pair("peach", "桃色"));if (ret.second)cout << "<peach, 桃色>不在map中, 已经插入" << endl;elsecout << "键值为peach的元素已经存在：" << ret.first->first << "--->"<< ret.first->second << " 插入失败" << endl;// 删除key为"apple"的元素m.erase("apple");if (1 == m.count("apple"))cout << "apple还在" << endl;elsecout << "apple被吃了" << endl;
}
四、multimap
- multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的。
- 在map中，键值key通常用于排序,同一个key可能会标识多个元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair（ typedef pair value_type;）。
- 在内部，map中的元素总是按照键值key进行比较排序的。
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
1. map的模板参数列表
template < class Key, // multimap::key_type
class T, // multimap::mapped_type
class Compare = less<Key>, // multimap::key_compare
class Alloc = allocator<pair<const Key,T> > // multimap::allocator_type
> class multimap;multiset与set的参数列表相同。
2. multimap常见接口的使用
multimap常见接口的使用与map相同，详情请参照multimap文档。
注意：
1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较。
3. multimap中没有重载operator[]操作，因为multimap中可能存在多个相同的键，因此无法确定要返回哪个值。
map、set的相关OJ
1. 两个数组的交集
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 先去重set<int> s1;for (auto e : nums1) {s1.insert(e);}set<int> s2;for (auto e : nums2) {s2.insert(e);}// set排过序，依次比较，小的一定不是交集，相等的是交集auto it1 = s1.begin();auto it2 = s2.begin();vector<int> ret;while (it1 != s1.end() && it2 != s2.end()) {if (*it1 < *it2) {it1++;} else if (*it2 < *it1) {it2++;} else {ret.push_back(*it1);it1++;it2++;}}return ret;}
};利用set去重，排序的特性将两个数组分别放到s1、s2对象中，然后同时遍历s1、s2依次比较。因为set默认是升序，让元素小的对象迭代器++。当元素相等时，迭代器都++，并将元素插入返回数组。直到其中一个set对象遍历完毕。
2. 前k个高频单词
class Solution {
public:class compare{public:bool operator()(const pair<string, int>& a, const pair<string, int>& b){return a.second==b.second?a.first>b.first:a.second<b.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> m;for(auto &e:words){m[e]++;}compare com;priority_queue<pair<std::string,int>,vector<pair<std::string,int>>> queue(m.begin(),m.end());vector<string> retv;while(k--){retv.push_back(queue.top().first);queue.pop();}return retv;}
};先用map<string,int>创建对象m，遍历words数组，让m通过m[e]++插入字符串,并统计单词出现频率。然后用m的迭代器区间初始化优先对列que,并将自定义的传入排序规则的仿函数。按照单词出现频率和字母顺序构建堆（如果父亲的出现次数<孩子的出现次数，则交换；而在父亲的出现次数=孩子的出现次数时，如果父亲的单词>孩子的单词，交换）。最后将que中顶部的单词插入返回数组。
3. 单词识别
用优先队列和仿函数+map,与上题类似
class compare {
public:bool operator()(const pair<string, int>& a, const pair<string, int>& b) {return a.second == b.second ? a.first > b.first : a.second <b.second;b.second;}
};int main() {string str;getline(cin, str);map<string, int> wordmap;int pos = 0;for (size_t i = 0; i < str.size(); i++) {if (str[i] == ' ' || str[i] == '.') {string temp = str.substr(pos, i - pos);pos = i + 1;if (temp[0] >= 'A' && temp[0] <= 'Z') {temp[0] += 32;}wordmap[temp]++;}}priority_queue <pair<std::string, int>, vector<pair<std::string, int>>, compare> que(wordmap.begin(), wordmap.end());int k = wordmap.size();while (k--) {cout << que.top().first << ":" << que.top().second << endl;que.pop();}return 0;
}用vector和sort排序+map
bool cmp(pair<string,int> w1,pair<string,int> w2)
{return w1.second>w2.second;
}int main() {string str;getline(cin, str);map<string, int> wordmap;int pos = 0;for (size_t i = 0; i < str.size(); i++) {if (str[i] == ' ' || str[i] == '.') {string temp = str.substr(pos, i - pos);pos = i + 1;if (temp[0] >= 'A' && temp[0] <= 'Z') {temp[0] += 32;}wordmap[temp]++;}}vector<pair<string, int>> v(wordmap.begin(), wordmap.end());sort(v.begin(), v.end(), cmp);auto it = v.begin();while (it != v.end()) {cout << it->first << ":" << it->second<<endl;it++;}return 0;
}这篇关于C++ STL系列容器（六）：树形结构的关联式容器（map、set、multimap、multiset）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
