【C++标准模版库】map和set的先容及利用

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

• 前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一样寻常没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序生存和访问的。
  
• 关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。关联式容器中的元素是按关键字来生存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
  
• 本章节讲解的map和set底层是红黑树，红黑树是一颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。而unordered_map和unordered_set的低层是哈希表。
  

二.set系列的利用

1.set和multiset参考文档

参考文档
2.set类的先容

1. template < class T,                    // set::key_type/value_type
2.                class Compare = less<T>,    // set::key_compare/value_compare
3.                class Alloc = allocator<T>  // set::allocator_type 空间配置器
4.            > class set;

复制代码

• set的声明如上，T就是set底层关键字key的范例。
  
• set默认要求T支持小于较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第⼆个模版参数。例如：传入日期类的指针比较日期。
  
• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
  
• 一样寻常环境下，我们都不需要传后两个模版参数。
  
• set底层是用红黑树实现，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，由于二叉搜索树的性质，左子树小于根，根小于右子树，所以中序是有序的。
  

3.set的构造和迭代器

• set的构造我们关注以下几个接口即可。
  
• set的支持正向和反向迭代遍历（双向迭代器：支持++/–，但是不支持+/-），遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
  

1. //empty (1) ⽆参默认构造
2. explicit set(const key_compare& comp = key_compare(),
3.              const allocator_type& alloc = allocator_type());
5. //range (2) 迭代器区间构造
6. template <class InputIterator>
7. set(InputIterator first, InputIterator last,
8.     const key_compare& comp = key_compare(),
9.     const allocator_type& = allocator_type());
11. //copy (3) 拷⻉构造
12. set(const set& x);
14. //initializer list (4) C++11支持: initializer 列表构造
15. set(initializer_list<value_type> il,
16.     const key_compare& comp = key_compare(),
17.     const allocator_type& alloc = allocator_type());
19. //迭代器是一个双向迭代器
20. iterator -> a bidirectional iterator to const value_type
22. //正向迭代器
23. iterator begin();
24. iterator end();
26. //反向迭代器
27. reverse_iterator rbegin();
28. reverse_iterator rend();

复制代码

1. int main()
2. {
3.         vector<int> v = { 1,5,4,2,3,6,7,8,9 };
5.         set<int> s1; //无参默认构造
6.         set<int> s2(v.begin(), v.end()); //迭代器区间构造
7.         set<int> s3(s2); //拷贝构造
8.         set<int> s4 = { 1,5,4,2,3,6,7,8,9 }; //列表初始化构造
10.         //1.正向迭代器
11.         auto it = s2.begin();
12.         while (it != s2.end())
13.         {
14.                 cout << *it << " "; //输出：1 2 3 4 5 6 7 8 9
15.                 ++it;
16.         }
17.         cout << endl;
19.         //2.set是双向迭代器迭代器支持++/--，但是不是随机迭代器不支持+/-
20.         it = --s2.end(); auto end = --s2.begin();
21.         while (it != end)
22.         {
23.                 cout << *it << " "; //输出：9 8 7 6 5 4 3 2 1
24.                 --it;
25.         }
26.         cout << endl;
28.         //3.反向迭代器
29.         set<int>::reverse_iterator rit = s4.rbegin();
30.         while (rit != s4.rend())
31.         {
32.                 cout << *rit << " "; //输出 9 8 7 6 5 4 3 2 1
33.                 ++rit;
34.         }
35.         cout << endl;
37.         return 0;
38. }

复制代码

4.set的增删查

set支持增删查，但是set不支持修改，因为修改之后就会可能失去红黑树的性质。
set的增删查关注以下几个接口即可：

1. template < class T,                    // set::key_type/value_type
2.                class Compare = less<T>,    // set::key_compare/value_compare
3.                class Alloc = allocator<T>  // set::allocator_type 空间配置器
4.            > class set;
5.            //1.单个数据插入，如果已经存在则插入失败 pair<iterator, bool> insert(const value_type& val);//2.列表插入，已经在容器中存在的值不会插入 void insert(initializer_list<value_type> il);//3.迭代器区间插入，已经在容器中存在的值不会插入 template <class InputIterator>void insert(InputIterator first, InputIterator last);//查找val，返回val地点的迭代器，没有找到返回end() iterator find(const value_type& val);//查找val，返回Val的个数 size_type count(const value_type& val) const;//1.删除一个迭代器位置的值 iterator erase(const_iterator position);//2.删除val，val不存在返回0，存在返回1 size_type erase(const value_type& val);//3.删除一段迭代器区间的值 iterator erase(const_iterator first, const_iterator last);//返回大于等于val位置的迭代器 iterator lower_bound(const value_type& val) const;//返回大于val位置的迭代器 iterator upper_bound(const value_type& val) const;

