C++: STL编程

TAGS: C++

STL概念

STL基础概念简介

线性表

顺序表

vector

vector 基础概念

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int a[6] = { 9, 8, 7, 6, 5, 4 };
    vector<int> v = { 2, 0, 2, 4 };
    cout << v.capacity() << endl; // 4 容量
    v.push_back(7);
    cout << v.capacity() << endl; // 5

    // 暂时把迭代器当前指针，实际上是类，它和指针差不多
    // front()                        back()
    // 2       0      2       4       7
    // ↑begin()                            ↑end()

    cout << "begin: -> " << *v.begin() << endl;     // 2
    cout << "end-1: -> " << *(v.end() - 1) << endl; // 7  因为end()位置是没有值的，会报错。这里取end前一个位置的值
    cout << "front: " << v.front() << endl;         // 2
    cout << "back: " << v.back() << endl;           // 7

    return 0;
}

vector 对象创建

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

void printVector(vector<int>& v) { // 使用引用就不会拷贝，const 不能改里面的值
    // 定义vector<int>的迭代器类型，从begin开始，到end结尾
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++ ) {
        cout << *iter << " ";
    }
    cout << endl;
}
int main() {
    // 1. 默认构造函数
    vector<int> v1;  // 创建后，v1中是没有内容的
    cout << "v1:";
    printVector(v1); // 无显示，因为没数据

    // 2. 初始化列表方式构造
    // int a[5] = {9, 8, 7, 6, 5};
    vector<int> v2_1 = { 9, 8, 7, 6, 5 }; // 隐式构造
    cout << "v2_1:";
    printVector(v2_1);
    vector<int> v2_2({ 9, 8, 7, 8, 5 });  // 有参构造
    cout << "v2_2:";
    printVector(v2_2);

    // 3. 迭代器方式
    vector<int> v3(v2_1.begin(), v2_1.end()); // 把v2_1的第1个元素到倒数第1个元素按顺序拷贝到v3上了。拷贝是左闭右开的
    cout << "v3:";
    printVector(v3);

    // 4. 全0初始化
    vector<int> v4(8); // 预申请8个内存空间，每个元素的值为0
    cout << "v4:";
    printVector(v4);

    // 5. vector<int> 变量名(a, b); 申请a个空间的元素，每个元素的值初始化为b
    vector<int> v5(8, 6);
    cout << "v5:";
    printVector(v5);

    // 6. 拷贝构造函数
    vector<int> v6(v2_2);
    cout << "v6:";
    printVector(v6);

    return 0;
}

vector 赋值操作

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

void printVector(vector<int>& v) {
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}
int main() {
    vector<int> v = { 9, 8, 5, 2, 1, 1 };
    cout << "v:";
    printVector(v);

    // 1. = 赋值
    vector<int> v1 = v;
    cout << "v1:";
    printVector(v1);

    // 2. assign(迭代器)
    vector<int> v2;
    v2.assign(v1.begin(), v1.end());
    cout << "v2:";
    printVector(v2);

    // 3. 初始化列表
    vector<int> v3;
    v3.assign({ 1,2,3,4,5,6 });
    cout << "v3:";
    printVector(v3);

    // 4. 初始化a个b
    vector<int> v4;
    v4.assign(8, 6);
    cout << "v4:";
    printVector(v4); // v4:6 6 6 6 6 6 6 6

    return 0;
}

vector 数据插入

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

void printVector(vector<int>& v) {
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}
/*
push_back(值)
insert(迭代器, 值)
*/
int main() {
    vector<int> v;
    for(int i = 0; i < 10; ++i) {
        v.push_back(i);
    }
    printVector(v);

    v.insert(v.begin(), 888); // 插在begin()的前面
    printVector(v);       // 888 0 1 2 3 4 5 6 7 8 9
    v.insert(v.begin()+1, 666); // 插在begin()的后面
    printVector(v);       // 888 666 0 1 2 3 4 5 6 7 8 9

    return 0;
}

vector 数据删除

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

void printVector(vector<int>& v) {
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}
/*
1、pop_back  从后面删除
2、erase  指定位置删除，返回迭代器指向该位置的下一个位置
3、clear  所有全部删除
*/
int main() {
    vector<int> v = { 9,8,5,211 };
    printVector(v);  // 9 8 5 211

    // 1、pop_back
    v.pop_back();
    printVector(v);  // 9 8 5

    // 2、erase
    vector<int>::iterator it = v.erase(v.begin());  // 返回刚才删除的下一个位置
    printVector(v);  // 8 5
    cout << *it << endl; // 8

    // 3、clear
    v.clear();
    printVector(v);

    return 0;
}

vector 扩容机制

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

void printVector(vector<int>& v) {
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}
/*
vector有容量和大小， 容量>=大小
容量：capacity()
大小：size()

resize   修改的是 size。不改变已有元素。
*/
int main() {
    vector<int> v1 = { 9,8,7,6 };
    printVector(v1);

    cout << "v1.size() = " << v1.size() << endl;             // 4
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 4

    v1.push_back(3);
    cout << "v1.size() = " << v1.size() << endl;             // 5
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 6 变成了原来的1.5倍。根据操作系统不同，可能扩容系数不同

    v1.push_back(1);
    v1.push_back(2);
    // 9 * 1.5 = 13.5 -> 14
    for (int i = 0; i < 3; ++i) {
        v1.push_back(i);
    }

    cout << "v1.size() = " << v1.size() << endl;             // 10
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 13 向下取整

    v1.resize(18); // 改变size大小
    cout << "v1.size() = " << v1.size() << endl;             // 18
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 19  = 13+13/2 向下取整
    printVector(v1);  // 9 8 7 6 3 1 2 0 1 2 0 0 0 0 0 0 0 0

    v1.resize(20, 6);     
    cout << "v1.size() = " << v1.size() << endl;             // 20
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 19 + 19/2 = 28 向下取整
    printVector(v1);  // 新加的2个元素初始化为6： 9 8 7 6 3 1 2 0 1 2 0 0 0 0 0 0 0 0 6 6

    v1.resize(100);
    cout << "v1.size() = " << v1.size() << endl;             // 100
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 100。看源码，100 > 20 + 20/2 = 30，所以直接扩容到100
    printVector(v1);
/*
push_back函数源码分析
private:
    _CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
        // given _Oldcapacity and _Newsize, calculate geometric growth
        const size_type _Oldcapacity = capacity();
        const auto _Max              = max_size();

        if (_Oldcapacity > _Max - _Oldcapacity / 2) {
            return _Max; // geometric growth would overflow
        }

        const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

        if (_Geometric < _Newsize) {
            return _Newsize; // geometric growth would be insufficient
        }

        return _Geometric; // geometric growth is sufficient
    }
*/

    v1.resize(5); // 改变size大小
    cout << "v1.size() = " << v1.size() << endl;             // 5
    cout << "v1.capacity() = " << v1.capacity() << endl;     // 100。
    printVector(v1);  // 9 8 7 6 3

    return 0;
}

vector 随机访问

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

void printVector(vector<int>& v) {
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v = { 9, 8, 7, 6 ,5 };
    cout << v[2] << endl;    // 7 和数组下标访问一样 用中括号访问效率更高些，见源码。
    cout << v.at(2) << endl; // 7 和数组下标访问一样

    //cout << v[12] << endl;    // 未定义行为
    //cout << v.at(12) << endl; // 抛出异常

    cout << "front: " << v.front() << endl;  // 9 5访问第一个元素
    cout << "back: " << v.back() << endl;    // 访问最后一个元素

    return 0;
}

vector 内存交换

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

void printVector(vector<int>& v) {
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}

int main() {
    // 1. 内存交换
    vector<int> v1 = { 1, 2, 3, 4, 5 };
    vector<int> v2 = { 9, 8 , 7, 6, 5};
    cout << "v1: ";
    printVector(v1);   // v1: 1 2 3 4 5
    cout << "v2: ";
    printVector(v2);   // v2: 9 8 7 6 5

    v1.swap(v2);       // 交换v1和v2的内存
    cout << "v1: ";
    printVector(v1);   // v1: 9 8 7 6 5
    cout << "v2: ";
    printVector(v2);   // v2: 1 2 3 4 5

    // 2. 缩容
    v1.resize(10000); 
    v1.resize(5);  // 重新调整v1的大小为5
    cout << "v1.capacity: " << v1.capacity() << endl;  // 10000 
    vector<int>(v1).swap(v1);  // 匿名拷贝构造 vector<>int ()
    cout << "v1.capacity: " << v1.capacity() << endl;  // 5
    cout << "v1.capacity: " << v1.capacity() << endl;  // 5
    vector<int> x(v1);         // 调用拷贝构造函数
    cout << "x.capacity = " << x.capacity() << endl;   // 5

    // 3. 内存清理
    v2.reserve(100000);
    v2.clear();                // 不会清理内存空间，只是会把其size减小
    cout << "v2.capacity: " << v2.capacity() << endl;  // 100000
    vector<int>({}).swap(v2);  // 清理内存
    cout << "v2.capacity: " << v2.capacity() << endl;  // 0


    return 0;
}

vector 空间预留

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

int main() {
    vector<int> v;
    v.reserve(100);  // 预留100个空间
    for (int i = 0; i < 100; ++i) {
        cout << "size = " << v.size() << ", " << "capacity = " << v.capacity() << endl;
        v.push_back(i);
     }

    // reserve  修改的是 capacity
    // resize   修改的是 size
    return 0;
}

vector 高效删除

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

void remove1(vector<int>& v, int index) {
    v.erase(v.begin() + index);  // 内部进行大量的内存移动
}
void remove2(vector<int>& v, int index) {
    swap(v[index], v.back());    // 与最一个元素交换  O(1)
    v.pop_back();                // 删除最后一个元素  O(1)
}

void printVector(vector<int>& v) {
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << ' ';
    }
    cout << endl;
}
int main() {
    // vector的物理结构是数组，所以中间某个元素被删除时，必需让后面的内存向前移动，这个效率就比较低了。
    vector<int> v;
    cout << "remove1: ";
    for (int i = 0; i < 150006; ++i) {
        v.push_back(i);
    }
    for (int i = 0; i < 150000; ++i) {
        remove1(v, 4);
    }
    cout << "结束" << endl;

    // 高效删除
    cout << "remove2: ";
    for (int i = 0; i < 200006; ++i) {
        v.push_back(i);
    }
    for (int i = 0; i < 200000; ++i) {
        remove2(v, 4);   // 前提，是对顺序要求不高的场景高效删除
    }
    //printVector(v);
    cout << "结束" << endl;

    return 0;
}

vector 数据排序

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void printVector(vector<int>& v) {
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << ' ';
    }
    cout << endl;
}

bool cmp(int a, int b) {
    return a > b; // 如果a > b就是逆序排列，如果a < b就是顺序排列
}

int main() {
    // vector数据实际上是一个数组，我们可以用sort接口来排序，需要引用头文件algorithm, 算法
    vector<int> v = { 9, 8 , 7, 1, 2, 3, 4 };
    //sort(v.begin(), v.end()); // sort传入的是左半右开的迭代器
    sort(v.begin(), v.end(), cmp); // 实现cmp做递减排序
    printVector(v);
/*
sort源码分析
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last)
     略
    _STD _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _STD _Pass_fn(_Pred));
}
_CONSTEXPR20 void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t<_RanIt> _Ideal, _Pr _Pred) {
    // order [_First, _Last)
    for (;;) {                                         // 迭代的死循环。不断地切分数组
        if (_Last - _First <= _ISORT_MAX) { // small   // 数组元素个数 <=32 时，使用插入排序。时间复杂度O(n^2)
            _STD _Insertion_sort_unchecked(_First, _Last, _Pred);
            return;
        }
        // divide and conquer by quicksort             // 大于32时，使用快排
        auto _Mid = _STD _Partition_by_median_guess_unchecked(_First, _Last, _Pred);
*/
}

练习

基于排列构建数组

https://leetcode.cn/problems/build-array-from-permutation/description/

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，
其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

示例 1：
输入：nums = [0,2,1,5,3,4]
输出：[0,1,2,4,5,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

示例 2：
输入：nums = [5,0,1,2,3,4]
输出：[4,5,0,1,2,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

提示：
1 <= nums.length <= 1000
0 <= nums[i] < nums.length
nums 中的元素 互不相同

进阶：你能在不使用额外空间的情况下解决此问题吗（即 O(1) 内存）？

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        // 考查vector的插入操作
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < nums.size(); ++i) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
};

数组串联

https://leetcode.cn/problems/concatenation-of-array/

给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，
数组下标 从 0 开始计数 ，对于所有 0 <= i < n 的 i ，满足下述所有要求：

ans[i] == nums[i]
ans[i + n] == nums[i]
具体而言，ans 由两个 nums 数组 串联 形成。

返回数组 ans 。


示例 1：
输入：nums = [1,2,1]
输出：[1,2,1,1,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]

示例 2：
输入：nums = [1,3,2,1]
输出：[1,3,2,1,1,3,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]


提示：
n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {

        int n = nums.size();
        vector<int> ans(nums);  // 利用初始化时拷贝构造函数
        ans.resize(2*n);        // 扩容，前面元素不变，后面值为0
        for (int i = 0; i < n; ++i ) {
            ans[i+n] = nums[i];
        }
        return ans;
    }
};

string

string 基础概念

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // C语言中的字符串是以\0结尾的字符数组
    char a[100] = "你好世界！ Hello, World!";
    cout << a << endl;
    cout << (void*)a << endl; // 转化成 void* 类型输出地址

    // C++中的字符串是以string类来表示的，内部封装了char数组
    string b = "你好世界！ Hello, World!";
    cout << b << endl;

    // a 和 b 的区别
    // a 是字符数组，b 是 string 类对象.
    cout << "sizeof(a): " << sizeof(a) << endl; // 数组大小  100
    cout << "sizeof(b): " << sizeof(b) << endl; // 类对象大小 40
    cout << "length of a: " << strlen(a) << endl; // 字符串长度 24
    cout << "length of b: " << b.length() << endl; // 字符串长度 24

    // 在C中所有对字符串的操作都是通过字符数组来完成的，C++中可以直接使用 string 类通过成员函数来操作字符串
    // 有了 string 类，C++程序员就不需要再去操心字符串的内存分配和释放问题了

    return 0;
}

string 对象创建

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // 1. 无参构造
    string s1;  // 默认构造，s1 为空字符串
    cout << s1 << endl;

    // 2. 初始化列表构造
    string s2({ 'H', 'e', 'l', 'l', 'o' });
    cout << s2 << endl; // 输出 "Hello"

    // 3. 字符串初始化
    string s3("你好，世界！");
    cout << s3 << endl; // 输出 "你好，世界！"

    // 4. 字符串的前n个字符初始化
    string s4("你好，世界！", 6);  // 取前6个字符， 一个中文字符点2个字节，跟编码有关
    cout << s4 << endl; // 输出 "你好，"
    cout << s4.size() << endl; // 输出 6
    cout << (int)s4[4] << endl; // -93 中文字符是由多个ASCII码组成的,并且第一个字节是负数

    // 5. 拷贝构造
    string s5(s4);
    cout << s5 << endl; // 输出 "你好，"

    // 6. a 个 字符 b
    string s6(5, 'A'); // 初始化5个字符A. 注意：这里的 'A' 是单引号，表示字符
    cout << s6 << endl; // 输出 "AAAAA"

    return 0;
}

string 赋值操作

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // 1. 字符串常量的赋值
    string s1;
    s1 = "你好，世界！";
    cout << s1 << endl;

    // 2. 字符串变量的赋值
    string s2;
    s2 = s1; // 将 s1 的值赋给 s2
    cout << s2 << endl;

    // 3. 字符常量赋值
    string s3;
    s3 = 'A'; // 将字符 'A' 赋值给字符串 s3
    cout << s3 << endl;

    // 4. assign() 方法赋值 v1
    string s4;
    s4.assign("你好，世界！");
    cout << s4 << endl;

    // 5. assign() 方法赋值 v2
    string s5;
    s5.assign("你好，世界！", 6); // 只赋值前 6 个字符
    cout << s5 << endl;

    // 6. assign() 方法赋值 v3
    string s6;
    s6.assign(s5); // 将 s5 的值赋给 s6
    cout << s6 << endl;

    // 7. a个b
    string s7;
    s7.assign(8, '6'); // 将字符 '6' 重复 8 次赋值给 s7
    cout << s7 << endl;

    return 0;
}

