杭州软件测试培训班_黑马培训机构可靠吗_谷歌浏览器网页版入口_网店培训

前言

一、序列式容器和关联式容器

二、set系列的使用

三、multiset和set的差异

四、set两道练习题

五、map系列的使用

六、multimap和map的差异

七、map两道练习题

总结

前言

本文主要讲述STL容器中的map和set的使用。

一、序列式容器和关联式容器

1.序列式容器：

前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，比如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

2.关联式容器：

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节讲解的map和set底层是红黑树，红黑树是⼀颗平衡二叉搜索树。set是key搜索场景的结构， map是key/value搜索场景的结构。
正因为底层是平衡二叉搜索树，所以 set 和 map 中元素与元素之间存在大小关系，我们不能随意交换不同位置的元素，这可能会导致平衡二叉搜索树结构被改变。这就是关联式容器的特点。
所以对于关联式容器的操作，通常只有增删查，而没有改。

二、set系列的使用

首先，在<set>头文件中是有两个容器的：

set不支持数据冗余（重复元素）
multiset支持数据冗余

我们先介绍 set

1.set类的介绍

set的声明如上，T 就是set底层关键字的类型
set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数 Compare
set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数 Alloc
一般情况下，我们都不需要传后两个模版参数。
set底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。

2.set的构造和迭代器

set的构造我们关注几个即可：

（1）无参默认构造：
（2）迭代区间构造：
（3）拷贝构造：

（4）initializer_list列表构造：

以上接口都是 STL 容器常用构造方式，前面我们已经学了string、vector等容器，因此这里不再演示了。

关于 set 的迭代器：

是一个双向迭代器：支持++、--。
迭代器接口和其他容器一致：

支持迭代器就支持范围for遍历：

#include <iostream>
#include <set>
using namespace std;int main()
{//initializer_list列表构造set<int> s({ 6,9,3,2,8,5,1,4,7 });for (auto e : s)//范围for{cout << e << " ";}cout << endl;return 0;
}

运行结果：

底层是一个二叉搜索平衡树，所以按中序输出就有排序效果。

3.set的增删查

（1）insert

inset 的接口我们关注以下几个：

pair insert (const value_type& val)：单个数据插入，返回值为一个 pair 类型，如果插入成功，pair 的第一个值为插入元素的迭代器，第二个值为true，反之第一个元素是 set 中已有的相等元素的迭代器，第二个值为false。
void insert (initializer_list il)：列表插入，已经在容器中存在的值不会插入。
template void insert (InputIterator first, InputIterator last)：迭代器区间插入，已经在容器中存在的值不会插入。

演示：

