目录

前言

一、set

1.set的基本介绍

2.set的使用

2.1构造与迭代器

2.2插入

2.3删除

2.4查找

 2.5获取需要的区间

2.6一些使用示例

3.set和multiset的区别

4.set相关oj题目

二、map

1.map的基本介绍

2.map的使用

2.1构造与迭代器

2.2增删查以及获取区间

2.3数据修改

3.map和multimap的区别

4.map相关oj题目

---

前言

set和map呢，底层是红黑树（后面我的博客也会重点讲解），红黑树是一种平衡二叉搜索树，set和map本身是不支持插入重复元素的，不过也有实现的支持插入重复元素的版本multiset和multimap。

set和map的区别呢，主要在于其应用场景，set用于key场景，map用于key/value场景（我上一篇博客有提到过，不知道的可以移步我上篇博客了解C++进阶——二叉搜索树-CSDN博客）。

这篇博客会着重讲解set和map的使用，模拟实现我会放到后续的博客来讲解。

---

一、set

文档资料：set - C++ Reference (cplusplus.com)

1.set的基本介绍

1.set的模板声明中，T就是key的类型，后面的Compare是仿函数，用于底层搜索树的比较逻辑，一般情况下不用我们自己传，缺省值给的就够用，当默认的仿函数不符合我们需求时，我们需要自己实现一个仿函数然后传递，第三个模板参数时空间配置器，这个我们暂时先不用管。

2.set的底层是红黑树，是一种与完全二叉树形态很相似的二叉搜索树，高度是logN，所以增删查的效率是O(logN)。

3.迭代器是双向迭代器（bidirectional iterator），走的中序遍历，也就是说迭代器遍历出的序列是有序的。

---

2.set的使用

2.1构造与迭代器

1.set支持默认构造、拷贝构造、初始化列表构造和迭代器区间构造等，跟之前的容器很类似，就不再一一演示。

2.迭代器是中序遍历，所以遍历出来的序列一定是有序的。

#include <iostream>
#include <set>
using namespace std;int main()
{set<string> s{ "banana","apple","pear","orange" };set<string>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}return 0;
}

2.2插入

1.支持指定key插入，如果存在key则插入失败，不存在则插入成功

pair<iterator, bool> insert(const value_type& val);

 pair<iterator, bool>是啥？

我们可以借由这个返回值来判断插入成功还是失败，以及获取插入后该结点对应的迭代器（插入失败则会返回原来存在的与key值相等的结点的迭代器） 

#include <iostream>
#include <set>
using namespace std;int main()
{set<string> s{ "banana","apple","pear","orange" };set<string>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;auto iit = s.find("apple");auto ret = s.insert("apple");auto iit1 = ret.first;if (iit1 == s.end()) cout << "插入失败1" << endl;if (iit1 == iit) cout << "插入失败2" << endl;// 所以插入失败了返回的迭代器是原相同key值对应的迭代器，一定不是end()return 0;
}

2.支持初始化列表插入，没有返回值，列表中搜索树中不存在的就插入，存在的就跳过。

void insert(initializer_list<value_type> il);

3.支持迭代器区间插入，已经存在的值将不会再插入，无返回值

template <class InputIterator>
void insert(InputIterator first, InputIterator last); 

2.3删除

1.删除指定迭代器对应结点

iterator erase(const_iterator position);

返回的迭代器是删除结点位置的下一个结点（中序），如果没有下一个就是返回end()。

2.删除指定值为key的结点

size_type erase(const value_type& val);

删除成功则返回1，不存在删除失败则返回0，为什么不是返回bool值？也是因为需要跟multiset的接口对其，multiset返回的是删除key值为val的结点的个数。 

3.删除一段迭代器区间（也就是中序遍历的一段序列）

iterator erase(const_iterator first, const_iterator last);

返回的迭代器是删除最后一个结点位置的下一个结点（中序），如果没有下一个就是返回end()。 

2.4查找

1.find，返回找到位置的迭代器，找不到就返回end()

iterator find(const value_type& val);

2.count，返回key值为val的结点的个数

size_type count(const value_type& val) const; 

为什么返回个数而不是bool值？同样是为了跟multiset的接口对齐

 2.5获取需要的区间

需要两个接口来打配合：

1.lower_bound    返回大于等于val位置的迭代器

iterator lower_bound(const value_type& val) const;

2.upper_bound        返回大于val位置的迭代器