复制代码

1. Member types
2. key_type   -> The first template parameter (T)
3. value_type -> The first template parameter (T)

复制代码

留意：

• set是key结构, map才是key/value结构, 这里的key_type和value_type是为了保持与map一致，所以才有了value_type，在set中实在就是key，当然key_type也是key。
  
• set不支持插入雷同的数据，multiset支持插入雷同的数据。
  

5.insert和迭代器遍历利用

1. int main()
2. {
3.         vector<int> v{ 8,7,9 };
5.         set<int> s1;
6.         s1.insert(1);
7.         s1.insert(2);
8.         s1.insert(2); //1.单个数据插入，如果已经存在则插入失败
9.         s1.insert(3);
11.         s1.insert({ 4,5,6,5 }); //2.插入列表，同理如果已经存在则该数据插入失败
13.         s1.insert(v.begin(), v.end()); //3.插入迭代器区间
15.         //排序+去重
16.         //升序<：set<int, less<int>> s;
17.         //降序>：set<int, greater<int>> s;
19.         set<int> s; //默认传入了仿函数less<int>
20.         s.insert(5);
21.         s.insert(2);
22.         s.insert(7);
23.         s.insert(5);
24.         s.insert(8);
25.         s.insert(1);
27.         set<int>::iterator it = s.begin();
28.         while (it != s.end())
29.         {
30.                 //*it = 10; 不支持修改
31.                 cout << *it << " "; //输出：1 2 5 7 8
32.                 ++it;
33.         }
35.         //set(initializer_list<value_type> il);
37.         //单参数支持隐式类型转换：构造tmp+用tmp拷贝构造strset1——>优化为直接构造strset1
38.         set<string> strset1 = { "sort", "insert", "add" };
40.         //调用默认构造
41.         set<string> strset2({ "sort", "insert", "add" });
43.         //遍历strset1比较ascll码大小顺序遍历的：set的范围for本质就是迭代器的中序遍历
44.         for (auto& e : strset1)
45.         {
46.                 cout << e << " "; //输出：add insert sort
47.         }
48.         cout << endl;
50.         return 0;
51. }

复制代码

6.find和erase的利用

• 算法库的遍历查找，实用于各种容器： O(N) auto pos1 = find(s.begin(), s.end(), x);
  
• set自身实现的查找，利用二叉搜索树举行查找： O(logN) auto pos2 = s.find(x);
  

1. //1.删除一个迭代器位置的值
2. iterator erase (const_iterator position);
4. //2.删除val，val不存在返回0，存在返回1
5. size_type erase (const value_type& val);
7. //3.删除⼀段迭代器区间的值
8. iterator erase (const_iterator first, const_iterator last);
11. //查找val，返回val所在的迭代器，没有找到返回end()
12. iterator find (const value_type& val);
14. //查找val，返回Val的个数
15. size_type count (const value_type& val) const;

复制代码

留意：删除具体的值返回size_type而不是bool是为了与multiset保持一致，multiset含有重复数据（例如：multiset中有3个5，若要删除5，则返回值就是3）

1. int main()
2. {
3.         set<int> s = { 4,6,5,8,9,7,2,3,1 };
5.         //1.迭代器删除最小值
6.         s.erase(s.begin());
8.         //2.删除具体的值val：低层就是find+迭代器删除
9.         int x;
10.         cin >> x;
11.         int num = s.erase(x);
12.         if (num == 0)
13.                 cout << x << "不存在！" << endl;
14.         else
15.                 cout << x << "删除成功！" << endl;
17.         //3.删除一段迭代器区间的值
18.         auto first = s.find(4);
19.         auto last = s.find(6);
20.         s.erase(first, last); //删除的值位于迭代器区间[first,last)中
21.         for (auto e : s)
22.                 cout << e << " ";
24.         //find+迭代器删除：与上面等价
25.         int y;
26.         cin >> y;
27.         auto pos = s.find(y); //找到返回该值的迭代器，找不到返回s.end()
28.         if (pos != s.end())
29.                 s.erase(pos);
30.         else
31.                 cout << y << "不存在！" << endl;
33.         //利用count间接实现快速查找
34.         int z;
35.         cin >> z;
36.         if (s.count(z))
37.                 cout << z << "在！" << endl;
38.         else
39.                 cout << z << "不存在！" << endl;
41.         return 0;
42. }