#include <iostream>
#include <vector>
#include <set>
using namespace std;int main()
{set<int> s;s.insert(6);s.insert({ 80,56,44,96,53,12,7,18 });vector<int> v({ 7,4,1,5,2,8 });s.insert(v.begin(), v.end());for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

运行结果：

（2）find

find 关注一个接口就行

演示：

#include <iostream>
#include <set>
using namespace std;int main()
{set<int> s({ 7,4,5,3,6,9,8,1,2 });auto it = s.find(6);cout << *it << endl;return 0;
}

运行结果：

（3）count

count 就只有一个接口，并且对于 set 来说，返回值只有 1 或者 0，表示该值存不存在，因为 set 不支持数据冗余，如果是 multiset 返回值就是 val 的个数。

演示：

#include <iostream>
#include <set>
using namespace std;int main()
{set<int> s({ 7,4,5,3,6,9,8,1,2 });cout << s.count(-1) << endl;cout << s.count(1) << endl;return 0;
}

运行结果：

该接口适合快速判断某个值存不存在

（4）erase

erase 我们关注3个接口即可：

（1）删除一个迭代器位置的值，成功则返回下一个元素的迭代器，失败则返回 end()
（2）删除 val ， val 不存在返回 0 ，存在返回 1
（3）删除一段迭代器区间的值，返回值同（1）

注意：迭代区间只能是 set 自己的。

演示：

#include <iostream>
#include <set>
#include <vector>
using namespace std;int main()
{set<int> s({ 7,4,5,3,6,9,8,1,2 });for (auto e : s)//打印set{cout << e << " ";}cout << endl;vector<int> v({ 1,2,3,4,100,7,8,9 });//删除for (auto e : v){if (s.erase(e) == 0)break;}//打印setfor (auto e : s){cout << e << " ";}cout << endl;//删除s.erase(s.begin(), s.end());//打印setfor (auto e : s){cout << e << " ";}cout << endl;return 0;
}

运行结果：

（5）lower_bound、upper_bound

lower_bound：返回大于等于 val 位置的迭代器，没有则返回 end()。
upper_bound：返回大于 val 位置的迭代器，没有则返回 end()。
注意这两个的区别就是一个大于等于，一个纯大于

演示：

#include <iostream>
#include <set>
using namespace std;int main()
{set<int> s({1,2,3,4,5,6,7,8,9});auto it1 = s.lower_bound(6);//大于等于cout << *it1 << endl;auto it2 = s.upper_bound(6);//大于cout << *it2 << endl;return 0;
}

运行结果：

（6）其他

像其他容器也常见的接口就不一一介绍了：

：判空
：元素个数
：交换两个set
：清除数据
等....

三、multiset和set的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么 insert/find/count/erase都围绕着支持值冗余有所差异。

（1）multise不去重

#include <iostream>
#include <set>
using namespace std;int main()
{set<int> s1({ 7,7,4,4,1,1,2,2,5,5,8,8 });multiset<int> s2({ 7,7,4,4,1,1,2,2,5,5,8,8 });//打印for (auto e : s1){cout << e << " ";}cout << endl;for (auto e : s2){cout << e << " ";}cout << endl;return 0;
}

运行结果：

（2）对于find，查找x可能会存在多个，multiset返回的是中序的第一个

#include <iostream>
#include <set>
using namespace std;int main()
{multiset<int> s({ 2,2,3,4,1,6,6,6,5,9 });//查找auto it = s.find(6);while (it != s.end() && *it == 6){cout << *it << " ";++it;}cout << endl;return 0;
}

（3）对于count，相比set来说，multiset会返回x的个数

#include <iostream>
#include <set>
using namespace std;int main()
{multiset<int> s({ 8,8,8,8,8,8,8 });cout << s.count(8) << endl;return 0;
}

运行结果：

（4）对于erase，multiset会删掉所有等于x的值

#include <iostream>
#include <set>
using namespace std;int main()
{multiset<int> s({ 6,6,6,8,8,8,8,8,8,8 });s.erase(8);//删除所有的8for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

运行结果：

四、set两道练习题

1.两个数组的交集

链接：349. 两个数组的交集 - 力扣（LeetCode）

题解：

这题我们可以有效利用 set 的去重和排序特性。
首先将两个数组丢到两个set容器中，因为题目要求交集，所以重复元素用不上。
然后我们使用迭代器遍历两个set，因为set迭代器走的是中序遍历，所以迭代器是从小往大遍历的，因此我们可以通过遍历两个set比较元素，谁小谁往后走一步，遇到相同值则存入返回值中即可。

代码：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;//利用set去重set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());auto it1=s1.begin();auto it2=s2.begin();while(it1!=s1.end() && it2!=s2.end()){//谁小谁往后走一步if(*it1 < *it2){++it1;}else if(*it1 > *it2){++it2;}else//相等则保存{ret.push_back(*it1);++it1;++it2;}}return ret;}
};

2.环形链表||

链接：142. 环形链表 II - 力扣（LeetCode）

题解：

这题有快慢指针解法，但是如果你使用set进行解决的话，那将是降维打击。
这题我们就利用set的去重功能，注意set是存储每个节点的指针，所以只是数值相同的两个节点是不会去重的。
因为环形指针它会绕到重复地址的节点，所以我们只需要根据set的count接口，判断该节点是否存在过，有点类似哈希，如果存在说明就循环了，此时返回该节点即可。不是的话就将该节点存入set。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur=head;while(cur){if(s.count(cur)){return cur;}else{s.insert(cur);}cur = cur->next;}return nullptr;}
};

