---

前言

---

一、set容器

序列式容器：
在初阶阶段，我们已经接触过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)
{}
};

我们通常将pair结构中的first设为key，而second设为value。

树形结构的关联式容器：
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面依次介绍每一个容器。

1、set容器介绍

1. set是按照一定次序存储元素的容器。
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const，因为修改元素的value可能会破坏二叉搜索树)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

需要注意的是：
6. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
7. set中插入元素时，只需要插入value即可，不需要构造键值对。
8. set中的元素不可以重复(因此可以使用set进行去重)。
9. 使用set的迭代器遍历set中的元素，可以得到有序序列
10. set中的元素默认按照小于来比较
11. set中查找某个元素，时间复杂度为：$lo{g}_{2}n$
12. set中的元素不允许修改(为什么?因为会破坏set底层的二叉搜索树结构)
13. set中的底层使用二叉搜索树(红黑树)来实现。
14.

2、set的使用

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

2.1 set的构造函数和迭代器

下面的代码中我们插入了多次1、2、3元素，但是在使用set的迭代器遍历s1中的元素时，发现每个元素只有一个，这是因为set底层为一个平衡二叉搜索树，所以没有冗余的数据。并且我们看到使用迭代器遍历set中的元素是按升序打印的，即set的迭代器是中序遍历的二叉搜索树。

set支持迭代器，所以也就支持范围for，并且set的数据不能通过迭代器和范围for修改，因为修改数据之后可能就不满足二叉搜索树了。

2.2 set的容量

2.3 set修改操作

insert：
我们看到set的insert函数中第一个重载函数会返回一个pair<itreator,bool> 类型的对象，在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>。我们看到下面的测试中当再次插入2元素时返回的p1对象中p1.second为false，表示插入失败，p1.first迭代器指向二叉搜索树中值为2的结点。当我们插入5元素时，返回的p1对象中p1.second为true，表示插入成功，p1.first迭代器指向新插入的结点。

int main()
{set<int> s1;s1.insert(3);s1.insert(1);s1.insert(2);s1.insert(4);//pair<iterator,bool> insert (const value_type& val);pair<set<int>::iterator, bool> p1 = s1.insert(2);cout << *(p1.first) << endl;cout << p1.second << endl;p1 = s1.insert(5);cout << *(p1.first) << endl;cout << p1.second << endl;//iterator insert (iterator position, const value_type& val);//返回的迭代器指向新插入的结点set<int>::iterator it1 = s1.insert(s1.begin(), 10);cout << *it1 << endl;for (auto e : s1){cout << e << " ";}cout << endl;//template <class InputIterator> void insert(InputIterator first, InputIterator last);int arr[] = { 8,7,9,12 };s1.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));for (auto e : s1){cout << e << " ";}cout << endl;return 0;
}

erase：

int main()
{set<int> s1;s1.insert(3);s1.insert(1);s1.insert(2);s1.insert(4);for (auto e : s1){cout << e << " ";}cout << endl;//void erase (iterator position);s1.erase(s1.begin());for (auto e : s1){cout << e << " ";}cout << endl;//size_type erase (const value_type& val);size_t n1 = s1.erase(2);cout << n1 << endl;size_t n2 = s1.erase(5);cout << n2 << endl;for (auto e : s1){cout << e << " ";}cout << endl;//void erase (iterator first, iterator last);s1.erase(s1.begin(), s1.end());for (auto e : s1){cout << e << " ";}cout << endl;return 0;
}

swap、clear、find、count：

int main()
{set<int> s1;s1.insert(3);s1.insert(1);s1.insert(2);s1.insert(4);cout << "交换前s1：";for (auto e : s1){cout << e << " ";}cout << endl;set<int> s2;int arr[] = { 10,20,30,40,50 };s2.insert(arr, arr + sizeof(arr) / sizeof(arr[0]));cout << "交换前s2：";for (auto e : s2){cout << e << " ";}cout << endl;//void swap (set& x);s1.swap(s2);cout << "交换后s1：";for (auto e : s1){cout << e << " ";}cout << endl;cout << "交换后s2：";for (auto e : s2){cout << e << " ";}cout << endl;//iterator find (const value_type& val) const;set<int>::iterator it1 = s1.find(20);cout << *it1 << endl;//size_type count (const value_type& val) const;size_t n = s1.count(30);cout << n << endl;//void clear();s1.clear();for (auto e : s1){cout << e << " ";}return 0;
}

