【C++】map和set的使用
📌 个人主页：孙同学_
🔧 文章专栏：C++
💡 关注我，分享经验，助你少走弯路
文章目录
1. 序列式容器和关联式容器
1.1 序列式容器
- 核心特征
- 按插入顺序存储：元素的物理存储顺序与插入顺序一致。
- 允许重复元素：可以存储多个相同的值。
- 通过位置访问：通过索引（如数组）或迭代器直接访问元素。
- 常见容器
vector:动态数组，支持快速随机访问，尾部插入高效。list:双向链表，支持快速插入/删除，但随机访问效率低。deque:双端队列，支持头尾高效插入/删除。array:固定大小数组，编译时确定大小。forward_list:单向链表，内存占用更小。
- 适应场景
- 需要保持插入顺序（如日志记录，操作历史）。
- 频繁通过索引随机访问（如vector的[ ]操作）。
- 需要高效头尾操作（如deque）。
1.2 关联式容器
- 核心特征
- 按键存储：元素基于键值对（key-value）键本身存储。
- 自动排序：元素按键的排序规则（默认升序）组织。
- 唯一性：
set和map要求键唯一；multiset和multimap允许重复键。
- 常见容器
set:存储唯一键的有序集合。map:存储键值对的有序映射。multiset:允许重复键的有序集合。multimap:允许重复键的有序映射。
- 适用场景
- 需要快速查找（如字典，数据库索引）。
- 需自动排序（如排行榜，有序事件调度）。
- 需要唯一性约束（如用户ID管理）。
2. set系列的使用
2.1 set和multiset的参考文档
2.2 set类的介绍
set的声明如下，T就是set底层关键字的类型。set默认要求T支持小于比较，如果不支持，可以手动实现一个仿函数传给第二个模板参数。set底层存储数据的内存是从空间配置器上申请的，如果需要可以自己手动实现一个内存池，传给第三个参数。- 一般情况下我们都不需要传后面的两个模板参数。
set的底层是用红黑树实现的，增删查的效率是O（logn）,迭代器遍历走的是搜索树的中序遍历，所以遍历后的元素是有序的。
template<classT,// set::key_type/value_typeclassCompare= less<T>,// set::key_compare/value_compareclassAlloc= allocator<T>// set::allocator_type>classset;2.3 set的构造函数和迭代器
set的构造我们只需关注一下几个即可
//empty (1) 无参默认构造explicitset(const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());// range (2) 迭代器区间构造 template<classInputIterator>set(InputIterator first, InputIterator last,const key_compare& comp =key_compare(),const allocator_type &=allocator_type());// copy (3) 拷⻉构造 set(const set& x);// initializer list (5) initializer 列表构造 set(initializer_list<value_type> il,const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());迭代器
// 迭代器是⼀个双向迭代器 iterator -> a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end();// 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();2.4 set的增删查
#include<iostream>#include<set>usingnamespace std;intmain(){//去重+升序排序 set<int> s;//去重+降序排序，给一个大于的仿函数//set<int, greater<int>> s;//set<int, greater<int>> s = {1,2,7,4,9,6,}; initializer_list初始化 s.insert(2); s.insert(1); s.insert(5); s.insert(6);//set<int> iterator it = s.begin();auto it = s.begin();while(it != s.end()){//*it = 1;不能修改里面的值 cout <<*it <<" "; it++;} cout << endl;//插入一段initilizer_list的值,已经存在则插入失败 s.insert({1,5,3,2,7,9});for(auto e : s){ cout << e <<" ";} cout << endl;//插入string类对象，string类对象比较是按照ascll码来比较大小的 set<string> strset ={"sort","add","insert"};for(auto&e : strset){ cout << e <<" ";} cout << endl;return0;}2.5 find和erase的使用样例
erase,find的使用案例：
intmain(){ set<int> s ={2,7,4,3,1,9,5,0};for(auto& e : s){ cout << e <<" ";} cout << endl;//删除最小值 s.erase(s.begin());for(auto& e : s){ cout << e <<" ";} cout << endl;//删除输入的值，这个值有可能在，也有可能不在int x; cin >> x;int num = s.erase(x);if(num ==0){ cout << x <<"不存在!"<< endl;}for(auto& e : s){ cout << e <<" ";} cout << endl;//直接查找，再利用迭代器删除 cin >> 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);//利用cout快速实现间接查找 cin >> x;if(s.count(x)){ cout << x <<"在!"<< endl;}else{ cout << x <<"不存在!"<< endl;}return0;}删除一段区间的值
intmain(){ set<int> myset;for(int i =1; i <10; i++){ myset.insert(i *10);//10 20 30 40 50 60 70 80 90}for(auto e : myset){ cout << e <<" ";} cout << endl;//实现查找到的[itlow,itup]包含[30,60]区间//返回>=30auto itlow = myset.lower_bound(30);//返回>60auto itup = myset.upper_bound(60);//删除这段区间的值 myset.erase(itlow,itup);for(auto e : myset){ cout << e <<" ";} cout << endl;return0;}2.6 multiset和set的差异
multiset和set基本完全相似，主要的区别点在于multiset支持键值冗余，那么insert/find/count/erase都围绕着支持键值冗余有所差异。
intmain(){ multiset<int> s ={4,6,4,3,6,7,8,9,2,5,3,7,8,9};auto it = s.begin();while(it != s.end()){ cout <<*it <<" ";++it;} cout << endl;//相比较set不同的是，x可能会存在多个，find查找的是中序的第一个int x; cin >> x;auto pos = s.find(x);while(pos != s.end()&&*pos == x){ cout <<*pos <<" ";++pos;} cout << endl;//相比set不同的是count会返回x的实际个数 cout << s.count(x)<< endl;//相比set不同的是erase会删掉里面的所有的x s.erase(x);for(auto e : s){ cout << e <<" ";} cout << endl;return0;}2.7 两个数组的交集 - 力扣（LeetCode）
题目连接：349. 两个数组的交集
解题思路：
两个数组依次比较，小的++，相等的就是交集，同时++，其中一个结束就结束了
代码实现：
classSolution{public: vector<int>intersection(vector<int>& nums1, vector<int>& nums2){//这里用set实现了对数组的排序+去重 set<int>s1(nums1.begin(),nums1.end());//用一段迭代器区间初始化 set<int>s2(nums2.begin(),nums2.end());//小的++，相等就是交集 vector<int> ret;auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end()&& it2 != s2.end()){if(*it1 <*it2) it1++;elseif(*it1 >*it2) it2++;else{ ret.push_back(*it1); it1++; it2++;}}return ret;}};2.8 环形链表 II - 力扣（LeetCode）
题目链接：142. 环形链表 II
解题思路：
遍历这个环形链表，如果count为0,就把此节点插入进set,如果不为0,则此节点为入口点。
代码实现：
classSolution{public: ListNode *detectCycle(ListNode *head){ set<ListNode*> s; ListNode* cur = head;while(cur){if(s.count(cur))return cur;//等于1即为入口点else s.insert(cur); cur = cur -> next;}returnnullptr;}};3. map系列的使用
3.1 map和multimap的参考文档
3.2 map类的介绍
map的声明如下，Key就是map底层关键字的类型，T是map底层Value的类型，map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模板参数。map底层存储数据的内存是从空间配置器申请的。一般情况下我们都不需要传后面两个模板参数。map的底层使用红黑树实现的，增删查改的效率是O（logn）,迭代器遍历走的是中序遍历,所以Key的值是有序的。
template<classKey,// map::key_typeclassT,// map::mapped_typeclassCompare= less<Key>,// map::key_compareclassAlloc= allocator<pair<const Key,T>>// map::allocator_type >classmap3.3 pair类型介绍
map底层红黑树节点中的数据，使用pair<Key,T>存储键值对数据。pair是一个类模板，里面有两个成员变量，一个是first,一个是second。
typedef pair<const Key, T> value_type;template<classT1,classT2>structpair{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<classU,classV>pair(const pair<U, V>& pr):first(pr.first),second(pr.second){}};template<classT1,classT2>inline pair<T1, T2>make_pair(T1 x, T2 y){return(pair<T1, T2>(x, y));}3.4 map的构造
map的构造我们只需关注以下接口即可map支持正向迭代器遍历和反向迭代器遍历，遍历默认按Key的升序，因为底层是二叉搜索树，走的是中序遍历。支持迭代器也就支持范围for。map支持value数据的修改，但不支持Key的修改。修改关键字的数据破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造 explicitmap(const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());// range (2) 迭代器区间构造 template<classInputIterator>map(InputIterator first, InputIterator last,const key_compare& comp =key_compare(),const allocator_type&=allocator_type());// copy (3) 拷⻉构造 map(const map& x);// initializer list (5) initializer 列表构造 map(initializer_list<value_type> il,const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());// 迭代器是⼀个双向迭代器 iterator -> a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end();// 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();3.5 map的增删查
map的增删查关注以下接口即可map的增接口，插入的是pair的键值对数据，跟set有所不同，但是查和删的接口只用关键字Key,跟set完全相似。不过fin返回的是iterator,不仅仅可以找到Key在不在，还能找到映射的Value,同时通过迭代还能修改Value。
Member types key_type->The first templateparameter(Key) mapped_type->The second templateparameter(T) value_type->pair<const key_type, mapped_type>// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 pair<iterator,bool>insert(const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊ voidinsert(initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ template<classInputIterator>voidinsert(InputIterator first, InputIterator last);// 查找k，返回k所在的迭代器，没有找到返回end() iterator find(const key_type& k);// 查找k，返回k的个数 size_type count(const key_type& k)const;// 删除⼀个迭代器位置的值 iterator erase(const_iterator position);// 删除k，k存在返回0，存在返回1 size_type erase(const key_type& k);// 删除⼀段迭代器区间的值 iterator erase(const_iterator first, const_iterator last);// 返回⼤于等k位置的迭代器 iterator lower_bound(const key_type& k);// 返回⼤于k位置的迭代器 const_iterator lower_bound(const key_type& k)const;3.6 map的数据修改
map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回Key所在的iterator修改。map还有一个非常重要的修改接口operator[],但是operator[]不仅仅支持数据的修改，还支持插入数据和查找数据，所以它是一个多功能复合接口。
Member types key_type->The first templateparameter(Key) mapped_type->The second templateparameter(T) value_type->pair<const key_type, mapped_type>// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type值 iterator find(const key_type& k);// ⽂档中对insert返回值的说明 // The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to theelement with an equivalent key in the map.The pair::second element in the pairis set to true if a new element was inserted or false if an equivalent keyalready existed.// insert插⼊⼀个pair<key, T>对象 // 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false// 2、如果key不在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[]// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另⼀个是insert返回值pair<iterator, bool> pair<iterator,bool>insert(const value_type & val); mapped_type&operator[](const key_type& k);// operator的内部实现 mapped_type&operator[](const key_type& k){// 1、如果k不在map中，insert会插⼊k和mapped_type默认值（默认值是用默认构造构造的），同时[]返回结点中存储mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能 pair<iterator,bool> ret =insert({ k,mapped_type()}); iterator it = ret.first;return it->second;}3.7 构造遍历以及增删查改样例
#include<map>intmain(){ pair<string, string> kv1 ={"left","左边"};//initializer_list构造以及迭代遍历 map<string, string> dict ={{"left","左边"},{"right","右边"},{"insert","插入"},{"erase","删除"}}; map<string, string>::iterator it = dict.begin();while(it != dict.end()){//cout << *it << " "; //pair不支持流提取和流插入，是一个结构体//cout << (*it).first << ":" << (*it).second << endl;; cout << it->first <<":"<< it->second << endl;//cout << it.operator->()->first << ":" << it.operator->()->second << endl;//原生写法++it;}//map的插入//insert插入pair的四种方式，对比之下最后一种最方便 pair<string, string>kv2("first","第一个"); dict.insert(kv2);//匿名对象 dict.insert(pair<string, string>("second","第二个"));//make_pair dict.insert(make_pair("sort","排序"));//make_pair是一个函数模板，不用声明模板参数，自己推导，在底层构造一个pair对象再返回//最后一种最好用 dict.insert({"auto","自动的"});//支持隐式类型转换//支持范围for遍历for(auto& e : dict){ cout << e.first <<":"<< e.second << endl;} cout << endl;//结构化绑定 C++17//for (const auto& [k,v] : dict)//{// cout << k << ":" << v << endl;//} string str;while(cin >> str){auto ret = dict.find(str);if(ret != dict.end()){ cout <<"->"<< ret->second << endl;}else{ cout <<"无此单词，请重新输入"<< endl;}}//first是不能被修改的，但是second可以被修改return0;}3.8 map的迭代器功能和[]功能样例
- 统计水果出现的次数
#include<iostream>#include<string>#include<map>usingnamespace std;intmain(){//统计水果出现的次数 string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"}; map<string,int> countMap;//先查找水果在不在map中//1.不在，说明水果第一次出现，则插入水果{水果，1}//2.在，则查找到的水果对应的次数+1for(constauto& str : arr){auto ret = countMap.find(str);if(ret == countMap.end())//则证明在{ countMap.insert({str,1});}//否则，在else{ ret->second++;}}//countMap[str]++; 第二种写法for(constauto& e : countMap){ cout << e.first <<":"<< e.second << endl;} cout << endl;return0;}3.9 multimap和map的差异
multimap和map的使用基本完全类似，主要区别是multimap支持关键字Key冗余，那么insert/find/count/erase都围绕着支持键值冗余有所差异。这里和set和multiset基本一样，比如find时有多个key返回中序中的第一个。其次是multimap不支持[],因为支持key冗余，[]就只能支持插入了，不支持修改。
3.10 随机链表的复制 - 力扣（LeetCode）
题目连接：138. 随机链表的复制
解题思路： 让原链表与拷贝链表通过map建立映射关系
代码实现：
classSolution{public: Node*copyRandomList(Node* head){ map<Node*,Node*> nodeMap; Node* copyhead =nullptr,*copytail =nullptr;//定义一个头一个尾 Node* cur = head;while(cur){//如果为空if(copytail ==nullptr){ copyhead = copytail =newNode(cur->val);}//如果不为空else{ copytail->next =newNode(cur->val); copytail = copytail->next;}//让原节点和拷贝节点建立map nodeMap[cur]= copytail; cur = cur->next;}//处理random cur = head; Node* copy = copyhead;while(cur){//原链表的random为空，则拷贝链表的random也为空if(cur->random ==nullptr){ copy->random =nullptr;}else{ copy->random = nodeMap[cur->random];} cur = cur->next; copy = copy->next;}return copyhead;}};3.11 前K个高频单词 - 力扣（LeetCode）
题目链接：692. 前K个高频单词
解题思路1：
用排序找前k个单词，因为map中已经对Key单词排序过，也就意味着遍历map时次序相同的单词，字典序小的在前面，字典序大的在后面，那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊的要求，但sort底层是快排，是不稳定的，所以我们要用table_sort,是稳定的。
代码实现：
classSolution{public:structCompare{booloperator()(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&str : words){ countMap[str]++;} vector<pair<string,int>>v(countMap.begin(),countMap.end());//迭代器区间初始化stable_sort(v.begin(),v.end(),Compare()); vector<string> retv;for(size_t i =0; i < k ;++i){ retv.push_back(v[i].first);//取的是每个pair对象中的单词}return retv;}};解题思路2：
将map统计出来的次序，放到vector中排序，或者放到priority_queue中选出前k个，利用仿函数强制控制次数相等的，字典序小的在前面。
代码实现：
classSolution{public:structCompare{booloperator()(const pair<string,int>& x,const pair<string,int>& y){return x.second > y.second ||(x.second == y.second && x.first < y.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(v.begin(), v.end(),Compare());// 取前k个 vector<string> strV;for(int i =0; i < k;++i){ strV.push_back(v[i].first);}return strV;}};classSolution{public:structCompare{booloperator()(const pair<string,int>& x,const pair<string,int>& y)const{// 要注意优先级队列底层是反的，⼤堆要实现⼩于⽐较，所以这⾥次数相等，想要字典序⼩的在前⾯要⽐较字典序⼤的为真return x.second < y.second ||(x.second == y.second && x.first > y.first);}}; vector<string>topKFrequent(vector<string>& words,int k){ map<string,int> countMap;for(auto& e : words){ countMap[e]++;}// 将map中的<单词，次数>放到priority_queue中，仿函数控制⼤堆，次数相同按照字典序规则排序 priority_queue<pair<string,int>, vector<pair<string,int>>, Compare>p(countMap.begin(), countMap.end()); vector<string> strV;for(int i =0; i < k;++i){ strV.push_back(p.top().first); p.pop();}return strV;}👍 如果对你有帮助，欢迎：
- 点赞 ⭐️
- 收藏 📌
- 关注 🔔