复制代码

7.erase迭代器失效问题

1. int main()
2. {
3.         set<int> s = { 1,5,6,3,2,4 };
4.         auto pos = s.find(3);
5.         s.erase(pos); //pos位置的迭代器失效
6.         cout << *pos << endl; //强行访问导致程序崩溃
8.         pos = s.erase(pos); //解决办法
9.         cout << *pos << endl; //输出：3的中序的下一个迭代器4
11.         //但是若查找的是6的话，那么删除6后迭代器pos就变成了s.end()，此时访问程序崩溃
13.         return 0;
14. }

复制代码

8.lower_bound与upper_bound

1. //返回大于等于val位置的迭代器：按照搜索树的规则找
2. iterator lower_bound(const value_type& val) const;
4. //返回大于val位置的迭代器：按照搜索树的规则找
5. iterator upper_bound(const value_type& val) const;

复制代码

1. int main()
2. {
3.         set<int> s1;
4.         for (int i = 1; i < 10; i++)
5.         {
6.                 s1.insert(i * 10); //10 20 30 40 50 60 70 80 90
7.         }
8.         set<int> s2(s1);
9.         cout << endl;
11.         //要求：删除[30, 50]区间的值
13.         //1.erase的迭代器区间删除左闭右开：[)
14.        
15.         auto first = s1.find(30);
16.         auto last = s1.find(70);
17.         s1.erase(first, last);
18.         for (auto e : s1)
19.         {
20.                 cout << e << " "; //10 20 70 80 90
21.         }
22.         cout << endl;
24.         //要求：删除[25, 55]区间的值：则上面的方法无效，因为find查找不到，返回的是s.end()迭代器
26.         //此时需要用到lower_bound和upper_bound
27.        
28.         auto itlow = s2.lower_bound(25); //返回 >= 25的迭代器：就是30位置的迭代器
29.         auto itup = s2.upper_bound(55);  //返回 > 55的迭代器：就是60位置的迭代器
30.         s2.erase(itlow, itup);
31.         for (auto e : s2)
32.         {
33.                 cout << e << " "; //10 20 60 70 80 90
34.         }
35.         cout << endl;
37.         return 0;
38. }

复制代码

9.multiset和set的差别

multiset和set的利用基本完全类似，主要区别点在于multiset支持值冗余，那么insert/find/count/erase都围绕着支持值冗余有所差别，具体参看下面的样例代码明白：

1. int main()
2. {
3.         //相比set不同的是，multiset是排序，但是不去重
4.         multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
5.         auto it = s.begin();
6.         while (it != s.end())
7.         {
8.                 cout << *it << " "; //输出：2 2 4 4 4 4 5 7 8 9
9.                 ++it;
10.         }
11.         cout << endl;
13.         //相比set不同的是，x可能会存在多个，find查找中序的第一个
14.         int x;
15.         cin >> x;
16.         auto pos = s.find(x);
17.         while (pos != s.end() && *pos == x)
18.         {
19.                 cout << *pos << " ";
20.                 ++pos;
21.         }
22.         cout << endl;
24.         //相比set不同的是，count会返回x的实际个数
25.         cout << s.count(x) << endl;
27.         //相比set不同的是，erase给值时会删除所有的x
28.         s.erase(x);
29.         for (auto e : s)
30.         {
31.                 cout << e << " ";
32.         }
33.         cout << endl;
35.         return 0;
36. }

复制代码

留意：查找3时，返回的是中序的第一个3的迭代器。好处：若背面另有3，则迭代器不绝++就可以找到背面的全部3。

10.set解决：leetcode例题

1.两个数组的交集

两个数组的交集

解法：set+双指针

1. class Solution {
2. public:
3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
4.     {
5.         //1.将nums1和nums2放入set中：去重+迭代器遍历时是有序的
6.         set<int> s1(nums1.begin(), nums1.end());
7.         set<int> s2(nums2.begin(), nums2.end());
8.         vector<int> ret;
10.         //2.双指针
11.         auto it1 = s1.begin();
12.         auto it2 = s2.begin();
13.         while(it1 != s1.end() && it2 != s2.end())
14.         {
15.             if(*it1 < *it2) ++it1;
16.             else if(*it1 > *it2) ++it2;
17.             else //相等时：将数据尾差到ret中
18.             {
19.                 ret.push_back(*it1);
20.                 ++it1;
21.                 ++it2;
22.             }
23.         }
24.         return ret;
25.     }
26. };