iterator upper_bound(const value_type& val) const; 

怎么打配合呢？ 

两者可以配合着来找我们需要找的迭代器区间，看名字也很容易记住，lower就是区间下限，upper就是区间下限嘛，然后返回的两个迭代器组成的区间（左闭右开）中就包含了所有搜索树中具有我们传递的[val1,val2]中的所有数据。（我们传递数据图方便和思维习惯肯定是左闭右闭了~）

#include <iostream>
#include <set>
#include <vector>
using namespace std;void test2()
{set<int> s{ 5, 4, 7, 5, 2, 1, 9, 4, 3, 5, 2, 6, 8 };// 1 2 3 4 5 6 7 8 9for (auto e : s)cout << e << " ";cout << endl;// 两个接口的配合，可以找到我们需要获取的迭代器区间auto lower_it = s.lower_bound(4);  // 大于等于4     4auto upper_it = s.upper_bound(7);  // 大于7          8//                    [4, 8)   迭代器都是左闭右开vector<int> v(lower_it, upper_it);// 4 5 6 7for (auto e : v)cout << e << " ";// 如果4 和 7 不在里面呢？会找到[5,8)      5，6，7也符合我们的需求（在[4, 7]区间内的所有数据组成的区间）// 总而言之，两个配合可以找到所有在[4, 7]区间内的所有数据构成的迭代器区间
}int main()
{test2();return 0;
}

2.6一些使用示例

下面是上面一些接口的使用示例，大家可以看看：

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;// 构造、迭代器、insert
void show1()
{// 去重+升序排序set<int> s;// 去重+降序排序（降序要自己传仿函数）（默认是升序Less<T>）//set<int, greater<int>> s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);auto it = s.begin();while (it != s.end()){// error C3892: “it”: 不能给常量赋值// key是肯定不能修改的，不管是不是const迭代器，修改了就可能会破坏掉搜索树的结构// *it = 1;cout << *it << " ";++it;}cout << endl;// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败s.insert({ 2,8,3,9 });for (auto e : s){cout << e << " ";}cout << endl;set<string> strset = { "banana","apple","pear","orange" };// 遍历string，比较的方法跟字符串一样，ascll比较for (auto& e : strset){cout << e << " ";}cout << endl;
}// find、erase
void show2()
{set<int> s = { 4,2,7,2,8,5,9 };for (auto e : s){cout << e << " ";}cout << endl;// 删除最小值s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);if (num == 0){cout << x << "不存在！" << endl;}for (auto e : s){cout << e << " ";}cout << endl;// 直接查找再利用迭代器删除xcin >> x;auto pos = s.find(x);if (pos != s.end()){s.erase(pos);}else{cout << x << "不存在！" << endl;}for (auto e : s){cout << e << " ";}cout << endl;// 算法库的查找 O(N)auto pos1 = find(s.begin(), s.end(), x);// set自身实现的查找 O(logN)auto pos2 = s.find(x);// 包是自身的查找好的呀，算法库里面的查找是双向迭代器的容器通用的，都没利用set的特性// 利⽤count间接实现快速查找cin >> x;if (s.count(x)){cout << x << "在！" << endl;}else{cout << x << "不存在！" << endl;}
}// lower_bound和upper_bound
void show3()
{set<int> s{ 5, 4, 7, 5, 2, 1, 9, 4, 3, 5, 2, 6, 8 };// 1 2 3 4 5 6 7 8 9for (auto e : s)cout << e << " ";cout << endl;// 两个接口的配合，可以找到我们需要获取的迭代器区间auto lower_it = s.lower_bound(4);  // 大于等于4     4auto upper_it = s.upper_bound(7);  // 大于7          8//                    [4, 8)   迭代器都是左闭右开vector<int> v(lower_it, upper_it);// 4 5 6 7for (auto e : v)cout << e << " ";// 如果4 和 7 不在里面呢？会找到[5,8)      5，6，7也符合我们的需求（在[4, 7]区间内的所有数据组成的区间）// 总而言之，两个配合可以找到所有在[4, 7]区间内的所有数据构成的迭代器区间
}int main()
{show2();return 0;
}

3.set和multiset的区别

首先注意：set和multiset都是在同一个头文件<set>里面的。

最主要的区别还是set不支持重复元素，multiset支持重复元素插入（废话）。

不过它们使用的时候的区别也是从这句废话中产生的：