string 拼接操作

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

// C语言字符串拼接使用 strcat 函数，C++中可以使用 string 类的 + 运算符进行字符串拼接。

int main() {
    // 1. +
    string s1 = "你好";
    string t1 = "世界";
    s1 = s1 + "，";      // 加字符串 const char*
    s1 = s1 + t1;        // const string&
    //cout << s1 << endl;
    s1 = s1 + ';';        // 加字符 char
    cout << s1 << endl;

    // 2. +=
    string s2 = "世界";
    string t2 = "好啊";
    s2 += "，";      // 加字符串 const char*
    s2 += t2;        // const string&
    //cout << s2 << endl;
    s2 += ';';        // 加字符 char
    cout << s2 << endl;

    // 3. append
    string s3 = "大家";
    string t3 = "好";
    s3.append("都");
    s3.append(t3);
    s3.append("5201314", 3);    // 字符串取3个
    //cout << s3 << endl;       // 大家都好520
    s3.append("5201314", 3, 4); // 从第三个位置开始取4个元素
    cout << s3 << endl;         // 大家都好5201314

    // 4. push_back
    string s4 = "你好";
    s4.push_back('6');           // 只能向后添加字符
    s4.push_back('6');
    s4.push_back('6');
    cout << s4 << endl;          // 你好666

    return 0;
}

string 比较操作

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // 1. compare
    string s1 = "aab";

    string t11 = "aab";
    int r11 = s1.compare(t11);  // 比较的结果有3种小于等于大于， 即-1 0 1
    cout << s1 << " compare " << t11 << " -> " << r11 << endl; // aab compare aab -> 0

    string t12 = "aaa";
    int r12 = s1.compare(t12);
    cout << s1 << " compare " << t12 << " -> " << r12 << endl; // aab compare aaa -> 1   a与a 比较返回0 a 与a比较, b>a 返回 1

    string t13 = "aac";
    int r13 = s1.compare(t13);
    cout << s1 << " compare " << t13 << " -> " << r13 << endl; // aab compare aac -> -1 

    string t14 = "aaba";
    int r14 = s1.compare(t14);
    cout << s1 << " compare " << t14 << " -> " << r14 << endl; // aab compare aaba -> -1 长度，短的减长的等于 -1

    string t15 = "aa";
    int r15 = s1.compare(t15);
    cout << s1 << " compare " << t15 << " -> " << r15 << endl; // aab compare aa -> 1 长度，长的减短的等于 1
/*
compare源码分析
    _NODISCARD _CONSTEXPR20 int compare(const basic_string& _Right) const noexcept {
        return _Traits_compare<_Traits>(_Mypair._Myval2._Myptr(), _Mypair._Myval2._Mysize,
            _Right._Mypair._Myval2._Myptr(), _Right._Mypair._Myval2._Mysize);
    }

constexpr int _Traits_compare(_In_reads_(_Left_size) const _Traits_ptr_t<_Traits> _Left, const size_t _Left_size,
    _In_reads_(_Right_size) const _Traits_ptr_t<_Traits> _Right, const size_t _Right_size) noexcept {
    // compare [_Left, _Left + _Left_size) to [_Right, _Right + _Right_size) using _Traits
    const int _Ans = _Traits::compare(_Left, _Right, (_STD min)(_Left_size, _Right_size));  // 取最小值 _STD min

    if (_Ans != 0) {
        return _Ans;
    }

    if (_Left_size < _Right_size) {  // 前面的长度小于后面的长度，返回-1
        return -1;
    }

    if (_Left_size > _Right_size) {  // 前面的长度大于后面的长度，返回1
        return 1;
    }

    return 0;
}
*/

    // 2. < > = <= >=
    cout << s1 << " == " << t11 << " -> " << (s1 == t11) << endl; // aab == aab -> 1 运算符的重载
    cout << s1 << " != " << t11 << " -> " << (s1 != t11) << endl; // aab != aab -> 0
    cout << s1 << " < " << t12 << " -> " << (s1 < t12) << endl;   // aab < aaa -> 0

    return 0;
}

string 随机访问

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // 随机访问任意一个下标位置
    string s = "I love you 1314";
    // 1. 访问
    cout << s << endl;   // I love you 1314
    for(int i = 0; i < s.size(); ++i) {
        // s.size() 返回字符串的长度，不包括终止符 '\0'
        cout << s[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < s.size(); ++i) {
        cout << s.at(i) << " ";
    }
    cout << endl;     // I   l o v e   y o u   1 3 1 4

    //s[100];

    // 2. 修改
    s[11] = '5';
    s[12] = '2';
    s.at(13) = '0';  // 返回的是引用，可以被修改
    s.at(14) = ' ';
    cout << s << endl;  // I love you 520

    return 0;
}

string 数据插入

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    string s1 = "Heworld";
    s1.insert(2, 2, 'l'); // 位置、个数、字符。 表示在2的位置前面插入2个l字符
    cout << s1 << endl;   // Hellworld
    s1.insert(4, "o");    // 在4的位置插入字符串o
    cout << s1 << endl;   // Helloworld

    s1.insert(s1.size(), "aaaa"); // 最后插入字符串
    cout << s1 << endl;   // Helloworldaaaa

    // 传迭代器，插入字符
    s1.insert(s1.begin(), ':');
    cout << s1 << endl;    // :Helloworldaaaa


    return 0;
}

string 数据删除

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    string s1;

    // 1
    s1 = "Hello woooorld";
    s1.erase();          // 全部删除
    cout << s1 << endl;  // 返回空串

    // 2
    s1 = "Hello woooorld";
    s1.erase(7);         // 删除从7位置开始到结尾的所有字符
    cout << s1 << endl;  // Hello w

    // 3
    s1 = "Hello woooorld";
    s1.erase(7, 3);      // 从7位置开始删除3个字符
    cout << s1 << endl;  // Hello world

    // 4
    s1 = "Hello woooorld";
    s1.erase(s1.begin()); // 传入迭代器，删除1个字符
    cout << s1 << endl;   // ello woooorld

    s1 = "Hello woooorld";
    s1.erase(s1.begin() + 7, s1.begin() + 10); // 删除左半右开区间中的字符。 [x, y)
    cout << s1 << endl;   // Hello world


    return 0;
}

string 数据查找

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // 查找一个字符串是否在另一个字符串中是否存在，并返回下标索引
    string s1;

    // 1
    s1 = "Hello woooorld";
    cout << s1.find("oooo") << endl;  // 7

    // 2
    s1 = "Hello woooorld";
    cout << (int)s1.find("oooo", 8) << endl;  // 从8位置开始找，没找到返回值为 -1
    cout << (int)s1.find("oooo", 5) << endl;  // 7

    // 3
    cout << s1.find('o') << endl;             // 4
    cout << s1.find('o', s1.find('o')+1) << endl;  // 从第5个位置开始找字符o的位置，输出为7

    // 4
    cout << s1.rfind("oo") << endl;          // 从右开始向左找，找到oo的位置，输出为 9

    return 0;
}

string 数据替换

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    string s;

    // 1
    s = "Hello woooorld";
    s.replace(7, 5, "or");   // 位置、个数、替换的字符串。 从7位置开始的5个元素oooor替换成or
    cout << s << endl;       // Hello world

    // 2
    s = "Hello woooorld";
    s.replace(s.begin() + 7, s.begin() + 12, "or"); // 传迭代器， [起始位置，终止位置)、替换的字符串
    cout << s << endl;       // Hello world

    // 3
    s = "Hello woooorld";
    s.replace(s.begin() + 7, s.begin() + 12, "orxxxxxxxxxxxxxxxxx", 2); // 传迭代器， [起始位置，终止位置)、替换的字符串前2个字符
    cout << s << endl;       // Hello world

    return 0;
}

string 子串获取

#include <iostream>
// #include <string> // 已经被包含在 <iostream> 中
using namespace std;

int main() {
    // 子串：给定一个字符串和一个下标以及要获取字符的数量，返回原字符串的子串
    string s1;
    s1 = "Hello woooorld";
    string subStr = s1.substr(7, 4);
    cout << subStr << endl;          // oooo

    // 应用
    string s2 = "你好&&世界";
    int pos = s2.find("&&");         // 拿到&&的位置
    string s3 = s2.substr(0, pos);
    string s4 = s2.substr(pos+2);    // 从pos+2位置开始到最后
    cout << s3 << ' ' << s4 << endl; // 你好 世界

    return 0;
}

练习

动态口令

https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

在学习章节提到过[[h:learn-module-up-packages][(精选 packages, 大大提升你的 Emacs 编辑效率)]]

某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：

设定一个正整数目标值 target
将 password 前 target 个字符按原顺序移动至字符串末尾
请返回更新后的密码字符串。

示例 1：
输入: password = "s3cur1tyC0d3", target = 4
输出: "r1tyC0d3s3cu"

示例 2：
输入: password = "lrloseumgh", target = 6
输出: "umghlrlose"

提示：
1 <= target < password.length <= 10000

class Solution {
public:
    string dynamicPassword(string password, int target) {
        return password.substr(target)+password.substr(0, target);
    }
};

查找包含给定字符的单词

https://leetcode.cn/problems/find-words-containing-character/

给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。

请你返回一个 下标数组 ，表示下标在数组中对应的单词包含字符 x 。

注意 ，返回的数组可以是 任意 顺序。

示例 1：
输入：words = ["leet","code"], x = "e"
输出：[0,1]
解释："e" 在两个单词中都出现了："leet" 和 "code" 。所以我们返回下标 0 和 1 。

示例 2：
输入：words = ["abc","bcd","aaaa","cbc"], x = "a"
输出：[0,2]
解释："a" 在 "abc" 和 "aaaa" 中出现了，所以我们返回下标 0 和 2 。

示例 3：
输入：words = ["abc","bcd","aaaa","cbc"], x = "z"
输出：[]
解释："z" 没有在任何单词中出现。所以我们返回空数组。

提示：
1 <= words.length <= 50
1 <= words[i].length <= 50
x 是一个小写英文字母。
words[i] 只包含小写英文字母。

class Solution {
public:
    vector<int> findWordsContaining(vector<string>& words, char x) {
        vector<int> ans;
        for(int i = 0; i < words.size(); ++i) {
            for(int j = 0; j < words[i].size(); ++j) {
                if(words[i][j] == x) {
                    ans.push_back(i);  // 只需插入一次
                    break;
                }
            }
        }
        return ans;
    }
};

分段顺序表

deque

deque 基础概念

双端队列，可以在头部和尾部插入。

front() 头部元素
- push_front() 头部插入
- po_front() 头部删除
back() 尾部元素
- push_back() 尾部插入
- pop_back() 尾部删除
begin() 指向头部的迭代器
end() 指向尾部的下一个元素迭代器

vector也支持，为什么要引入deque?

因为vector在头部插入元素时，会把后面的元素向后挪。当vector元素很多时，插入效率就非常低了。

deque核心是指针数组，数组中的元素是指针指向一块连续的内存。

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

int main() {
    deque<int> d;

    return 0;
}

deque 对象创建

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