3、multiset容器

3.1 multiset容器介绍

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
5. multiset底层结构为二叉搜索树(红黑树)。

注意：
6. multiset中再底层中存储的是<value, value>的键值对。
7. mtltiset的插入接口中只需要插入即可。
8. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的。
9. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列。
10. multiset中的元素不能修改
11. 在multiset中找某个元素，时间复杂度为$O(lo{g}_{2}N)$
12. multiset的作用：可以对元素进行排序。
13.

3.2 multiset容器使用

multiset容器与set容器的区别就是multiset里面的元素可以重复。
我们下面演示一下multiset与set的不同之处。
可以看到当向multiset中插入相同的元素时，都会成功插入进去，这就是multiset容器和set容器最本质的区别。

那么multiset容器中可以插入多个重复的元素，当我们使用find函数查找一个元素时，会返回哪一个呢？
其实返回的是中序遍历multiset这个二叉搜索树时第一个出现的元素。

multiset容器中的count函数可以返回二叉搜索树中元素的个数。

multiset容器中调用erase函数时会将二叉搜索树中所有的指定元素都删除，并且返回删除元素的个数。

上面我们演示了multiset容器和set容器中一些接口的不同使用方法，而multiset中其他的接口的使用和set容器的接口使用类似，我们只需按照文档中的使用即可。

二、map容器

1、map容器介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
   
   key: 键值对中key的类型
   T： 键值对中value的类型
   Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)。
   Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

2、map容器使用

在map容器中存储由键值key和值value组合而成的元素，而STL库中提供了一个pair结构体模板，这个结构体中可以存储两个类型的元素，所有我们通过在map中存pair结构体对象，然后在pair中存key和value构成的键值对。

2.1 map的构造函数与迭代器

下面我们使用迭代器访问了map容器中的元素。

但是我们发现向map对象中插入元素时，还需要显示写pair模板的类型，这样会很麻烦。所以一般我们都使用make_pair来向map容器中插入元素。make_pair模板会根据类型生成一个函数，这个函数会返回一个匿名对象，这样就不用自己来写类型了。

swap、clear、find、count函数

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;map<string, string> subject;subject.insert(make_pair("math", "数学"));subject.insert(make_pair("english", "英语"));subject.insert(make_pair("physics", "物理"));for (auto e : subject){cout << e.first << " : " << e.second << endl;}cout << endl;dict.swap(subject);for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;for (auto e : subject){cout << e.first << " : " << e.second << endl;}cout << endl;subject.clear();for (auto e : subject){cout << e.first << " : " << e.second << endl;}cout << endl;map<string, string>::iterator it1 = dict.find("math");cout << (*it1).first << " : " << (*it1).second << endl;size_t n = dict.count("english");cout << n << endl;return 0;
}

2.2 map中元素的修改

insert：
因为key-value模型的二叉搜索树中按key的值来进行各种判断和维护二叉搜索树。所以在map容器中的元素的value的值可以重复，但是key的值不能重复。

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));//pair<iterator,bool> insert (const value_type& val);pair<map<string, string>::iterator, bool> p1 = dict.insert(make_pair("count", "计数"));cout << (*p1.first).first << " : " << (*p1.first).second << endl;cout << p1.second << endl;//在map中以key的值来判断唯一性，所以key不可以相同，但是value可以相同p1 = dict.insert(make_pair("count2", "计数"));cout << (*p1.first).first << " : " << (*p1.first).second << endl;cout << p1.second << endl;//iterator insert (iterator position, const value_type& val); map<string, string>::iterator it1 = dict.insert(dict.begin(), make_pair("math", "数学"));cout << it1->first << " : " << it1->second << endl;//template <class InputIterator> void insert(InputIterator first, InputIterator last);pair<string, string> parr[] = { make_pair("english","英语"), make_pair("math", "数学"), make_pair("physics","物理")};map<string, string> sub(parr, parr + sizeof(parr) / sizeof(parr[0]));for (auto e : sub){cout << e.first << " : " << e.second << endl;}return 0;
}