复制代码

已知：集合A = {1, 2, 3, 4, 5}，集合B = {4, 5, 6, 7, 8}，求A与B的差集和B与A的差集？
A - B = A - AB = {1, 2, 3}；
B - A = B - AB = {6, 7, 8}；
思考：怎样找差集？

• 小的就是差集。
  
• 相称就同时++。
  
• 若其中一个走完了另一个没走完的值也是属于差集。
  

2.交集与差集的应用：数据同步

云相册是一种将照片和视频等多媒体内容存储在云端（即互联网上的服务器）的相册服务。具体来说，云相册具备以下几个核心特点和上风：

• 用户可以将手机、相机等装备中的照片和视频上传到云端，通过云相册提供的平台，随时随地检察、编辑和分享这些照片和视频。
  
• 支持多装备同步，用户可以在任何装备上检察和编辑自己的照片和视频，无需担心数据丢失或无法访问的问题。
  
• 解决存储问题：传统存储方式存在容量有限、携带未便等问题，云相册的出现极大地缓解了这些问题，用户可以无穷量地存储照片和视频。
  
• 跨平台利用：无论是iOS、Android还是Windows等操作体系，用户都可以通过相应的应用步伐或网页版云相册来访问和管理自己的照片和视频。
  
• 节流装备空间：存储在云端的照片和视频不会占用装备的存储空间，用户可以释放装备空间以存储更多其他范例的文件。
  

3.环型链表||

环型链表||

解法一：快慢指针
在C语言中：我们通过证实一个指针重新开始走一个指针从相遇点开始走，会在入口点相遇，明白证实都会很贫苦。

1. struct ListNode* detectCycle(struct ListNode* head)
2. {
3.     ListNode* slow = head;
4.     ListNode* fast = head;
5.     while (fast && fast->next)
6.     {
7.         slow = slow->next;
8.         fast = fast->next->next;
9.         if (slow == fast)
10.         {
11.             //有环
12.             ListNode* meet = slow;//相遇点
13.             while (meet != head)
14.             {
15.                 //一个指针从相遇点开始走，一个指针从起点开始走，最终一定在入环点相遇
16.                 head = head->next;
17.                 meet = meet->next;
18.             }
19.             return meet;//入环点
20.         }
21.     }
22.     return NULL;//无环
23. }

复制代码

解法二：set容器
而C++中的set查找记录解决非常简单方便，这里表现了set在解决一些问题时的价值，完满是降维打击。

1. class Solution {
2. public:
3.     ListNode *detectCycle(ListNode *head)
4.     {
5.         set<ListNode*> s;
6.         ListNode* cur = head;
7.         while(cur) //遍历链表
8.         {
9.             if(s.count(cur)) return cur; //若set中有cur，那么链表带环并且cur就是入口点
10.             else s.insert(cur); //若set中没有cur，那么cur插入到set中
12.             cur = cur->next;
13.         }
14.         return nullptr; //此时遍历完链表后，说明链表不带环
15.     }
16. };

复制代码

三.map系列的利用

1.set和multiset参考文档

参考文档
2.map类的先容

1. template < class Key,                                     // map::key_type
2.            class T,                                       // map::mapped_type
3.            class Compare = less<Key>,                     // map::key_compare
4.            class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
5.            > class map;

复制代码

• map的声明如上，Key就是map底层关键字的范例，T是map底层value的范例。
  
• map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第⼆个模版参数。
  
• map底层存储数据的内存是从空间配置器申请的。
  
• 一样寻常环境下，我们都不需要传后两个模版参数。
  
• map底层是用红黑树实现，增删查改效率是O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
  

3.pair范例先容

1. typedef pair<const Key, T> value_type;
3. template <class T1, class T2>
4. struct pair
5. {
6.         typedef T1 first_type;
7.         typedef T2 second_type;
8.         T1 first;
9.         T2 second;
11.         pair() //无参默认构造
12.                 :first(T1())
13.                 ,second(T2())
14.         {}
16.         pair(const T1& a, const T2& b) //拷贝构造
17.                 :first(a)
18.                 ,second(b)
19.         {}
21.         template<class U, class V>
22.         pair(const pair<U, V>& pr) //有参构造
23.                 :first(pr.first)
24.                 ,second(pr.second)
25.         {}
26. };
28. template <class T1, class T2>
29. inline pair<T1, T2> make_pair(T1 x, T2 y) //创建pair对象
30. {
31.         return (pair<T1, T2>(x, y));
32. }