void printDeque(deque<int>& d) {
    for (deque<int>::iterator iter = d.begin(); iter != d.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}
int main() {
    // 1. 默认构造函数
    deque<int> d1;
    cout << "d1: ";
    printDeque(d1);    // d1:

    // 2. 初始化列表
    deque<int> d2_1({ 9, 8, 8, 6, 5 });
    cout << "d2_1: ";
    printDeque(d2_1);  // d2_1: 9 8 8 6 5
    deque<int> d2_2 = { 1, 8, 8, 6, 5 };
    cout << "d2_2: ";
    printDeque(d2_2);  // d2_2: 1 8 8 6 5

    // 3. 迭代器
    deque<int> d3(d2_1.begin()+1, d2_1.end()-1);
    cout << "d3: ";
    printDeque(d3);    // d3: 8 8 6

    // 4. 全0初始化
    deque<int> d4(10);
    cout << "d4: ";
    printDeque(d4);    // d4: 0 0 0 0 0 0 0 0 0 0

    // 5. deque<int> 变量名(a, b)  表示申请a个元素空间，每个元素的值初始化为b
    deque<int> d5(8, 6);
    cout << "d5: ";
    printDeque(d5);    // d5: 6 6 6 6 6 6 6 6

    // 6. 拷贝构造函数
    deque<int> d6(d5);
    cout << "d6: ";
    printDeque(d6);    // d6: 6 6 6 6 6 6 6 6

    return 0;
}

deque 赋值操作

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

void printDeque(deque<int>& d) {
    for (deque<int>::iterator iter = d.begin(); iter != d.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}
int main() {
    deque<int> d = { 9,8,5,2,1,1 };
    cout << "d: ";
    printDeque(d);  // d: 9 8 5 2 1 1

    // 1. = 赋值
    deque<int> d1;
    d1 = d;
    cout << "d1: ";
    printDeque(d1); // d1: 9 8 5 2 1 1

    // 2. assign(迭代器)
    deque<int> d2;
    d2.assign(d1.begin() + 1, d1.end());
    cout << "d2: ";
    printDeque(d2); // d2: 8 5 2 1 1

    // 3. 初始化列表
    deque<int> d3;
    d3.assign({ 1,2,3,5,6,7 });
    cout << "d3: ";
    printDeque(d3); // d3: 1 2 3 5 6 7

    // 4. 初始化a个b
    deque<int> d4;
    d4.assign(8, 6); // 申请8个元素空间，元素值都为6
    cout << "d4: ";
    printDeque(d4);  // d4: 6 6 6 6 6 6 6 6

    return 0;
}

deque 大小操作

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

void printDeque(deque<int>& d) {
    /*for (deque<int>::iterator iter = d.begin(); iter != d.end(); iter++) {
        cout << *iter << " ";
    }*/
    for (int i = 0; i < d.size(); ++i) {
        cout << d[i] << " ";
    }
    cout << endl;
}

/*
1、empty  判断是否为空
2、size   获取元素个数
3、resize 设置元素个数
*/
int main() {
    deque<int> d;

    cout << "d.empty() = " << d.empty() << endl;  // 1
    cout << "d.size() = " << d.size() << endl;    // 0

    d.assign({ 1,2,3 });
    cout << "d.empty() = " << d.empty() << endl;  // 0
    cout << "d.size() = " << d.size() << endl;    // 3
    printDeque(d);  // 1 2 3

    d.resize(18);
    cout << "d.size() = " << d.size() << endl;    // 18
    printDeque(d);  // 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    d.resize(20, 6); // 从18到20，对新增的2个元素初始化为6    
    cout << "d.size() = " << d.size() << endl;    // 20
    printDeque(d);  // 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6

    d.resize(10000);
    d.resize(5);
    cout << "d.size() = " << d.size() << endl;    // 5
    printDeque(d);  // 1 2 3 0 0

    return 0;
}

deque 数据插入

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

void printDeque(deque<int>& d) {
    /*for (deque<int>::iterator iter = d.begin(); iter != d.end(); iter++) {
        cout << *iter << " ";
    }*/
    for (int i = 0; i < d.size(); ++i) {
        cout << d[i] << " ";
    }
    cout << endl;
}

/*
1、push_front 头插
2、push_back  尾插
3、insert     中间插
*/
int main() {
    deque<int> d;

    // 1、push_front 头插
    d.push_front(-1);
    d.push_front(-2);
    d.push_front(-3);
    printDeque(d); // -3 -2 -1

    // 2、push_back  尾插
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    printDeque(d); // -3 -2 -1 1 2 3

    // 3、insert     中间插
    d.insert(d.begin() + 3, 0); // 在3的位置插入0
    d.insert(d.end() - 1, 5, 8); // 在最后前面的位置插入5个8
    printDeque(d); // -3 -2 -1 0 1 2 8 8 8 8 8 3

    d.insert(d.begin() + 1, d.begin() + 4, d.begin() + 6); // 在1的位置插入从4位置到6位置的值, 左闭右开 [4, 6)。
    printDeque(d); // -3 1 2 -2 -1 0 1 2 8 8 8 8 8 3

    return 0;
}

deque 数据删除

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

void printDeque(deque<int>& d) {
    /*for (deque<int>::iterator iter = d.begin(); iter != d.end(); iter++) {
        cout << *iter << " ";
    }*/
    for (int i = 0; i < d.size(); ++i) {
        cout << d[i] << " ";
    }
    cout << endl;
}

/*
1、pop_front 头删
2、pop_back  尾删
3、erase、clear
*/
int main() {
    deque<int> d = { -1, 9, 8, 5, 2, 1, 1, -1 };
    printDeque(d);  // -1 9 8 5 2 1 1 -1

    // 1、pop_front 头删
    d.pop_front();
    printDeque(d); // 9 8 5 2 1 1 -1

    // 2、pop_back  尾删
    d.pop_back();
    printDeque(d); // 9 8 5 2 1 1

    // 3、erase、clear
    // 删除1个元素
    deque<int>::iterator it = d.erase(d.begin() + 2);  // 删除位置2的值，返回下一个位置
    printDeque(d);  // 9 8 2 1 1
    cout << *it << endl;  // 2
    it = d.erase(it);
    printDeque(d);  // 9 8 1 1
    cout << *it << endl; // 1
    // 删除多个元素
    d.erase(d.begin() + 1, d.begin() + 3); // 从位置1删除2个元素
    printDeque(d); // 9 1

    // 删除所有
    d.clear();

    cout << "d.empty() = " << d.empty() << endl;  // 1
    cout << "d.size() = " << d.size() << endl;    // 0

    return 0;
}

deque 扩容机制

deque物理结构是一个指针数组。

源码中

_Map = 0x0000000 指针数组的首地址
_Mysize = 0 元素大小
_Myoff = 0 每次往前插入off减1。向后插这个值不更新
Mapsize = 0 指针数组的长度
_Ty = long long 类型
_Block_size = 2 根据类型更新对应的值

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

int main() {
    deque<long long> d;

    for (int i = 0; i < 9; ++i) {
        d.push_back(i);
    }
    for (int i = 9; i < 18; ++i) {
        d.push_front(i);
    }
    return 0;
}

打断点调试。

deque 随机访问

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

int main() {
    // 随机访问可以理解为数组的下标访问 
    deque<int> d = { 9, 8, 7, 6, 5 };

    cout << d[2] << endl;    // 7
    cout << d.at(3) << endl; // 6

    cout << d.front() << endl; // 9
    cout << d.back() << endl;  // 5

/* 源码分析
at()：检查范围并返回指定位置的元素，如果索引超出范围则抛出异常。
operator[]：直接返回指定位置的元素，不进行范围检查。
    _NODISCARD reference operator[](size_type _Pos) noexcept {
#if _MSVC_STL_HARDENING_DEQUE || _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Pos < _Mysize(), "deque subscript out of range");
#endif

        return _Subscript(_Pos);
    }
    _NODISCARD reference at(size_type _Pos) {
        if (_Mysize() <= _Pos) {
            _Xran();
        }

        return _Subscript(_Pos);
    }

        reference _Subscript(size_type _Pos) noexcept {
        return _Get_data()._Subscript(_Myoff() + _Pos);
    }

    class _Deque_val : public _Container_base12 {
public:
    _Map_difference_type _Getblock(size_type _Off) const noexcept {
        // NB: _Mapsize and _Block_size are guaranteed to be powers of 2
        return static_cast<_Map_difference_type>((_Off / _Block_size) & (_Mapsize - 1));
    }

    reference _Subscript(size_type _Off) noexcept {
        const auto _Block     = _Getblock(_Off);
        const auto _Block_off = static_cast<difference_type>(_Off % _Block_size);
        return _Map[_Block][_Block_off];
    }

    _Map[_Block][_Block_off]：
      _Map 是指针数组，
      _Block 位置_Off/_Block_size 得到块索引，
      再通过下标索引_Block_off拿到具体的值

*/
    return 0;
}

练习

设计循环双端队列

https://leetcode.cn/problems/design-circular-deque/

设计实现双端队列。

实现 MyCircularDeque 类:

MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。


示例 1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", 
"insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);                    // 返回 true
circularDeque.insertLast(2);                    // 返回 true
circularDeque.insertFront(3);                   // 返回 true
circularDeque.insertFront(4);                   // 已经满了，返回 false
circularDeque.getRear();                        // 返回 2
circularDeque.isFull();                         // 返回 true
circularDeque.deleteLast();                     // 返回 true
circularDeque.insertFront(4);                   // 返回 true
circularDeque.getFront();                       // 返回 4

提示：
1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull  调用次数不大于 2000 次

class MyCircularDeque {
    deque<int> d;
    int capacity; // 容量
    int size;     // 当前元素个数
public:
    MyCircularDeque(int k) {
        d.clear();
        capacity = k;
        size = 0;
    }

    bool insertFront(int value) {
        if (capacity == size) {  // 队列满了不能执行插入
            return false;
        }
        ++size;
        d.push_front(value);
        return true;
    }

    bool insertLast(int value) {
        if (capacity == size) {  // 队列满了不能执行插入
            return false;
        }
        ++size;
        d.push_back(value);
        return true;
    }

    bool deleteFront() {
        if (size == 0) {  // size为0时不能执行删除
            return false;
        }
        size--;
        d.pop_front();
        return true;
    }

    bool deleteLast() {
                if (size == 0) {  // size为0时不能执行删除
            return false;
        }
        size--;
        d.pop_back();
        return true;
    }

    int getFront() {
        if(size == 0) return -1;
        return d.front();
    }

    int getRear() {
        if(size == 0) return -1;
        return d.back();
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

设计浏览器历史记录

class BrowserHistory {
    deque<string> urls;
    int currIndex;
public:
    BrowserHistory(string homepage) {
        urls.push_back(homepage);
        currIndex = 0;
    }

    void visit(string url) {
        while(urls.size() > currIndex+1){
            urls.pop_back();
        }
        urls.push_back(url);
        currIndex++;
    }

    string back(int steps) {
        currIndex = max(currIndex - steps, 0);
        return urls[currIndex];
    }

    string forward(int steps) {
        currIndex = min(currIndex + steps, int(urls.size() - 1));
        return urls[currIndex];
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */

链表

list

list 基础概念

底层结构是deque双端队列。

逻辑结构和vector是一样的

front() 头部元素
- push_front() 头部插入
- po_front() 头部删除
back() 尾部元素
- push_back() 尾部插入
- pop_back() 尾部删除
begin() 指向头部的迭代器
end() 指向尾部的下一个元素迭代器

物理结构

节点node
- val
- next 指向下一个node的指针
- prev 指向上一个node的指针

是个双向循环链表。

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

int main() {
    list<int> l;

/*
class list { // bidirectional linked list
    _Compressed_pair<_Alnode, _Scary_val> _Mypair;
};

    using _Scary_val = _List_val<_Val_types>;

    class _List_val : public _Container_base {
public:
    _List_val() noexcept : _Myhead(), _Mysize(0) {} // initialize data
    ...};
    ...

        _Nodeptr _Myhead; // pointer to head node
    ...

    using _Nodeptr = typename _Val_types::_Nodeptr;
    ...

    using _Node    = _List_node<_Ty, void*>;
    using _Nodeptr = _Node*;
    ...

    struct _List_node { // list node
    using value_type = _Value_type;
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _List_node>;
    _Nodeptr _Next; // successor node, or first element if head
    _Nodeptr _Prev; // predecessor node, or last element if head
    _Value_type _Myval = // the stored value, unused if head
*/

    return 0;
}

list 对象创建

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    // 1. 默认构造函数
    list<int> l1;
    cout << "l1: ";
    printList(l1); // l1:

    // 2. 初始化列表
    list<int> l2_1 = {9,8,7,6,5};
    cout << "l2_1: ";
    printList(l2_1);  // l2_1: 9 8 7 6 5

    list<int> l2_2({ 9,8,7,1,5 });
    cout << "l2_2: ";
    printList(l2_2);  // l2_2: 9 8 7 1 5

    // 3. 迭代器
    list<int> l3(l2_1.begin(), l2_1.end()); // 把l2_1的元素复制到l3
    cout << "l3: ";
    printList(l3);    // l3: 9 8 7 6 5

    // 4. 全0初始化
    list<int> l4(8);
    cout << "l4: ";
    printList(l4);    // l4: 0 0 0 0 0 0 0 0

    // 5. list<int> 变量名(a, b) 表示申请a个空间的元素，每个元素初始化为b
    list<int> l5(8, 6);
    cout << "l5: ";
    printList(l5);    // l5: 6 6 6 6 6 6 6 6

    // 6. 拷贝构造函数
    list<int> l6(l2_2);
    cout << "l6: ";
    printList(l6);    // l6: 9 8 7 1 5

    return 0;
}

list 赋值操作

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    list<int> l = { 9, 8, 5, 2, 1, 1 };
    cout << "l: ";
    printList(l);  // l: 9 8 5 2 1 1

    // 1. = 赋值
    list<int> l1;
    l1 = l;
    cout << "l1 ";
    printList(l1);  // l1: 9 8 5 2 1 1

    // 2. assign(迭代器区间)
    list<int> l2;
    l2.assign(l.begin(), l.end());
    cout << "l2: ";
    printList(l1);  // l2: 9 8 5 2 1 1

    // 3. assign(初始值列表)
    list<int> l3;
    l3.assign({ 1,3,1,4 });
    cout << "l3: ";
    printList(l3);  // l3: 1 3 1 4

    // 4. assign(元素个数a, 初始值b) 初始化a个b
    list<int> l4;
    l4.assign(8, 6);
    cout << "l4: ";
    printList(l4);  // l4: 6 6 6 6 6 6 6 6

    return 0;
}

list 大小操作

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

/*
1、empty 判断列表是否为空
2、size 返回列表中元素的个数
3、resize 改变列表的大小 并把数据初始化为指定值
*/
int main() {
    list<int> l;
    cout << "l.empty() = " << l.empty() << endl; // 1
    cout << "l.size() = " << l.size() << endl;   // 0

    l.assign({ 1,2,3 });
    cout << "l.empty() = " << l.empty() << endl; // 0
    cout << "l.size() = " << l.size() << endl;   // 3

    l.resize(18);
    cout << "l.empty() = " << l.empty() << endl; // 0
    cout << "l.size() = " << l.size() << endl;   // 18
    printList(l); // 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    l.resize(20, 6);
    cout << "l.empty() = " << l.empty() << endl; // 0
    cout << "l.size() = " << l.size() << endl;   // 20
    printList(l); // 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6

    l.resize(10000);
    l.resize(5);
    cout << "l.empty() = " << l.empty() << endl; // 0
    cout << "l.size() = " << l.size() << endl;   // 5
    printList(l); // 1 2 3 0 0

    return 0;
}

list 数据插入

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

/*
1、push_front 头插
2、push_back  尾插
3、insert     中间插
*/

int main() {
    list<int> l;

    // 1、push_front 头插
    l.push_front(-1); // -1
    l.push_front(-2); // -2 -1
    l.push_front(-3); // -3 -2 -1
    printList(l);     // -3 -2 -1

    // 2、push_back  尾插
    l.push_back(1);  // -3 -2 -1 1
    l.push_back(2);  // -3 -2 -1 1 2
    l.push_back(3);  // -3 -2 -1 1 2 3
    printList(l);    // -3 -2 -1 1 2 3

    // 3、insert     中间插
    // 3.1 insert(迭代器, 值)
    list<int>::iterator it = l.begin();
    it++;
    it++;
    it++;
    //it = it + 1; // 没有这样的运算，如果实现了会造成访问效率低下如 it = it + 7000000000
    l.insert(it, 0); // -3 -2 -1 0 1 2 3
    printList(l);    // -3 -2 -1 0 1 2 3

    // 3.1 insert(迭代器, 数量, 值)
    it = l.end();
    --it;
    l.insert(it, 5, 8);
    printList(l); // -3 -2 -1 0 1 2 8 8 8 8 8 3

    // 3.1 insert(迭代器, 迭代器的开始位置, 迭代器的结束位置)
    it = l.begin();
    it++;
    l.insert(it, l.begin(), l.end());
    printList(l);  // -3 -3 -2 -1 0 1 2 8 8 8 8 8 3 -2 -1 0 1 2 8 8 8 8 8 3

    return 0;
}

list 数据删除

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

/*
1、pop_front 头删
2、pop_back  尾删
3、erase、clear
*/

int main() {
    list<int> l = { -1, 9, 8 ,5 ,2,1,1, -1};
    printList(l);   // -1 9 8 5 2 1 1 -1
    l.pop_back();
    printList(l);   // -1 9 8 5 2 1 1
    l.pop_front();
    printList(l);   // 9 8 5 2 1 1

    list<int>::iterator it = l.erase(l.begin());  // 删除第一个元素，返回下一个元素的迭代器
    printList(l);   // 8 5 2 1 1
    cout << *it << endl;  // 8
    it = l.erase(it);  // 删除8，返回下一个元素的迭代器
    printList(l);   // 5 2 1 1
    cout << *it << endl;  // 5

    it++;
    it++;
    l.erase(it, l.end());  // 删除从it到结尾的所有元素
    printList(l);   // 5 2

    l.clear();  // 清空列表
    printList(l);   // 空
    cout << "l.size() = " << l.size() << endl; // 0

    return 0;
}

list 数据访问

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int getListItemByIndex(list<int>& l, int index) {
    list<int>::iterator it = l.begin();
    while (index) {  // 让it向后走
        it++;
        index--;
    }
    return *it;
}

int main() {
    list<int> l = { -1, 9, 8 ,5 ,2,1,1, -1};

    // list没有 l[4] l.at(4) 方法，无法进行随机访问，因为效率低(底层是双向链表)。不希望被滥用

    list<int>::iterator it = l.begin();
    //it++;
    //it = it + 1000000000; 没有实现，效率低
    cout << getListItemByIndex(l, 4) << endl;  // 2

    cout << l.front() << endl;  // -1
    cout << l.back() << endl;   // -1

    return 0;
}

list 链表反转

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    list<int> l({1,2,3});
    printList(l);
    l.reverse();
    printList(l);

/*reverse反转函数源码参考
    void reverse() noexcept { // reverse sequence
        const _Nodeptr _Phead = _Mypair._Myval2._Myhead; // 获取链表头节点指针
        _Nodeptr _Pnode       = _Phead;

        for (;;) { // flip pointers in a node  遍历链表节点，交换每个节点的前驱和后继指针
            const _Nodeptr _Pnext = _Pnode->_Next;
            _Pnode->_Next         = _Pnode->_Prev;
            _Pnode->_Prev         = _Pnext;

            if (_Pnext == _Phead) { // 如果下一个节点是头节点，说明已经遍历完整个链表，退出循环
                break;
            }

            _Pnode = _Pnext;  // 当前执行交换后，移动到下一个节点继续交换
        }
    }
*/
    return 0;
}

list 链表排序

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

void printList(const list<int>& l) {
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int cmp(int a, int b) {
    return a > b;
}

int main() {
    list<int> l({4,2,6,5,3,1});
    l.sort();
    printList(l);  // 1 2 3 4 5 6
    l.sort(cmp);
    printList(l);  // 6 5 4 3 2 1

    /* 排序相关代码片段
     void sort(_Pr2 _Pred) { // order sequence
        auto& _My_data = _Mypair._Myval2;
        _Scary_val::_Sort(_My_data._Myhead->_Next, _My_data._Mysize, _STD _Pass_fn(_Pred));
    }

     static _Nodeptr _Sort(_Nodeptr& _First, const size_type _Size, _Pr2 _Pred) {
        // order [_First, _First + _Size), return _First + _Size
        switch (_Size) {
        case 0:
            return _First;
        case 1:
            return _First->_Next;
        default:
            break;
        }

        auto _Mid        = _Sort(_First, _Size / 2, _Pred);        // 递归调用 前半段让它有序
        const auto _Last = _Sort(_Mid, _Size - _Size / 2, _Pred);  // 递归调用 后半段让它有序
        _First           = _Merge_same(_First, _Mid, _Last, _Pred);  // 合并两个有序链表，归并排序的过程
        return _Last;
    }

    _Nodeptr _Myhead; // pointer to head node
    size_type _Mysize; // number of elements
};

    static _Nodeptr _Merge_same(_Nodeptr _First, _Nodeptr _Mid, const _Nodeptr _Last, _Pr2 _Pred) {
        // Merge the sorted ranges [_First, _Mid) and [_Mid, _Last)
        // Returns the new beginning of the range (which won't be _First if it was spliced elsewhere)
        _STL_INTERNAL_CHECK(_First != _Mid && _Mid != _Last);
        _Nodeptr _Newfirst;
        if (_DEBUG_LT_PRED(_Pred, _Mid->_Myval, _First->_Myval)) {  // DEBUG_LT_PRED是个宏，实际调用了_Pred函数
            // _Mid will be spliced to the front of the range
            _Newfirst = _Mid;
        } else {

#define _DEBUG_LT_PRED(pred, x, y)                _STD _Debug_lt_pred(pred, x, y)

_NODISCARD constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right)
    noexcept(noexcept(_Pred(_Left, _Right)) && _Debug_lt_pred_order_check_noexcept<_Pr, _Ty1, _Ty2>) {
    const auto _Result = static_cast<bool>(_Pred(_Left, _Right));  // 比较函数

    if constexpr (_Enable_debug_lt_pred_order_check<_Pr, _Ty1, _Ty2>) {
        if (_Result) {
            _STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
        }
    }
        return _Result;

 */
    return 0;
}

归并排序比快排更容易理解、比冒泡排序的效率更高。

练习

设计循环双端队列

https://leetcode.cn/problems/design-circular-deque/

设计实现双端队列。

实现 MyCircularDeque 类:
MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：
输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);                            // 返回 true
circularDeque.insertLast(2);                            // 返回 true
circularDeque.insertFront(3);                           // 返回 true
circularDeque.insertFront(4);                           // 已经满了，返回 false
circularDeque.getRear();                                // 返回 2
circularDeque.isFull();                                 // 返回 true
circularDeque.deleteLast();                             // 返回 true
circularDeque.insertFront(4);                           // 返回 true
circularDeque.getFront();                               // 返回 4


提示：
1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull  调用次数不大于 2000 次

class MyCircularDeque {
    list<int> d;   // deque和list的逻辑结构是一样的，不一样的是物理结构
    int capacity; // 容量
    int size;     // 当前元素个数
public:
    MyCircularDeque(int k) {
        d.clear();
        capacity = k;
        size = 0;
    }

    bool insertFront(int value) {
        if (capacity == size) {  // 队列满了不能执行插入
            return false;
        }
        ++size;
        d.push_front(value);
        return true;
    }

    bool insertLast(int value) {
        if (capacity == size) {  // 队列满了不能执行插入
            return false;
        }
        ++size;
        d.push_back(value);
        return true;
    }

    bool deleteFront() {
        if (size == 0) {  // size为0时不能执行删除
            return false;
        }
        size--;
        d.pop_front();
        return true;
    }

    bool deleteLast() {
                if (size == 0) {  // size为0时不能执行删除
            return false;
        }
        size--;
        d.pop_back();
        return true;
    }

    int getFront() {
        if(size == 0) return -1;
        return d.front();
    }

    int getRear() {
        if(size == 0) return -1;
        return d.back();
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

回文链表

https://leetcode.cn/problems/aMhZSa/

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：
输入: head = [1,2,3,3,2,1]
输出: true

示例 2：
输入: head = [1,2]
输出: false

提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 用list实现，把原链表中的元素值按顺序遍历出来，存储在list中。再用list中的反向迭代器逆序遍历
        list<int> li;
        ListNode* tmp = head;
        while (tmp) {
            li.push_back(tmp->val);
            tmp = tmp->next;
        }
        for(list<int>::reverse_iterator it = li.rbegin(); it != li.rend(); it++) {
            if( (*it) != head->val) {
                return false;
            }
            head = head->next;
        }
        return true;
    }
};

容器适配器

stack

stack 基础概念

相比于vector和deque，它是只支持在尾部插入和删除的容器，并且遵循后进先出。

top() 获取栈顶元素
push() 入栈：向容器插入元素
pop() 出栈：从栈顶删除元素

stack不支持遍历。低层使用deque实现。

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

int main() {
    stack<int> stk; // 定义一个存储整数的栈

    return 0;
}

stack 对象创建

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

int main() {
    // 1. 默认构造函数
    stack<int> stk1;

    // 2. 拷贝构造函数
    stack<int> stk2(stk1);

    // 低层使用了deque作为底层容器,只要复用尾插功能即可

/* 源码分析
_EXPORT_STD template <class _Ty, class _Container = deque<_Ty>>
class stack {
*/

    return 0;
}

stack 赋值操作

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

int main() {
    stack<int> stk1;
    stack<int> stk2;

    stk1 = stk2;  // 调用了deque中的=号运算符重载
/*deque源码分析
    deque& operator=(const deque& _Right) {
*/

    return 0;
}

stack 入栈操作

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

int main() {
    stack<int> stk;

    stk.push(5);  // 调用的deque的push_back, 双端队列的尾插法
    stk.push(4);
    stk.push(3);
    stk.push(2);
    stk.push(1);  // 5 4 3 2 1

    return 0;
}

stack 获取栈顶

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

int main() {
    stack<int> stk;
    stk.push(5); cout << stk.top() << endl; // 5  获取栈顶元素
    stk.push(4); cout << stk.top() << endl; // 4
    stk.push(3); cout << stk.top() << endl; // 3

/* top源码实现
    _NODISCARD reference top() noexcept(noexcept(c.back()))  {
        return c.back(); // 双端队列的最后一个元素
    }
*/
    return 0;
}

stack 出栈操作

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

int main() {
    stack<int> stk;
    stk.push(5); cout << stk.top() << endl; // 5  获取栈顶元素
    stk.push(4); cout << stk.top() << endl; // 4
    stk.push(3); cout << stk.top() << endl; // 3

    stk.pop(); cout << stk.top() << endl; // 4 弹出栈顶元素
    stk.pop(); cout << stk.top() << endl; // 5
    stk.pop(); cout << stk.top() << endl; // 报错 back() called on empty deque

/* pop源码实现
    void pop() noexcept(noexcept(c.pop_back())) {
        c.pop_back();
    }

#if _MSVC_STL_HARDENING_DEQUE || _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(!empty(), "back() called on empty deque");
#endif
*/
    return 0;
}

stack 大小操作

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

int main() {
    stack<int> stk;
    for (int i = 0; i < 5; ++i) {
        cout << "stk.empty() = " << stk.empty() << "," << "stk.size() = " << stk.size() << endl;
        stk.push(i);
    }

    for (int i = 0; i < 5; ++i) {
        stk.pop();
        cout << "stk.empty() = " << stk.empty() << "," << "stk.size() = " << stk.size() << endl;
    }
    return 0;
    /* 输出结果
stk.empty() = 1,stk.size() = 0
stk.empty() = 0,stk.size() = 1
stk.empty() = 0,stk.size() = 2
stk.empty() = 0,stk.size() = 3
stk.empty() = 0,stk.size() = 4
stk.empty() = 0,stk.size() = 4
stk.empty() = 0,stk.size() = 3
stk.empty() = 0,stk.size() = 2
stk.empty() = 0,stk.size() = 1
stk.empty() = 1,stk.size() = 0
*/

/* empty函数源码实现 调用的deque的empty函数
    _NODISCARD_EMPTY_MEMBER_NO_CLEAR bool empty() const noexcept(noexcept(c.empty())) {
        return c.empty();
    }
*/
}

stack 容器替换

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    stack<int, vector<int>> stk;  // 把deque换成vector类型. 也可以自己实现容器，有对应的接口就可以
    stk.push(6);

    return 0;
}

练习

七进制数

https://leetcode.cn/problems/base-7/description/

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

示例 1:
输入: num = 100
输出: "202"

示例 2:
输入: num = -7
输出: "-10"

提示：
-107 <= num <= 107

class Solution {
public:
    string convertToBase7(int num) {
        if(num == 0) {
            return "0";
        }
        string ans = "";
        stack<char> stk;

        // 正数和负责情况统一处理
        if (num < 0) {
            num = -num;
            ans = "-";
        }
        // 得到结果的逆序
        while(num) {
            stk.push('0'+(num %7));
            num /= 7;
        }

        // 弹出栈
        while(!stk.empty()) {
            ans += stk.top();
            stk.pop();
        }
        return ans;
    }
};

回文链表

https://leetcode.cn/problems/aMhZSa/

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：
输入: head = [1,2,3,3,2,1]
输出: true

示例 2：
输入: head = [1,2]
输出: false

提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<ListNode*> stk;
        ListNode* tmp = head;
        while (tmp) {
            stk.push(tmp);
            tmp = tmp->next;
        }
        while(head) {
            if( head->val != stk.top()->val) {
                return false;
            }
            stk.pop();
            head = head->next;
        }
        return true;
    }
};

