set类的实现

set的声明：T就是set底层的关键字的类型；
set默认要求支持T比较，如果不支持或者想按照自己的需求走可以自行实现仿函数传给第二个模板参数。
set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。

set底层是红黑树实现，增删查效率是O（logN),迭代器遍历走的是搜索树的中序，所以是有序的。
中序遍历一定是按照升序排的。

set的构造和迭代器：

来插入结构数字，当set<int>s;就是将set看作是T类型的模板参数。排序加去重的操作。

#include<iostream>
#include<set>
using namespace std;

int main()
{
   
    set<int> s;
    //set<int,greater<int>> s;
    s.insert(4);
    s.insert(3);
    s.insert(8);
    s.insert(9);
    s.insert(2);
    s.insert(6);

    //set<int>::iterator it=s.begin();
    auto it = s.begin();
    while (it != s.end())
    {
   
        cout << *it <<" ";
        //*it = 1;//这里会报错，因为set不支持修改，一旦修改就会破坏结构。
        ++it;
    }
    cout << endl;//2 3 4 6 8 9 

    return 0;
}

降序：set<int,greater<int>> s;也即是说比根大的数传到左边，比根小的数传到右边。拍出来降序的操作。

还支持插入initializer_list列表值，已经插入的值插入失败。

s.insert({
    2,3,4,5 });
for (auto e : s)
{
   
    cout << e << " ";
}
cout << endl;

set:erase和find

删除最小的值：由于按照升序排序的，所以s.erase(s.begin())会删除最小的值。

s.erase(s.begin());
for (auto e : s)
{
   
    cout << e << " ";//3 4 6 8 9 
}
cout << endl;

//直接删除
int x;
cin >> x;
int num = s.erase(x);
if(num==0){
   cout << x << "不存在" << endl; }//num==0是指个数，x有几个有一个x,删除成功x就=0了
else {
    cout << x << "删除成功" << endl; }

//方法2
int x;
cin >> x;
auto pos = s.find(x);
if (pos != s.end()) {
    s.erase(pos); cout << x << "删除成功" << endl; }
else {
    cout << x << "不存在" << endl; }

迭代器失效问题：

方法2中pos一定会失效，erase删除了节点，那么指向节点的指针一定会失效，就会出现野指针的问题。

如果删除的是根节点，由于是替代法删除，除了根节点，其他节点都在，虽然没有破坏二叉搜索树的的结构，但是迭代器的意义已经改变了。cout<<*pos<<endl;访问就会报错。

查找：（容器自身的效率更高)

int x;
auto pos1 = find(s.begin(), s.end(), x);//算法库中实现的O(N)

auto pos2 = s.find(x);//容器自身的O（logN)

set:count

利用count进行间接的查找。如果找到了返回真，不在返回假。

cin >> x;
if (s.count(x))
{
   
    cout << x << "在的" << endl;
}
else {
    cout << x << "不在" << endl; }

set:lower_bound和upper_bound

寻找这块区间左闭右开。

#include<iostream>
#include<set>
using namespace std;
int main()
{
   
    set<int>mset;
    for (int i = 1; i < 10; i++) {
    mset.insert(i * 10); }
    for (auto e : mset) {
    cout << e << " "; }cout << endl;// 10 20 30 40 50 60 70 80 90
    // 实现查找到的[itlow,itup)包含[30, 50]区间
    auto itlow = mset.lower_bound(30);//返回>=30
    auto itup = mset.upper_bound(50);//返回>50
    mset.erase(itlow, itup);//删除这段区间的值
    for (auto e : mset) {
    cout << e << " "; }cout << endl;// 10 20 60 70 80 90
    return 0;
}

multiset和set

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余。
也就是multiset仅仅是排序，不去重。

int main()
{
   
    multiset<int>s = {
    4,2,3,1,5,6,8,6,43,2,5 };
    auto it = s.begin();
    while (it != s.end()) {
    cout << *it << " "; ++it; }cout << endl;

    int x;
    cin >> x;
    auto pos = s.find(x);
    while (pos != s.end()&&*pos==x) {
    cout << *pos << " "; ++pos; }cout << endl;
}