复制代码

1. Member types
2. key_type        ->  The first template parameter (Key)       
3. mapped_type        ->  The second template parameter (T)       
4. value_type        ->  pair<const key_type,mapped_type>

复制代码

留意：map是key/value搜索场景的结构，key_type就是key，而mapped_type就是value，而value_type才是pair。
4.map的构造和迭代器

• map的构造我们关注以下几个接口即可。
  
• map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，但是不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
  

1. //empty (1) 无参默认构造
2. explicit map(const key_compare& comp = key_compare(),
3.                  const allocator_type& alloc = allocator_type());
5. //range (2) 迭代器区间构造
6. template <class InputIterator>
7. map(InputIterator first, InputIterator last,
8.         const key_compare& comp = key_compare(),
9.         const allocator_type & = allocator_type());
11. //copy (3) 拷贝构造
12. map(const map& x);
14. //initializer list (4) initializer 列表构造
15. map(initializer_list<value_type> il,
16.         const key_compare& comp = key_compare(),
17.         const allocator_type& alloc = allocator_type());
20. //迭代器是一个双向迭代器
21. iterator->a bidirectional iterator to const value_type
23. //正向迭代器
24. iterator begin();
25. iterator end();
27. //反向迭代器
28. reverse_iterator rbegin();
29. reverse_iterator rend();

复制代码

1. int main()
2. {
3.         map<int, int> m1; //无参默认构造
4.         map<int, int> m2(m1.begin(), m1.end()); //迭代器区间构造
5.         map<int, int> m3(m2); //拷贝构造
6.         map<int, int> m4 = { {1,1},{2,2} }; //列表初始化构造
8.         //1.正向迭代器
9.         auto it = m4.begin();
10.         while (it != m4.end())
11.         {
12.                 cout << it->first << " " << it->second << endl; //输出：1 2 1 2
13.                 ++it;
14.         }
15.         cout << endl;
17.         //2.反向迭代器
18.         map<int, int>::reverse_iterator rit = m4.rbegin();
19.         while (rit != m4.rend())
20.         {
21.                 cout << rit->first << " " << rit->second << endl; //输出：1 2 1 2
22.                 ++rit;
23.         }
24.         cout << endl;
26.         return 0;
27. }

复制代码

5.map的增删查

• map的增删查关注以下几个接口即可：
  
• map插入的是pair键值对数据，跟set全部不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不但仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value。
  

1. Member types
2. key_type        ->  The first template parameter (Key)        //key
3. mapped_type        ->  The second template parameter (T)        //value
4. value_type        ->  pair<const key_type,mapped_type>    //pair
6. //单个数据插入，如果已经key存在则插入失败，key存在相等value不相等也会插入失败
7. pair<iterator, bool> insert(const value_type& val);
9. //列表插入，已经在容器中存在的值不会插入
10. void insert(initializer_list<value_type> il);
12. //迭代器区间插入，已经在容器中存在的值不会插入
13. template <class InputIterator>
14. void insert(InputIterator first, InputIterator last);
16. //查找k，返回k所在的迭代器，没有找到返回end()
17. iterator find(const key_type& k);
19. //查找k，返回k的个数
20. size_type count(const key_type& k) const;
22. //删除一个迭代器位置的值
23. iterator erase(const_iterator position);
25. //删除k，k存在返回0，存在返回1
26. size_type erase(const key_type& k);
28. //删除一段迭代器区间的值
29. iterator erase(const_iterator first, const_iterator last);
31. //返回大于等于k位置的迭代器
32. iterator lower_bound(const key_type& k);
34. //返回大于k位置的迭代器
35. const_iterator upper_bound(const key_type& k) const;

复制代码

6.map构造遍历及增删查的利用