queue

queue 基础概念

相比于deque，queue只支持在尾部插入，在头部进行删除的容器，并且遵循先进先出。

不支持遍历，底层deque实现

front() 头部元素
back() 尾部元素
pop() 出队，在队首进行
push() 入队，尾部插入

queue 对象创建

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

int main() {
    // 1. 默认构造函数
    queue<int> q1;

    // 2. 拷贝构造函数
    queue<int> q2(q1);

/*
// 1. 默认构造函数
_EXPORT_STD template <class _Ty, class _Container = deque<_Ty>>
class queue {
public:
    using value_type      = typename _Container::value_type;
    using reference       = typename _Container::reference;
    using const_reference = typename _Container::const_reference;
    using size_type       = typename _Container::size_type;
    using container_type  = _Container;

    static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");
    static_assert(is_object_v<_Ty>, "The C++ Standard forbids container adaptors of non-object types "
                                    "because of [container.requirements].");

    queue() = default;  // 编译器生成构造函数的默认实现
protected:
    _Container c{};    // 容器成员变量，调用了c的构造函数，c是deque<_Ty>类型,查看deque的默认构造函数

_EXPORT_STD template <class _Ty, class _Alloc = allocator<_Ty>>
class deque {
public:
    deque() : _Mypair(_Zero_then_variadic_args_t{}) {
        _Get_data()._Alloc_proxy(static_cast<_Alproxy_ty>(_Getal()));
    }

// 2. 拷贝构造函数
_EXPORT_STD template <class _Ty, class _Container = deque<_Ty>>
class queue {
    explicit queue(const _Container& _Cont) : c(_Cont) {}  // 调用c的拷贝构造函数

_EXPORT_STD template <class _Ty, class _Alloc = allocator<_Ty>>
class deque {
public:
    deque(const deque& _Right)
        : _Mypair(_One_then_variadic_args_t{}, _Alty_traits::select_on_container_copy_construction(_Right._Getal())) {
        _Construct(_Right._Unchecked_begin(), _Right._Unchecked_end());
    }
*/
    return 0;
}

queue 赋值

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

int main() {
    queue<int> q1;
    queue<int> q2;
    q2 = q1;

/* 赋值源码分析，来自deque头文件：
    deque& operator=(const deque& _Right) {
        ....
        assign(_Right._Unchecked_begin(), _Right._Unchecked_end());

        return *this;
    }

*/
    return 0;
}

queue 入队操作

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

// q.push(element)
int main() {
    queue<int> q;

    q.push(5);  // 尾部插入 5
    q.push(4);  // 5 4
    q.push(3);  // 5 4 3
    q.push(2);  // 5 4 3 2
    q.push(1);  // 5 4 3 2 1

/* 源码分析 调用deque的push_back函数
    void push(value_type&& _Val) {
        c.push_back(_STD move(_Val));
    }

*/
    return 0;
}

queue 获取队首

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

// q.front() 返回队列的第一个元素

int main() {
    queue<int> q;

    q.push(5);  cout << q.front() << endl; // 尾部插入 5   5
    q.push(4);  cout << q.front() << endl; // 5 4          5
    q.push(3);  cout << q.front() << endl; // 5 4 3        5
    q.push(2);  cout << q.front() << endl; // 5 4 3 2      5
    q.push(1);  cout << q.front() << endl; // 5 4 3 2 1    5

/* 源码分析 调用deque的front函数
    _NODISCARD reference front() noexcept(noexcept(c.front())) {
        return c.front();
    }
*/
    return 0;
}

queue 获取队尾

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

// q.back()：返回队列的最后一个元素（队尾元素）。

int main() {
    queue<int> q;

    for (int i = 0; i < 5; i++) {
        q.push(i);
        cout << "push " << i << ", back = " << q.back() << endl;
    }
/*执行结果
push 0, back = 0
push 1, back = 1
push 2, back = 2
push 3, back = 3
push 4, back = 4
*/

/* 源码分析 调用deque的back函数
    _NODISCARD reference back() noexcept(noexcept(c.back())) {
        return c.back();
    }

    void push(const value_type& _Val) {
        c.push_back(_Val);
    }
*/
    return 0;
}

queue 出队操作

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

// q.pop() 出队操作 删除队头元素

int main() {
    queue<int> q;
    for (int i = 0; i < 5; i++) {
        q.push(i);
    }
    // 0 1 2 3 4
    for (int i = 0; i < 5; i++) {
        cout << "front = "  << q.front() << ", back = " << q.back() << endl;
        q.pop(); // 出队
    }
/* 执行结果  队列是先进先出
front = 0, back = 4
front = 1, back = 4
front = 2, back = 4
front = 3, back = 4
front = 4, back = 4
*/

/* 源码分析 调用deque的pop_front函数
    void pop() noexcept(noexcept(c.pop_front())) {
        c.pop_front();
    }
*/
    return 0;
}

queue 大小操作

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

// empty 判断队列是否为空
// size 返回队列中元素的个数

int main() {
    queue<int> q;
    for (int i = 0; i < 5; i++) {
        q.push(i);
    }
    // 0 1 2 3 4
    while (!q.empty()) {
        cout << "front = " << q.front() << ", back = " << q.back() << ", size = " << q.size() << endl;
        q.pop();
    }
/* 执行结果  队列是先进先出
front = 0, back = 4, size = 5   size=back位置 - front位置 + 1
front = 1, back = 4, size = 4
front = 2, back = 4, size = 3
front = 3, back = 4, size = 2
front = 4, back = 4, size = 1
*/

/* 源码分析 调用deque的size函数
    _NODISCARD size_type size() const noexcept(noexcept(c.size())) {
        return c.size();
    }
    _NODISCARD_EMPTY_MEMBER_NO_CLEAR bool empty() const noexcept(noexcept(c.empty())) {
        return c.empty();
    }
    //deque源码
    _NODISCARD_EMPTY_MEMBER bool empty() const noexcept {
        return _Mysize() == 0;
    }
*/
    return 0;
}

练习

`priority_queue`

`priority_queue` 基础概念

优先队列，每次优化级高的先出。

数组表示二叉树

255 128 200 55 33 15 75

知道下标就可以知道它父节点的下标
parent(id) = (id-1)/2
left(id) = id*2+1  如200的左子树下标 = 2*2 + 1 =5
right(id) = id*2+2

堆：满足完全二叉树上任意节点的值都比它的子节点的值大或者小

大顶堆：满足完全二叉树上任意节点的值都比它的子节点的值大

小顶堆：满足完全二叉树上任意节点的值都比它的子节点的值小

元素插入：

数组尾部插入元素
对于插入元素，比较它(在树形结构中)和它的父节点的大小关系，来决定是否和父节点进行交换。按层序遍历，如是大顶堆，插入元素比父节点大则与父节点元素交换，循环类推。

获取堆顶：获取所有元素中的最大值

返回数组中的第0个元素

元素删除：删除堆顶元素

把数组第0个元素和最后一个元素交换
然后对堆顶的元素不断做“下沉”操作，选择大的进行交换，直到”自己”成为最大的。
删除数组中的最后一个元素
元素删除就是优先队列的出队操作。

容器特点

线性容器：vector, string, list
树形容器：set, multiset, map, multimap
线性模拟树： priority_queue

`priority_queue` 对象创建

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

int main() {
    // 最大优先队列
    priority_queue<int> q1;

    // 最小优先队列
    priority_queue<int, vector<int>, greater<int>> q2;
    return 0;
}

`priority_queue` 入队操作

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

int main() {
    // 最大优先队列
    priority_queue<int> q1;  // 默认是less
    //priority_queue<int, vector<int>, less<int>> q1; 
    q1.push(6);
    q1.push(3);
    q1.push(9);
    q1.push(1);
    q1.push(12);
    q1.push(17);
    q1.push(0);

    // 最小优先队列
    priority_queue<int, vector<int>, greater<int>> q2;
    q2.push(6);
    q2.push(3);
    q2.push(9);
    q2.push(1);
    q2.push(12);
    q2.push(17);
    q2.push(0);

    return 0;
}

