【C++篇】map和set的利用

1，序列式容器和关联式容器

   前面我们已经相识过STL中的部分容器：string,vector,list,queue等等，这些容器称为序列式容器，由于逻辑布局为线性序列的数据布局，两个位置存储的值之间一样平常没有精密接洽，好比交换一下，他仍然是序列式容器。
  关联式容器也是用来存储数据的，与序列式容器差异的是，关联式容器逻辑上一样平常好坏线性布局的，两个位置的值由精密接洽，交换一下，它的存储布局就被粉碎了。而这种容器的元素是通过关键字来举行访问和生存的。
  关联式容器由map/set系列，以及 unordered_map/unordered_set系列
  本篇讲的map/set,其底层是红黑树，红黑树底层是一颗平衡二叉搜刮树(详细可看之前的文章—二叉搜刮树）。set是key搜刮场景下的布局，map是key/value搜刮场景下的布局。
2，set系列的利用

2.1,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),迭代器遍历走的是中序遍历，以是是有序的
2.2,set的构造和迭代器

  

1. //无参构造
2. explicit set (const key_compare& comp = key_compare(),
3.               const allocator_type& alloc = allocator_type());

复制代码

1. //迭代器区间构造
2. template <class InputIterator>
3.   set (InputIterator first, InputIterator last,
4.        const key_compare& comp = key_compare(),
5.        const allocator_type& = allocator_type());

复制代码

1. //initializer_list列表构造  其中value_type就是关键字key
2. set (initializer_list<value_type> il,
3.      const key_compare& comp = key_compare(),
4.      const allocator_type& alloc = allocator_type());

复制代码

1. //拷贝构造
2. set (const set& x);

复制代码

1. 官方文档示例：

复制代码

   //迭代器是一个双向迭代器
  

iterator	a bidirectional iterator to value_type	convertible to const_iterator
const_iterator	a bidirectional iterator to const value_type

  

1. //正向迭代器      
2.        iterator begin() noexcept;
3. const_iterator begin() const noexcept;   
4.        iterator end() noexcept;
5. const_iterator end() const noexcept;

复制代码

//反向迭代器

1.       reverse_iterator rbegin() noexcept;
2. const_reverse_iterator rbegin() const noexcept;

复制代码

1.       reverse_iterator rend() noexcept;
2. const_reverse_iterator rend() const noexcept;

复制代码

set支持正向和反向迭代遍历，遍历默认按升序序次，由于底层是⼆叉搜刮树，迭代器遍历走的中 序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改 关键字数据，粉碎了底层搜刮树的布局
2.3,set的增删查

   //set中的key_type和value_type指的都是关键字key，它的范例是T
  key_type -> The first template parameter (T)
  value_type -> The first template parameter (T)
  2.3.1,inset插入 

   // 单个数据插入，假如已经存在则插⼊失败

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

复制代码

// 列表插入，已经在容器中存在的值不会插入

1. void insert (initializer_list<value_type> il);

复制代码

// 迭代器区间插入，已经在容器中存在的值不会插入
  

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

复制代码

代码示例： 

1. #include<iostream>
2. #include<set>
3. #include <string>
4. using namespace std;
6. int main()
7. {
8.     //去重+升序排序
9.     set<int> s;
10.     //去重+降序排序
11.     //set<int, greater<int>> s;
13.     s.insert(5);
14.     s.insert(2);
15.     s.insert(7);
16.     s.insert(5);
17.     //迭代器遍历
18.     auto it = s.begin();
19.     while (it != s.end())
20.     {
21.         cout << *it << " ";
22.         it++;
23.     }
24.     cout << endl;
25.     //重复的值不会插入
26.     s.insert({ 2,8,3,9 });
27.     for (auto e : s)
28.     {
29.         cout << e << " ";
30.     }
31.     cout << endl;
32.     //按ASCLL码大小比较
33.     set<string> str = { "sort","insert","add" };
34.     for (auto& e : str)
35.         cout << e << " ";
36.     cout << endl;
37.     return 0;
38. }

复制代码

 

2.3.2,find+erase 

   // 查找 val ，返回 val 地点的迭代器，没有找到返回 end()

1. iterator  find (const value_type& val);

复制代码

// 查找 val ，返回 Val 的个数

1. size_type count (const value_type& val) const;

复制代码

// 删除⼀个迭代器位置的值

1. iterator  erase (const_iterator position);

复制代码

// 删除 val ， val 不存在返回 0 ，存在返回 1

1. size_type erase (const value_type& val);

复制代码

// 删除⼀段迭代器区间的值

1. iterator  erase (const_iterator first, const_iterator last);

复制代码

// 返回⼤于等 val 位置的迭代器

1. iterator lower_bound (const value_type& val);

复制代码

// 返回⼤于 val 位置的迭代器