erase：

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;//void erase (iterator position);dict.erase(dict.begin());for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;//size_type erase (const key_type& k);//根据map中元素的key值来查找元素并进行删除。cout << dict.erase("string") << endl;for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;// void erase (iterator first, iterator last);dict.erase(dict.begin(), dict.end());for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;return 0;
}

2.3 map的容量与元素访问

map的容量：


map的元素访问：
在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。


下面为operator[]实现的分析。

通过上面的分析我们知道了operator[]的括号里面填的是map元素中的key的值，然后operator[]可以完成插入、插入+修改、修改、查找等操作。

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;dict["left"];    //插入 ("left" -- "") ，value为string类的默认值，即空字符串dict["right"] = "右边";     //插入+修改dict["string"] = "(字符串)";    //修改cout << dict["string"] << endl;    //查找for (auto e : dict){cout << e.first << " : " << e.second << endl;}cout << endl;return 0;
}

可以看到当key值不存在时，at函数会直接抛异常。

2.4 map应用

我们使用map来写一个水果个数统计的小程序。

我们还可以使用operator[]重载函数来将上面的代码进行简化。因为我们前面分析了map类中的operator[]重载函数在检测到当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，然后使用operator[]重载函数查找到key存在时，就会返回与key对应的value的引用。

2.5 总结

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找。

3、multimap容器

3.1 multimap容器介绍

1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。
2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;
3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
5. multimap在底层用二叉搜索树(红黑树)来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

3.2 multimap容器使用

1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较。
3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。这是因为multimap容器中key值有重复，所以不知道要修改的是哪一个key对应的value，所以无法提供operator[]。
4. 使用时与map包含的头文件相同。

我们看到在multimap容器中可以将key值相同的元素插入，即multimap容器支持键值冗余。

multimap容器中的find函数返回的是中序遍历时第一个访问到的结点，当没有插值的key时，返回end()迭代器。并且当被const修饰的multimap对象调用find时，返回被const修饰的迭代器。

当调用erase的size_type erase (const key_type& k);重载函数时，会返回成功删除当前容器中key为k的键值对的个数。

count函数返回容器中key值为k的键值对的个数。

我们只演示了multimap和map的一些接口的不同使用，multimap容器的接口的使用和map接口的使用类似，所以我们不再过多的演示。

4、练习

4.1 随机链表的复制

题目链接

我们把前面学习c语言时写的随机链表的复制使用map来做一遍。我们以题目中给的链表的结点为key值，然后让新生成的拷贝结点为value值，将新链表和旧链表建立映射关系。这样我们在改变新链表的random值时就可以以旧链表的结点为key值来查找了。