`priority_queue` 获取堆顶

优先队列底层实现是一个二叉堆。堆顶元素一定是当前堆中的最值元素。

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

int main() {
    // 最大优先队列
    priority_queue<int> q1;  // 默认是less
    //priority_queue<int, vector<int>, less<int>> q1; 
    q1.push(6); cout << q1.top() << endl;
    q1.push(3); cout << q1.top() << endl;
    q1.push(9); cout << q1.top() << endl;
    q1.push(1); cout << q1.top() << endl;
    q1.push(12); cout << q1.top() << endl;
    q1.push(17); cout << q1.top() << endl;
    q1.push(0); cout << q1.top() << endl;
    cout << "------" << endl;

    // 最小优先队列
    priority_queue<int, vector<int>, greater<int>> q2;
    q2.push(6); cout << q2.top() << endl;
    q2.push(3); cout << q2.top() << endl;
    q2.push(9); cout << q2.top() << endl;
    q2.push(1); cout << q2.top() << endl;
    q2.push(12); cout << q2.top() << endl;
    q2.push(17); cout << q2.top() << endl;
    q2.push(0); cout << q2.top() << endl;

    return 0;
}
/* 执行结果：
6
6
9
9
12
17
17
------
6
3
3
1
1
1
0
*/

/* top源码分析
    _NODISCARD const_reference top() const noexcept(noexcept(c.front())) {
    return c.front();
}
*/

`priority_queue` 出队操作

出队，即删除二叉树顶部元素。

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

int main() {

    priority_queue<int> q;

    q.push(6);
    q.push(3);
    q.push(9);
    q.push(1);
    q.push(12);
    q.push(17);
    q.push(0);

    for (int i = 0; i < 7; ++i) {
        cout << "top() = " << q.top() << endl;
        q.pop();
    }

    return 0;
}

/* pop源码分析：
    void pop() {
        _STD pop_heap(c.begin(), c.end(), _STD _Pass_fn(comp)); {
        c.pop_back();  // 如果是pop_front，则需要移动所有元素，复杂度为O(n)。实际上是把第0个元素和最后一个元素交换，然后删除最后一个元素
    }
*/

`priority_queue` 大小操作

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

int main() {
    priority_queue<int> q;

    q.push(6);
    q.push(3);
    q.push(9);
    q.push(1);
    q.push(12);
    q.push(17);
    q.push(0);

    while (!q.empty()) {
        cout << "top() = " << q.top() << ", size() = " << q.size() << endl;
        q.pop();
    }

    return 0;
}

/* 执行结果：
top() = 17, size() = 7
top() = 12, size() = 6
top() = 9, size() = 5
top() = 6, size() = 4
top() = 3, size() = 3
top() = 1, size() = 2
top() = 0, size() = 1
*/

`priority_queue` 自定义结构

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

struct type {
    int key;
    int value;
    type() { key = value = 0; }
    type(int k, int v) :key(k), value(v) {}

    // 实现一个函数知道比较key 还是 value 大小。小于号重载函数
    bool operator<(const type& t) const {
        //return key < t.key; // 大顶堆
        return key > t.key; // 小顶堆
    }
};

int main() {
    priority_queue<type> q;
    q.push(type(6, 1));
    q.push(type(3, 2));
    q.push(type(9, 0));
    q.push(type(1, 8));
    q.push(type(12, 4));
    q.push(type(17, 2));
    q.push(type(0, 21));
    q.push(type(99, 6));

    while (!q.empty()) {
        cout << "top() = " << q.top().key << ", size() = " << q.size() << endl;
        q.pop();
    }
    return 0;
}

/* 自定义类型需要知道比较哪个大小。 不然走到源码中的less 比较器会报错
struct less {
    using _FIRST_ARGUMENT_TYPE_NAME _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS  = _Ty;
    using _SECOND_ARGUMENT_TYPE_NAME _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS = _Ty;
    using _RESULT_TYPE_NAME _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS          = bool;

    _NODISCARD constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
        noexcept(noexcept(_STD _Fake_copy_init<bool>(_Left < _Right)))  {
    return _Left < _Right;
}
};
*/

/* 执行结果
top() = 0, size() = 8
top() = 1, size() = 7
top() = 3, size() = 6
top() = 6, size() = 5
top() = 9, size() = 4
top() = 12, size() = 3
top() = 17, size() = 2
top() = 99, size() = 1
*/

练习

丑数 II

http://leetcode.cn/problems/ugly-number-ii/

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：
1 <= n <= 1690

class Solution {
    #define ll long long
public:
    int nthUglyNumber(int n) {
        // 定义一个小顶堆
        priority_queue<ll, vector<ll>, greater<ll>> q;
        q.push(1);
        ll pre = -1;  // 有可能有重复的
        while(1) {
            ll val = q.top();
            q.pop();
            // 如果堆顶元素和上一个是一样的就继续弹
            while(val == pre) {
                val = q.top();
                q.pop();
            }
            // 如果是不样的，更新pre
            pre = val;
            --n;
            if(n == 0) {
                return val;
            }
            q.push(val * 2);
            q.push(val * 3);
            q.push(val * 5);
        }
        return -1;
    }
};

矩阵中的和

https://leetcode.cn/problems/sum-in-a-matrix/

给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：

矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数 中。
请你返回最后的 分数 。

示例 1：
输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
输出：15
解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。

示例 2：
输入：nums = [[1]]
输出：1
解释：我们删除 1 并将分数增加 1 ，所以返回 1 。

提示：
1 <= nums.length <= 300
1 <= nums[i].length <= 500
0 <= nums[i][j] <= 103

class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        int n = nums.size();    // 缓存矩阵行数
        int m = nums[0].size(); // 缓存矩阵列数
        priority_queue<int> q[300];
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j <m; ++j) {
                q[i].push(nums[i][j]);
            }
        }
        int sum = 0;      // 返回的分数
        while(m--) {
            int ret = -1; // 定义每一行的最大值
            for(int i = 0; i < n; ++i){
                ret = max(ret, q[i].top());
                q[i].pop();
            }
            sum += ret;
        }
        return sum;
    }
};

有序集合(红黑树)

set

set 基础概念

set特点：

容器内元素不重复
每插入一个元素，容器中的元素会进行有序排列

multiset特点：

容器内元素可以重复
每插入一个元素，容器中的元素会进行有序排列

线性容器：vector, string, list
树形容器：set, multiset 底层利用红黑树实现，红黑树是一种平衡二叉树，它是二叉搜索树，所以中序遍历的结果是一个有序序列。

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

int main() {
    // set, multiset用的同一个头文件
    set<int> s;
    multiset<int> ms;

    return 0;
}

set 对象创建

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    // 1. 默认构造函数
    set<int> s1;
    cout << "s1: ";
    printSet(s1);     // s1:

    // 2. 使用初始化列表构造
    set<int> s2_1 = { 9, 8, 7, 6, 5 };
    cout << "s2_1: ";
    printSet(s2_1);   // s2_1: 5 6 7 8 9  底层是红黑树，自动排序且去重

    set<int> s2_2({ 9, 8, 7,7,6,5 });  // set不支持重复元素，multiset支持
    cout << "s2_2: ";
    printSet(s2_2);   // s2_2: 5 6 7 8 9

    // 3. 迭代器的方式
    set<int> s3(s2_1.begin(), s2_1.end());
    cout << "s3: ";
    printSet(s3);     // s3: 5 6 7 8 9

    // 4. 拷贝构造函数
    set<int> s4(s2_2);
    cout << "s4: ";
    printSet(s4);     // s4: 5 6 7 8 9

    return 0;
}

set 赋值操作

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    set<int> s = { 9, 8, 5, 2, 1, 1};
    cout << "s: ";
    printSet(s);    // s: 1 2 5 8 9

    // 1. = set 对象
    set<int> s1;
    s1 = s;
    cout << "s1: ";
    printSet(s1);   // s1: 1 2 5 8 9

    // 2. = 初始化列表
    set<int> s2;
    s1 = s2 = { 3, 4, 5 };  // 可连续赋值
    cout << "s2: ";
    printSet(s2);   // s2: 3 4 5

/* set源码分析
class set : public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false>> {
    // ordered red-black tree of key values, unique keys
public:

    set& operator=(const set& _Right) {
        _Mybase::operator=(_Right);
        return *this;
    }

    set& operator=(initializer_list<value_type> _Ilist) {  // 初始化列表
        this->clear();         // 清空
        this->insert(_Ilist);  // 插入元素
        return *this;          // 返回自己。可支持连续赋值
    }
*/
    return 0;
}

set 大小操作

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    set<int> s1;
    cout << "s1.empty() = " << s1.empty() << endl;   // 1
    cout << "s1.size() = " << s1.size() << endl;     // 0

    set<int> s2 = { 1, 1,1,1, 6,7,8,9 };
    cout << "s2.empty() = " << s2.empty() << endl;   // 0 
    cout << "s2.size() = " << s2.size() << endl;     // 5

    return 0;
}

set 数据插入

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    set<int> s;

    // 插入操作O(logn)

    s.insert(3);  printSet(s); // 3
    s.insert(2);  printSet(s); // 2 3
    s.insert(5);  printSet(s); // 2 3 5
    s.insert(4);  printSet(s); // 2 3 4 5
    s.insert(1);  printSet(s); // 1 2 3 4 5
    printSet(s);               // 1 2 3 4 5

    vector<int> v = { 0, 5, 6, 9, 8 };
    s.insert(v.begin(), v.end());
    printSet(s);               // 0 1 2 3 4 5 6 8 9

    return 0;
}

set 数据查找

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    set<int> s = { 1, 2, 3, 4, 5 };

    set<int>::iterator it = s.find(3); // 反加一个迭代器 指向元素3, 找到就是返回一个非s.end()的迭代器
    if (it != s.end()) {  // 找到了
        cout << "find: " << (*it) << endl;
    }

    it = s.find(10);
    if (it == s.end()) {  // 没找到
        cout << "can't find 10" << endl;
    }
    return 0;
}

set 数据删除

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    set<int> s = { 1, 2, 3, 4, 5 };

    // 指定元素删除
    s.erase(3);
    printSet(s); // 1 2 4 5

    // 指定迭代器删除
    set<int>::iterator rm = s.find(4);
    if (rm != s.end()) {
        s.erase(rm);
    }
    printSet(s); // 1 2 5

    // 指定范围删除
    s = { 1, 2, 3, 4, 5 };
    set<int>::iterator start = s.find(2);
    set<int>::iterator end = s.find(4);
    s.erase(start, end); // 左闭右开区间
    printSet(s); // 1 4 5
    // 删除后，迭代器就失效了，不能再使用 start 和 end
    //cout << *start << endl; // 未定义行为

    return 0;
}

set 数据统计

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

void printSet(const set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void printMultiSet(const multiset<int>& s) {
    for (multiset<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    set<int> s = { 1, 2, 3, 4, 5 };
    for (int i = 0; i < 8; i += 2) {
        cout << "元素：" << i << "的出现次数为 " << s.count(i) << endl;
    }

    multiset<int> ms = { 1,1,1,1,1,1,4,4,4,4,4,2,2,2,2,6,6,6,6,8,8,8, 5,5,5,5 };
    for (int i = 0; i < 8; i += 2) {
        cout << "元素：" << i << "的出现次数为 " << ms.count(i) << endl;
    }
    printMultiSet(ms); // 1 1 1 1 1 1 2 2 2 2 4 4 4 4 4 5 5 5 5 6 6 6 6 8 8 8

    return 0;
}

set 排序规则

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

class CGaGa {
public:
    CGaGa() {
        _name = "";
        _priority = -1;
    }
    CGaGa(string name, int pri) : _name(name), _priority(pri) {}


    // 使用运算符重载，让其能比较大小
    bool operator<(const CGaGa& other) const {  // 前面const保证other不被修改，后面的const保证成员变量不被修改
        return _priority < other._priority;
    }

    void print() const {
        cout << "(" << _priority << ")" << _name << endl;
    }
private:
    string _name;
    int _priority;
};

int main() {
    set<CGaGa> s;
    s.insert(CGaGa("C++算法零基础", 5));
    s.insert(CGaGa("C++面向对象", 2));
    s.insert(CGaGa("C++基础语法", 1));
    s.insert(CGaGa("C++数据结构", 3));
    s.insert(CGaGa("C++项目实战(贪吃蛇、扫雷、3D赛车)", 6));

/* 报错 类无法比较大小
1>D:\Program Files\Microsoft Visual Studio\2026\VC\Tools\MSVC\14.50.35717\include\type_traits(2387,54): error C2678: 二进制“<”: 没有找到接受“const _Ty”类型的左操作数的运算符(或没有可接受的转换)

type_traits(2387,54)源码
struct less {
    using _FIRST_ARGUMENT_TYPE_NAME _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS  = _Ty;
    using _SECOND_ARGUMENT_TYPE_NAME _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS = _Ty;
    using _RESULT_TYPE_NAME _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS          = bool;

    _NODISCARD constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
        noexcept(noexcept(_STD _Fake_copy_init<bool>(_Left < _Right))) {  // left 小于 right不行
        return _Left < _Right;
    }
};

解决：增加小于符号重载
*/

    for (set<CGaGa>::iterator it = s.begin(); it != s.end(); it++) {
        (*it).print();
    }
/*执行结果
(1)C++基础语法
(2)C++面向对象
(3)C++数据结构
(5)C++算法零基础
(6)C++项目实战(贪吃蛇、扫雷、3D赛车)
*/

    return 0;
}

练习

不间断子数组

https://leetcode.cn/problems/continuous-subarrays/

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

i，i + 1 ，...，j  表示子数组中的下标。对于所有满足 i <= i1, 
i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1：
输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。

示例 2：
输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。

提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        // 利用滑动窗口来求解，求最大和最小值，可以用平衡二叉树来做。数据可能重复用multiset
        multiset<int> mst;
        // 定义左区间
        int i = 0, j = -1;
        int n  = nums.size();
        long long ans = 0;
        while(j ++ < n - 1) { // 右区间在不断向后滑，直到滑动到边界
            mst.insert(nums[j]);
            // 最小值和最大值
            int min = *mst.begin();
            int max = *mst.rbegin();
            while (max - min > 2) {
                multiset<int>::iterator it = mst.find(nums[i]);
                mst.erase(it);
                i++;
                min = *mst.begin();
                max = *mst.rbegin();
            }
            // max - min < 2
            ans += j - i + 1;
        }
        return ans;
    }
};

最高频率的 ID

https://leetcode.cn/problems/most-frequent-ids/

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，
nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

增加 ID 的数目：如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
减少 ID 的数目：如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。
请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ，
如果在某次操作后集合为空，那么 ans[i] 为 0 。


示例 1：
输入：nums = [2,3,2,1], freq = [3,2,-3,1]
输出：[3,3,2,2]
解释：
第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。
第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。
第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。
第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

示例 2：
输入：nums = [5,5,3], freq = [2,-2,1]
输出：[2,0,1]
解释：
第 0 步操作后，有 2 个 ID 为 5 的元素，所以 ans[0] = 2 。
第 1 步操作后，集合中没有任何元素，所以 ans[1] = 0 。
第 2 步操作后，有 1 个 ID 为 3 的元素，所以 ans[2] = 1 。

提示：
1 <= nums.length == freq.length <= 105
1 <= nums[i] <= 105
-105 <= freq[i] <= 105
freq[i] != 0
输入保证任何操作后，集合中的元素出现次数不会为负数。

class Solution {
public:
    // 整体时间复杂度：O(logn)
    vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
        multiset<long long> ms;           // 定义有序集合
        multiset<long long>::iterator it; // 定义迭代器
        long long cnt[100001] = {0};       // 定义hash表  cnt[i] 代表i这个元素出现的次数
        vector<long long> ans(nums.size(), 0); // 结果数组, nums.size个元素,并初始化元素值为0
        for(int i = 0; i < nums.size(); ++i) { // 时间复杂度O(n)
            int x  = nums[i];
            long long &c = cnt[x] ;   // 查找x元素之前出现了多少次 这里&引用为了对c进行修改.出现次数一定在红黑树ms中
            it = ms.find(c);          // 找到c  时间复杂度O(logn)
            if(it != ms.end()) {      // 找到了就删除
                ms.erase(it);         // 时间复杂度O(logn)
            }
            c += freq[i];
            ms.insert(c);              // 插入到ms红黑树中  时间复杂度O(logn)
            ans[i] = *ms.rbegin();     // 最大值存储到ans[i]中
        }
        return ans;
    }
};

