1.set 系列的使用
(1) set简述
set的特性是，所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值（value）和键值（key），set 元素的键值就是实值，实值就是键值。set不允许两个元素有相同的键值。
① set 的声明如下，T 就是 set 底层关键字的类型② set 默认要求 T 支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模 版参数③ set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参 数。④ 一般情况下，我们都不需要传后两个模版参数。⑤ set 底层是用红黑树实现，增删查效率是 O(logN) ，迭代器遍历是走的搜索树的中序，所以是有序 的。
template < class T, // set::key_type/value_type (是用的是同一个比较函数)class Compare = less<T>, // 缺省情况下采用递增排序class Alloc = allocator<T> // set::allocator_type
> class set;(2) set 的构造和迭代器
set 的迭代器支持正向和反向迭代遍历， 遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for。
我们可以通过 set 的迭代器改变 set 的元素值吗？不行， 因为 set 元素值就是其键值，关系到 set 元素的排列规则。如果任意改变 set 元素值，会严重破坏 set 组织。 以后你会在 set 源代码中看到，set<T>::iterator 被定义成底层 RB-tree 的 const_iterator，杜绝写入操作。换句话说，set iterators 是一种 constant iterators。
// 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();(3) set的增删查
set 拥有 list 相同的某些性质：当客户端对它进行元素新增操作（insert）或删除（erase）时，操作之前的所有迭代器，在操作完成之后都依然有效。当然，被删除的那个元素的迭代器是个例外。
对于关联式容器，应该使用其所提供的find函数来搜寻元素（O(logN)），会比是用STL算法 find( ) 更有效率。因为STL算法 find( ) 只是循序搜寻（O(N)）。
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的个数，所以返回值只能是1
size_type count(const value_type& val) const;// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase(const value_type& val);
// 删除⼀段迭代器区间的值
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;
(4) insert 和迭代器使用样例
#include<iostream>
#include<set>
using namespace std;int main()
{// 去重+升序set<int> st;// 去重 + 降序(给一个大于的仿函数)//set<int, greater<int>> s;st.insert(4);st.insert(4);st.insert(5);st.insert(2);st.insert(9);st.insert(6);auto it = st.begin();while (it != st.end()){cout << *it << " ";++it;}cout << endl;st.insert({ 2,1,4,5,7 });for (auto e : st){cout << e << " ";}cout << endl;set<string> strset = { "left","insert","erase" };for (auto s : strset){cout << s << " ";}cout << endl;return 0;
}(5) erase 和 find 的使用样例
void testerase()
{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;size_t num = s.erase(x); // 删除val，val不存在返回0，存在返回1if (num == 0){cout << "该元素不存在" << 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;
}void testfind()
{set<int> s = { 40,20,70,20,80,50,90 };for (auto e : s){cout << e << " ";}cout << endl;int x;cin >> x;// 算法库的查找 O(N)auto pos1 = find(s.begin(), s.end(), x);// set⾃⾝实现的查找 O(logN)auto pos2 = s.find(x);// 利用count间接实现快速查找if (s.count(x)){cout << x << "在！" << endl;}else{cout << x << "不存在！" << endl;}// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 >= 30auto itlow = s.lower_bound(30); // 该函数将返回一个不小于val的第一个元素的迭代器// 返回 > 60auto itup = s.upper_bound(60); // 该函数会向大于val的第一个元素返回一个迭代器// 删除这段区间的值s.erase(itlow, itup);for (auto e : s){cout << e << " ";}cout << endl;
}(6) multiset 和 set 的差异
multiset 与 set 的使用基本类似，主要区别点在于 multiset 允许键值冗余，那么insert / erase / find / count 围绕着支持键值冗余都会有所差异。
void testmultiset()
{// 相⽐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给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;
}(7) 349. 两个数组的交集
class Solution {
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());// 两个指针分别指向两个数组，比较大小，小的++，相等的就是交集auto p1 = s1.begin();auto p2 = s2.begin();vector<int> res;while(p1 != s1.end() && p2 != s2.end()){if(*p1 > *p2)++p2;else if (*p1 < *p2)++p1;else{res.push_back(*p1);++p1;++p2; }}return res;}
};(8) 142. 环形链表 II
class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur= head;while(cur)//一个一个插入{// 返回值：1.插入位置的迭代器 2.插入的布尔值auto ret = s.insert(cur); if(ret.second == 0)return cur;// 重复位置就是入环节点cur = cur->next;}return nullptr;}
};2.map 系列的使用
(1) map 简述
map 的特性是，所有元素都会根据元素的键值自动被排序。map 的所有元素都是pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。map 不允许两个元素拥有相同的键值。
map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型， set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数， map底层存储数据的 内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。 map底层是用红黑树实现，增删查改效率是 O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
template < class Key, // map::key_typeclass T, // map::mapped_typeclass Compare = less<Key>, // map::key_compareclass Alloc = allocator<pair<const Key, T> > //map::allocator_type
> class map;(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));
}(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();(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;(5) map 的数据修改
前面我提到map支持修改mapped_type 数据，不支持修改key数据，修改关键字数据，破坏了底层搜 索树的结构。 map第一个支持修改的方式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改 ，map 还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数 据，所以他是一个多功能复合接口。需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为mapped_type，而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的 T映射值叫做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>① find
// 查找k，返回k所在的迭代器，没有找到返回end()，
// 如果找到了通过iterator可以修改key对应mapped_type值
iterator find (const key_type& k);② insert
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);③ operator[] 内部实现
1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能
2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能
mapped_type& operator[] (const key_type& k);
// operator的内部实现
mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}(6) 构造遍历及增删查使⽤样例
#include<iostream>
#include<map>
using namespace std;
int main()
{// initializer_list构造及迭代遍历map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插入"},{ "string", "字符串" } };//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){// map的迭代基本都使用operator->,这⾥省略了一个->// 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;// insert插入pair对象的4种方式，对比之下，最后一种最⽅便pair<string, string> kv1("first", "第一个");dict.insert(kv1);dict.insert(pair<string, string>("second", "第⼆个"));dict.insert(make_pair("sort", "排序"));dict.insert({ "auto", "自动的" });// "left"已经存在，插入失败dict.insert({ "left", "左边，剩余" });// 范围for遍历for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;}else{cout << "无此单词，请重新输⼊" << endl;}}return 0;
}(7) map的迭代器和[]功能样例
举例[ ]插入+修改功能挺吊的！
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插⼊ {"insert", string()}dict["insert"];// 插入+修改(kv存储)dict["left"] = "左边";// 修改dict["left"] = "左边、剩余";// key存在->查找cout << dict["left"] << endl;// 利⽤[]插入+修改功能，巧妙实现统计谁水果出现的次数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;return 0;
}(8) multimap和map的差异
multimap和map的使用基本完全类似，主要区别点在于 multimap支持关键值key冗余 ，那么 insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如 find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支 持插入了，不能支持修改。
(9) 138. 随机链表的复制
这里我们直接让{原结点,拷贝结点}建立映射关系放到map中，控制随机指 针会非常简单方便，这里体现了map在解决一些问题时的价值。下面代码我用来两种方式实现，但原理是相同的。
class Solution {
public:Node* copyRandomList(Node* head) {Node* cur = head;Node* copyhead = nullptr;Node* copytail = nullptr;map<Node*,Node*> mp;// 1、先将这些原节点放到map里(next顺序)while(cur){if(copytail == nullptr){ // 拷贝第一个节点copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}// 原节点cur和拷贝节点coptail -> kv存储// mp 中没有cur，插入<cur,copytail>// 插入的cur仍会保留其特性(next,random,val)mp[cur] = copytail; cur = cur->next; } // 2、处理copy链表的random指针cur = head; // 重新指向原头Node* copycur = copyhead;while(cur){if(cur->random == nullptr){copycur->random = nullptr; }else{ // 映射关系，查找功能// 1.[]查找cur的random指针指向的节点(在map中)// 2.将拷贝链表random指针指向该节点copycur->random = mp[cur->random];}cur = cur->next;copycur = copycur->next;}return copyhead;}
};递归实现：
class Solution {
public:map<Node*,Node*> mp; Node* copyRandomList(Node* head) {if(head == nullptr)return nullptr;if(!mp.count(head)){Node* copy = new Node(head->val);mp[head] = copy;copy->next = copyRandomList(head->next);// 上一行代码的回溯结束后，已经将所有原节点与拷贝节点//建立映射关系并插入map里了// 1.下一行的所有回溯不会进入if语句里，// 而是执行最后一行返回语句,回溯上来就是mp[head->random]// 2.[]作用是在map中查找head的random指向的节点// 3. 将拷贝链表random指针指向该节点copy->random = copyRandomList(head->random);}return mp[head];}
};(10) 692. 前K个高频单词
方法1：
⽤排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词， 字典序⼩的在前⾯，字典序⼤的在后⾯。那么我们将数据放到vector中⽤⼀个稳定的排序就可以实现 上⾯特殊要求，但是sort底层是快排，是不稳定的，所以我们要⽤stable_sort，他是稳定的。
class Solution {
public:// 仿函数控制升序struct Compare{bool operator()(const pair<string,int>& x,const pair<string,int>& y){return x.second > y.second;}};vector<string> topKFrequent(vector<string>& words, int k) {// 1.放入map实现按字典序排序map<string,int> mp;for(auto w:words){mp[w]++; // 存在->++ ; 不存在->插入}// 2.放入vector实现按次数排序vector<pair<string,int>> vv(mp.begin(),mp.end());// 要用稳定的排序stable_sort,sort底层是快排，是不稳定的stable_sort(vv.begin(),vv.end(),Compare());// 3.取前k个vector<string> v;for(int i = 0;i < k ;i++){v.push_back(vv[i].first);}return v;}
};方法二：
将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数 强行控制次数相等的，字典序小的在前面。
class Solution {
public:// 仿函数控制升序的同时，相同次数的单词按字典序排列struct Compare{bool operator()(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) {// 1.放入map实现按字典序排序map<string,int> mp;for(auto w:words){mp[w]++; // 存在->++ ; 不存在->插入}// 2.放入vector实现按次数排序vector<pair<string,int>> vv(mp.begin(),mp.end());sort(vv.begin(),vv.end(),Compare());// 3.取前k个vector<string> v;for(int i = 0;i < k ;i++){v.push_back(vv[i].first);}return v;}
};class Solution {
public:// 优先级队列底层是反的，大堆要实现⼩于比较，// 所以这里次数相等，想要字典序小的在前面要比较字典序大的为真struct Compare{bool operator()(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) {// 1.放入map实现按字典序排序map<string,int> mp;for(auto w:words){mp[w]++; // 存在->++ ; 不存在->插入}// 2.放入priority_queue实现按次数排序,其默认排序是升序priority_queue<pair<string,int>,vector<pair<string,int>>,Compare> pq(mp.begin(),mp.end());// 3.取前k个vector<string> v;while(k-- && !pq.empty()){v.push_back(pq.top().first);pq.pop();}return v;}
};
_今日的最新消息_长沙官网seo收费标准)