五、map系列的使用

首先，在<map>头文件中也是有两个容器的：

因为 map 是 key:value 的结构，所以这两者的区别就是map不支持key冗余，multimap支持。

1.map类的介绍

map的声明如下，Key就是map底层关键字的类型
T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，
map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。
map底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
注意：map存储的是键值对，也就是 key:value ，C++中一般使用pair类型来表示这种键值对。

pair类型介绍

map底层的红黑树节点中的数据，使用 pair<Key,T> 存储键值对数据。

pair底层：没有详细实现

typedef pair<const Key, T> value_type;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){}template<class U, class V> pair (const pair<U,V>& pr): first(pr.first), second(pr.second){}
};template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

我们只需要知道，pair中 first 是Key的值，second 是value的值

2.map的构造和迭代器

map的构造我们关注以下几个接口即可：

这些也都是常见的构造了，我长话短说，第一个是无参构造，第二个是迭代器区间构造，第三个是拷贝构造，第四个是列表构造。

关于迭代器：

map的迭代器是一个双向迭代器
所以map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，因为修改关键字数据，就破坏了底层搜索树的结构。

范围for：

#include <iostream>
#include <map>
using namespace std;int main()
{//因为节点是pair类型，pair也需要使用{}进行构造map<int, int> m({ {1,1},{2,1 },{3,1} });//initializer_list构造//遍历，需要分别打印key和valuefor (auto& e : m){cout << e.first << ":" << e.second << endl;}return 0;
}

运行结果：

3.map的增删查

（1）insert

:单个数据插入，如果已经 key 存在则插入失败 ,key 存在相等 value 不相等也会插入失败，插入失败返回值中的bool为false，iterator为已存在相等节点的迭代器，反之插入成功bool为true，迭代器为插入节点的迭代器
：列表插入，已经在容器中存在的key值不会插入
：迭代器区间插入，已经在容器中存在的值不会插入

演示：

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, int> m;m.insert({ "苹果",1 });m.insert({ {"香蕉",1},{"西瓜",1},{"橘子",1},{"苹果",2} });for (auto& e : m){cout << e.first << ":" << e.second << endl;}return 0;
}

运行结果：

（2）find

查找 k ，返回 k 所在的迭代器，没有找到返回 end()

演示：

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, int> m({ { "苹果",1 }, {"香蕉",1},{"西瓜",1},{"橘子",1} });auto e = m.find("苹果");cout << e->first << ":" << e->second << endl;return 0;
}

运行结果：

（3）count

查找 k ，返回 k 的个数
同set一样，map只有1和0，multimap返回的是key个数

演示：

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, int> m({ { "苹果",3 }, {"香蕉",2},{"西瓜",1},{"橘子",1} });cout << m.count("苹果") << endl;//返回的是key的个数return 0;
}

运行结果：

（4）erase

：删除⼀个迭代器位置的值，成功返回删除节点的下一个节点迭代器，否则返回end()
：删除 k ， k 存在返回 0 ，存在返回 1
：删除⼀段迭代器区间的值，返回值同第一个

代码：

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, int> m({ { "苹果",3 }, {"香蕉",2},{"西瓜",1},{"橘子",1} });for (auto& e : m){cout << e.first << ":" << e.second << endl;}cout << endl;//erase可以配合find使用auto pos = m.find("香蕉");m.erase(pos);for (auto& e : m){cout << e.first << ":" << e.second << endl;}cout << endl;//erase直接删除m.erase("苹果");for (auto& e : m){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

运行结果：

（5）lower_bound、upper_bound

：返回大于等于 k 位置的迭代器
：返回大于 k 位置的迭代器
和set一样，就是有没有等于的区别

演示：

#include <iostream>
#include <map>
using namespace std;int main()
{map<int, int> m({ {1,1},{2,1},{3,1} });auto it1 = m.lower_bound(2);auto it2 = m.upper_bound(2);cout << it1->first<<":"<<it1->second << endl;cout << it2->first << ":" << it2->second << endl;return 0;
}

运行结果：

（6）其他