map

map 基础概念

重要性和使用频率仅次于vector。

先了解pair， pair是类模板

template <class _Ty1, class _Ty2>
struct pair {
  _Ty1 first;
  _Ty2 second;
};

通用传入类型可以实例化出很多模板类，甚至是自定义类型，还支持嵌套。如

pair<int, int>
pair<double, int>
pair<double, string>
pair<char, short>
pair<long long, long>
pair<long long, pair<double, int>>

通过模板类实例化的对象和普通结构体用法是一样的，可以获取first进行赋值，也可以获取second进行赋值。

pair<int, int> p;

p.first = 13;
p.second = 14;

当然也可以这么写构造函数，也可以用make_pair进行构造

pair<int, int> p(13, 14);


pair<int, int> p = make_pair(13, 14);

了解pair这个结构体后，我们来介绍一下map

map特点

容器中所有元素都是pair，first不重复
pair中第一个数据是key(键)，第二个数据value(值)
所有元素都会根据元素的key值排序

multimap特点

容器中所有元素都是pair，first 可以重复
pair中第一个数据是key(键)，第二个数据value(值)
所有元素都会根据元素的key值排序

容器特点

线性容器：vector, string, list
树形容器：set, multiset, map, multimap

物理结构

所有的pair被组织到红黑树上，排序规则是对pair的first进行排序。

逻辑结构

线性的，提供begin, end函数

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

int main() {
    // pair用法
    pair<int, int> p1;
    p1.first = 13;
    p1.second = 14;
    cout << p1.first << " " << p1.second << "\n";  // 13 14

    pair<int, string> p2(2, "333");
    cout << p2.first << " " << p2.second << endl;  // 2 333

    pair<char, int> p3 = make_pair(52, 0);
    cout << p3.first << " " << p3.second << endl;  // 4 0 // '0'->48, '1'->49, '4'->52

    // map定义
    map<int, int> m;
    set<int> s;
/* 
// map标准库源码片段 继承自_Tree 红黑树
class map : public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false>> {
    // ordered red-black tree of {key, mapped} values, unique keys
public:

class _Tree { // ordered red-black tree for map/multimap/set/multiset 红黑树的类
public:
    using key_type       = typename _Traits::key_type;
    using value_type     = typename _Traits::value_type;
    using allocator_type = typename _Traits::allocator_type;

// set标准库源码片段 继承自_Tree 红黑树
class set : public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false>> {
    // ordered red-black tree of key values, unique keys
public:
*/
    return 0;
}

map 对象创建

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    // 常用的4种方法
    // 1. 默认构造函数
    map<int, int> m1;
    cout << "m1: " << endl;
    printMap(m1);

    // 2. 初始化列表
    map<int, int> m2_1 = {
        pair<int, int>(1, 10),
        pair<int, int>(4, 24),
        pair<int, int>(3, 43),
        pair<int, int>(2, 15)
    };  // 调用的隐式构造函数
    cout << "m2_1: " << endl;
    printMap(m2_1); // 按key排序

    map<int, int> m2_2({
        pair<int, int>(1, 18),
        pair<int, int>(4, 23),
        pair<int, int>(3, 41),
        pair<int, int>(2, 11)
        }); // 调用的显式构造函数
    cout << "m2_2: " << endl;
    printMap(m2_2); // 按key排序

    // 3. 迭代器
    map<int, int> m3(m2_1.begin(), m2_1.end());
    cout << "m3: " << endl;
    printMap(m3);

    // 4. 拷贝构造函数
    map<int, int> m4(m2_2);
    cout << "m4: " << endl;
    printMap(m4);

    return 0;
}

/* 执行结果
m1:
------------------
m2_1:
key = 1  value = 10
key = 2  value = 15
key = 3  value = 43
key = 4  value = 24
------------------
m2_2:
key = 1  value = 18
key = 2  value = 11
key = 3  value = 41
key = 4  value = 23
------------------
m3:
key = 1  value = 10
key = 2  value = 15
key = 3  value = 43
key = 4  value = 24
------------------
m4:
key = 1  value = 18
key = 2  value = 11
key = 3  value = 41
key = 4  value = 23
------------------
*/

map 赋值操作

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    map<int, int> m ={
        pair<int, int>(1, 18),
        pair<int, int>(4, 23),
        pair<int, int>(3, 41),
        pair<int, int>(2, 11)
        };
    cout << "m: " << endl;
    printMap(m); // 按key排序

    // 1. = 对象
    map<int, int> m1;
    m1 = m;
    cout << "m1: " << endl;
    printMap(m1);

    // 2. = 初始化列表
    map<int, int> m2;
    m2 = {
        pair<int, int>(1, 8),
        pair<int, int>(4, 36),
        pair<int, int>(3, 18),
        pair<int, int>(2, 22)
    };
    cout << "m2: " << endl;
    printMap(m2);

    return 0;
}

/* 执行结果
m:
key = 1  value = 18
key = 2  value = 11
key = 3  value = 41
key = 4  value = 23
------------------
m1:
key = 1  value = 18
key = 2  value = 11
key = 3  value = 41
key = 4  value = 23
------------------
m2:
key = 1  value = 8
key = 2  value = 22
key = 3  value = 18
key = 4  value = 36
------------------
*/

map 大小操作

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}
/*
empty 判空
size 有多少键值对
*/
int main() {
    map<int, int> m1;
    cout << "m1.empty() = " << m1.empty() << endl; // 1
    cout << "m1.size() = " << m1.size() << endl;   // 0

    map<int, int> m2 = { pair<int, int>(1, 10), pair<int, int>(3, 5), pair<int, int>(4, 8) };
    cout << "m2.empty() = " << m2.empty() << endl; // 0
    cout << "m2.size() = " << m2.size() << endl;   // 3

    return 0;
}

map 数据插入

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    // 常用4种插入
    map<int, int> m;

    // 1
    m.insert(pair<int, int>(1, 10));
    printMap(m);

    // 2
    m.insert(make_pair(3, 20));
    printMap(m);

    // 3
    m.insert(map<int, int>::value_type(2, 78));
    printMap(m);

    // 4
    m[4] = 6;
    printMap(m);

    // 5
    pair< map<int, int>::iterator, bool > ret = m.insert(make_pair(3, 21)); // key存在，插入失败
    cout << "insert(3, 21) = " << ret.second << endl; // 0
    printMap(m);

    // 6 
    m[3] = 22;  // 改变了
    printMap(m);

    // 7 用中括号访问但键不存在时，会插入，有一定的危险
    m[0];  // 键是0，value是0
    printMap(m);

    return 0;
}

/* 执行结果
key = 1  value = 10
------------------
key = 1  value = 10
key = 3  value = 20
------------------
key = 1  value = 10
key = 2  value = 78
key = 3  value = 20
------------------
key = 1  value = 10
key = 2  value = 78
key = 3  value = 20
key = 4  value = 6
------------------
insert(3, 21) = 0
key = 1  value = 10
key = 2  value = 78
key = 3  value = 20
key = 4  value = 6
------------------
key = 1  value = 10
key = 2  value = 78
key = 3  value = 22
key = 4  value = 6
------------------
key = 0  value = 0
key = 1  value = 10
key = 2  value = 78
key = 3  value = 22
key = 4  value = 6
------------------
*/

map 数据查找

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    map<int, int> m = {
        pair<int, int>(1, 4),
        pair<int, int>(3, 20),
        pair<int, int>(2, 80),
        pair<int, int>(4, 17),
    };

    for (int i = 4; i <= 5; ++i) {
       map<int, int>::iterator it = m.find(i);  // 找键
       if (it != m.end()) {
           cout << "找到键值对：(" << it->first << "," << it->second << ") "<< endl;
       }
       else {
           cout << "未找到键值：" << i << endl;
       }
    }

    return 0;
}

/* 执行结果

*/

map 数据删除

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    map<int, int> m = {
        pair<int, int>(1, 4),
        pair<int, int>(3, 20),
        pair<int, int>(2, 80),
        pair<int, int>(4, 17),
    };
    printMap(m);

    m.erase(1);                  // 删掉1键值
    printMap(m);

    m.erase(m.begin());          // 删除2键值
    printMap(m);

    m.erase(m.begin(), m.end()); // 删除区间
    printMap(m);

    m = {
        pair<int, int>(1, 4),
        pair<int, int>(3, 20),
        pair<int, int>(2, 80),
        pair<int, int>(4, 17),
    };
    m.clear();                    // 删除所有
    printMap(m);

    return 0;
}

/* 执行结果
key = 1  value = 4
key = 2  value = 80
key = 3  value = 20
key = 4  value = 17
------------------
key = 2  value = 80
key = 3  value = 20
key = 4  value = 17
------------------
key = 3  value = 20
key = 4  value = 17
------------------
------------------
------------------
*/

map 数据修改

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    map<int, int> m;
    m.insert(make_pair(1, 20));
    m.insert(make_pair(2, 330));
    m.insert(make_pair(3, 44440));

    m[3] = 888;
    printMap(m);

    m[2]++;
    printMap(m);

    // 支持复合运算
    m[1] -= 21;
    printMap(m);

    return 0;
}

/* 执行结果
key = 1  value = 20
key = 2  value = 330
key = 3  value = 888
------------------
key = 1  value = 20
key = 2  value = 331
key = 3  value = 888
------------------
key = 1  value = -1
key = 2  value = 331
key = 3  value = 888
------------------
*/

map 数据统计

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

void printMap(const map<int, int>& m) {
    for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        // it->first, it->second
        cout << "key = " << it->first << " " << " value = " << it->second << endl;
    }
    cout << "------------------" << endl;
}

int main() {
    map<int, int> m = {
        pair<int, int>(1, 4),
        pair<int, int>(3, 30),
        pair<int, int>(2, 80),
        pair<int, int>(4, 90)
    };

    // 统计某键出现次数,对于map来说键只会出现0次或1次
    for (int i = -1; i < 3; ++i) {
        cout << i << "的出现次数是" << m.count(i) << endl;
    }

    // multimap
    multimap<int, int> mm = {
        pair<int, int>(1, 4),pair<int, int>(1, 4),pair<int, int>(1, 4),pair<int, int>(1, 4),
        pair<int, int>(3, 30),pair<int, int>(3, 30),pair<int, int>(3, 30),pair<int, int>(3, 30),
         pair<int, int>(2, 80), pair<int, int>(2, 80),
        pair<int, int>(4, 90),pair<int, int>(4, 90)
    };
    for (int i = -1; i < 3; ++i) {
        cout << i << "的出现次数是" << mm.count(i) << endl;
    }
    return 0;
}

/* 执行结果
-1的出现次数是0
0的出现次数是0
1的出现次数是1
2的出现次数是1
-1的出现次数是0
0的出现次数是0
1的出现次数是4
2的出现次数是2
*/

练习

两个数组的交集 II

https://leetcode.cn/problems/intersection-of-two-arrays-ii/

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。
可以不考虑输出结果的顺序。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> cnt;
        vector<int> ans;
        for(int i = 0; i < nums1.size(); ++i) {
            int x = nums1[i];
            cnt[x]++;
        }
        for(int i = 0; i < nums2.size(); ++i) {
            int x = nums2[i];
            if(cnt[x] > 0) {
                cnt[x]--;
                ans.push_back(x);
            }
        }
        return ans;
    }
};

合并相似的物品

https://leetcode.cn/problems/merge-similar-items/

给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质：