1. int main()
2. {
3.         map<string, string> dict;
5.         pair<string, string> kv1("first", "第一个"); //插入有名对象
6.         dict.insert(kv1);
8.         dict.insert(pair<string, string>("second", "第二个")); //插入匿名对象
10.         dict.insert(make_pair("sort", "排序")); //利用make_pair函数返回构造的pair对象，插入
12.         dict.insert({ "auto", "自动的" }); //C++11支持多参数隐式类型转换成pair对象，插入
14.         dict.insert({ "first", "首先" }); //"first"已经存在，插入失败
17.         //map<string, string>::iterator it = dict.begin();
18.         auto it = dict.begin();
19.         while (it != dict.end())
20.         {
21.                 //不能这样写，pair没有重载流插入和流提取，*it是pair
22.                 //cout << *it << endl;
23.                 //++it;
25.                 //cout << (*it).first <<":"<<(*it).second << endl;
27.                 //map的迭代基本都使用operator->，这里省略了一个->
28.                 //第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据
29.                 //cout << it.operator->()->first << ":" << it.operator->()->second << endl;
31.                 cout << it->first << ":" << it->second << endl; //原本是两个箭头，但是为了方便省略了一个箭头
32.                 ++it;
34.                 //it->first += 'x';   key不支持修改
35.                 //it->second += 'x';  value支持修改
36.         }
37.         cout << endl;
39.         //范围for遍历
40.         for (const auto& e : dict)
41.         {
42.                 cout << e.first << ":" << e.second << endl;
43.         }
44.         cout << endl;
46.         string str;
47.         while (cin >> str)
48.         {
49.                 auto ret = dict.find(str);
50.                 if (ret != dict.end())
51.                 {
52.                         cout << "->" << ret->second << endl;
53.                 }
54.                 else
55.                 {
56.                         cout << "无此单词，请重新输入" << endl;
57.                 }
58.         }
60.         //erase与set中的erase可以说一模一样，就不做演示了
62.         return 0;
63. }

复制代码

7.map的数据修改：重载operator[]

• 前面我提到map支持修改mapped_type数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
  
• map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key地点的iterator修改，map另有一个非常重要的修改接口operator[]，但是operator[]不但仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。
  
• 需要留意从内部实现角度，map这理把我们传统说的value值，给的是T范例，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常利用我们还是风俗将这里的T映射值叫做value。
  

1. Member types
2. key_type     ->  The first template parameter (Key)
3. mapped_type  ->  The second template parameter (T)
4. value_type   ->  pair<const key_type,mapped_type>

复制代码

1. //查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type(value)值
2. iterator find(const key_type& k);
4. //insert插入一个pair<key, T>对象
5. //1.如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，
6. //返回pair对象first是key所在结点的迭代器，second是false
8. //2.如果key不在map中，插入成功，则返回一个pair<iterator,bool>对象，
9. //返回pair对象first是新插入key所在结点的迭代器，second是true
11. //也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器
12. //那么也就意味着insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[]
15. //需要注意的是这里有两个pair，不要混淆了，
16. //一个是map底层红黑树节点中存的pair<key, T>，
17. //另一个是insert返回值pair<iterator, bool>
18. pair<iterator, bool> insert(const value_type& val);
19. mapped_type& operator[] (const key_type& k);
22. //operator的内部实现
23. mapped_type& operator[] (const key_type& k)
24. {
25.         //1.如果key不在map中，insert会插入key和mapped_type(value)的默认值，同时[]返回结点pair<iterator,bool>中存储
26.         //中的迭代器中存储的mapped_type(value)值的引用，那么我们可以通过引用修改返映射值。所以[]具备了插入 + 修改功能
27.        
28.         //2.如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向与key值相同的结点的
29.         //迭代器，同时[]返回结点中存储mapped_type(value)值的引用，所以[]具备了查找 + 修改的功能
31.         pair<iterator, bool> ret = insert({ k, mapped_type() });
32.         iterator it = ret.first;
34.         return it->second;
35. }

复制代码

1. int main()
2. {
3.         map<string, string> dict;
5.         dict.insert(make_pair("sort", "排序"));
7.         //insert不存在：插入
8.         dict["insert"]; //插入{"insert", string()}
10.         //left不存在：插入+修改
11.         dict["left"] = "左边"; //将""修改为"左边"
13.         //left存在：修改
14.         dict["left"] = "左边、剩余"; //将"左边"修改为"左边、剩余"
16.         //left存在：查找（确认left在才能这么用，否则就是插入了）
17.         cout << dict["left"] << endl; //输出：左边、剩余
19.         //boy不存在：插入
20.         cout << dict["boy"] << endl; //输出：什么都没有
22.         return 0;
23. }

复制代码

8.map的迭代器和[]功能样例

1. int main()
2. {
3.         //利用find和iterator修改功能，统计水果出现的次数
4.         string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
5.                                          "苹果", "香蕉", "苹果", "香蕉" };
7.         map<string, int> countMap;
8.         for (const auto& str : arr)
9.         {
10.                 //先查找水果在不在map中
11.                 //1、不在，说明水果第一次出现，则插入{水果, 1}
12.                 //2、在，则查找到的节点中水果对应的次数++
13.                 auto ret = countMap.find(str);
14.                 if (ret == countMap.end())
15.                         countMap.insert({ str, 1 });
16.                 else
17.                         ret->second++;
18.         }
20.         for (const auto& e : countMap)
21.         {
22.                 cout << e.first << ":" << e.second << endl;
23.         }
24.         cout << endl;
26.         return 0;
27. }

