C++之旅-set和map掌握篇
目录
前言
序列式容器和关联式容器前面已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为 序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间意一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是， 关联式容器逻辑结构通常是非线性结构， 两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。本章节讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构， map是key/value搜索场景的结构。
使用set和map头文件
#include <set> #include <map>1.set的使用
1.1set类的介绍
set的声明如下，T就是set底层关键字的类型set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。一般情况下，都不需要传后两个模版参数。set底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。
template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;
1.2 set的构造和迭代器
set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
底层代码展示
// empty (1) ⽆参默认构造 explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> 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();1.3 set的增删查
相关函数原参数展示
Member types key_type -> The first template parameter (T) value_type -> The first template parameter (T) // 单个数据插⼊，如果已经存在则插⼊失败 pair<iterator,bool> insert (const value_type& val); // 列表插⼊，已经在容器中存在的值不会插⼊ void insert (initializer_list<value_type> il); // 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 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; // 删除一个迭代器位置的值 iterator erase (const_iterator position); // 删除val，val不存在返回0，存在返回1 size_type erase (const value_type& val); // 删除一段迭代器区间的值 iterato 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;学习了vector/list等容器的使用，STL容器接口设计，高度相似，所以上手很容易
1.4 代码练习
1.4.1 set的构造，插入与删除
#include <iostream> #include <vector> #include <set> using namespace std; //int main() { // //默认从小到大排列 // set<int> s1{ 1,23,4 }; // for (auto s : s1) { // cout << s << endl; // } // int arr[] = { 1,2,4,3,7,5,9 }; // //修改比较器 // set<int,greater<int>>s2(arr, arr + sizeof(arr) / sizeof(int)); // set<int> ::iterator it = s2.begin(); // //auto it = s2.begin(); // while (it != s2.end()) { // cout << *it << " "; // it++; // } // set<int>s3(s2.begin(), s2.end()); // set<int>s4 = s1; // return 0; //} int main() { set<int> s; s.insert(19); s.insert(5); s.insert(10); int arr[] = { 2,6,4,8 ,5}; //去重插入 s.insert(arr, arr + 4); for (auto e : s) cout << e << " "; cout << endl; set<string> str({ "hello", "world", "love" }); // 遍历string比较ascll码大小遍历 for (auto& e : str) { cout << e << " "; } cout << endl; int n; cin >> n; int num = s.erase(n); if (num == 0) cout << n << "不存在" << endl; else cout << "删除成功" << endl; for (auto e : s) cout << e << " "; return 0; }
不能给常量赋值
set<int> ::iterator it = s2.begin(); //auto it = s2.begin(); while (it != s2.end()) { cout << *it << " "; *it = 1;//错误写法 it++; }
1.4.2 set 的find的使用样例，与erase结合
int main() { set<int> s = { 4,2,7,2,8,5,9 }; for (auto e : s) { cout << e << " "; } cout << endl; auto pos = s.find(7); if (pos != s.end()) { s.erase(pos); } for (auto e : s) { cout << e << " "; } cout << endl; int x; cout << "删除的数" << endl; cin >> x; auto pos1 = find(s.begin(), s.end(), x);//O(N)查找 while (pos1 != s.end()) { cout << x << "存在，并删除成功！" << endl; break; } for (auto e : s) { cout << e << " "; } cout << endl; // 利⽤count间接实现快速查找 int y; cin >>y; if (s.count(y)) { cout << y << "在！" << endl; } else { cout << y << "不存在！" << endl; } return 0; }我们通过了set自带的查找以及算法库的查找，然后也用了set中的count进行了间接查找，通过数据的次数进行判断。
1.4.3 set获取区间值函数的应用
/ 返回大于等val位置的迭代器 iterator lower_bound (const value_type& val) const; // 返回大于val位置的迭代器 iterator upper_bound (const value_type& val) const;两个函数的区间是左闭右开的
int main() { set<int>s; for (int i = 1; i <= 9; i++) { s.insert(i * 10); } auto it = s.begin(); while (it != s.end()) { cout << *it << " "; it++; } cout << endl; auto itlow = s.lower_bound(30); //set<int>:: iterator itup = s.upper_bound(70); auto itup = s.upper_bound(70); s.erase(itlow, itup); for (auto e : s) { cout << e << " "; } //lower_bound（30） 返回一个迭代器 30，而 upper_bound（70） 返回一个迭代器 80。 return 0; }
1.5 multiset和set的差异
multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
int main() { // 相⽐set不同的是，multiset是排序，但是不去重 multiset<int> s = { 4,2,7,2,4,8,4,5,4,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; return 0; }
1.6 set强化练习（上链接！！！）
环形链表
在数据结构链表篇，我们采用了双指针的算法，先定义快慢指针判断链表是否带环，如果相遇，则链表有环存在，然后定义一个meet指针在相遇的位置，头结点和meet 同时往前移动，相遇的时候就是环的位置。
在学习了set之后，我们可以将节点存放到set中，当set中节点个数重复的时候说明有环的存在，就可以返回该节点位置。
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 NULL; } };2.map的使用
2.1 map类的介绍
map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是 O( logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key,T> > // map::allocator_type > class map;2.2 pair类型
map底层的红黑树节点中的数据，使用pair<Key, T>存储键值对数据。
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) ); }2.3 map的构造
map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历⾛的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造 explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> 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();2.4 map的增删查
map增接口， 插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value
Member types 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不相等也会插⼊失败 pair<iterator,bool> insert (const value_type& val); // 列表插⼊，已经在容器中存在的值不会插⼊ void insert (initializer_list<value_type> il); // 迭代器区间插⼊，已经在容器中存在的值不会插⼊ template <class InputIterator> void insert (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; 2.5 map 的数据修改
前面提到map支持修改mapped_type 数据，不支持修改key数据，修改关键字数据，破坏了底层搜 索树的结构。 map第一个支持修改的方式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数 据，所以他是一个多功能复合接口。
需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为 mapped_type。而value_type是红黑树结点中存储的pair键值对值
Member types key_type -> The first template parameter (Key) mapped_type -> The second template parameter (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 the
element with an equivalent key in the map. The pair::second element in the pair
is set to true if a new element was inserted or false if an equivalent key
already 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; }2.6 代码练习
2.6.1 构造遍历及增删查使用样例
int main() { map<string, string>dict{ { "left","左边"},{"right", "右边"}, {"insert", "插入"}}; pair<string, string>kv( "first","第一个" ); dict.insert(kv); dict.insert(pair<string, string>{"second", "第二个"}); dict.insert(make_pair("third", "第三个")); dict.insert({ "string","字符串" }); // 插入时只看key，value不相等不会更新 dict.insert({ "left", "自动的xxxx" }); map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { //cout << (*it).first << "->" << (*it).second << endl; //it->first+='x'; key不能修改 //it->second += 'x';//值可以修改 cout << it->first << ":" << it->second << endl; // << it.operator->()->first << ":"<<it.operator->()->second << endl; it++; } dict.insert({ "string","字符串串" });//string存在,插入失败 cout << "输入查询的单词" << endl; string s; while (cin >> s) { auto ret = dict.find(s); if (ret != dict.end()) { cout << "->" << ret->second << endl; break; } else { cout << "没有该单词，请重新输入！" << endl; } } dict.erase("second"); auto it1 = dict.find("first"); dict.erase(it1); for (auto s : dict) { cout << s.first << "->" << s.second << endl; } return 0; }2.6.2 map的迭代器和[]功能
前提引入
如果我们要统计一个物件的数目，我们就可以采map结构，例如下面代码：
int main() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int>countMap; for (auto&s : arr) { auto pos = countMap.find(s); if (pos == countMap.end()) { countMap.insert({ s,1 }); } else pos->second++; } for (auto s : countMap) { cout << s.first << "->" << s.second << endl; } return 0; }先查找水果在不在map中1、不在，说明水果第一次出现，则插入{水果, 1}2、在，则查找到的节点中水果对应的次数++
这里使用常见的insert来进行数数，通过对[ ]的认识，我们可以利用它的特点同样的来实现计数的功能。
int main() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int>cm; for (const auto& str : arr) { cm[str]++; } for (auto& s : cm) { cout << s.first << "->" << s.second << endl; } return 0; }[ ]拆分讲解
int main() { map<string, string> dict; dict.insert(make_pair("sort", "排序")); // key不存在->插入 {"insert", string()} dict["insert"]; // 插入+修改 dict["left"] = "左边"; // 修改 dict["left"] = "左边、剩余"; // key存在->查找 cout << dict["left"] << endl; for (auto s : dict) { cout << s.first << "->" << s.second << endl; } return 0; }2.6 multimap和map的差异
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如 find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。
2.7 map强化练习
前k个高频单词
解决思路1用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词， 字典序小的在前面，字典序大的在后面。那么将数据放到vector中用一个稳定的排序就可以实现 上面特殊要求，但是sort底层是快排，是不稳定的，所以要用stable_sort，是稳定的。
代码1：
class Solution { public: static bool compare(const pair<string,int>&s1,const pair<string,int>&s2){ return s1.second>s2.second; } vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> m; for(auto &s:words){ m[s]++; } vector<pair<string,int>> v(m.begin(),m.end()); stable_sort(v.begin(),v.end(),compare); vector<string>v1; for(int i=0;i<k;i++){ v1.push_back(v[i].first); } return v1; } };代码2：
class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { return x.second > y.second; } }; 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()); // 仿函数控制降序 stable_sort(v.begin(), v.end(), Compare()); //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; } };解决思路2
将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数 强行控制次数相等的，字典序小的在前面。
class Solution { public: static bool compare(const pair<string,int>&s1,const pair<string,int>&s2){ return s1.second>s2.second ||(s1.second==s2.second && s1.first<s2.first); } vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> m; for(auto &s:words){ m[s]++; } vector<pair<string,int>> v(m.begin(),m.end()); sort(v.begin(),v.end(),compare); vector<string>v1; for(int i=0;i<k;i++){ v1.push_back(v[i].first); } return v1; } };结束语
本节内容就到此结束啦，内容很多，其实是代码有点多，希望通过本节内容的学习大家对set和map有了深刻的理解认识，下节我们将对map和set的底层进行认识，实现自己的map和set。
最后感谢各位友友们的支持！！！谢谢三连！！！