问题：那么既然不去重，如果说要找一个在multiset中出现很多次的数字，具体会找哪一个呢？

会找到中序的第一个。这样是有好处的，找到中序的第一个，迭代器不断++会找到multiset的所有x。

map：insert

pairinsert(const value_type& val)文档中的结构,insert的返回值是pair
pairinsert(const pair**& val>展开来看是这样的。

==插入成功：返回pair<新插入值的迭代器，true>
插入失败：返回pair<已经存在的跟key相等的值的迭代器，false>==

insert插入一个pair对象：

1.如果key已经在map中了，那么就会插入失败，会返回一个pair<iterator,bool>的对象，返回pair对象first是key所在节点的迭代器，second是false;
2.如果key不在map中，插入成功的时候，就会返回一个pair<iterator,bool>的对象返回的pair对象是first新插入key节点所在的迭代器，second是true.

所以就是说，insert除了充当插入的 功能，还充当查找的功能。

map:operator[ ]

operator的内部实现：

mapped_type& operator[](const key_type& k)
{
   
pair<iterator,bool>ret=insert({
   k,mapped_type()});
iterator it=ret.first;
return it->second;
}

这里解释，在map中插入一个k值，插入k值的同时有一mapped_type的键值对。

1.如果k不在map中，在插入k的同时，也将会插入mapped_type的默认构造初始化的参数，不管是什么类型，同时[]会返回节点中存储的mapped_type的值的引用，那么我们就可以通过引用来修改映射值。所以这里[]既有修改又有插入的功能。

2.如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key节点的迭代器，返回值同时[]返回节点中存储的mapped_type值的引用，所以[]既有查找也有修改的功能。

int main()
{
   
    string myarray[]= {
    "秋","冬","夏","春","夏","秋","夏","春","夏","秋","秋","冬"};
    map<string, int>countMap;
    for (const auto& e : myarray) {
    countMap[e]++; }//春：2 冬：2 秋：4 夏：4 
    for (const auto& it : countMap) {
    cout << it.first << ":" << it.second << endl; }cout << endl;
    return 0;
}

问题：countMap的插入是怎么实现的？

我们知道countMap的功能就是迭代器遍历string类型的数组myarray，
如果元素e本来不在map中，就插入成功，插入e值，同时mapped_type是整型的缺省值，也即是0，bool返回true;
同时返回插入值的迭代器，在pair里面，pair<iterator,bool>,只是返回在pair中，通过pair的迭代器取到first，迭代器用箭头可以取到second，++一下，插入成功，也就是将元素e，缺省值从0+成了1.这样也就是插入成功了。

总结：必看！！！

如果插入成功，说明e不在map中，会插入一个键值对（e,mapped_type的默认构造值），对于什么类型返回对应的默认构造，比如说int默认构造值就是0，double默认构造值就是0.0，同时会返回该键值对的引用。++操作将其从0更新到1；

如果插入失败,说明e在map中，直接返回该键值对对应值的引用。++操作将其值从1更新到2.

multimap和map的差异：

multimap和map的使用基本相似，

1.主要区别在于multimap支持关键值key冗余，也就是说multimap不会去重。那么insert/find/erase都围绕者支持关键值key冗余有所差异，这里find的时候，会有多个key,但是都会返回中序的第一个

2.其次就是multimap不支持[],因为支持key冗余，[]就只能支持插入了，不支持修改。

力扣题目链接：

两个数组的交集

两个数组的交集

题目解析：
题目中有两个数组，要求返回他们的交集，也就是返回的是两个数组中相等的部分。

思路：

==相等就是交集，小的++，因为小的一定不是交集。==

这里首先用set进行==去重+升序==，两个数组都需要去重+升序的处理，所以set<int>s1(nums1.begin(),nums1.end()), set<int>s2(nums2.begin(),nums2.end()),

1. 用两个指针来遍历，分别指向两个数组，
2. it1指向的值如果小于it2指向的值，就让it1++；直到挪动到和it2指向的相等的值，然后插入到最终返回的vector类型的数组中；
3. 同理，it2指向的值如果小于it1指向的值，那就让it2++,直到挪动到和it1指向的相等的值，然后插入到最终返回的vector类型的数组中,这里如果两个指针指向是相同的数字，随意返回it1或者it2,只插入一个值。
4. 如果两个指针都没有指向各自数组的末尾，都需要++；最后走出循环的条件是两个指针有一个走到空就结束循环。
5. 最后返回ret.

class Solution {
   
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
   
        //思路：将两个数组放进set1和set2中，可以去重操作还会进行排序
        //相等就放入交集，小的++，大的++
        vector<int> ret;
        set<int>s1(nums1.begin(),nums1.end());
        set<int>s2(nums2.begin(),nums2.end());
        auto it1=s1.begin();
        auto it2=s2.begin();
        while(it1!=s1.end()&&it2!=s2.end())
        {
   
            if(*it1<*it2){
   ++it1;}
            else if(*it1>*it2){
   ++it2;}
            else{
   ret.push_back(*it1);++it2;++it1;}
        }
        return ret;

    }
};