复制代码

在实践当中不太喜好用上面的代码来统计次数，而喜好用重载的[]来统计次数，如下：

1. int main()
2. {
3.         //利用[]插入+修改功能，巧妙实现统计水果出现的次数
4.         string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
5.                                          "苹果", "香蕉", "苹果", "香蕉" };
7.         map<string, int> countMap;
8.         for (const auto& str : arr)
9.         {
10.                 //[]先查找水果在不在map中
11.                 //1、不在，说明水果第一次出现，则插入{水果, 0}，同时返回次数的引用，++一下就变成1次了
12.                 //2、在，则返回水果对应的次数++
13.                 countMap[str]++;
14.         }
16.         for (const auto& e : countMap)
17.         {
18.                 cout << e.first << ":" << e.second << endl;
19.         }
20.         cout << endl;
22.         return 0;
23. }

复制代码

9.multimap和map的差别

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

1. int main()
2. {
3.         multimap<string, string> dict;
5.         //插入一定成功
6.         dict.insert({ "sort", "排序" });
7.         dict.insert({ "sort", "排序1" });
8.         dict.insert({ "sort", "排序2" });
9.         dict.insert({ "sort", "排序3" });
10.         dict.insert({ "sort", "排序" });
11.         dict.insert({ "string", "字符串" });
13.         //将sort全部删除
14.         dict.erase("sort");
16.         return 0;
17. }

复制代码

10.map解决：leetcode例题

1.随机链表的复制

随机链表的复制

解法一：不利用map容器

1. class Solution {
2. public:
3.     Node* copyRandomList(Node* head)
4.     {
5.         //1.拷贝节点插入在原节点的后面
6.         Node* cur = head;
7.         while(cur)
8.         {
9.             Node* copy = new Node(cur->val); //创建新节点
11.             copy->next = cur->next; //插入新节点
12.             cur->next = copy;
14.             cur = copy->next;
15.         }
17.         //2.修改拷贝节点的random指针的指向
18.         cur = head;
19.         while(cur)
20.         {
21.             Node* copy = cur->next;
22.             if(cur->random == nullptr) copy->random = nullptr;
23.             else copy->random = cur->random->next;
25.             cur = copy->next;
26.         }
28.         //3.把拷贝节点取下来尾插形成新链表，然后恢复原链表
29.         Node* copyHead = nullptr, *copyTail = nullptr;
30.         cur = head;
31.         while(cur)
32.         {
33.             Node* copy = cur->next;
34.             Node* next = copy->next;
36.             if(copyHead == nullptr)
37.             {
38.                 copyHead = copyTail = copy;
39.             }
40.             else
41.             {
42.                 copyTail->next = copy; //尾差
43.                 copyTail = copyTail->next;
44.             }
45.             cur->next = next;
46.             cur = next;
47.         }
48.         return copyHead;
49.     }
50. };

复制代码