class Solution {
public:Node* copyRandomList(Node* head) {map<Node*, Node*> copyNodeMap;Node* cur = head;Node* copyhead, *copytail;copyhead = copytail = nullptr;while(cur){//创建新结点Node* copy = new Node(cur->val);//以cur为key，copy为value建立mapcopyNodeMap[cur] = copy;//拷贝的链表为空，将头指针和尾指针都指向新结点if(copytail == nullptr){copyhead = copy;copytail = copy;}else{//在拷贝的链表的尾部插入新结点copytail->next = copy;copytail=copytail->next;}cur = cur->next;}cur = head;Node* copy = copyhead;while(cur){if(cur->random == nullptr){copy->random = nullptr;}else{copy->random = copyNodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

4.2 前K个高频单词

题目链接

第一种方法：
我们可以使用map来记录字符串和出现的次数，然后我们再使用一个vector<pair<string, int>>容器将map容器中的数据拷贝过来，然后使用sort函数将vector容器中的元素进行排序。但是因为我们需要靠pair对象中的second的值来排序，而pair类模板中自带的比较是先比较first，如果first相当再比较second，所以这和我们排序的依据不同。我们需要自己实现Compare排序函数。然后我们排序完之后，再创建一个vector< string > ret对象，将前面排序好的vector容器的前k个元素拷贝到ret对象中，然后将ret对象返回。

但是我们发现出现了错误，这是因为sort函数底层使用的快速排序，而快速排序为不稳定排序，所以当有两个字符串出现的次数相同时，使用快速排序可能会打乱它们的相对顺序。但是题目中明确规定了要按字母顺序来打印。所以我们需要使用一个稳定排序算法。因为map底层为二叉搜索树，所以当map中的数据拷贝到vector<pair<string,int>>容器中时，字符串已经按照字母顺序排好序了，但是因为sort函数为不稳定排序算法，所以排过序后又打乱了字符串的位置，这样字符串就不按照字母顺序了。

在c++提供的算法中，有一个稳定排序的算法stable_sort，下面我们使用stable_sort函数来排序。然后我们就可以通过测试了。

class Solution {
public:struct Compare{bool operator()(const pair<string,int>& kv1, const pair<string,int>& kv2){return kv1.second > kv2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e:words){countMap[e]++;}vector<pair<string,int>> v(countMap.begin(),countMap.end());//因为此时为sort函数中，所以要填写Compare匿名对象的()重载函数//使用稳定的排序函数stable_sort(v.begin(),v.end(),Compare());vector<string> ret;for(size_t i = 0; i < k; ++i){ret.push_back(v[i].first);}return ret;}
};

第二种方法：
如果我们不适用稳定排序算法也可以，只不过我们需要修改仿函数Compare，即在仿函数中比较时，当字符串的次数相等时，比较字符串的大小，让字符串小的放在前面。这样vector容器中的字符串顺序就为我们想要的顺序了。

class Solution {
public:struct Compare{bool operator()(const pair<string,int>& kv1, const pair<string,int>& kv2) const{return kv1.second > kv2.second || (kv1.second==kv2.second && kv1.first<kv2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e:words){countMap[e]++;}//vector<pair<string,int>> v(countMap.begin(),countMap.end());//将sort中的比较大小的函数中的比较规则改变。sort(v.begin(),v.end(),Compare());vector<string> ret;for(int i = 0; i<k; ++i){ret.push_back(v[i].first);}return ret;}
};

第三种方法：
当我们修改了仿函数Compare中的比较方法后，此时我们可以将map容器中统计的字符串和出现的次数放到set容器中，然后set容器的比较方法我们使用Compare来进行比较，这样当字符串的次数相等时，就比较字符串的大小。set容器中就先按字符串次数，再按字符串大小来构建二叉搜索树了。

class Solution {
public:struct Compare{bool operator()(const pair<string,int>& kv1, const pair<string,int>& kv2) const{return kv1.second > kv2.second || (kv1.second==kv2.second && kv1.first<kv2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e:words){countMap[e]++;}set<pair<string,int>,Compare> s(countMap.begin(),countMap.end());vector<string> ret;auto it = s.begin();while(k--){ret.push_back(it->first);++it;}return ret;}
};

4.3 两个数组的交集

题目链接

这种求交集和求差集的题，我们可以先进行排序，再进行去重，然后再使用下面的双指针思想求交集或差集。

第一种方法：
我们根据c++库中提供的sort函数先将nums1和nums2里面的元素进行排序，然后使用unique函数将nums1和nums2里面的元素进行去重，需要注意的是unique函数并不会将容器里面的重复元素删除，也不会改变容器的有效数据长度，只会返回一个迭代器，这个迭代器指向不重复元素的后一个元素。所以我们想要得到不重复的元素就需要以这个迭代器结尾。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//排序+去重//排序sort(nums1.begin(),nums1.end());sort(nums2.begin(),nums2.end());//去重auto end1 = unique(nums1.begin(),nums1.end());auto end2 = unique(nums2.begin(),nums2.end());vector<int> vv;auto it1 = nums1.begin();auto it2 = nums2.begin();while(it1!=end1 && it2 != end2){if(*it1 == *it2){vv.push_back(*it1);it1++;it2++;}else if(*it1<*it2){it1++;}else{it2++;}}return vv;}
};

第二种方法：
我们学习了set和map容器后，知道了set容器使用迭代器访问元素时就是按升序的顺序来访问的，并且set容器中不允许元素冗余，所以我们可以将nums1和nums2中的数据放到set容器中。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1;set<int> s2;for(auto e:nums1){s1.insert(e);}for(auto e:nums2){s2.insert(e);}vector<int> vv;auto it1 = s1.begin();auto it2 = s2.begin();while(it1!=s1.end() && it2!=s2.end()){if(*it1 == *it2){vv.push_back(*it1);it1++;it2++;}else if(*it1<*it2){it1++;}else{it2++;}}return vv;}
};