multiset的增删查由于支持相同数据的插入所以会相对set有所变动。

1.构造：都会排序，但是multiset不去重

2.insert：multiset不去重插入，给什么插入什么

3.erase：multiset会删除所有的值为x的结点

4.find：查找中序遍历的第一个值为x的结点

5.count：返回值为x的结点的个数，结果不再是0或1

4.set相关oj题目

相关思路及细节我都会写在代码的注释中~

1.349. 两个数组的交集 - 力扣（LeetCode）

// 这里两个数组的交集是不用考虑重复元素的问题的，也就是说，我们可以利用set去重之后再进行找交集的操作
// set天然的结构使迭代器的遍历（中序）是有序的，且数据是去重过的，那么我们小小地使用一下双指针就可以解决~~class Solution
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());vector<int> ret;// 利用双指针（迭代器）来遍历s1和s2auto 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，插入之前count或者find一下
// 如果有这个数据了之前，那么就一定是环形链表class Solution
{
public:ListNode *detectCycle(ListNode *head){// 注意这里的模板类型和后面的插入类型相匹配，*是必须的set<ListNode*> s;ListNode* cur = head;while(cur){if(s.count(cur) == 1)return cur;elses.insert(cur);cur = cur->next;}return nullptr;}
};

二、map

文档资料：map - C++ Reference (cplusplus.com)

1.map的基本介绍

map与set极为类似，不同的是多了一个模板参数类型T，这个T本质上就是key/value类型的value。

Key用作比较，T是跟Key相关的数据。

 但是这里有个设计比较搓的地方，key_type是K（key）没问题，mapped_type按理来说设计成V（value）会更好理解，不过它设计成了T那也就按这么来吧。

再下面的value_type是一个pair类型的类类型，这个类里面存了两个类型（K和T）的参数分别一个，这个pair正是map底层红黑树存储的结点数据。

2.map的使用

由于map和set的使用真的很相似很相似，我只列举比较重要且核心的

2.1构造与迭代器

只需要了解一点与set不同的：

1.由于map的底层红黑树的结点数据是pair<K, T>类型的，所以我们需要在构造的时候传pair<K, T>类型的参数而不是让K和T分开传

2.迭代器用->访问key或者value

#include <iostream>
#include <map>
using namespace std;void map_test1()
{map<string, string> m{ {"apple", "苹果"}, {"pear", "梨"}};// 匿名对象m.insert(pair<string, string>("orange", "橙子"));// 调用函数返回pairm.insert(make_pair("banana", "香蕉"));// 隐式类型转换//map<string, string> m{ {"apple", "苹果"}, {"pear", "梨"} };auto it = m.begin();while (it != m.end()){//cout << (*it).first << " : " << (*it).second << endl;// operator->()是特殊处理过的，这里是省略一个箭头的写法// operator->()返回的是pair的指针//cout << it.operator->()->first;cout << it->first << " : " << it->second << endl;++it;}// map这边operator->()很常用}int main()
{map_test1();return 0;
}

2.2增删查以及获取区间

皆与set相类似，就不再赘述

2.3数据修改

与set不同，set不能修改key主要是因为修改key会造成结构损坏，而map虽不能修改key，但是可以修改与key连带在一起的value，这样不会破坏底层红黑树的结构。

#include <iostream>
#include <map>
using namespace std;void map_test2()
{// 利用[]插⼊+修改功能，巧妙实现统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找水果果在不在map中// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引用，++⼀下就变成1次了// 2、在，则返回⽔果对应的次数++countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;
}void map_show1()
{map<string, string> m{ {"apple", "苹果"}, {"pear", "梨"}, {"banana", "香蕉"}, {"orange", "橙子"} };// iterator find (const key_type& k);auto ret = m.find("apple");// ret是迭代器ret->second = "_苹果";for (auto e : m){cout << e.first << "   " << e.second << endl;}// pair<iterator,bool> insert (const value_type& val);auto iit = m.insert({"pineapple", "菠萝"});// insert 的返回值:// 插入成功就是返回当前结点的迭代器+true// 插入失败就是返回与插入key值相同的原有结点的迭代器+false// 也就是说无论插入成功与否都能返回值为key的结点// 所以我们也可以利用insert来充当查找的功能iit.first->second = "_菠萝";for (auto e : m){cout << e.first << "   " << e.second << endl;}// mapped_type& operator[] (const key_type& k);// 传key// [] 返回的是value的引用，所以就可以利用这个来统计出现次数// []的内部实现原理：//mapped_type& operator[] (const key_type& k)//{//	// 传key进来，利用value的缺省值构造出一个pair//	// 插入这个pair，如果有就插入，没有就算了，不过还是都返回了key值的结点迭代器//	// 实现了查找功能//	pair<iterator, bool> ret = insert({ k, mapped_type() });//	iterator it = ret.first;//	return it->second;//}map_test2();}int main()
{map_show1();return 0;
}

3.map和multimap的区别

两者主要区别在于是否允许key值冗余，所以增删查会有所区别，与set和multiset的区别几乎完全一样，还有就是multimap不支持[]，因为multimap的key是可以冗余的，所以就算实现[]也是插入，不过我们已经有insert了。

4.map相关oj题目

1.138. 随机链表的复制 - 力扣（LeetCode）

法1（利用插入结点建立映射关系）：

// 解决这道题需要：结点的深拷贝、结点的映射关系
// 如果不用map，这个映射关系需要深拷贝一个个结点插入原链表中，完成映射
// 也就是说7，13，11，10，1变成了7，7，13，13，11，11，10，10，1，1
// 然后再给新结点通过结点之间的映射关系来进行链接
// 最后还得再解除两个链表的链接，让两个链表再次独立class Solution 
{
public:Node* copyRandomList(Node* head) {if (!head) return nullptr; // 处理空链表Node* cur = head;// 结点深拷贝，插入原链表，建立映射关系while(cur){Node* copycur = new Node(cur->val); // 创建新的节点copycur->next = cur->next; // 将新节点的 next 指向原链表的下一个节点cur->next = copycur; // 将原节点的 next 指向新节点cur = copycur->next; // 移动到下一原节点}// 搞定新链表各节点的random指针cur = head;while(cur){   if(cur->random) // 检查是否有随机指针cur->next->random = cur->random->next; // 新节点的随机指向// random初始值就是nullptr所以不需要再elsecur = cur->next->next; // 移动到下一个原节点}// 分离两个链表cur = head;Node* newHead = head->next; // 新链表的头节点Node* copyCur = newHead; // 复制链表的当前指针while(cur){cur->next = cur->next->next; // 恢复原链表if (copyCur->next)copyCur->next = copyCur->next->next; // 移动复制链表cur = cur->next; // 继续移动原链表copyCur = copyCur->next; // 继续移动复制链表}return newHead; // 返回新链表的头节点}
};

法2（利用map建立映射关系）： 

/*
// 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){if (!head) return nullptr; // 处理空链表map<Node*, Node*> nodeMap; // 创建一个映射，原节点 -> 新节点Node* cur = head;// 第一遍历：复制节点并建立映射关系while (cur) {nodeMap[cur] = new Node(cur->val); // 创建新节点并存入映射cur = cur->next; // 移动到下一个原节点}// 第二遍历：设置新节点的 next 和 random 指针cur = head;while (cur) {nodeMap[cur]->next = nodeMap[cur->next]; // 设置 next 指针nodeMap[cur]->random = nodeMap[cur->random]; // 设置 random 指针cur = cur->next; // 移动到下一个原节点}return nodeMap[head]; // 返回新链表的头节点}
};

2.692. 前K个高频单词 - 力扣（LeetCode）

class Solution
{
public:struct myCmp{bool operator()(const pair<string, int>& p1, const pair<string, int>& p2){// 由于出现次数相同的单词需要用字典序排序，所以加上后面的这个判断条件（sort本身是不稳定排序）return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);// 次数不同次数大的在前面，次数相同字典序小的在前面// 如果没有字典序后面的判断也可以，但是需要用stable_sort}};vector<string> topKFrequent(vector<string>& words, int k){// 给的单词列表需要排序，又因为需要统计次数，那么自然需要mapmap<string, int> m;for(auto& e : words)m[e]++;vector<pair<string, int>> vs(m.begin(), m.end());// 其实插入后m和vs已经是字典序了// 不过sort排序不是一个稳定排序，并且sort默认的仿函数不能解决我们pair比较的需求sort(vs.begin(), vs.end(), myCmp());vector<string> ret;auto vsit = vs.begin();while(k--){ret.push_back((*vsit).first);++vsit;}return ret;}
};

---

完结撒花~~~~~~~~~~~

耶╰(✿´⌣`✿)╯♡