==找交集：==

1.相等就是交集，小的++；小的一定不是交集；
2.返回相等的值就是交集。

==拓展：找差集==

1.小的就是差集，小的++；
2.相等就同时++
其中一个走到尾部了，另一个没有走完的值也是属于差集。

环形链表

环形链表

题目解析：
链表中如果有环，返回链表中的环的第一个节点，如果没有环，就返回null.

思路：

问题：放到set里面，为什么要放到set中？

set容器s，用于存储已经访问过的链表节点指针，利用set元素唯一性的特性，来判断节点是否重复，也即是是否进环。

用一个cur指针遍历链表，当链表节点cur没有走到空，
有一个接口count,利用count进行间接的查找。如果找到了返回真，不在返回假。

1. 在循环体内判断，set 的s中是否存在当前的节点指针cur;
2. s.count(cur)会返回cur在s中数量（因为set的元素唯一，所以结果是0或者1）如果存在就返回1，返回值是1，说明这个已经被访问过了，链表是存在环的，这个cur指向的值就是环的第一个节点；
3. 如果s不再当前节点指针，s.count(cur)返回0，就将cur插入到set中，标记为已经访问，然后cur继续向后走继续遍历链表。一直走到cur走到空，结束循环。
4. 如果走到空了，所有元素都没有二次访问，那就说明该链表没有环，直接返回null.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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 nullptr;
    }
};

随机链表的复制

随机链表的复制

题目解析：
这道题要求构造一个已知链表的深拷贝，将已知链表的next和random指针都要指向新的链表中的节点，也就是将已知链表中的构造完完整整拷贝到新的链表中，这里我们用一个map映射就可以解决。

思路：

1. 首先需要有一个map映射，randomMap;构造一个新链表，它的头节点和尾节点分别指向空，然后将原链表中的next和random指针分别按照对应的结构拷贝到新链表中；用一个ptr指针来从原链表的头节点一直遍历到尾节点。
2. 接着开始处理next：

当copytail==nullptr,说明新链表才刚开始插入，我们就建立新的节点让copyhead=copytail=new Node(ptr->val);
如果拷贝链表中不为空，那么就让copytail->next=new Node(ptr->val);copytail=copytail->next;拷贝新的节点，然后让拷贝节点走向新的位置；需要将拷贝链表和映射randomMap建立关系，这样才好插入，randomMap[ptr]=copytail; 接着ptr不断向后进行遍历。
此时如果ptr走到空，也就是ptr已经遍历完成了原链表。

1. 现在来处理random节点:

此时copytail一定不为空，但是需要按照原链表的构造完成random的拷贝，让ptr重新进行遍历，然后此时拷贝链表已经有了雏形，给一个copy指针让其从拷贝链表的头节点遍历到尾节点。
如果原链表中ptr指向的random指向为空，那么就让copy的random也是指向为空；
如果不为空呢，就需要建立映射关系，copy->random=randomMap[ptr->random];
copy=copy->next,ptr=ptr->next,ptr和copy分别向后遍历。
如果ptr走到空节点，遍历完原链表，就结束循环。

1. 最后就完成了拷贝链表的构造拷贝，返回头节点结束作答。

上代码！

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
   