1. iterator upper_bound (const value_type& val);

复制代码

利用示例1：

1. #include<iostream>
2. #include<set>
3. #include <string>
4. using namespace std;
5. int main()
6. {
7.         set<int> s = { 4,2,7,2,8,5,9 };
8.         for (auto x: s)
9.         {
10.                 cout << x << " ";
11.         }
12.         cout << endl;
14.         cout << "删除最小值:";
15.         s.erase(s.begin());
16.         for (auto x : s)
17.         {
18.                 cout << x << " ";
19.         }
20.         cout << endl;
22.         int x1 = 2;
23.         int num = s.erase(x1);
24.         if (num == 0)
25.                 cout << "x1不存在!" << endl;
27.         int x2 = 10;
28.         auto pos = s.find(x2);
29.         if (pos == s.end())
30.                 cout << "x2不存在" << endl;
31.         //利用count实现快速查找
32.         /*if(s.count(x2))
33.         {
34.                 cout << "x在" << endl;
35.         }
36.         else
37.         {
38.                 cout << "x不存在" << endl;
39.         }*/
40.         return 0;
41. }

复制代码

 

利用示例2：

1. #include<iostream>
2. #include<set>
3. using namespace std;
5. int main()
6. {
7.         set<int> myset;
8.         for (int i = 1; i < 10; i++)
9.                 myset.insert(i * 10);
10.         for (auto e : myset)
11.                 cout << e << " ";
12.         cout << endl;
14.         //实现查找[itlow,itup]包含[30,60]区间
15.         //>=30的位置
16.         auto itlow = myset.lower_bound(30);
17.         //>60的位置
18.         auto itup = myset.upper_bound(60);
19.         //删除这段区间
20.         myset.erase(itlow, itup);
21.         for (auto e : myset)
22.                 cout << e << " ";
23.         cout << endl;
24.         return 0;
25. }

复制代码

 

2.4,multiset和set的差异

multiset和set的使⽤根本完全雷同，重要区别点在于multiset支持值冗余，那么 insert/find/count/erase都围绕着支持值冗余有所差异，详细参看下⾯的样例代码明确。

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

复制代码

2.5,干系oj题 

1. class Solution {
2. public:
3.     ListNode *detectCycle(ListNode *head) {
4.         set<ListNode*> s;
5.         ListNode* cur=head;
6.         while(cur)
7.         {
8.             auto it=s.insert(cur);
9.             if(it.second==false)
10.             return cur;
12.             cur=cur->next;
13.         }
14.         return nullptr;
15.     }
16. };

复制代码

3，map系列的利用

3.1,map类的先容

map的声明如下，Key就是map底层关键字的范例，T是map底层value的范例。
map默认要求Key支持比力，假如不支持大概须要的话可以自行实现仿函数传给第⼆个模版参数.
map底层存储数据的 内存是从空间设置器申请的。⼀般情况下，我们都不须要传后两个模版参数
map底层是⽤红⿊树实现，增删查改服从是O(logN),迭代器走的中序遍历。
  

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;

复制代码

3.2,pair范例的先容

map底层的红⿊树节点中的数据，使⽤pair存储键值对数据。
  

1. template <class T1, class T2> struct pair;

复制代码

 

3.3,map的构造和迭代器

map的⽀持正向和反向迭代遍历，遍历默认按key的升序序次，由于底层是⼆叉搜刮树，迭代器遍历⾛ 的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，粉碎了底层搜刮树的布局。
  

1. //无参构造
2. explicit map (const key_compare& comp = key_compare(),
3.               const allocator_type& alloc = allocator_type());

复制代码

1. //迭代器区间构造
2. template <class InputIterator>
3.   map (InputIterator first, InputIterator last,
4.        const key_compare& comp = key_compare(),
5.        const allocator_type& alloc = allocator_type());

复制代码

1. //拷贝构造
2. map (const map& x);

复制代码

