一、序列式容器和关联式容器
序列式容器：逻辑结构为线性序列的容器，两个位置所存放的数据一般没有紧密关系，例如两个位置交换一下，逻辑结构没有改变。
关联式容器：通常是非线性结构（堆例外），两个位置存放数据有紧密的关联关系，交换一下逻辑结构就改变了。
常见的序列式容器：string，vector，list，deque，array，forward_list
常见的关联式容器：map/set系列和unordered_map/unordered_set系列
map（key/value）和 set（key），底层是红黑树，红黑树是一颗平衡二叉搜索树。
易错点1：
map可以是升序，也可是降序，默认情况下是升序，如果需要降序，需要用户在实例化map时指定比较规则。
set中可以存储键值对，实例化set时，将set中元素类型设置为pair即可。
二、set的介绍
template < class T , // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type> class set;1.set默认T支持小于比较，若不支持或要改变比较逻辑要显式传仿函数。2.set增删查时间复杂度是O(logN)，迭代器遍历走的是搜索树的中序，即有序序列。
set的构造函数
empty (1) range (2) copy (3) 1）默认构造
2）迭代器区间构造
3）拷贝构造
set的迭代器是双向迭代器。
iterator a bidirectional iterator to value_type convertible to const_iterator const_iterator a bidirectional iterator to const value_type
Modifiers:
insert:
// 单个数据插⼊，如果已经存在则插⼊失败pair<iterator, bool > insert ( const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊void insert (initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊template < class InputIterator >void insert (InputIterator first, InputIterator last);
erase:
1）删除迭代器位置，返回删除后中序遍历下一个位置的迭代器
(1) (2) (3)
2）删除val，删除了返回1，没有删除返回0
3）删除一段迭代器区间
注：erase()一个迭代器后，迭代器就失效了
原因：
1.如果该节点是叶子节点，或者左右子树有一为空的节点，会被直接删除，导致野指针的问题，迭代器失效了。
2.如果该节点的左右子树都不为空，会使用替换删除，虽然该节点没有被释放掉，但是意义变了，也认为迭代器失效了。
find和count
// 查找 val ，返回 val 所在的迭代器，没有找到返回 end()iterator find ( const value_type& val);// 查找 val ，返回 Val 的个数，通常用于查找size_type count ( const value_type& val) const ;
lower_bound和upper_bound
// 返回大于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回大于val位置的迭代器
iterator upper_bound (const value_type& val) const;void test_set1() {set<int> s({ 10,20,30,40,50,60,70,80,90,100 });//若要得到[20,55]区间的值//lower_bound闭区间，upper_bound开区间set<int>::iterator bit = s.lower_bound(20);set<int>::iterator eit = s.upper_bound(50);while(bit != eit){cout << *bit << " ";++bit;}cout << endl; }
lower_bound返回大于等于key的值，upper_bound返回大于key的值。
mutiset和set的区别：
find的示例，特别注意，++mit是按中序遍历走，有序序列的方式走，不会错过。
和set不同的是，count不只是返回0和1，而是可能有多个，erase删除key值也是删除所有key值。
set的使用场景（两个OJ题）：
349. 两个数组的交集 - 力扣（LeetCode）
思路：使用两个set达到排序和去重的效果，然后遍历两个set，输出有序序列，如果两个值相等，vector尾插这个值，两个迭代器都走；如果两个值不相等，值小的迭代器走，因为值大的后面没有比值小的更小了。拓展：若所求的是差集，那么遇到相等的跳过，两个迭代器都走；如果两个值不相等，值小的vector尾插这个值，值小的迭代器走，因为值大的后面没有比值小的更小了，值小的就是差集；如有一迭代器走完了，另一迭代器没走完的部分全是差集。
class Solution { public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1,s2;for(const auto& ch:nums1){s1.insert(ch);}for(const auto& ch:nums2){s2.insert(ch);}vector<int> v;set<int>::iterator it1 = s1.begin();set<int>::iterator it2 = s2.begin();while(it1!=s1.end() && it2!=s2.end()){if(*it1==*it2){v.push_back(*it1);++it1;++it2;}//小的走，因为大的后面没有比这小的了else if(*it1>*it2){++it2;}else{++it1;}}return v;} };142. 环形链表 II - 力扣（LeetCode）
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。对于环形链表，用C语言解决的话有两种方式：
定义两个指针，慢指针一次走1步，快指针一次走2步或者3步，它们一定会相遇在环内部的一个节点，将这个节点记录为相遇节点。
1.在相遇节点处断开，然后就转化成了链表相交的问题，长链表从头走到和短链表一样长的位置，然后找到相交节点，由于题目本身不让破坏节点，最后相遇节点链接回去。
2.定义两个指针一个从头开始走，另一个从链表相交位置开始走，它们一定会在入口节点相遇，证明法。
对于C++，简单很多，只需要将定义一个节点指针cur从头开始走，插入到set中，直到set插入失败，即回到环的开始节点了，此时插入失败的节点指针就是入环的第一个节点。
class Solution { public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while(cur){pair<set<ListNode*>::iterator,bool> ret = s.insert(cur);if(ret.second==false)return cur;cur = cur->next;}return nullptr;} };
三、map系列的使用
map的声明
map底层也是红黑树，key-value模型，按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;map增删查改的效率是O(logN)。
pair结构
template <class T1, class T2> struct pair;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) ); }
member type definition notes key_type The first template parameter (Key) mapped_type The second template parameter (T) value_type pair<const key_type,mapped_type>
在map中，pair<const key_value,mapped_typed>被重命名为了value_type，第一个是const key，第二个是value，用了一个结构pair封装。
map的构造函数
// 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 ();
map具体案例1：
void test_map1() {map<string, string> m({ {"sort","排序"},{"left","左边"} });//多参数的隐式类型转换,C++11// "right","右边"隐式类型转换成string//{string,string}隐式类型转换成pair<const string,string>m.insert({ "right","右边" });//利用make_pair创建一个pair<const string,string>的匿名对象m.insert(make_pair("right", "右边")); }map可以用初始化列表初始化，C++11支持多参数的隐式类型转换，用{}括起来。
map具体案例2：
void test_map2() {map<string, string> m({ {"sort","排序"},{"left","左边"} });map<string, string>::iterator it = m.begin();while (it != m.end()){//注意it所指向的对象是一个pair结构的，不能直接解引用访问cout << it->first << ":" << it->second << endl;++it;}cout << endl; }注意map的迭代器指向的是一个pair结构，不能直接解引用访问。
map具体案例3：
void test_map3() {map<string, string> m({ {"sort","排序"},{"left","左边"} });//insert一个已经存在的key，不会做任何修改m.insert({ "left","剩余" });for (const auto& ch : m){cout << ch.first << ":" << ch.second << endl;}cout << endl; }
易错点：insert一个已经存在的key值，不会做任何修改。
map的增删查接口：
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;
map具体案例4和5：
void test_map4() {// 利用find和iterator修改功能，统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> m;//插入数据for (const string& s : arr){m.insert({ s,0 });}map<string, int>::iterator it;//再次遍历一遍arr// 用find查找对应key位置的迭代器，使value++for (const string& s : arr){it = m.find(s);it->second++;}for (const auto& ch : m){cout << ch.first << ":" << ch.second << endl;}cout << endl; }这里利用find和iterator修改功能，统计水果出现的次数。但是这种写法太麻烦了，要遍历两便arr数组可改为以下写法：
void test_map5() {string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> m;//operator[]有插入，查找，修改三种功能//key不存在，插入数据，返回value的引用，修改数据//key存在，根据key查找，返回value的引用，修改数据for (const string& s : arr){m[s]++;}for (const auto& ch : m){cout << ch.first << ":" << ch.second << endl;}cout << endl; }
operator[]的作用：插入，查找，修改。
1.key不存在，插入（期间会调用value的默认构造），返回value的引用。
2.key存在，查找，返回value的引用。
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;}可以看到，operator[]内部调用insert，insert返回一个pair<iterator,bool>的结构，插入成功，pair.second为true，反之为false，pair.first为key位置所在的迭代器，operator[]返回该迭代器位置的value的引用。
mutimap和map的区别：
void test_mutimap1() {multimap<string, string> m({ {"sort","排序"},{"left","左边"} });m.insert({ "left","剩余" });for (const auto& s : m){cout << s.first << ":" << s.second << endl;}cout << endl;m.erase("left");for (const auto& s : m){cout << s.first << ":" << s.second << endl;}cout << endl; }
multimap允许key值冗余，insert一定成功。
erase()删除所有key。
equal_range()
pair<const_iterator,const_iterator> equal_range (const key_type& k) const; pair<iterator,iterator> equal_range (const key_type& k);返回pair结构封装的迭代器区间，左闭右开。
两个OJ题：
138. 随机链表的复制 - 力扣（LeetCode）
若按C语言做，思路如下：
随机指针是原链表节点之间的关系，要使拷贝链表也具有这种关系，在每个原链表节点位置将拷贝节点插入到原链表节点的后面。
1）遍历一遍原链表，在每个原链表节点后复制一个节点插入到节点后面
2）再次遍历一遍链表，复制随机指针
3）再次遍历一遍链表，将复制链表取下来
按C++做，思路如下：
定义一个map<ListNode*,ListNode*>，key存原链表节点指针，value存现拷贝链表的指针。这样原链表节点的映射关系，拷贝链表也有了。
1）遍历一遍原链表，原链表指针作为key插入，new出来的拷贝链表指针的val和next赋值为原链表节点中对应的值
2）遍历两个链表，将节点指针插入进map
3）遍历一遍map，如果key->random为nullptr，value->random也为nullptr；如果key->random不为空，value->random = map[key->random]; 。
class Solution { public:Node* copyRandomList(Node* head) {map<Node*,Node*> m;Node* cur = head;Node *copyhead,*tail;copyhead = tail = nullptr;//1.复制链表的值和next指针while(cur){Node* newnode = new Node(cur->val);if(copyhead==nullptr){tail = copyhead = newnode;}else{tail->next = newnode;tail = tail->next;}cur = cur->next;}//2.插入到map中cur = head;Node* copycur = copyhead;while(cur && copycur){m.insert({cur,copycur});cur = cur->next;copycur = copycur->next;}//3.复制random指针map<Node*,Node*>::iterator it = m.begin();while(it!=m.end()){if(it->first->random==nullptr){it->second->random = nullptr;}else{it->second->random = m[it->first->random];}++it;}return copyhead;} };
思路1：将单词插入map中统计单词出现的次数，然后转入vector，对vector按次数排序，取出vector里的前k个高频单词。
注意点：map中默认是按单词string排了字典序，因此用vector排序时：
1）用稳定的排序。
2）使用sort，比较逻辑中特殊处理：对于出现次数相同的单词按字典序比较。
思路2：将单词插入map中统计单词出现的次数，然后转入priority_queue，比较逻辑特殊处理：对于出现次数相同的单词按字典序比较，取出priority_queue的前k个高频单词。
第一种：
class Solution { public:struct great{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second > p2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> m;for(const string& s:words){//若不存在，插入，返回插入位置value的引用//若存在，查找，返回key位置value的引用m[s]++;}//转入vector中vector<pair<string,int>> v(m.begin(),m.end());//按降序排列stable_sort(v.begin(),v.end(),great());vector<string> ret;for(size_t i = 0;i<k;++i){ret.push_back(v[i].first);}return ret;} };第二种：
class Solution { public:struct great{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second > p2.second || (p1.second==p2.second && p1.first < p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> m;for(const string& s:words){//若不存在，插入，返回插入位置value的引用//若存在，查找，返回key位置value的引用m[s]++;}//转入vector中vector<pair<string,int>> v(m.begin(),m.end());//按降序排列sort(v.begin(),v.end(),great());vector<string> ret;for(size_t i = 0;i<k;++i){ret.push_back(v[i].first);}return ret;} };第三种：
class Solution { public:struct less{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second < p2.second || (p1.second==p2.second && p1.first > p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> m;for(const string& s:words){//若不存在，插入，返回插入位置value的引用//若存在，查找，返回key位置value的引用m[s]++;}//转入priority_queue中priority_queue<pair<string,int>,vector<pair<string,int>>,less> q(m.begin(),m.end());vector<string> ret;for(size_t i = 0;i<k;++i){ret.push_back(q.top().first);q.pop();}return ret;} };注意正常的大小堆的逻辑与大于小于相反，less排大堆，great排小堆。
这里也可转化成topK问题，建立一个大小为k的小堆，大堆每次插入时与小堆的堆顶比较，如果比小堆的堆顶大，就插入（如果满了就替换堆顶），然后调整。最后取出来的小堆的逆序就是topK。
![[极客大挑战 2019]BabySQL—3.20BUUCTF练习day4(3)](https://i-blog.csdnimg.cn/direct/ab6285d2a37a427d9f53eceda32bfdab.png)
![[Effective C++]条款20:宁以 pass-by-reference-to-const替换 pass-by-value](https://i-blog.csdnimg.cn/direct/9b353c3b29204445a2d8c494bfe1661f.png#pic_center)