剩余一些也是其他容器常见的接口，不再一一赘述：

4.map的[]使用

set没有重载[ ] ，但是map有
[ ] 对于map来说，具有查询和插入key以及修改value的功能
[ ] 中传 key 值，返回值为对应value的引用

场景案例：统计水果数量

#include <iostream>
#include <string>
#include <map>
using namespace std;int main()
{//利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto str : arr){//1.当str在countMap中不存在时，则插入，并且value=1//2.str存在时，则value++countMap[str]++;//是不是很方便？}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}return 0;
}

运行结果：

六、multimap和map的差异

multimap和map的区别同multiset和set。就是支不支持数据冗余的区别
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，，那么 insert/find/count/erase 都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全⼀样，
比如 find 时，有多个key，返回中序第一个。其次就是multimap不支持[ ]，因为支持key冗余，[]就只能支持插入了，不能支持修改。

具体差异参考multiset，这里不再赘述。总之multiset和multimap实际运用并不多。

七、map两道练习题

1.随机链表的复制

链接：138. 随机链表的复制 - 力扣（LeetCode）

题解：

这题我们可以充分利用map的key:value特性，将原链表与复制链表建立链接。
这题本身的主要难点就是random指针的复制，原链表可以通过random指针访问到对应的节点。想要复制这种连接。我们可以借助map。
我们可以创建一个map<Node*,Node*> copyMap，copyMap的key值存储原链表的每一个节点，key对应的value存储该节点的复制节点。
这样有什么好处呢？当我们使用copyMap[key]就能访问对应的复制节点，所以copyMap[key->random]也能访问随机节点对应的复制节点。这样我们就能建立链接了。

代码：

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {map<Node*,Node*> copyMap;Node* copyHead=nullptr,*copyTail=nullptr;Node* cur = head;//深拷贝，先复制链表while(cur){if(copyHead==nullptr){copyHead = copyTail = new Node(cur->val);}else{copyTail->next = new Node(cur->val);copyTail = copyTail->next;}copyMap[cur]=copyTail;//将原链表与复制链表建立连接cur=cur->next;}//随机链表复制Node* curCopy = copyHead;cur = head;while(cur){if(cur->random==nullptr){curCopy->random=nullptr;}else{//通过copyMap就能找到需要链接的随机节点curCopy->random=copyMap[cur->random];}cur=cur->next;curCopy=curCopy->next;}return copyHead;}
};

2.前k个高频单词

链接：692. 前K个高频单词 - 力扣（LeetCode）

题解：

这题我们可以利用map来统计每个单词出现的次数。
但是单统计次数还不够，我们还需要找出前k个高频单词，我们可以使用排序。
但是排序存在两个问题：1.我们需要自己写一个仿函数用于排序的比较，因为map是一个key:value的结构。2.排序需要稳定排序，因为题目要求频率相同的单词按字典序排列。
这题关于排序有两个选择，一个是稳定排序stable_sort，一个是优先级队列priority_queue。我选择的是优先级队列，也就是堆，但无论哪个都需要写仿函数。
关于优先级队列的仿函数，小于对应的大堆，所以我们需要实现一个小于比较的仿函数，关于仿函数的写法，我们先比较的是两个单词出现的频率，也就是value，对于pair结构来说就是second，但是当频率相同时，我们需要比较key的大小，按字典序比较，因为我们实现的是大堆，对于字典序，本来小的应该在前面，但是因为大堆对应小于比较，所以比较key时我们是大于返回true，有点绕，慢慢看代码理解

代码：

class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k){vector<string> ret;//仿函数struct compare{bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){//注意second相同时，比较first时是大于比较return kv1.second < kv2.second || (kv1.second == kv2.second && kv1.first > kv2.first);}};//计数map<string, int> countWords;for (auto& str : words){countWords[str]++;}//堆取前k个单词priority_queue<pair<string, int>, vector<pair<string, int>>, compare> pq;for (auto& e : countWords){pq.push(e);}while (k--)//生成结果，出堆{ret.push_back(pq.top().first);pq.pop();}return ret;}
};

总结

以上就是本文的全部内容了，感谢支持！