解法二：利用map容器
为了控制随机指针，我们将拷贝结点链接在原节点的背面解决，背面拷贝节点还得解下来链接，非常贫苦。这里我们直接让{原结点，拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里表现了map在解决一些问题时的价值，完满是降维打击。

1. class Solution {
2. public:
3.     Node* copyRandomList(Node* head)
4.     {
5.         //创建map：原节点映射拷贝节点
6.         map<Node*, Node*> nodeMap;
8.         //1.拷贝新链表
9.         Node* copyHead = nullptr, *copyTail = nullptr;
10.         Node* cur = head;
11.         while(cur)
12.         {
13.             if(copyTail == nullptr)
14.             {
15.                 copyHead = copyTail = new Node(cur->val);
16.             }
17.             else
18.             {
19.                 copyTail->next = new Node(cur->val); //尾差新节点
20.                 copyTail = copyTail->next;
21.             }
22.             //原节点映射拷贝节点
23.             nodeMap[cur] = copyTail; //或者nodeMap.insert({cur, copyTail});
25.             cur = cur->next;
26.         }
28.         //2.利用映射处理random
29.         cur = head;
30.         Node* copy = copyHead;
31.         while(cur)
32.         {
33.             if(cur->random == nullptr) copy->random = nullptr;
34.             else copy->random = nodeMap[cur->random];
36.             cur = cur->next;
37.             copy = copy->next;
38.         }
39.         return copyHead;
40.     }
41. };

复制代码

2.前K个高频单词

前K个高频单词

本题目我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特别要求，如果不同的单词有雷同出现频率，按字典顺序排序（string从小到大排序）。
解法一：map+排序
用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数雷同的单词，字典序小的在前面，字典序大的在背面。那么我们将数据放到vector中用一个稳固的排序就可以实现上面特别要求，但是sort底层是快排，是不稳固的，所以我们要用stable_sort，他是稳固的。

1. class Solution {
2. public:
3.     struct kvCompare
4.     {
5.         bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
6.         {
7.                 //要实现int的降序用的是>
8.                 //int相等: 要实现string的升序用的是<
9.             return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
10.         }
11.     };
13.     vector<string> topKFrequent(vector<string>& words, int k)
14.     {
15.         map<string, int> countMap;
16.         for(auto& e : words) countMap[e]++; //统计单词出现的次数
18.         //利用数组进行排序：vector支持随机迭代器，map不支持随机迭代器
19.         vector<pair<string, int>> v(countMap.begin(), countMap.end());
21.         //需要用pair的第二个int数据排降序：自己实现仿函数（函数传的是仿函数对象：可以传一个匿名对象）
22.         //v是由countMap用迭代器区间初始化的，满足字典序
23.         //而题目要求次数出现多的排在前面，若次数出现相等的情况下，按照字典序排
24.         //若用普通的sort(快排)是不稳定的，算法库中有稳定的排序stable_sort(大概是归并)可以满足题目要求
25.         //stable_sort(v.begin(), v.end(), kvCompare());
27.         //或者修改仿函数也可以完成目的：int排降序就是>; int相等的话: string排升序就是<
28.         sort(v.begin(), v.end(), kvCompare());  
30.         vector<string> ret;
31.         for(int i = 0; i < k; i++)
32.         {
33.             ret.push_back(v[i].first); //尾插前K个高频单词
34.         }
35.         
36.         return ret;
37.     }
38. };

复制代码

解法二：map+优先级队列
将map统计出的次数的数据放到priority_queue中来选出前k个。利用仿函数强行控制次数相称的，字典序小的在前面。

1. class Solution {
2. public:
3.     struct kvCompare
4.     {
5.         bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
6.         {
7.             //注意：堆的逻辑是发过来的
8.             //要实现int的大堆用的是<;
9.             //int相等时：要实现string的小堆用的是>;
10.             return kv1.second < kv2.second || (kv1.second == kv2.second && kv1.first > kv2.first);
11.         }
12.     };
14.     vector<string> topKFrequent(vector<string>& words, int k)
15.     {
16.         map<string, int> countMap;
17.         for(auto& e : words) countMap[e]++; //统计单词出现的次数
19.         //利用优先级队列：将int大的放在上面; 若int相等: 将字典序小的放上面
20.         //模版传的是类型：直接传仿函数，仿函数就是一个类
21.         priority_queue<pair<string, int>, vector<pair<string, int>>, kvCompare> p(countMap.begin(), countMap.end());
23.         vector<string> ret;
24.         for(int i = 0; i < k; i++)
25.         {
26.             ret.push_back(p.top().first);
27.             p.pop();
28.         }
30.         return ret;
31.     }
32. };

复制代码

解法三：也是map+优先级队列
建立小堆，再不绝出堆顶数据，实现堆中满是满足要求的数据。

1. class Solution {
2. public:
3.     struct kvCompare
4.     {
5.         bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
6.         {
7.             //要实现int的小堆用的是>;
8.             //int相等时：要实现string的大堆用的是<;
9.             return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
10.         }
11.     };
13.     vector<string> topKFrequent(vector<string>& words, int k)
14.     {
15.         map<string, int> countMap;
16.         for(auto& e : words) countMap[e]++;
18.         priority_queue<pair<string, int>, vector<pair<string, int>>, kvCompare> p; //小堆
20.         for(auto& e : countMap)
21.         {
22.             p.push(e); //入堆
23.             if (p.size() > k) //若堆中的个数大于K
24.             {
25.                 p.pop(); //删除堆顶：小的出堆
26.             }
27.         }
29.         vector<string> ret(k);
30.         for (int i = k - 1; i >= 0; i--)
31.         {
32.             ret[i] = p.top().first; //将小的放在后面，大的放在前面
33.             p.pop(); //出堆
34.         }
36.         return ret;
37.     }
38. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。