1. //列表构造
2. map (initializer_list<value_type> il,
3.      const key_compare& comp = key_compare(),
4.      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.4,map的增删查

map增接⼝，插⼊的pair键值对数据，跟set全部差异，但是查和删的接⼝只⽤关键字key跟set是完全 雷同的，不外find返回iterator，不但仅可以确认key在不在，还找到key映射的value，同时通过迭代 还可以修改value。
   //key_type就是关键字，value_type就是pair<key,value>
  //mapped_type就是关键字Key映射的value值
  key_type -> The first template parameter (Key)
  mapped_type -> The second template parameter (T）
  value_type -> pair<const key_type,mapped_type>
     // 单个数据插⼊，假如已经 key 存在则插⼊失败 ,key 存在相称  value不相称也会插入失败

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

复制代码

// 列表插⼊，已经在容器中存在的值不会插⼊
  void insert (initializer_list<value_type> il);
  
  // 迭代器区间插⼊，已经在容器中存在的值不会插⼊

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

复制代码

// 查找 k ，返回 k 地点的迭代器，没有找到返回 end()

1. iterator find (const key_type& k);

复制代码

// 查找 k ，返回 k 的个数

1. size_type count (const key_type& k) const;

复制代码

// 删除⼀个迭代器位置的值

1. iterator  erase (const_iterator position);

复制代码

// 删除 k ， k 存在返回 0 ，存在返回 1

1. size_type erase (const key_type& k);

复制代码

// 删除⼀段迭代器区间的值

1. iterator  erase (const_iterator first, const_iterator last);

复制代码

// 返回⼤于等 k 位置的迭代器

1. iterator lower_bound (const key_type& k);

复制代码

// 返回⼤于 k 位置的迭代器

1. iterator upper_bound (const key_type& k);

复制代码

3.5,map的数据修改 

map支持修改value数据，不支持修改关键字key，修改关键字数据，会粉碎底层搜刮树的布局
map第⼀个支持修改的方式时通过迭代器，迭代器遍历时大概find返回key地点的iterator修改，map 另有⼀个非常告急的修改接口operator[]，但是operator[]不但仅⽀持修改，还支持插入数据和查找数据，以是他是⼀个多功能复合接口
map的迭代器和[]功能样例1：

1. #include <map>
2. #include <iostream>
3. using namespace std;
5. int main()
6. {
7.         string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西瓜",
8.                 "苹果","香蕉","苹果","香蕉" };
9.         //记录水果和水果对应的出现次数
10.         map<string, int> countMap;
11.         for (const auto& str : arr)
12.         {
13.                 //先查找对应水果在不在
14.                 auto ret = countMap.find(str);
15.                 //不存在就插入对应{水果,1}
16.                 //存在就让水果对应次数++
17.                 if (ret == countMap.end())
18.                         countMap.insert({ str,1 });
19.                 else
20.                         ret->second++;
21.         }
23.         for (auto& e : countMap)
24.         {
25.                 cout << e.first << ":" << e.second << endl;
26.         }
27.         cout << endl;
29.         return 0;
30. }

复制代码

 样例2：

2. #include <map>
3. #include <iostream>
4. #include <string>
5. using namespace std;
7. int main()
8. {
9.         map<string, string> dict;
11.         //make_pair(x,y) 用x,y构造出一个pair类型
12.         dict.insert(make_pair("sort", "排序"));
14.         //insert不存在，插入{"insert",string()}
15.         dict["insert"];
17.         //插入+修改
18.         dict["left"] = "左边";
20.         //修改
21.         dict["left"] = "左边，剩余";
23.         //key存在->查找
24.         cout << dict["left"] << endl;
26.         return 0;
27. }

复制代码

3.6,multimap和map的差异

multimap和map的使⽤根本完全雷同，重要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如 find时，有多个key，返回中序第一个。其次就是multimap不⽀持[]，由于⽀持key冗余，[]就只能支持插入了，不能支持修改
3.7,干系oj题

解法一：

1. class Solution {
2. public:
3. struct cmp
4. {
5.     bool operator()(const pair<string,int>& p1,const pair<string,int>& p2)
6.     {
7.         return p1.second>p2.second;
8.     }
9. };
10.     vector<string> topKFrequent(vector<string>& words, int k) {
11.         map<string,int> countMap;
12.         for(auto& e:words)
13.         countMap[e]++;
15.         vector<pair<string,int>> v(countMap.begin(),countMap.end());
16.         //sort(v.begin(),v.end())
17.         //sort底层是快排，不稳定，需用stable_sort
18.         stable_sort(v.begin(),v.end(),cmp());
20.         vector<string> str;
21.         for(int i=0;i<k;i++)
22.         str.push_back(v[i].first);
24.         return str;
25.     }
26. };

复制代码

 解法二：利用仿函数强行控制次数

1. class Solution {
2. public:
3. struct cmp
4. {
5.     bool operator()(const pair<string,int>& p1,const pair<string,int>& p2)
6.     {
7.         return p1.second>p2.second||(p1.second==p2.second&&p1.first<p2.first);
8.     }
9. };
10.     vector<string> topKFrequent(vector<string>& words, int k) {
11.         map<string,int> countMap;
12.         for(auto& e:words)
13.         countMap[e]++;
15.         vector<pair<string,int>> v(countMap.begin(),countMap.end());
16.         //仿函数控制降序，同时控制次数相等，字典序小的在前面
17.         sort(v.begin(),v.end(),cmp());
19.         vector<string> str;
20.         for(int i=0;i<k;i++)
21.         str.push_back(v[i].first);
23.         return str;
24.     }
25. };

复制代码