items[i] = [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ，weighti 表示第 i 件物品的 重量 。
items 中每件物品的价值都是 唯一的 。
请你返回一个二维数组 ret，其中 ret[i] = [valuei, weighti]， weighti 是所有价值为 valuei 物品的 重量之和 。

注意：ret 应该按价值 升序 排序后返回。

示例 1：
输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出：[[1,6],[3,9],[4,5]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 5 ，总重量为 5 。
所以，我们返回 [[1,6],[3,9],[4,5]] 。

示例 2：
输入：items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
输出：[[1,4],[2,4],[3,4]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
所以，我们返回 [[1,4],[2,4],[3,4]] 。

示例 3：
输入：items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
输出：[[1,7],[2,4],[7,1]]
解释：
value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。
所以，我们返回 [[1,7],[2,4],[7,1]] 。


提示：
1 <= items1.length, items2.length <= 1000
items1[i].length == items2[i].length == 2
1 <= valuei, weighti <= 1000
items1 中每个 valuei 都是 唯一的 。
items2 中每个 valuei 都是 唯一的 。

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        map<int, int> mp; // 键为价值
        for(int i = 0; i < items1.size(); ++i) {
            int val = items1[i][0];
            int wei = items1[i][1];
            mp[val] += wei;
        }
        for(int i = 0; i < items2.size(); ++i) {
            int val = items2[i][0];
            int wei = items2[i][1];
            mp[val] += wei;
        }

        vector<vector<int>> ans;
        for(map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
            int val = it->first;
            int wei = it->second;
            ans.push_back({val, wei});
        }
        return ans;
    }
};

无序集合(哈希表)

`unordered_set`

`unordered_set` 基础概念

和有序容器相比它是无序容器，它的底层实现是哈希表。

哈希表

除了C++的STL，Python、Lua、Redis底层都有哈希表的实现，大体的实现逻辑都是差不多的，但是在解决哈希冲突的时候会有略微的差别。

时间复杂度

数组：O(n)
二叉树：O(logn)
哈希表：O(1)

哈希表的本质原理

哈希表一股是任意类型，所以需要先通过哈希函数转换成整数，我们叫它哈希值，再通过取模（一般实现的时候采用的是位与运算），映射到某个桶中。这样就可以把任意类型的数据存储到数组中，且能快速查找到。

哈希键                  哈希值                      桶ID
1314  --哈希函数--> 4958349058439891 --取模/位与-->  3

桶

下标索引又叫桶ID，桶ID是用来索引到某个具体的桶的。因为用的取模，所以得到的桶ID都是连续的自然数，这样的桶可以用数组来实现。

1314-->3  981-->4 871-->6
0 1 2 3 4 5 6 7

哈希冲突

哈希冲突，是指两个元素的键不同，但是它们计算得到的桶ID相同的情况

1314  --> 49583490584395891 --> 3

520   --> 19183410582397891 --> 3

哈希冲突解决方案

常见的哈希冲突解决方案，是一个桶（bucket）中盛放多个元素，这样就可以通过哈希算法快速找到桶，再通过遍历桶中所有元素，实现快速查找。

STL的哈希表

STL中，数据并不是存储在bucket这个桶中的，而是利用了(bucket << 1) 和(bucket <<1)+1两个位置，并且把所有桶中元素串联成一个链表，它里面的元素是从 (bucket<<1)的位置作为链表起点，(bucket<<1)+1作为链表终点，来存储哈希表中的所有桶ID为bucket的结点。

     bucket<<1          (bucket<<1)+1
...  1314                520 ...
            --> 886 <--

STL哈希表结点串联

所有的哈希表结点会被链接到一个全局的双向链表中，双向链表有虚拟头结点 _Head 。
当bucket中没有任何元素的时候，那么在bucket<<1和(bucket<<1)+1 位置上的值正好是 _Head 。

_Head <--> 1314 <-->  886 <--> 520 <--> _Head

     bucket<<1          (bucket<<1)+1
...  _Head               _Head ...

模拟哈希表的增删查

# bucket 桶中没有任何元素
     bucket<<1          (bucket<<1)+1
...  _Head               _Head ...

# 插入一个1314就会变成这样
     bucket<<1          (bucket<<1)+1
...  1314                1314 ...
            --> _Head <--

# 插入一个520
## 先遍历所在链表，且是从后往前遍历。如果没有找到520则会插到头部
     bucket<<1          (bucket<<1)+1
...  520                1314 ...
            --> _Head <--

# 插入一个886
## 在520前面插入一个886
     bucket<<1          (bucket<<1)+1
...  886               1314 ...
            520
            --> _Head <--

元素查找：从双向链表的尾部开始，不断向前遍历。如果键相等就返回，如果一直找不到就会返回全局双向链表的头结点。
元素删除：先找到桶ID，然后逆序遍历链表，找到对应结点执行删除操作。

容器特点：

线性容器:vector、string、list
树形容器:set、multiset、map、multimap
线性模拟树:priority_queue
散列容器:unordered_set、unordered_map

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

int main() {
    unordered_set<int> s;
    return 0;
}

`unordered_set` 对象创建

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
int main() {
    // 1. 默认构造函数
    unordered_set<int> s1;
    cout << "s1: ";
    printUSet(s1);

    // 2. 初始化列表
    unordered_set<int> s2_1 = { 9, 8, 7, 5, 6 , 1, 2, 3, 4 };
    cout << "s2_1: ";
    printUSet(s2_1);  // s2_1: 1 9 8 7 5 6 2 3 4

    unordered_set<int> s2_2({ 9, 8, 7, 5, 6 , 1, 2, 3, 4 , 6,6,6,6});
    cout << "s2_2: ";
    printUSet(s2_2);  // s2_2: 1 9 8 7 5 6 2 3 4

    // 3. 迭代器
    unordered_set<int> s3(s2_1.begin(), s2_1.end());
    cout << "s3: ";
    printUSet(s3);  // s3: 9 1 8 7 5 6 2 3 4

    // 4. 拷贝构造函数
    unordered_set<int> s4(s2_2);
    cout << "s4: ";
    printUSet(s4);  // s4: 1 9 8 7 5 6 2 3 4

    return 0;
}

`unordered_set` 赋值操作

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
int main() {
    unordered_set<int> s = { 9, 8, 5, 2, 1, 1 };  // 构造逻辑
    cout << "s: ";
    printUSet(s);  // s: 1 9 8 5 2

    // 1. = set对象
    unordered_set<int> s1;
    s1 = s;
    cout << "s1: ";
    printUSet(s1);  // s1: 9 1 8 5 2

    // 2. 初始化列表
    unordered_set<int> s2;
    s2 = { 3, 4, 7, 6, 7, 8, 9,2,1 };  // 赋值逻辑
    cout << "s2: ";
    printUSet(s2);  // s2: 3 4 7 6 8 1 9 2

    return 0;
}

/*
    unordered_set& operator=(const unordered_set& _Right) {
        _Mybase::operator=(_Right);  // 调用基类的赋值运算符
        return *this;
    }
    unordered_set& operator=(initializer_list<value_type> _Ilist) {  // 赋值列表
        this->clear();
        this->insert(_Ilist);
        return *this;
    }

    using _Mybase        = _Hash<_Uset_traits<_Kty, _Mytraits, _Alloc, false>>;

class _Hash { // hash table -- list with vector of iterators for quick access
    _Hash& operator=(_Hash&& _Right) { // assign by moving _Right
        if (this == _STD addressof(_Right)) {
            return *this;
        }
        .... 从内存中移动数据 ....

*/

`unordered_set` 大小操作

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
int main() {
    unordered_set<int> s1;
    cout << "s1.empty() = " << s1.empty() << endl;     // 1
    cout << "s1.size() = " << s1.size() << endl;       // 0

    unordered_set<int> s2 = { 1,1,1, 9,9,9,9, 7, 7, 7 };
    cout << "s2.empty() = " << s2.empty() << endl;     // 0
    cout << "s2.size() = " << s2.size() << endl;       // 3

    // unordered_multiset 支持重复元素
    unordered_multiset<int> ms1 = { 1,1,1, 9,9,9,9, 7, 7, 7 };
    cout << "ms1.empty() = " << ms1.empty() << endl;     // 0
    cout << "ms1.size() = " << ms1.size() << endl;       // 10

    return 0;
}

`unordered_set` 数据插入

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
int main() {
    unordered_set<int> s;

    s.insert(3); printUSet(s); // 3
    s.insert(2); printUSet(s); // 3 2
    s.insert(5); printUSet(s); // 3 2 5
    s.insert(4); printUSet(s); // 3 2 5 4
    s.insert(1); printUSet(s); // 3 2 5 4 1
    s.insert(9); printUSet(s); // 3 2 5 4 9 1
    s.insert(8); printUSet(s); // 3 2 5 4 9 1 8
    s.insert(6); printUSet(s); // 3 2 5 4 9 1 8 6

    vector<int> v = { 1, 9, 9, 7 };
    s.insert(v.begin(), v.end()); 
    printUSet(s);              // 3 2 5 4 9 1 8 6 7

    return 0;
}
/* 插入源码片段
    conditional_t<_Multi, iterator, pair<iterator, bool>> insert(value_type&& _Val) {
        return emplace(_STD move(_Val));
    }
    conditional_t<_Multi, iterator, pair<iterator, bool>> emplace(_Valtys&&... _Vals) {
        // try to insert value_type(_Vals...)
        using _In_place_key_extractor = typename _Traits::template _In_place_key_extractor<_Valtys...>;
        if constexpr (_Multi) {
            _Check_max_size();
            _List_node_emplace_op2<_Alnode> _Newnode(_List._Getal(), _STD forward<_Valtys>(_Vals)...);
            const auto& _Keyval = _Traits::_Kfn(_Newnode._Ptr->_Myval);
            const auto _Hashval = _Traitsobj(_Keyval);
            if (_Check_rehash_required_1()) {
                _Rehash_for_1();
            }

            const auto _Target = _Find_last(_Keyval, _Hashval);
            return _List._Make_iter(_Insert_new_node_before(_Hashval, _Target._Insert_before, _Newnode._Release()));
        } else if constexpr (_In_place_key_extractor::_Extractable) {
            const auto& _Keyval = _In_place_key_extractor::_Extract(_Vals...);
            const auto _Hashval = _Traitsobj(_Keyval);
            auto _Target        = _Find_last(_Keyval, _Hashval);
            if (_Target._Duplicate) {
                return {_List._Make_iter(_Target._Duplicate), false};
            }

            _Check_max_size();
            // invalidates _Keyval:
            _List_node_emplace_op2<_Alnode> _Newnode(_List._Getal(), _STD forward<_Valtys>(_Vals)...);
            if (_Check_rehash_required_1()) {
                _Rehash_for_1();
                _Target = _Find_last(_Traits::_Kfn(_Newnode._Ptr->_Myval), _Hashval);
            }

            return {
                _List._Make_iter(_Insert_new_node_before(_Hashval, _Target._Insert_before, _Newnode._Release())), true};
        } else {
            _List_node_emplace_op2<_Alnode> _Newnode(_List._Getal(), _STD forward<_Valtys>(_Vals)...);
            const auto& _Keyval = _Traits::_Kfn(_Newnode._Ptr->_Myval); // 拿到键值
            const auto _Hashval = _Traitsobj(_Keyval);                  // 算出哈希值
            auto _Target        = _Find_last(_Keyval, _Hashval);        // 在桶中找到最后一个相同键值的位置
            if (_Target._Duplicate) {  // 如果找到了重复的键值,直接返回
                return {_List._Make_iter(_Target._Duplicate), false};
            }

            _Check_max_size();
            if (_Check_rehash_required_1()) {
                _Rehash_for_1();
                _Target = _Find_last(_Traits::_Kfn(_Newnode._Ptr->_Myval), _Hashval);
            }

            return { // 没有重复键值,插入新节点
                _List._Make_iter(_Insert_new_node_before(_Hashval, _Target._Insert_before, _Newnode._Release())), true};
        }
    }

    _Nodeptr _Insert_new_node_before(
       // 双向链表插入操作
        const size_t _Hashval, const _Nodeptr _Insert_before, const _Nodeptr _Newnode) noexcept {
        const _Nodeptr _Insert_after = _Insert_before->_Prev;
        ++_List._Mypair._Myval2._Mysize;
        _Construct_in_place(_Newnode->_Next, _Insert_before);
        _Construct_in_place(_Newnode->_Prev, _Insert_after);
        _Insert_after->_Next  = _Newnode;
        _Insert_before->_Prev = _Newnode;

        // 处理插入时，两个桶的边界
        // ==========================================
        const auto _Head                = _List._Mypair._Myval2._Myhead;
        const auto _Bucket_array        = _Vec._Mypair._Myval2._Myfirst;
        const size_type _Bucket         = _Hashval & _Mask;
        _Unchecked_iterator& _Bucket_lo = _Bucket_array[_Bucket << 1];
        _Unchecked_iterator& _Bucket_hi = _Bucket_array[(_Bucket << 1) + 1];
        if (_Bucket_lo._Ptr == _Head) {
            // bucket is empty, set both
            _Bucket_lo._Ptr = _Newnode;
            _Bucket_hi._Ptr = _Newnode;
        } else if (_Bucket_lo._Ptr == _Insert_before) {
            // new node is the lowest element in the bucket
            _Bucket_lo._Ptr = _Newnode;
        } else if (_Bucket_hi._Ptr == _Insert_after) {
            // new node is the highest element in the bucket
            _Bucket_hi._Ptr = _Newnode;
        }
        // ==========================================

#ifdef _ENABLE_STL_INTERNAL_CHECK
        _Stl_internal_check_container_invariants();
#endif // _ENABLE_STL_INTERNAL_CHECK
        return _Newnode;
    }
*/

`unordered_set` 数据查找

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
int main() {
    unordered_set<int> s = { 1, 2, 3,4,5 };
    unordered_set<int>::iterator it = s.find(3);

    if (it != s.end()) { // find成功
        cout << "find :" << *it << endl;
    }
    it = s.find(10);
    if (it == s.end()) { // find失败
        cout << "can't find: 10" << endl;
    }


    return 0;
}
/* 源码片段
    _NODISCARD iterator find(const key_type& _Keyval) {
        return _List._Make_iter(_Find(_Keyval, _Traitsobj(_Keyval)));
    }

    _Nodeptr _Find(const _Keyty& _Keyval, const size_t _Hashval) const {
        if constexpr (_Traits::_Multi) {
            return _Find_first(_Keyval, _Hashval);
        } else { // 如果不是multiset，则使用_Find_last
            // use _Find_last for unique containers to avoid increase in code size of instantiating _Find_first
            auto _Target = _Find_last(_Keyval, _Hashval)._Duplicate;
            if (_Target) {
                return _Target;
            }

            return _List._Mypair._Myval2._Myhead; // 没找到，返回双向链表的头结点
        }
    }

    _NODISCARD _Hash_find_last_result<_Nodeptr> _Find_last(const _Keyty& _Keyval, const size_t _Hashval) const {
        // find the insertion point for _Keyval and whether an element identical to _Keyval is already in the container
        const size_type _Bucket = _Hashval & _Mask;  // 哈希取模后，得到桶ID
        _Nodeptr _Where         = _Vec._Mypair._Myval2._Myfirst[(_Bucket << 1) + 1]._Ptr; // 找到桶的尾部
        const _Nodeptr _End     = _List._Mypair._Myval2._Myhead;
        if (_Where == _End) {  // 如果桶的尾部和全局双向链表的头结点相同，说明桶是空的，没找到
            return {_End, _Nodeptr{}};  // 返回end
        }

        const _Nodeptr _Bucket_lo = _Vec._Mypair._Myval2._Myfirst[_Bucket << 1]._Ptr;
        for (;;) { // 从桶的尾部开始向前搜索
            // Search backwards to maintain sorted [_Bucket_lo, _Bucket_hi] when !_Standard
            if (!_Traitsobj(_Keyval, _Traits::_Kfn(_Where->_Myval))) {
                if constexpr (!_Traits::_Standard) {
                    if (_Traitsobj(_Traits::_Kfn(_Where->_Myval), _Keyval)) {
                        return {_Where->_Next, _Nodeptr{}};
                    }
                }

                return {_Where->_Next, _Where};
            }

            if (_Where == _Bucket_lo) {
                return {_Where, _Nodeptr{}};
            }

            _Where = _Where->_Prev;
        }
    }
*/

`unordered_set` 数据删除

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
int main() {
    unordered_set<int> s = { 1, 2, 3,4,5 };
    s.erase(3);
    printUSet(s);  // 1 2 4 5

    unordered_set<int>::iterator it = s.find(4);
    if (it != s.end()) {
        s.erase(it);
    }
    printUSet(s);  // 1 2 5

    s = { 16, 12,3,4,5,6,7,8,9,10,11,12,13,14,15 };
    unordered_set<int>::iterator itl = s.find(12);
    unordered_set<int>::iterator itr = s.find(14);
    s.erase(itl, itr);  // 如果是个范围删除，删除的是前闭后开区间，不建议使用，因为unordered_set是无序的，范围删除意义不大
    printUSet(s); // 8 16 4 14 15

    s.clear(); // 清空

    return 0;
}
/* 源码片段
    size_type erase(const key_type& _Keyval) noexcept(noexcept(_Erase(_Keyval))) {
    return _Erase(_Keyval);
}

    size_type _Erase(const _Keytype& _Keyval) noexcept(_Noexcept_heterogeneous_erasure<_Keytype>()){
    const size_t _Hashval = _Traitsobj(_Keyval);
    if constexpr (_Multi) {
        const auto _Where = _Equal_range(_Keyval, _Hashval);
        _Unchecked_erase(_Where._First._Ptr, _Where._Last._Ptr);
        return _Where._Distance;
    }
    else {
        const auto _Target = _Find_last(_Keyval, _Hashval)._Duplicate;
        if (_Target) { // 有这个结点执行删除
            _Erase_bucket(_Target, _Hashval & _Mask); // 处理bucket的边界
            _List._Unchecked_erase(_Target);          // 删除操作
            return 1;
        }

        return 0;
    }
}

    void _Erase_bucket(_Nodeptr _Plist, size_type _Bucket) noexcept {
        // remove the node _Plist from its bucket
        _Nodeptr& _Bucket_lo = _Vec._Mypair._Myval2._Myfirst[_Bucket << 1]._Ptr;
        _Nodeptr& _Bucket_hi = _Vec._Mypair._Myval2._Myfirst[(_Bucket << 1) + 1]._Ptr;
        if (_Bucket_hi == _Plist) {
            if (_Bucket_lo == _Plist) { // make bucket empty 如果头尾节点都删完了，头尾变成全局双向链表的虚拟头节点
                const auto _End = _List._Mypair._Myval2._Myhead;

                _Bucket_lo = _End;
                _Bucket_hi = _End;
            } else {
                _Bucket_hi = _Plist->_Prev; // move end back one element
            }
        } else if (_Bucket_lo == _Plist) {
            _Bucket_lo = _Plist->_Next; // move beginning up one element
        }
    }

class list { // bidirectional linked list
    _Nodeptr _Unchecked_erase(const _Nodeptr _Pnode) noexcept { // erase element at _Pnode
        const auto _Result = _Pnode->_Next;
        _Mypair._Myval2._Orphan_ptr2(_Pnode);
        --_Mypair._Myval2._Mysize;
        _Pnode->_Prev->_Next = _Result; // _Pnode是要删除的节点。把它的前驱节点的_next指向它的后继节点
        _Result->_Prev       = _Pnode->_Prev; // 把它的后继节点的_prev指向它的前驱节点
        _Node::_Freenode(_Getal(), _Pnode);
        return _Result;
    }
*/

`unordered_set` 数据统计

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

void printUSet(const unordered_set<int>& s) {
    for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void printUMSet(const unordered_multiset<int>& s) {
    for (unordered_multiset<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    unordered_set<int> s = { 1, 2, 3,4,5 };
    for (int i = 0; i < 8; i += 2) {
        cout << "元素：" << i << "的出现次数是 " << s.count(i) << endl;
    }
    printUSet(s); // 1 2 3 4 5

    // 为什么引入count，而不是has(i)?  尽量保持一致

    unordered_multiset<int> ms = { 1,1,1,1,2,2,2,2,2, 3,3,3,3,3,4,4,4,7,7,7,7 };
    for (int i = 0; i < 8; i += 2) {
        cout << "元素：" << i << "的出现次数是 " << ms.count(i) << endl;
    }
    printUMSet(ms); // 1 2 3 4 5
    return 0;
}
/* 执行结果
元素：0的出现次数是 0
元素：2的出现次数是 1
元素：4的出现次数是 1
元素：6的出现次数是 0
1 2 3 4 5
元素：0的出现次数是 0
元素：2的出现次数是 5
元素：4的出现次数是 3
元素：6的出现次数是 0
1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 7 7 7 7
*/

/* 源码片段
    _NODISCARD size_type count(const key_type& _Keyval) const {
        const size_t _Hashval = _Traitsobj(_Keyval);
        if constexpr (_Multi) {
            return _Equal_range(_Keyval, _Hashval)._Distance;
        } else {
            return static_cast<bool>(_Find_last(_Keyval, _Hashval)._Duplicate);
        }
    }
*/

练习

相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：


题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。
如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> us;
        while(headA) {
            us.insert(headA);
            headA = headA->next;
        }
        while(headB) {
            if(us.find(headB) != us.end()) {
                return headB;
            }
            headB = headB->next;
        }
        return NULL;
    }
};

重复的DNA序列

https://leetcode.cn/problems/repeated-dna-sequences/

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。
你可以按 任意顺序 返回答案。

示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：
0 <= s.length <= 105
s[i]=='A'、'C'、'G' or 'T'

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_multiset<string> ums;
        vector<string> ans;
        for(int i = 0; i < s.size(); ++i) {
            string sub = s.substr(i, 10); // 从指定位置出发找到10个字符
            ums.insert(sub);
            if(ums.count(sub) == 2 ) {
                ans.push_back(sub);
            }
        }
        return ans;
    }
};

