1.set

1 set存储-避免存储(insert(logn))相同的数据:
https://www.acwing.com/activity/content/code/content/7946218/

2 multiset查找数据k出现次数的应用（s.count(k)函数(logn)）： https://www.acwing.com/activity/content/code/content/7595964/

3 set可以查找值为k的元素并删除（s.erase(k)(logn)）
https://www.acwing.com/activity/content/code/content/7597189/

4 unordered_set
本质：是哈希表,增删查改(1~n))
:存储数据快速查找，求两集合的交集 https://www.acwing.com/activity/content/code/content/8668874/
查找数组中和为s的两个数（遍历数组时若在set中没有找到与其和为s的数，则将数据存入set，再继续遍历查找）https://www.acwing.com/activity/content/code/content/7598647/
O(n)复杂度查找序列中最长的连续序列的长度https://leetcode.cn/problems/longest-consecutive-sequence/submissions/526356000/?envType=study-plan-v2&envId=top-100-liked

2.map

1.unordered_map[HTML_REMOVED]d应用，将每个字符串（状态）配上一个值（步数）https://www.acwing.com/activity/content/code/content/7694977/

2.利用unordered_map[HTML_REMOVED]S存储数据，用O(1)复杂度S.count(t(关键字))查找
https://www.acwing.com/activity/content/code/content/7896592/

3.multimap的使用

 #include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;cin>>n>>m;
    multimap<string,string>mp;
    while(n--)
    {
        string a,b;cin>>a>>b;
        mp.insert(make_pair(a,b));
    }
    multimap<string,string>t;  //创建临时的map，不能边遍历边改变map
    for(auto a:mp){
        for(auto b:mp){
            string c=a.first+b.first;
            t.insert(make_pair(c,a.second+b.second));
        }
    }
    mp.insert(t.begin(),t.end());
    while(m--)
    {
        string s;cin>>s;
        if(mp.count(s)==1)    cout<<mp.find(s)->second<<endl;
        else    cout<<"D\n";
    }
    return 0;
}

3.priority_queue
默认的优先队列是大根堆，堆顶是最大值。
优先队列存储结构体时要重载运算符,大根堆重载 ‘<’，小根堆重载 ‘>’

bool operator <(const node& other) const 
{
        return val < other.val;
}

 bool operator >(const node& other) const 
{
        return val > other.val;
}

priority_queue<int,vector<int>,greater<int>>haep是小根堆，堆顶是最小值。

小根堆解决合并果子（不是相邻，区别合并石子）问题 https://www.acwing.com/activity/content/code/content/7859551/
哈夫曼树
https://www.acwing.com/activity/content/code/content/8717460/
较复杂的例题
1.https://www.acwing.com/blog/content/54998/
2. https://www.acwing.com/problem/content/description/5138/

4.pair

5.vector

易错点

  class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> c;
        for (int i = 0; i < numRows; i++) {
            vector<int> row;  // c[i].push_back(1);是错误的，c[i]是访问空指针
            row.push_back(1);
            for (int j = 1; j < i + 1; j++) {
                if (j != i) row.push_back(c[i - 1][j - 1] + c[i - 1][j]);
                else row.push_back(1);
            }
            c.push_back(row);
        }
        return c;
    }
};

6.string的函数

// 最常用的操作
str.size();//返回字符串长度
str.length();//返回字符串长度
str.empty();//检查 str 是否为空，为空返回 1，否则返回 0
 str[n];//存取 str 第 n + 1 个字符
str.at(n);//存取 str 第 n + 1 个字符（如果溢出会抛出异常）

// 反转
reverse(str.begin(), str.end());

 // 查找
str.find("ab");//返回字符串 ab 在 str 的位置
str.find("ab", 2);//在 str[2]~str[n-1] 范围内查找并返回字符串 ab 在 str 的位置
str.rfind("ab", 2);//在 str[0]~str[2] 范围内查找并返回字符串 ab 在 str 的位置
if(str.find("ab")!=string::npos)
 {    cout << "下标为:" << str.find("ab"); }

 // 子串
str.substr(3);  // 返回 [3] 及以后的子串
str.substr(2, 4); // 返回 str[2]~str[2+(4-1)] 子串(即从[2]开始4个字符组成的字符串)
 str.substring(5, 10);  // 返回 str[5]~str[9] 子串(不包含结尾)

 // 插入
str.insert(2, "sz");//从 [2] 位置开始添加字符串 "sz"，并返回形成的新字符串
str.insert(2, "abcd",3);//从[2]位置开始添加字符串"abcd"的前3个字符，并返回形成的新字符串
str.insert(2, "abcd", 1, 3);//从 [2] 位置开始添加字符串 "abcd" 的前 [2]~[2+(3-1)] 个字符，并返回形成的新字符串

// 删除
str.erase(3);//删除 [3] 及以后的字符，并返回新字符串
str.erase(3, 5);//删除从 [3] 开始的 5 个字符，并返回新字符串
str.pop_back(); //删除最后一个字符

// 替换
str.replace(2, 4, "sz");//返回把 [2]~[2+(4-1)] 的内容替换为 "sz" 
后的新字符串
str.replace(2, 4, "abcd", 3);//返回把 [2]~[2+(4-1)] 的内容替换为 
"abcd" 的前3个字符后的新字符串

// 追加
str = str + "abc";
 str.push_back('a');//在 str 末尾添加字符'a'
 str.append("abc");//在 str 末尾添加字符串"abc