public:
    Node* copyRandomList(Node* head) {
   
        map<Node*,Node*>randomMap;
        Node* copyhead=nullptr,*copytail=nullptr;
        Node* ptr=head;
        while(ptr)
        {
   
            if(copytail==nullptr){
   copytail=copyhead=new Node(ptr->val);}
            else{
   copytail->next=new Node(ptr->val);copytail=copytail->next;}
            randomMap[ptr]=copytail;
            ptr=ptr->next;
        }
        Node* copy=copyhead;
        ptr=head;
        while(ptr)
        {
   
            if(ptr->random==nullptr){
   copy->random=nullptr;}
            else{
   copy->random=randomMap[ptr->random];}
            copy=copy->next;
            ptr=ptr->next;
        }
        return copyhead;
    }
};

前k个高频单词

前k个高频单词

题目解析：
有一个单词表，要返回前k个出现次数最多的单词，这里涉及到统计次数，快速回顾我们之前学过的，什么可以统计次数，countMap,这道题如果有map这块的知识加持，应该会好解答很多，接着看，返回的答案要按照单词的出现频率由高到低排序，涉及排序，是不是要用到sort，又出现一个关键元素，还要按照字典序排序。

思路：

1. 要统计每个单词的出现的次数，就要放到map里面进行映射，map<string,int>countMap;用一个迭代器对words进行遍历，for(auto& it:words),countMap[it]++;对每一个出现的元素都进行分析，没有出现过的从默认构造缺省值0++到1；出现过的再++1；直到遍历完所有的元素。

==然后需要排序，map本身不支持直接排序，所以将其转换为vector后更灵活。为了同时存储“单词”和它的出现"次数“，将这两个信息绑在一起，可以将单词（string类型）和次数（int类型）封装在一个整体中，pair<string,int>,==

1. vector<pair<string,int>> v (count.begin(),count.end());然后对容器v进行初始化，用的是countMap.begin()和countMap.end()
2. 将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的.
3. 接着排序的时候，这里要实现自定义排序，也就是出现频率由高到低进行排序，stable_sort的参数除了传迭代器的起始地址，还要额外加一个仿函数的对象，这个仿函数就是用来实现将单词的出现频率由高到低进行排序，再定义一个结构体
4. 这个结构体kvFunction中重载operator[]对出现的单词进行排序，要传的不仅仅是单词，还有出现的频率，所以这里再次用pair进行封装，bool operator()(const pair<string,int>w1,const pair<string,int>w2),返回的应该是second，如果w1的出现频率比w2高，那么就让w1排在前面，迭代器中first代表单词，second才是代表出现的频率。 return w1.second>w2.second;
5. 最后关键一步，打印出前k个出现频率最高的单词，这里我们用vector容器ret对结果进行封装，对前k个单词尾插进入ret，ret.push_back(v[i].first).first就是指单词。

有一个问题：那么这道题是怎么按照字典序排序的呢？
1.借助map的天然字典序特性，代码中首先使用map<string,int>countMap;统计单词出现的频率，map是基于红黑树实现的，会自动按照键的字典序升序。
2.借助stable_sort的稳定型：当两个元素的排序频率相同的时候，会保持他们在排序前的（也就是map中的字典序）相对顺序。
==所以map的字典序存储+stable_sort的稳定性，共同保证了”频率降序，频率相同则字典序升序“的排序规则。==

class Solution {
   
public:
    struct kvFunction
    {
   
        bool operator()(const pair<string,int>w1,const pair<string,int>w2)
        {
   
            return w1.second>w2.second;//表示次数多的排在前面
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
   
        map<string,int>countMap;
        for(auto& it:words){
   countMap[it]++;}//统计每一个单词出现的次数

        vector<pair<string,int>>v(countMap.begin(),countMap.end());//将一个键值对转换为一个vector容器，方便后序排序
        stable_sort(v.begin(),v.end(),kvFunction());
        //稳定排序（出现次数相同，保持原map中的字典序）
        vector<string>ret;
        for(int i=0;i<k;i++){
   ret.push_back(v[i].first);}return ret;
    }
};

set和map的构造对比:

set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

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