`unordered_map`

`unordered_map` 基础概念

功能和map类似。相比map的有序映射，它的底层数据存储时是无序的，并且底层数据和unordered_set一样是哈希表。

因为是无序，它又是一种键值对，所以叫它无序映射。

set和map区别

set的元素是一个数据，map的元素则是两个数据(一个pair)

unordered_set和unordered_map区别和set和map区别一样。

unordered_set<type>

unordered_map<type1, type2>

容器特点:

线性容器:vector、string、list
树形容器:set、multiset、map、multimap
线性模拟树:priority_queue
散列容器:unordered_set、unordered_map

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

int main() {
    unordered_map<int, int> m;

    return 0;
}
/* 源码片段：
// 与unordered_set一样继承自_Hash
// 通过_Umap_traits来区分是map还是set
class unordered_map : public _Hash<_Umap_traits<_Kty, _Ty, _Uhash_compare<_Kty, _Hasher, _Keyeq>, _Alloc, false>> {


class _Umap_traits : public _Tr { // traits required to make _Hash behave like a map
public:
    using key_type            = _Kty;
    using value_type          = pair<const _Kty, _Ty>;
    using _Mutable_value_type = pair<_Kty, _Ty>;
    using key_compare         = _Tr;
    using allocator_type      = _Alloc;

    // 这里有_In_place_key_extract_map
    using _In_place_key_extractor = _In_place_key_extract_map<_Kty, _Args...>;

using _In_place_key_extract_map = _In_place_key_extract_map_impl<_Remove_const_ref_t<_Valtys>...>;

struct _In_place_key_extract_map_impl<_Key, _Key, _Second> {
    // if we would call the pair(key, value) constructor family, we can use the first parameter as the key
    static constexpr bool _Extractable = true;
    static const _Key& _Extract(const _Key& _Val, const _Second&) noexcept { // 在插入hash时要有个key作为hash表索引
        return _Val;
    }
};

struct _In_place_key_extract_map_impl<_Key, pair<_First, _Second>> { 
    // if we would call the pair(pair<other, other>) constructor family, we can use the pair.first member as the key
    static constexpr bool _Extractable = is_same_v<_Key, _Remove_const_ref_t<_First>>;
    static const _Key& _Extract(const pair<_First, _Second>& _Val) noexcept { // 在插入hash时要有个key作为hash表索引
        return _Val.first;
    }
};
*/

`unordered_map` 对象创建

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

void printUMap(const unordered_map<int, int>& m) {
    for (unordered_map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << " " << "value = " << it->second << endl;
    }
    cout << "-----------------" << endl;
}
int main() {
    // 1. 默认构造函数
    unordered_map<int, int> m1;
    cout << "m1: " << endl;
    printUMap(m1);

    unordered_map<int, int> m2_1 = {
        pair<int, int>(1, 10),
        pair<int, int>(4, 24),
        pair<int, int>(3, 43),
        pair<int, int>(2, 15),
    };
    cout << "m2_1: " << endl;
    printUMap(m2_1);

    unordered_map<int, int> m2_2({
    pair<int, int>(1, 10),
    pair<int, int>(4, 24),
    pair<int, int>(3, 43),
    pair<int, int>(2, 15),
    });
    cout << "m2_2: " << endl;
    printUMap(m2_2);

    // 3. 迭代器
    unordered_map<int, int> m3(m2_1.begin(), m2_1.end());
    cout << "m3: " << endl;
    printUMap(m3);

    // 4. 拷贝构造函数
    unordered_map<int, int> m4(m2_2);
    cout << "m4: " << endl;
    printUMap(m4);

    return 0;
}
/* 执行结果：
m1:
-----------------
m2_1:
key = 1 value = 10
key = 4 value = 24
key = 3 value = 43
key = 2 value = 15
-----------------
m2_2:
key = 1 value = 10
key = 4 value = 24
key = 3 value = 43
key = 2 value = 15
-----------------
m3:
key = 1 value = 10
key = 4 value = 24
key = 3 value = 43
key = 2 value = 15
-----------------
m4:
key = 1 value = 10
key = 4 value = 24
key = 3 value = 43
key = 2 value = 15
-----------------
*/

`unordered_map` 赋值操作

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

void printUMap(const unordered_map<int, int>& m) {
    for (unordered_map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << " " << "value = " << it->second << endl;
    }
    cout << "-----------------" << endl;
}
int main() {
    unordered_map<int, int> m = {
        pair<int, int>(1, 10),
        pair<int, int>(2, 30),
        pair<int, int>(4, 30),
        pair<int, int>(3, 110),
    };
    cout << "m: " << endl;
    printUMap(m);

    // 1. = 对象
    unordered_map<int, int> m1;
    m1 = m;
    cout << "m1: " << endl;
    printUMap(m1);

    // 2. 初始化列表
    unordered_map<int, int> m2;
    m2 = {
        pair<int, int>(5,10), pair<int, int>(2, 10), pair<int, int>(4,31), pair<int, int>(3,610)
    };
    cout << "m2: " << endl;
    printUMap(m2);
    return 0;
}
/* 执行结果：
m:
key = 1 value = 10
key = 2 value = 30
key = 4 value = 30
key = 3 value = 110
-----------------
m1:
key = 1 value = 10
key = 2 value = 30
key = 4 value = 30
key = 3 value = 110
-----------------
m2:
key = 5 value = 10
key = 2 value = 10
key = 4 value = 31
key = 3 value = 610
-----------------
*/

`unordered_map` 大小操作

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

int main() {
    unordered_map<int, int> m;
    cout << "m.empty() = " << m.empty() << endl;  // 1
    cout << "m.size() = " << m.size() << endl;    // 0

    m = { pair<int, int>(52,0), pair<int, int>(13,14) };
    cout << "m.empty() = " << m.empty() << endl;  // 0
    cout << "m.size() = " << m.size() << endl;    // 2

    return 0;
}

`unordered_map` 数据插入

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

void printUMap(const unordered_map<int, int>& m) {
    for (unordered_map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << " " << "value = " << it->second << endl;
    }
    cout << "-----------------" << endl;
}

int main() {
    unordered_map<int, int> m;

    // 1
    m.insert(pair<int, int>(1, 10));
    printUMap(m);

    // 2
    m.insert(make_pair(3, 20));
    printUMap(m);

    // 3
    m.insert(unordered_map<int, int>::value_type(4, 7));  // 函数重载
    printUMap(m);

    // 4
    m[88] = 6; // 运算符重载
    printUMap(m);

    // 区别
    // 5
    pair<unordered_map<int, int>::iterator, bool> ret = m.insert(pair<int, int>(4, 10));
    cout << "insert(4, 10) = " << ret.second << endl;  // insert(4, 10) = 0  键已经有了，就会插入失败
    printUMap(m);

    // 6 
    m[3] = 66; // 键存在，则修改该对应的值
    printUMap(m);

    // 是否是中括号更好？
    // 7
    m[0];  // 访问0时，如果不存在会直接赋值 key = 0 value = 0
    printUMap(m);

    return 0;
}
/* 源码片段：
    pair<iterator, bool> insert(_Valty&& _Val) {
        return this->emplace(_STD forward<_Valty>(_Val));
    }
*/

/* 执行结果：
key = 1 value = 10
-----------------
key = 1 value = 10
key = 3 value = 20
-----------------
key = 1 value = 10
key = 3 value = 20
key = 4 value = 7
-----------------
key = 1 value = 10
key = 3 value = 20
key = 4 value = 7
key = 88 value = 6
-----------------
insert(4, 10) = 0
key = 1 value = 10
key = 3 value = 20
key = 4 value = 7
key = 88 value = 6
-----------------
key = 1 value = 10
key = 3 value = 66
key = 4 value = 7
key = 88 value = 6
-----------------
key = 1 value = 10
key = 3 value = 66
key = 4 value = 7
key = 0 value = 0
key = 88 value = 6
-----------------
*/

`unordered_map` 数据查找

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

int main() {
    unordered_map<int, int> m;
    m[1] = 1;
    m[2] = 3;
    m[3] = 6;
    m[666] = 886;

    for (int i = 0; i <= 4; ++i) {
        unordered_map<int, int>::iterator it = m.find(i);
        if (it != m.end()) {
            cout << "找到键值对：(" << it->first << "," << it->second << ")" << endl;
        }
        else {
            cout << "未找到键" << i << endl;
        }
    }
    //cout << m[3] << endl; // 这种方式不能做为查找键的依据
    //cout << m[5] << endl; // 不存在时会赋值

    return 0;
}

`unordered_map` 数据删除

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

void printUMap(const unordered_map<int, int>& m) {
    for (unordered_map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << " " << "value = " << it->second << endl;
    }
    cout << "-----------------" << endl;
}

int main() {
    unordered_map<int, int> m;
    m[1] = 1;
    m[2] = 5;
    m[4] = 7;
    m[9] = 8;
    printUMap(m);

    // 1
    m.erase(2); // 删除2这个键
    printUMap(m);

    // 2
    m.erase(m.begin());
    printUMap(m);

    // 3
    m.erase(m.begin(), m.end());
    printUMap(m);

    // 4
    m[5] = 3;
    m[7] = 9;
    printUMap(m);
    m.clear(); // 清空
    printUMap(m);

    return 0;
}


/* 执行结果：
key = 9 value = 8
key = 1 value = 1
key = 2 value = 5
key = 4 value = 7
-----------------
key = 9 value = 8
key = 1 value = 1
key = 4 value = 7
-----------------
key = 1 value = 1
key = 4 value = 7
-----------------
-----------------
key = 5 value = 3
key = 7 value = 9
-----------------
-----------------
*/

`unordered_map` 数据修改

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

void printUMap(const unordered_map<int, int>& m) {
    for (unordered_map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << " " << "value = " << it->second << endl;
    }
    cout << "-----------------" << endl;
}

int main() {
    unordered_map<int, int> m;
    m.insert(make_pair(1, 20));
    m.insert(make_pair(2, 333));
    m.insert(make_pair(3, 666));

    m[3] = 888;
    printUMap(m);

    m[2]++;
    printUMap(m);

    m[1] -= 21; // 复合运算符
    printUMap(m);

    return 0;
}


/* 执行结果：
key = 1 value = 20
key = 2 value = 333
key = 3 value = 888
-----------------
key = 1 value = 20
key = 2 value = 334
key = 3 value = 888
-----------------
key = 1 value = -1
key = 2 value = 334
key = 3 value = 888
-----------------
*/

`unordered_map` 数据统计

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

void printUMap(const unordered_map<int, int>& m) {
    for (unordered_map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << " " << "value = " << it->second << endl;
    }
    cout << "-----------------" << endl;
}

int main() {
    unordered_map<int, int> m = {
        pair<int, int>(1, 4),
        pair<int, int>(3, 33),
        pair<int, int>(2, 88),
        pair<int, int>(2, 77),
        pair<int, int>(5, 666),
    };
    for (int i = -1; i < 3; ++i) {
        cout << i << "的出现次数是" << m.count(i) << endl;
    }
    cout << "--------" << endl;

    unordered_multimap<int, int> mm = {
    pair<int, int>(1, 4),
    pair<int, int>(1, 4),
    pair<int, int>(1, 4),
    pair<int, int>(3, 33),
    pair<int, int>(3, 33),
    pair<int, int>(2, 88),
    pair<int, int>(2, 77),
    pair<int, int>(5, 666),
    };
    for (int i = -1; i < 3; ++i) {
        cout << i << "的出现次数是" << mm.count(i) << endl;
    }


    return 0;
}

/* 执行结果：
-1的出现次数是0
0的出现次数是0
1的出现次数是1
2的出现次数是1
--------
-1的出现次数是0
0的出现次数是0
1的出现次数是3
2的出现次数是2
*/

练习

四数相加 II

https://leetcode.cn/problems/4sum-ii/

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums1.size(); ++i) {
            for(int j = 0; j < nums2.size(); ++j) {
               hash[ -(nums1[i] + nums2[j]) ]++;
            }
        }
        int ans = 0;
        for(int k = 0; k < nums3.size(); ++k) {
            for(int l = 0; l < nums4.size(); ++l) {
               ans += hash[ nums3[k] + nums4[l] ];
            }
        }
        return ans;
    }
};

// nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
//  nums3[k] + nums4[l] == -(nums1[i] + nums2[j])

和为 K 的子数组

https://leetcode.cn/problems/subarray-sum-equals-k/

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt; // 键是pre[i]的值，值是pre[i]出现的次数
        int ans = 0;
        int pre = 0;
        cnt[pre]++;
        for(int i = 0; i < nums.size(); ++i) {
            pre = pre + nums[i]; // 等于 pre[i] = pre[i-1] + nums[i];
            ans += cnt[pre - k];
            cnt[pre]++;
        }
        return ans;
    }
};

/*
[j ... i] 子数组和是k,         sum(j...i) = k
pre[i] 代表了[0...i]中元素的和  pre[i] = sum(0...i)
于是
1. pre[i] - pre[j-1] == k
2. pre[j-1] = pre[i] - k   (0 <= j <= i)
所以以i为结尾的和为k连续数组的个数，就是计算出pre[i] - k的值，然后到下标0到i中找所以满足的前缀和的个数。
*/

STL概念

STL基础概念简介

线性表

顺序表

vector

vector 基础概念

vector 对象创建

vector 赋值操作

vector 数据插入

vector 数据删除

vector 扩容机制

vector 随机访问

vector 内存交换

vector 空间预留

vector 高效删除

vector 数据排序

练习

string

string 基础概念

string 对象创建

string 赋值操作

string 拼接操作

string 比较操作

string 随机访问

string 数据插入

string 数据删除

string 数据查找

string 数据替换

string 子串获取

练习

分段顺序表

deque

deque 基础概念

deque 对象创建

deque 赋值操作

deque 大小操作

deque 数据插入

deque 数据删除

deque 扩容机制

deque 随机访问

练习

链表

list

list 基础概念

list 对象创建

list 赋值操作

list 大小操作

list 数据插入

list 数据删除

list 数据访问

list 链表反转

list 链表排序

练习

容器适配器

stack

stack 基础概念

stack 对象创建

stack 赋值操作

stack 入栈操作

stack 获取栈顶

stack 出栈操作

stack 大小操作

stack 容器替换

练习

七进制数

回文链表

queue

queue 基础概念

queue 对象创建

queue 赋值

queue 入队操作

queue 获取队首

queue 获取队尾

queue 出队操作

queue 大小操作

练习

最近的请求次数

priority_queue

priority_queue 基础概念

priority_queue 对象创建

`priority_queue`

`priority_queue` 基础概念

`priority_queue` 对象创建

`priority_queue` 入队操作

`priority_queue` 获取堆顶

`priority_queue` 出队操作

`priority_queue` 大小操作

`priority_queue` 自定义结构

`unordered_set`

`unordered_set` 基础概念

`unordered_set` 对象创建

`unordered_set` 赋值操作

`unordered_set` 大小操作

`unordered_set` 数据插入

`unordered_set` 数据查找

`unordered_set` 数据删除

`unordered_set` 数据统计

`unordered_map`

`unordered_map` 基础概念

`unordered_map` 对象创建

`unordered_map` 赋值操作

`unordered_map` 大小操作

`unordered_map` 数据插入

`unordered_map` 数据查找

`unordered_map` 数据删除

`unordered_map` 数据修改

`unordered_map` 数据统计