C++理论学习

数据类型

变量

在 C++ 中，未初始化的变量可能包含随机值，这可能导致程序行为不可预测，因此在定义变量时就进行初始化

整型

类型	字节数	取值范围
int	4字节	$-2^{31}\sim 2^{31}-1$
unsigned int	4字节	$0\sim 2^{32}-1$
long long	8字节	$-2^{63}\sim 2^{63}-1$
sunsigned long long	8字节	$0\sim 2^{64}-1$

当数据范围可能超出 int 类型的限制时，应使用 long long 类型，避免整数溢出导致错误结果，参与的数的类型也要转换为long

算法题中频繁使用1e9+7作为取模对象，因为对于32位整数，1e9+7刚好在正整数范围内，取模后的结果可以用int存储，避免整数溢出

若题目要求“结果对1e9+7取模”，必须在计算过程中逐步取模（每一步乘法/加法后都取模），否则会溢出
1e9+7的质数属性是其核心优势，支持逆元计算，这是组合数、排列数等问题的关键

浮点型

类型	字节数	非0最小值
float	4字节	约-38次方
double	8字节	约-308次方
long double	16字节	约-4932次方

浮点数计算存在精度误差，不应直接用 == 比较两个浮点数是否相等，而应判断它们的差值是否小于某个很小的数（如1e-9)

字符型

用于存储单个字符，在C++中使用 char 类型，1字节，0~255，用来表示ASCII字符集

char 类型在C++中既可以当作字符使用，也可以当作小整数使用。例如，'A' 的ASCII值为65

输入输出

使用 cin 进行输入，使用 cout 进行输出

cin 语句会自动读入用户在终端的输入，并以空格或换行作为默认的该次读入的结束的标识（后面的内容则会被留给下一个需要读入的变量），然后把这一部分的值直接赋值给需要输入的变量

输出时可以使用 fixed 和 setprecision 来控制浮点数的输出精度。常见的应用有以下两种：

保留小数点后n位（四舍五入)

1 2	cout << defaultfloat; //清空以前对小数输出格式的设置 cout << fixed << setprecision(n) << 待输出变量名; // 输出待输出变量名（保留n位小数）

保留有效数字n位（四舍五入）

1 2	cout << defaultfloat; //清空以前对小数输出格式的设置 cout << setprecision(n) << 待输出变量名; // 输出待输出变量名（保留n位有效数字）

类型转换

C风格的强制类型转换

隐式转换：将一种类型的变量直接赋值给另一种类型的变量，编译器在编译阶段自动进行，能转就转，不能转就编译失败；

隐式转换可能导致数据丢失
显式转换：使用强制类型转换运算符来将一种类型的变量强制转换为另一种类型的变量，比如(int)d，但这个操作只能得到转换后的值，并不会改变原本变量的类型；

显式转换可能导致严重的运行时错误或未定义行为

从浮点型转换为整型时，小数部分会被截断，而不是四舍五入

C++强制类型转换

优先使用C++风格转换，避免C风格的 (type)value，提高代码可读性和安全性

基础类型用static_cast替代；下行转换首选dynamic_cast，尤其处理多态类型时

慎用reinterpret_cast，最小化const_cast使用

static_cast

静态转换，用于编译时确定的类型转换

适用场景：

基本数据类型之间的转换（如 int → double）
指针/引用在继承体系中的上行转换（派生类→基类）（将父类转换为子类是不安全的）

转换分析：

#include <iostream>
 
class Animal {
public:
    virtual void sound() const {
        std::cout << "Animal makes a sound" << std::endl;
    }
};
 
class Dog : public Animal  // 继承
{
public:
    void sound() const override  // override显式声明虚函数重写,const需保持一致
{
        std::cout << "Dog barks" << std::endl;
    }
};
 
int main() {
    Dog myDog;
    Animal* animalPtr = static_cast<Animal*>(&myDog);  // 安全的上行转换
    animalPtr->sound();  // 调用的是 Dog 的 sound，因为它是虚函数
 
    return 0;
}

虽然指针类型是Animal*，但实际指向的是Dog对象
使用static_cast进行上行转换（派生类→基类）不会改变对象类型
虚函数调用只取决于对象的实际类型（这里是Dog），与指针类型无关

dynamic_cast

动态转换，处理多态类型的安全下行转换（基类→派生类）

dynamic_cast会在运行时进行检查，失败时返回 nullptr（指针）或抛出异常（引用）

转换分析：

#include <iostream>
 
class Animal {
public:
    virtual ~Animal() {}  
    virtual void makeSound() const { // 基类需要至少有一个虚函数
        std::cout << "Animal sound" << std::endl;
    }
};
 
class Dog : public Animal {
public:
    void makeSound() const override {
        std::cout << "Dog barks" << std::endl;
    }
    void fetch() const {
        std::cout << "Dog fetches the ball" << std::endl;
    }
};

 
int main() {
    Animal* animalPtr = new Dog();  // 父类指针指向一个Dog对象
 
    // 使用 dynamic_cast 进行下行转换
    Dog* dogPtr = dynamic_cast<Dog*>(animalPtr);
 
    if (dogPtr) {  // 如果转换成功
        dogPtr->makeSound();  // 输出: Dog barks
        dogPtr->fetch();      // 输出: Dog fetches the ball
    } else {
        std::cout << "Conversion failed!" << std::endl;
    }
 
    delete animalPtr;
    return 0;
}

const_cast

常量转化，修改类型的 const 或 volatile 属性

谨慎移除const属性

转换分析：

#include <iostream>
 
void modify(int* p) 
{
    *p = 100;  // 修改指针指向的值
}
 
int main() 
{
    const int a = 10;  // a 是常量
    int b = 20;        // b 是非常量
    int c = 30;        // c 是非常量
    const int* pa = &a;  // pa 是指向常量的指针
    const int* pb = &b;  // pb 是指向常量的指针，但指向非常量
    int* pc = &c;
    
    // 使用 const_cast 去除 const 属性
    modify(const_cast<int*>(pa));  // 修改常量 a，不安全，可能导致未定义行为
    modify(const_cast<int*>(pb));  // 安全修改 b
    // 使用 const_cast 增添 const 属性
    const_cast<const int*>(pc);
    
    std::cout << "a = " << a << std::endl;  // 输出未定义结果
    std::cout << "b = " << b << std::endl;  // 输出: b = 100
    std::cout << "c = " << c << std::endl;
    return 0;
}

reinterpret_cast

重新解释转换，允许在不同类型之间进行低级别的类型转换，重新解释二进制位的含义，直接将一个类型的位模式重新解释为另一个类型

使用场景：

指针↔整数之间的转换
不相关指针类型间的转换

string

在 C++ 中，无法直接通过 (string) 整数类型变量名 的方法将整数类型变量转换为字符串类型变量，也无法直接通过 (int) 字符串类型变量名 的方法将字符串类型变量转换为整数类型变量

关于字符串常用到以下三个函数：

stoi() 函数：将字符串转换为整数
stod() 函数：将字符串转换为双精度浮点数
to_string() 函数：将数值转换为字符串

运算符

括号可以调节优先级，()优先级很高

优先级：

优先级	运算符
1 后缀运算符	`++` `--`
2 前缀运算符	`++` `--` `+` `-` `!` `~`
3 算术运算符	`*` `/` `%`
4	`+` `-`
5 移位运算符	`<<` `>>`
6 关系运算符	`<` `<=` `>` `>=`
7 相等运算符	`==` `!=`
8 位运算符	`&`
9	`^`
10	`
11 逻辑运算符	`&&`
12	`
13 赋值运算符	`=` `+=` `-=` `*=` `/=` `%=` `<<=` `>>=` `&=` `^=` `

位运算符：直接操作二进制位，仅适用于整数类型

运算名称	运算符	功能说明	二进制举例
按位与	`&`	对应位同为1时结果为1	`a & 0b1100` → `0b1000`
按位或	`	`	对应位有1时结果为1
按位异或	`^`	对应位不同时结果为1	`a ^ 0b1100` → `0b0110`
按位取反	`~`	每一位取反（0变1，1变0）	`~a` → `0b0101`（4位）
左移	`<<`	左移n位，低位补0	`a << 2` → `0b101000`
右移	`>>`	右移n位，高位补符号位（有符号数）	`a >> 1` → `0b0101`

常用数学函数：

数学函数名称	函数名
根号	`sqrt(x)` 输入输出类型匹配，隐式转换double
绝对值	整型：`abs(x)` 浮点型：`fabs(x)`
向上取整	`ceil(x)`
向下取整	`floor(x)`
四舍五入	`round(x)`
幂函数	`pow(a,b)` 输出浮点型

程序结构

顺序结构：代码逐行执行
选择结构：条件分支执行
循环结构：重复执行代码

选择结构：if switch 三目运算符

闰年的判断规则：

能被4整除但不能被100整除的年份是闰年
能被400整除的年份是闰年

if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))  // 判断是否为闰年
    cout << "yes";  // 如果是闰年，输出yes
else
    cout << "no";  // 如果不是闰年，输出no

循环结构：for主要被用于明确知道循环次数的情境下；while主要被用于知道循环进行的条件，但无法明确知道循环次数的情境下

素数判断：

int j = 2;
for (; j <= num; j++) {
    if ((num % j) == 0)
        break;
}

排序方法

排序次数 = 数组size - 1

比较次数 = 数组size - 1 - 排序轮次

定义交换函数

template <typename T>
void Swap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

冒泡法

重复遍历数组，比较相邻元素
如果顺序错误（前 > 后），则交换它们
每轮遍历将最大元素”冒泡”到正确位置

template <typename T>
void MSort(T arr[], const auto size) {
    for (int i = 0; i < size - 1; i++) 
        for (int j = 0; j < size - i - 1; j++) 
            if (arr[j] > arr[j + 1]) 
                Swap(arr[j], arr[j + 1]);
}

选择法

每次从未排序部分选出最大/小元素
将其放到已排序序列的末尾

template <typename T>
void XSort(T arr[], const auto len) {
    for (int i = 0; i < size-1; i++) {
        int min = i;
        for (int j = i+1; j < size; j++)
            if (arr[j] < arr[min])
                min = j;
        if (min!=i)
            swap(arr[i], arr[min]);
    }
}

程序内存

当一个 C++ 程序运行时，操作系统会为它分配一块虚拟内存，这块内存一般可以分为以下几个区域：

代码区（Text Segment）

存放程序的二进制机器指令（编译后的代码）

只读，防止程序意外修改指令

存放比如函数定义、类方法等

全局/静态区（Data Segment）

存放全局变量、静态变量

分为两个部分：

初始化数据区（.data）：存放已初始化的全局/静态变量
未初始化数据区（.bss）：存放未初始化的全局/静态变量（系统自动初始化为 0）

堆区（Heap）

程序员手动申请和释放的内存（new/delete、malloc/free）

需要手动管理，否则会造成内存泄漏；

栈区（Stack）

存放函数的局部变量、参数、返回地址等

自动管理：变量在作用域结束时自动释放，如果想保留需要加上static关键字放入全局区

空间小（通常1~8MB），但访问速度最快

常量区

存储字符串常量和编译期确定的常量，通常和只读数据段在一起

修改会导致未定义行为（崩溃）

示例：

#include <iostream>
#include <cstring>

int global_init = 10;    // data段（初始化）
int global_uninit;       // bss段（未初始化）

int main() {
    static int static_var = 20;   // data段
    const char* str = "Literal";  // "Literal"在常量区
    char stack_arr[100];          // 栈区

    int* heap_int = new int(30);  // 堆区
    delete heap_int;              // 必须释放！

    // 修改常量区（错误！）
    // str[0] = 'X'; // 崩溃！
}

区域	存储内容	生命周期	管理方式
代码区	程序指令	整个程序运行期间	自动
全局/静态区	全局/静态变量	整个程序运行期间	自动
栈区	局部变量、函数参数	作用域内	自动
堆区	动态分配对象	直到手动释放	手动（new/delete）
常量区	字符串常量	整个程序运行期间	只读

常见问题

野指针：

指针指向的内存已经被释放，但仍然访问

1
2
3

int* p = new int(10);
delete p;
*p = 20; // 野指针，未定义行为

内存泄漏：

堆内存未释放 → 程序长时间运行耗尽内存

void foo() {
    int* p = new int[100]; 
    // 忘记 delete[] p;
}

解决方案：使用智能指针（std::unique_ptr, std::shared_ptr）

悬空指针：

访问已释放的内存 → 崩溃或数据损坏

int* createAndReturn() {
    int local = 10;
    return &local;  // 危险！函数结束后local不再存在
}

int main() {
    int* ptr = createAndReturn();
    cout << *ptr << endl;  // 不确定的行为，可能崩溃
    return 0;
}

修复：释放后置指针为 nullptr

栈溢出：

递归过深或大局部变量 → 程序崩溃

规避：避免大对象在栈分配（改用堆）

数组

数组是C++中用于存储相同类型元素的连续内存数据结构

C++中既有传统的 C 风格数组（T a[N]），也有更安全/便利的类型：std::array（固定长度）和 std::vector（动态长度）[vector放到容器部分讲]

优先用 std::array/std::vector/std::span 来写更安全，现代的C++只有必要时才用裸数组

T a[N]

数组名是首元素地址的常量指针，所以数组作为函数参数时，函数参数写成 T arr[] 时会衰退为 T*

如果要在参数里保留数组大小，需要使用模板引用

#include <iostream>
using namespace std;

template<typename T, size_t N>
void printArray(T (&arr)[N]) { // 保留大小信息
    for (size_t i = 0; i < N; ++i) cout << arr[i] << ' ';
    cout << '\n';
}
int main() {
    int a[] = {3,1,4,1,5};
    printArray(a);
}

array

std::array 是 C++11 引入的固定大小数组容器，位于 <array> 头文件中

它结合了原生数组的性能优势和标准容器的便利接口，大小固定

重要成员函数：

函数	描述	时间复杂度
`size()`	返回元素数量	O(1)
`empty()`	检查是否为空	O(1)
`at()`	安全访问，带越界检查	O(1)
`fill(value)`	用指定值填充所有元素	O(n)

at用法：

int main() {
    array<int, 8> arr{};
    // 调试时使用 at() 进行边界检查
    try {
        int value = arr.at(10); // 抛出异常
    } catch (const std::out_of_range& e) {
        cerr << e.what() << '\n';
    }
}

span

std::span是 C++20 引入的一个非常实用的轻量级容器视图

std::span 是一个 不拥有数据 的对象，它只是指向一段连续内存（array/vector/C-array）的视图(不能用于 list、map)，修改 span 内元素会影响原数组

可以看成是 指针 + 长度 的组合，比裸指针更安全

常用于函数定义

void print(const span<int>arr) {
    for (const auto i : arr) cout << i << " ";
    cout << endl;
}

int main() {
    int a[] = {1,2,3,4};
    array<int,5>b = {5,6,7,8,9};
    vector<int>c = {1,2,3,4,5};
    print(a);print(b);print(c);
}

一个函数就能同时支持 C 数组、std::array、std::vector，而且安全

指针与引用

空指针表示”不指向任何地址”，用于初始化或重置指针，不能访问

引用和指针之间的主要不同：

不存在空引用，引用必须连接到一块合法的内存；但存在空指针
引用被初始化后就不能被指向到另一个对象；指针可以在任何时候指向到另一个对象
引用必须在创建时被初始化，指针可以在任何时间被初始化

引用的本质是一个指针常量

const 修饰	表达式	意义
常量指针	`const int* p = &a`	指针的指向(地址)可以改，但指针指向的值不可修改
指针常量	`int* const p = &a`	指针的指向(地址)不可以改，但指针指向的值可以改
指向常量的常量指针	`const int* const p = &a`	指针的指向(地址)不可以改，指针指向的值也不可修改
常量引用（只读访问）	`const int& ref = num;`	不可修改对象

优先使用引用：

函数参数传递（避免拷贝，修改原始对象）
操作符重载（如 <<, >>, =）
范围for循环迭代容器元素

必须使用指针：

动态内存管理（new/delete）
可选参数（可能为 nullptr）
多态对象处理（基类指针指向派生类）
C语言接口兼容
低级硬件/内存操作

智能指针

传统指针的问题：

内存泄漏：忘记 delete 分配的内存
悬空指针：访问已释放的内存
双重释放：多次 delete 同一内存

标准库 <memory> 里提供了三种常见智能指针

类型	所有权策略	复制/移动行为	适用场景
`std::unique_ptr`	独占所有权	不可复制，仅可移动	单一所有者场景（默认首选）
`std::shared_ptr`	共享所有权	可复制，引用计数递增，也可移动	多个所有者共享资源
`std::weak_ptr`	弱引用（无所有权）	可复制，不增加引用计数，也可移动	解决 `shared_ptr` 循环引用问题

unique_ptr

独占式指针

独占资源所有权（不可复制）
离开作用域自动释放资源
不支持拷贝（拷贝构造函数被禁用），但支持移动语义（std::move）

举例：

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

int main() {
    auto p1 = make_unique<int>(10);     // c++14+ 推荐
    // unique_ptr<int> p1(new int(10)); // 传统写法，不建议
    cout << *p1 << endl;

    // unique_ptr 不能拷贝
    // unique_ptr<int> p2 = p1; 

    // 但可以转移所有权
    unique_ptr<int> p2 = std::move(p1); // p1 失效
    cout << *p2 << endl;
}

shared_ptr

共享指针

多个 shared_ptr 可共享同一对象的所有权
通过引用计数跟踪所有者数量，计数为 0 时自动释放内存

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

int main() {
    auto p1 = make_shared<int>(20);
    {
        auto p2 = p1;
        cout << p1.use_count() << endl; // 输出2
    } // p2析构
    cout << p1.use_count() << endl; // 输出1
}

常用函数：

p.get()：返回p中保存的指针，不会影响p的引用计数
p.reset()：释放p指向的对象，将p置为空
p.reset(q)：释放p指向的对象，令p指向q

weak_ptr

弱引用指针

不增加引用计数，常与 shared_ptr 配合使用
解决 shared_ptr 循环引用问题

循环引用是指两个或多个对象之间通过shared_ptr相互引用，形成了一个环，导致它们的引用计数都不为0，从而导致内存泄漏

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

struct B;
struct A {
    shared_ptr<B> bptr;
    ~A() { cout << "A destroyed\n"; }
};
struct B {
    weak_ptr<A> aptr; // 用 weak_ptr 打破循环引用
    ~B() { cout << "B destroyed\n"; }
};

int main() {
    auto a = make_shared<A>();
    auto b = make_shared<B>();
    a->bptr = b;
    b->aptr = a; // 如果用 shared_ptr 会导致内存泄漏
}

需转换为 shared_ptr 才能访问资源

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

int main() {
    auto shared = make_shared<int>(200);
    weak_ptr<int> weak = shared;   // 不增加引用计数
    cout << shared.use_count() << endl; // 输出1
    
    if (auto temp = weak.lock()) { // 尝试转为 shared_ptr
        *temp = 300; // 访问对象
        cout << shared.use_count() << endl; // 输出2
    } // temp 析构，不影响引用计数
    
    cout << *shared << endl; // 输出300
    cout << shared.use_count() << endl; // 输出1
}

常用函数：

p.expired() 检查所指对象是否已经被释放
p.lock() 返回一个指向共享对象的shared_ptr，若对象不存在则返回空shared_ptr

自定义删除器

智能指针支持自定义资源释放逻辑（如文件句柄、网络连接）

统计文件行数程序：

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

int main() {
    auto file_closer = [](FILE* fp) { if (fp) fclose(fp); }; // 定义文件关闭器
    auto file = unique_ptr<FILE,decltype(file_closer)>(fopen("test.txt", "r"), file_closer); // 用 unique_ptr 管理 FILE
    if (!file) {
        cerr << "Error opening file" << endl;
        return 1;
    }
    // 统计行数
    char buffer[1024];
    int line_count = 0;
    while (fgets(buffer, sizeof(buffer), file.get())) {
        line_count++;
    }
    cout << line_count << endl;
}

结构体

在 C++中用 struct 关键字定义一个结构体类型，别忘了结尾的分号;

对于结构体/类使用点运算符.来访问或修改对象的成员变量
对于结构体/类的指针，还可以通过->来访问或修改对象的成员变量

struct 默认成员是 public，都可以直接访问（class默认为private）

构造函数是一个特殊的成员函数，名字和结构体/类名完全相同，并且没有返回值类型

推荐使用初始化列表来初始化成员，这对于 const 成员或引用成员是必须的

struct Student {
    string name;
    int chinese, math, english, total_score;
    
    // 使用初始化列表的构造函数
    Student(string s, int c, int m, int e) : name(std::move(s)), chinese(c), math(m), english(e) {
        total_score = chinese + math + english; // 可以在函数体进行别的运算
    }
}; // <-- 注意分号

优先用 struct 表示纯数据集合（如坐标、配置项）

类和对象的构造

面向对象的三大特性为：封装、继承、多态

类（class）：一种用户自定义的类型（类型模板），把数据（成员变量）和操作这些数据的代码（成员函数）封装在一起
对象（object）：类的实例，是运行时分配的实体，有自己的状态（成员变量值）

定义类的过程就是对问题进行抽象和封装的过程

头文件构造

一般来说会将类单独写到头文件中，在main中include

在类的.h文件中将类的内容复制过去，但是具体实现删去，只保留语句和函数，分号结尾；

在类的.cpp文件中定义函数，这时候不需要再用Class框起来，而且在函数前带上class::声明函数的所属(以成员函数的形式)

举例：

头文件

#ifndef MYCLASS_H      // 宏防止重复包含
#define MYCLASS_H

#include <string>      // 需要的库
using namespace std;
class MyClass {
private:
    string name;
    int age;

public:
    // 构造函数
    MyClass(const string& n, int a);

    // 成员函数
    void say() const;

    // getter
    string getName() const;
    int getAge() const;
};

#endif // MYCLASS_H

源文件

#include "MyClass.h"
#include <iostream>    // 输出需要
#include <utility>

// 构造函数实现
MyClass::MyClass(string n, int a)
    : name(move(n)), age(a) {}

// 成员函数实现
void MyClass::say() const {
    cout << "姓名: " << name << " 年龄: " << age << '\n';
}

string MyClass::getName() const {
    return name;
}

int MyClass::getAge() const {
    return age;
}

类的访问权限

类成员的访问限制是通过在类主体内部对各个区域标记public、private、protected来指定的

默认情况下，类的所有成员是私有的

一般会在私有区域定义数据，在公有区域定义相关的函数，以便在类的外部也可以调用这些函数

类的公有部分(public)只暴露必要的接口，私有部分(private)隐藏具体实现

public：在类的外部是可访问的，可以不使用任何成员函数来设置和获取公有变量的值
private：在类的外部是不可访问的，只有类和友元函数可以访问，不能被派生类访问

例如：儿子不可以访问父亲的私有内容
protected：与私有成员十分相似，但protected成员在派生类(即子类)中是可访问的

例如：儿子可以访问父亲的保护内容

常用前缀

关键字	作用范围	含义	常见用途
`explicit`	构造函数/转换运算符	禁止隐式转换	单参数构造函数、`operator bool`
`constexpr`	变量/函数/构造函数	允许在编译期计算（如果条件满足）	常量表达式、模板参数、数组大小
`noexcept`	函数/构造函数/析构函数	承诺不会抛异常	移动构造、析构，方便 STL 优化

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

class Vec {
    int x, y;
public:
    // explicit: 禁止隐式转换
    explicit Vec(int v) : x(v), y(v) {
        cout << "explicit constructor called\n";
    }

    // constexpr: 可以在编译期构造
    constexpr Vec(int a, int b) : x(a), y(b) {}

    // noexcept: 保证不会抛异常（常用于移动构造）
    // Vec(Vec&& other)：移动构造函数的声明
    // 右值引用(&&)只能绑定到临时对象、即将销毁的对象,直接转移资源所有权（避免深拷贝）
    Vec(Vec&& other) noexcept : x(other.x), y(other.y) {
        cout << "move constructor (noexcept)\n";
        other.x = other.y = 0;
    }

    void print() const noexcept {
        cout << "(" << x << "," << y << ")\n";
    }
};

constexpr Vec makeVec() {
    return Vec(1, 2); // 编译期构造
}

int main() {
    // 1. explicit 演示
    // Vec v1 = 5;      // 错误：被 explicit 禁止
    Vec v1 = Vec(5);    // 显式调用
    v1.print();

    // 2. constexpr 演示
    constexpr Vec v2 = makeVec(); //  编译期构造
    v2.print();

    // 3. noexcept 演示
    vector<Vec> arr;
    Vec tmp(10);         // 调用 explicit 构造
    arr.push_back(move(tmp)); // 强制调用移动构造
}

构造和析构函数

类的构造和析构函数都是类的一种特殊的成员函数，都是可以手动调用的，允许但不建议

构造函数：对象创建时调用；可用初始化列表初始化成员（推荐）

构造函数的名称与类的名称是完全相同的，并且不会返回任何类型，也不会返回 void
析构函数：对象销毁时调用，用于释放堆区开辟的资源（文件、内存、锁等）

不会返回任何值，也不能带有任何参数

class Buffer {
public:
    Buffer(size_t n) : data(new char[n]), size(n) {}
    ~Buffer() { delete[] data; }
private:
    char* data;
    size_t size;
};

一般构造函数分为默认构造函数，有参构造函数，拷贝构造函数(一般用来复制类)

如果提供了有参构造函数，编译器不再提供默认构造函数，但仍然提供拷贝构造函数
如果提供了拷贝构造函数，就不再提供其它构造函数

默认的拷贝构造函数为浅拷贝

浅拷贝是简单的赋值拷贝操作(=操作) -> 带来的问题是内存的重复释放

先进后出，释放的时候拷贝的析构函数已经把new出来的区域delete，但是原类释放析构函数又delete相同区域，报错

如果类包含原始指针指向堆内存，就必须使用深拷贝；

深拷贝：在堆区重新申请空间，进行拷贝操作

class Person {
public:
    Person(const int age, const int height) {
        this->age = age;
        this->height = new int(height);
    }
    Person(const Person &p) {
        this->age = p.age;
        this->height = new int(*p.height);
    }
    int age{};
    int *height{};
    ~Person() {
        delete this->height;
    }
};

成员函数

成员函数可以定义在类定义内部，或者单独在类的外部使用范围解析运算符 :: 来定义

普通成员函数：可以直接读写类的成员变量，调用时隐式传递一个 this 指针给它，this 的类型是 Class* const(指针常量)
const 成员函数：在函数声明后加const，表示不会修改对象的成员变量，函数调用时 this为const Class* const(指向常量的常量指针)

在 const 对象上，只能调用 const 成员函数
static 静态成员函数：与对象无关，没有 this 指针，只能访问类的静态数据成员或通过对象/参数访问数据
虚函数（virtual）：用于多态，通过基类指针/引用调用时会动态绑定到实际对象的方法

析构函数做基类时通常写成虚函数

成员变量和成员函数是分开存储的，只有非静态成员变量内存上属于类的对象

this指针

每一个 非静态成员函数 内部，都隐式带有一个指向当前对象的指针，叫做 this

this的作用：让成员函数知道自己正在操作哪个对象

this指针的用途：

当形参和成员变量同名时，可用this指针来区分
在类的非静态成员函数中返回对象本身，可使用return *this

return *this 这种情况下如果要返回本体需要函数的返回类型为类的引用

如果是函数类型不是引用相当于拷贝类对象，函数的效果无法叠加！

类允许空指针，但是如果空指针传入后调用类对象(this)，程序会崩溃

静态成员

可以使用 static 关键字来把类成员定义为静态的

没有 this 指针，因此不能直接访问非静态成员（除非通过传入的对象）

静态成员函数定义在类作用域内、但不依赖于某个对象实例，本质上编译器把它当成“在类命名空间下的普通函数”，即使在类对象不存在的情况下也能被调用，只要使用类名加范围解析运算符 :: 就可以访问

当声明类的成员为静态时，这意味着无论创建多少个类的对象，静态成员都只有一个副本，静态成员在类的所有对象中是共享的

class Counter {
    inline static int count = 0; // C++17 起可直接在类内初始化
public:
    static void inc() { ++count; }   // 静态成员函数（定义在类内）
    static int get() { return count; }
};

// 在类外定义静态数据成员（C++17 之前必须这样）
int Counter::count = 0;

int main() {
    Counter::inc();
    std::cout << Counter::get() << "\n"; // 1
}

指针与类型

class C {
public:
    static void sfunc();
    void mfunc();
};

// 静态函数指针 —— 普通函数指针
void (*fp)() = &C::sfunc; // OK

// 非静态成员函数指针 —— 成员函数指针类型
void (C::*mp)() = &C::mfunc; // 不同的类型，调用时需要对象：(obj.*mp)();

并发 / 线程安全相关

静态成员函数本身通常无状态（除非操作静态数据），因此是线程安全的

“线程安全”取决于是否访问共享可变状态，如果静态成员函数只是做纯计算、不读写任何共享的可变数据，那么多个线程同时调用通常是安全的
静态数据（shared state）的访问需考虑同步（互斥、原子等）
局部静态变量初始化自 C++11 起是线程安全的（只会初始化一次且同步）

友元函数

friend 用于在类内部声明某个函数或另一个类可以访问该类的 private / protected 成员

被声明为友元的函数/类并非该类的成员函数，它只是被“授予访问权”

易错点：

友元不是互相的：如果A声明B为friend，B能访问A的私有；但A并不能访问B的私有（除非B也声明A为friend）
友元不继承

基类把某个函数声明为friend，不代表派生类也会把该函数视作friend（每个类的私有是独立的）
友元不是传递的

AfriendB，BfriendC不意味着AfriendC
友元会破坏严格的封装边界（因为允许外部直接读写私有成员），应当有限度地使用

使用场景：

实现非成员但需要访问私有的操作符
若两个类紧密耦合并互相操作对方内部结构，可以用friend class（但先考虑重构或暴露更小的接口）

举例：

用友元实现 operator<<（常见用法）

#include <iostream>
class Point {
    int x, y;
public:
    Point(int x,int y):x(x),y(y){}
    friend ostream& operator<<(ostream& os, const Point& p);
};
ostream& operator<<(ostream& os, const Point& p) {
    return os << "(" << p.x << "," << p.y << ")";
}

流插入操作符<<的标准用法是：std::cout << 对象，如果operator<<定义为类的成员函数，左操作数必须是类对象（如point << std::cout;），这与自然用法矛盾，因此，必须定义为非成员函数，使左操作数为流对象

友元类（friend class）

class B; // 前向声明
class A {
    int v = 1;
    friend class B; // B 的所有成员都能访问 A::private
};
class B {
public:
    void setA(A& a, int x) { a.v = x; }
};

友元成员函数

class C; // 前向声明

class A {
    int x = 0;
    friend void C::mutate(A&); // 需要事先声明 class C { public: void mutate(A&); };
};

class C {
public:
    void mutate(A& a) { a.x = 100; }
};

类的继承

有public, protected, private三种继承方式，它们相应地改变了基类成员的访问属性

继承方式	public 成员	protected 成员	private 成员
public 继承	public	protected	private
protected 继承	protected	protected	private
private 继承	private	private	private

1	class Dog : public Animal {}; // 语法

但无论哪种继承方式，下面两点都没有改变：

private 成员只能被本类成员和友元访问，不能被派生类访问
protected 成员可以被派生类访问

父类中所有非静态成员属性都会被子类继承下去，私有成员是被编译器给隐藏了，因此访问不到，但是被继承下去了

构造/析构顺序

构造：

先构造基类（如果有多个基类，按声明顺序，虚基类先）
然后构造成员（按声明顺序）
最后执行派生类构造函数体

class Base {
public:
    Base(int x) { std::cout << "Base(" << x << ")->"; }
};

class Derived : public Base {
    int m;
public:
    Derived(int x, int y) : Base(x), m(y) {
        std::cout << "Derived\n";
    }
};

// 输出：Base(x) -> Derived

析构顺序相反：先派生析构，再成员析构，再基类析构

多重继承问题

示例：

1
2
3

class A { public: void f() {} };
class B { public: void g() {} };
class C : public A, public B { };

调用 C 对象可以同时使用 A::f() 和 B::g()

向上向下转换时：

向上转换，安全

当把派生类对象按值赋给基类对象时，会发生“切片”——派生部分被切掉，只保留基类子对象
向下转换，不安全，需要检查

使用 dynamic_cast 做安全下转（基类必须有虚函数）

static_cast 可以做不检查的转换（更快但不安全）

菱形继承问题（同一祖先被重复继承）

   Top
  /   \
Left  Right
  \   /
  Bottom

若 Left 和 Right 都 public Top，那么 Bottom 会有两个 Top 子对象

解决方法：虚继承，使得最底层只有一个共享的 Top

struct Top { int v; };
struct Left : virtual public Top {};
struct Right : virtual public Top {};
struct Bottom : public Left, public Right {};
// Bottom 只有一个 Top 子对象

类的多态

当类之间存在层次结构，并且类之间是通过继承关联时，就会用到多态

多态分为两类

静态多态：通过函数重载、模板、运算符重载实现，在程序编译阶段就能确定具体调用哪个函数
动态多态：基类指针/引用 + virtual 函数 + 派生类覆盖来实现（动态绑定），实际调用在运行时根据对象的真实类型决定

运行时多态需要三个关键条件：

存在继承关系
基类中有关键字 virtual 声明的虚函数
通过基类的指针或引用来调用虚函数

虚函数

在成员函数前加上 virtual 关键字，该函数就变成了虚函数

派生类可以重写这个虚函数，并且在用基类指针/引用调用时，根据对象的真实类型执行对应的版本

常常先创建一个父类空指针，在后续过程再让其指向new开辟子类的区域

#include <iostream>
using namespace std;

class Animal {
public:
    virtual void speak() { cout << "Animal sound\n"; } // 虚函数
};

class Dog : public Animal {
public:
    void speak() override { cout << "Woof!\n"; } // 重写虚函数
};

int main() {
    Animal* a = new Dog;   // 基类指针指向派生类对象
    a->speak();            // 调用 Dog::speak()，而不是 Animal::speak()
    delete a;
}

纯虚函数

纯虚函数声明但没有实现，声明时使用= 0

包含至少一个纯虚函数的类被称为抽象类，它不能被直接实例化，强制派生类提供具体的实现

如果子类也声明为抽象类，则可以不实现父类的纯虚函数，而是将实现推迟到其子类

#include <iostream>
using namespace std;

class Shape {
public:
    virtual void draw() = 0;  // 纯虚函数
    virtual ~Shape() = default;
};

class Circle : public Shape {
public:
    void draw() override { cout << "Draw Circle\n"; }
};

class Square : public Shape {
public:
    void draw() override { cout << "Draw Square\n"; }
};

int main() {
    // Shape s;   // 报错：抽象类不能实例化
    Shape* p1 = new Circle();
    Shape* p2 = new Square();

    p1->draw();  // Draw Circle
    p2->draw();  // Draw Square

    delete p1;
    delete p2;
}

虚析构

如果基类的析构函数不是虚的，那么通过基类指针删除一个派生类对象会导致派生部分的析构函数不被调用，从而引发资源泄漏

如果一个类有任何虚函数，它就应该有一个虚析构函数，即使基类不需要自定义析构，也提供一个空的虚析构函数

推荐写法：

class Base {
public:
    virtual ~Base() = default;  // 默认实现
};

拥有纯虚析构函数的类属于抽象类

重载运算符

在同一个作用域内，可以声明几个功能类似的同名函数，但是这些同名函数的形式参数（指参数的个数、类型或者顺序）必须不同

最主要就是区分输入的参数能够唯一地满足某个函数

重载运算符规则：函数名是由关键字 operator 和其后要重载的运算符符号构成的

只能重载 C++ 已有的运算符，不能新增运算符，也不能改变优先级或结合性

不能重载的运算符：

::（域/作用域解析）、.（点成员访问）、.*（成员指针访问）、?:（三目条件）

sizeof（大小运算符）

重载为成员函数 or 非成员函数的规则：

运算符	推荐形式	原因
`=`, `()`, `[]`, `->`	必须是成员函数	语言规定
`+=`, `-=`, `/=`, `*=`	通常是成员函数	修改左操作数，天然是 `this`
一元运算符 (`++`, `--`, `-`, `!`)	通常是成员函数	操作一个对象，天然是 `this`
算术运算符 (`+`, `-`, `*`, `/`)	通常是非成员函数	支持左右操作数的对称性
关系运算符 (`==`, `!=`, `<`, `>`)	通常是非成员函数	支持左右操作数的对称性
流运算符 (`<<`, `>>`)	必须是非成员函数	左操作数是流，不是类

赋值运算符 =

推荐使用copy-and-swap 模式来重载

operator= 接受形参 other，会利用拷贝或移动构造创建 other，再 swap，出错时不会改变原对象

左值：有名字、可取地址，可以反复用（如变量 x）

右值：临时、没名字，用完就丢

copy-and-swap模式：

如果等号右边为左值，进入拷贝构造
如果等号右边为右值，进入移动构造

然后都会进入operate=函数体，这样就实现了复用函数体

即使是自等于也不会出问题，因为other是拷贝的副本，交换后other拿着原对象的指针，函数结束后自动释放，也避免了自赋值检查；

class Buffer {
    char* p; size_t n;
public:
    Buffer(const char* s);
    Buffer(const Buffer&); // copy ctor           
    // move ctor
    Buffer(Buffer&& other) noexcept:p(other.p),n(other.n) {
        other.p = nullptr;
        other.n = 0;
    }
    
    ~Buffer() { delete[] p; }

    // copy-and-swap assignment (pass-by-value leverages copy/move)
    Buffer& operator=(Buffer other) noexcept {
        swap(other);
        return *this; // 为了像原来等号可以连等，需要重载时返回引用
    }
    void swap(Buffer& o) noexcept { std::swap(p, o.p); std::swap(n, o.n); }
};

为了避免默认拷贝函数的影响，需要定义拷贝函数，避免浅拷贝

传统写法：需要先释放 this 的旧资源，然后再进行深拷贝分配新资源

class Person {
public:
    Person(int age);
    Person(const Person& p);
    Person& operator=(const Person &p);
    ~Person();
    int *age;
};
Person& Person::operator=(const Person &p) {
    // 要先判断自身堆区有无内容
    if (this->age != nullptr) {
        delete this->age;
    }
    age = new int (*p.age);
    return *this;
}

复合赋值运算符

修改左操作数，天然是 this，所以通常是成员函数

class Vec {
    int x, y;
public:
    Vec(int x, int y): x(x), y(y) {}
    // +=
    Vec& operator+=(const Vec& rhs) {
        x += rhs.x;
        y += rhs.y;
        return *this;
    }

前缀/后缀 ++/–

前缀：T& operator++() 返回 *this 的引用（效率高）

后缀：T operator++(int) 参数 int 用以区分前++和后++（只能int），返回修改前的值（通常返回值）

struct Counter {
    int v;
    Counter& operator++() { ++v; return *this; }  // prefix
    Counter operator++(int) { Counter tmp = *this; ++v; return tmp; } // postfix
};

同样-和!都是操作本身，返回this方便，通常是成员函数

算术运算符

算术和比较运算符一般希望左右操作数对称

例如 a + b 和 b + a 都要支持，如果写成成员函数，就只能保证 a + b，而 b + a（若 b 不是同类对象）可能失效

class Vec {
    int x, y;  // 私有成员
public:
    Vec(int x = 0, int y = 0): x(x), y(y) {}

    // 让友元函数可以访问 x, y
    friend Vec operator+(const Vec& lhs, const Vec& rhs);
    friend bool operator==(const Vec& lhs, const Vec& rhs);
    friend bool operator<(const Vec& lhs, const Vec& rhs);
};

// 加法运算符（算术运算符）
Vec operator+(const Vec& lhs, const Vec& rhs) {
    return Vec(lhs.x + rhs.x, lhs.y + rhs.y);
}

// 等于运算符（比较运算符）
bool operator==(const Vec& lhs, const Vec& rhs) {
    return (lhs.x == rhs.x && lhs.y == rhs.y);
}

// 小于运算符（比较运算符，假设比较模长）
bool operator<(const Vec& lhs, const Vec& rhs) {
    int len1 = lhs.x * lhs.x + lhs.y * lhs.y;
    int len2 = rhs.x * rhs.x + rhs.y * rhs.y;
    return len1 < len2;
}

输入/输出流 <</>>

通常作为非成员 friend，让 std::ostream 在左侧

class Person {
    friend ostream & operator<<(ostream &, const Person &); // 避免无法访问私有内容
    string name = "Alice";
    int age = 12;
};
// 这里返回ostream &是为了避免后续追加内容报错，链式规则，返回void就无法再加内容
ostream & operator<<(ostream& cout, const Person& person) {
    cout << "name:" <<person.name << "\tage:" << person.age;
    return cout;
}
int main(){
    Person person;
    cout << person << endl;
}

函数调用()

重载函数调用操作符()的类，其对象常称为函数对象

行为和函数调用类似，称为仿函数

仿函数的优势是非常灵活，没有固定写法

类后面直接带()称为匿名函数对象，适用于只需要一下的结果

#include <iostream>
#include <string>
using namespace std;
class Print {
public:
    void operator()(const string& test) const {
        cout << test << endl;
    }
};
class Add {
public:
    int operator()(const int& x, const int& y) const {
        return x + y;
    }
};

int main() {
    Print myprint;
    myprint("hello world");
    cout << Add()(1, 2) <<endl;
}

函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
函数对象超出普通函数的概念，函数对象可以有自己的状态

比较运算符

返回bool类型的仿函数称为谓词，谓词不应修改元素

如果operator接受一个参数，那么叫做一元谓词

如果operator接受两个参数，那么叫做二元谓词

文件操作

iostream 标准库，它提供了 cin 和 cout 方法分别用于从标准输入读取流和向标准输出写入流

从文件读取流和向文件写入流需要用到 C++ 中另一个标准库 fstream

数据类型	描述
ofstream	该数据类型表示输出文件流，用于创建文件并向文件写入信息
ifstream	该数据类型表示输入文件流，用于从文件读取信息
fstream	该数据类型通常表示文件流，且同时具有 ofstream 和 ifstream 两种功能

输出文件流过程：

创建流对象：ofstream ofs;
打开文件：ofs.open(“文件路径”,打开方式);
写数据：ofs << “写入的数据”;
关闭文件：ofs.close();

open函数

1	void open(const char *filename, ios::openmode mode);

模式标志	描述
ios::app	追加模式，所有写入都追加到文件末尾
ios::ate	文件打开后定位到文件末尾
ios::in	打开文件用于读取
ios::out	打开文件用于写入
ios::trunc	如果该文件已经存在，先删除再创建
ios::binary	二进制模式

可以把以上两种或两种以上的模式结合使用

1 2	ofstream outfile; outfile.open("file.dat", ios::out \| ios::trunc );

在读取过程中使用<< 碰到换行，空格，其它类型数据会自动停止

输入文件流过程：

创建流对象：ifstream ifs;
打开文件并判断文件是否打开成功

ifs.open(“文件路径”,打开方式);

if(!ifs.is_open()) ：文件不存在

char ch; ifs >> ch; if (ifs.eof()) ：判断文件是否为空
读数据：四种方式读取
关闭文件：ifs.close();

char buf[1024] = {0};
// 方法1:
while (ifs>>buf) 
    cout << buf << endl;
// 方法2:
while (ifs.getline(buf, sizeof(buf)))
    cout << buf << endl;

二进制方式：

class Person {
public:
    char name[64];
    int age;
};
void test01() {
    ofstream ofs("person.txt", ios::out | ios::binary);
    Person p = {"Alice", 18};
    ofs.write((const char*)&p, sizeof(Person));
    ofs.close();
}
void test02() {
    ifstream ifs("person.txt", ios::in | ios::binary);
    if (!ifs.is_open()) {
        cerr << "Can't open person.txt" << endl;
        return;
    }
    Person p{};
    ifs.read((char*)&p, sizeof(Person));
    cout << p.name << endl;
    cout << p.age << endl;
}
int main() {
    test01();
    test02();
}

string

string和char *区别：

char *是—个指针
string是一个类，类内部封装了char*，是一个char*型的容器

构造函数：

函数	说明
`string()`	默认构造空字符串
`operator=`	赋值（支持C风格字符串、`string`对象、字符）
`string(size_t n, char c)`	构造包含 `n` 个字符 `c` 的字符串

元素访问：

函数	说明
`operator[]`	访问指定位置字符（不检查越界）
`at(size_t pos)`	访问指定位置字符（越界抛出`out_of_range`异常）
`front()`	首字符
`back()`	末字符
`c_str()`	返回C风格字符串（以`\0`结尾）

容量操作：

函数	说明
`size()` / `length()`	返回字符数量
`empty()`	判断字符串是否为空
`capacity()`	返回当前分配的存储容量
`reserve(size_t n)`	预分配至少 `n` 字符的内存（优化性能关键）
`shrink_to_fit()`	请求移除未使用的容量（C++11）

修改操作：

函数	说明
`append()`	追加（支持子串/重复字符）
`push_back(char c)`	末尾添加字符
`insert(size_t pos, const string&)`	插入字符串
`erase(size_t pos, size_t len)`	删除从 `pos` 开始的 `len` 个字符
`replace(pos, len, new_str)`	替换指定范围的字符

字符串操作：

函数	说明
`substr(pos, len)`	返回从 `pos` 开始的子串（默认到末尾）
`find()`	查找子串，返回首次位置（失败返回 `string::npos`）
`rfind()`	从后向前查找子串
`find_first_of()`	查找字符集中任意字符首次出现的位置
`find_last_of()`	查找字符集中任意字符最后一次出现的位置
`compare(str)`	比较字符串（返回0表相等，<0表小于，>0表大于）
`stoi()`, `stod()`,`stol()`（C++11）	字符串转数值类型
`to_string(val)`（C++11）	数值转字符串（全局函数，非成员函数）

字符串

字符是计算机中最基本的信息单位之一，通常以 ASCII码的形式存储和表示

ASCII 码是一种将字符映射到数字的标准编码方式，它使用7位二进制数（0-127）来表示128个字符

十进制	字符	描述
0	\0	空字符(Null)
9	\t	水平制表(HT)
10	\n	换行(LF)
48~57	`0`~`9`	数字字符 `0` 到字符 `9`
65~90	`A`~`Z`	大写字母 `A` 到字符 `Z`
97~122	`a`~`z`	小写字母 `a` 到字符 `z`
126	~	波浪号
127		删除(DEL)

判断大小写字母函数：isupper()/islower()

转化为大小写字母函数：toupper()/tolower()

碰到移位不要直接减/加位移数：

1 2	c = 'a' + (c - 'a' + n) % 26; // 右移n位 c = 'z' - ('z' - c + n) % 26; // 左移n位

链表

虽然说STL中有list容器，但是还是需要学会手搓链表

链表的核心特征是，数据分散存储在动态生成的结点中，每个结点的先后顺序通过指针来维护

单向链表：

包含两个域，一个信息域和一个指针域

第一个部分保存关于节点的信息，第二个部分存储下一个节点的地址，单向链表只可向一个方向遍历

双向链表：

双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针

不支持随机访问，访问任意位置的元素都需要从头结点开始遍历，更适合那些主要以顺序访问为主的场景

链表在存储上是非连续的，不需要预先分配固定大小的内存空间，结点可以按需动态生成

插入或删除结点只需要调整相邻结点的指针，时间复杂度为O(1)

单向链表

节点结构定义

// 定义链表节点的结构体
struct Node {
    int val;        // 数据域：存储节点的值
    Node *next; // 指针域：指向下一个节点的指针
    
    // 构造函数1：默认构造，创建值为0的节点，指针指向nullptr
    Node() : val(0), next(nullptr) {}
    // 构造函数2：创建值为x的节点，指针指向nullptr
    Node(int x) : val(x), next(nullptr) {}
    // 构造函数3：创建值为x的节点，并指定下一个节点
    Node(int x, Node *next) : val(x), next(next) {}
};

单向链表类框架

class LinkedList {
private:
    Node* head; // 头指针
    
public:
    // 构造函数
    LinkedList() : head(nullptr) {}
    
    // 析构函数（重要！）
    ~LinkedList() {
        clear(); // 释放所有节点内存
    }
    
    // 插入操作
    void insertFront(int value);  // 头插法
    void insertEnd(int value);    // 尾插法
    void insertAfter(Node* prevNode, int value); // 指定位置后插入
    
    // 删除操作
    void deleteNode(int value);
    
    // 遍历打印
    void printList();
    
    // 查找操作
    Node* search(int value);
    
    // 清空链表
    void clear();
};

头插法（插入到链表开头）:

void LinkedList::insertFront(int value) {
	// 1. 创建新节点
    Node* newNode = new Node(value);
    
    // 2. 新节点指向原头节点
    newNode->next = head;
    
    // 3. 头指针指向新节点
    head = newNode;
}

尾插法（插入到链表结尾）：

void LinkedList::insertEnd(int value) {
    Node* newNode = new Node(value);
    
    // 情况1: 空链表
    if (!head) {
        head = newNode;  // 直接将新节点设为头节点
        return;
    }
    
    // 情况2: 非空链表，找到尾节点
    Node* cur = head;
    while (!cur->next) {
        cur = cur->next;
    }
    // 当前节点是尾节点，链接新节点
    cur->next = newNode;
}

指定位置后插入：

void LinkedList::insertAfter(Node* pre, int value) {
    if (!pre) {
        cout << "前一个节点不能为空" << endl;
        return;
    }
    
    Node* newNode = new Node(value);
    newNode->next = pre->next;
    pre->next = newNode;
}

链表的遍历：

void LinkedList::printList() {
    Node* cur = head;
    while (!cur) {
        std::cout << cur->val << " -> ";
        cur = cur->next;
    }
    cout << "nullptr" << endl;
}

删除节点：（多删除）

void LinkedList::deleteNode(int value) {
	// 处理头结点连续删除的情况
    while(head && head->val == value){
        Node* temp = head;
        head = head->next;
        delete temp;
    }
    // 处理空链表情况
    if(!head) return;
    Node* pre = head;
    Node* cur - head->next;
    while(!cur){
        if(cur->val == value){
            pre->next = cur->next;
            Node* temp = cur;
            cur = cur->next;
            delete temp;
        }else{
            pre = cur;
            cur = cur->next;
        }
    }   
}

删除节点：（单删除）

void LinkedList::deleteNode(int value){
	if(!head) return;
	if(head && head->val == val){
        Node* temp = head;
        head = head->next;
        delete temp;
        return;}
    Node* pre = head;
    Node* cur = head->next;
    while(!cur){
        if(cur->val == val){
            pre->next = cur->next;
        	delete cur;
        	return;}
        pre = cur;
        cur = cur->next;
    }
}

清空链表（析构函数使用）：

void LinkedList::clear() {
    Node* current = head;
    while (current != nullptr) {
        Node* next = current->next; // 保存下一个节点
        delete current;           // 删除当前节点
        current = next;           // 移动到下一个节点
    }
    head = nullptr; // 头指针置空
}

双向链表

双向链表每个节点包含两个指针，分别指向前后节点：

struct DNode {
    int data;
    DNode* prev; // 指向前一个节点
    DNode* next; // 指向后一个节点
    
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
private:
    DNode* head;
    DNode* tail; // 添加尾指针提高效率
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    
    ~DoublyLinkedList() {
        clear();
    }
    
    // 插入操作（尾插法示例）
    void insertEnd(int value) {
        DNode* newNode = new DNode(value);
        
        if (tail == nullptr) { // 空链表
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }
    
    // 清空链表
    void clear() {
        DNode* current = head;
        while (current != nullptr) {
            DNode* next = current->next;
            delete current;
            current = next;
        }
        head = tail = nullptr;
    }
};

链表两两交换

class Solution {
public:
    // 两两交换链表中的相邻节点
    // 参数：head - 链表的头节点
    // 返回值：交换后的链表的头节点
    ListNode* swapPairs(ListNode* head) {
        // 处理边界情况：如果链表为空或只有一个节点，直接返回
        if (!head || !head->next) return head;
        
        // 由于要交换第一组节点，新的头节点将是原始链表的第二个节点
        ListNode* result = head->next;
        
        // 初始化四个指针，用于完成节点交换
        ListNode* pre = nullptr;    // 指向待交换的两个节点的前一个节点
        ListNode* p1 = head;        // 指向待交换的第一个节点
        ListNode* p2 = head->next;  // 指向待交换的第二个节点
        ListNode* nxt = p2->next;   // 指向下一组待交换节点的第一个节点
        
        while (true) {
            // 如果不是第一组节点，需要将前一个节点与当前组的第二个节点相连
            if (pre) pre->next = p2;
            
            // 完成一组节点的交换
            p1->next = nxt;     // 第一个节点指向下一组的第一个节点
            p2->next = p1;      // 第二个节点指向第一个节点
            
            // 如果没有更多节点需要交换，退出循环
            if (!nxt || !nxt->next) break;
            
            // 更新四个指针，准备交换下一组节点
            pre = p1;           // 更新前驱节点
            p1 = nxt;           // 更新第一个待交换节点
            p2 = nxt->next;     // 更新第二个待交换节点
            nxt = p2->next;     // 更新下一组的第一个节点
        }
        
        // 返回新的头节点
        return result;
    }
};

模板

主要为STL服务

模板的核心：编写与数据类型无关的通用代码，让编译器根据使用方式自动生成针对特定类型的代码

模板不可以直接使用，它只是一个框架

模板特化

采用< 具体 >表示

类模板可以部分特化与显式完全特化（所有参数都指定具体的类型，模板参数列表为空）

函数模板不能部分特化（只能重载或显式完全特化，但后者很少用）

函数模板

使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型

T是一个通用的数据类型，通常用大写字母表示

模板举例：

template<typename T>
T add(const T& a, const T& b) {
    return a + b;
}

template → 声明创建模板
typename → 表面其后面的符号是一种数据类型，可以用class代替

使用函数模板有两种方式：自动类型推导、显式指定类型

1 2	cout << add<int>(1, 2) << "\n"; // 显式指定 cout << add(1.5, 2.5) << "\n"; // 自动类型推导

普通函数与函数模板区别：

普通函数调用时可以发生自动类型转换（隐式类型转换）
函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
如果利用显示指定类型的方式，可以发生隐式类型转换

如果函数复杂尽量显式指定类型

普通函数与函数模板的调用规则：

如果函数模板和普通函数都可以调用，优先调用普通函数(所以尽量不要写同名)
可以通过空模板参数列表强制调用函数模板 func<>()
函数模板可以发生函数重载
如果函数模板可以产生更好的匹配，优先调用函数模板

类模板

简单栈模板：

template<typename T>
class SimpleStack {
    vector<T> data;
public:
    void push(const T& v) { data.push_back(v); }
    T pop() { T v = data.back(); data.pop_back(); return v; }
};

类模板允许定义通用的类，例如 STL 中的 vector, list, map 等都是类模板

使用类模板时，必须显式指定模板参数，因为编译器无法像函数模板那样通过参数推导类型

当类模板碰到继承时，需要注意一下几点：

当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型

如果不指定，编译器无法给子类分配内存

template<class T>
class Base {
    T data;
};
class Son : public Base<int>{
};

如果想灵活指定出父类中T的类型，子类也需变为类模板

template<class T>
class Base {
    T data;
};
template<class T1,class T2>
class Son : public Base<T2>{
    T1 obj;
};
int main() {
    Son<int,char> s1{};
}

构造函数的类外实现：

template<class T1,class T2>
class Person {
public:
    Person(T1 name,T2 age);
    T1 name;
    T2 age;
    void display();
};
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) { // Person 要加<T1,T2>
    this->name = name;
    this->age = age;
}

成员函数的类外实现：

template<class T1, class T2>
void Person<T1, T2>::display() {  // Person 要加<T1,T2>
    cout << this->name << " " << this->age << endl;
}

全局函数的实现：

#include <iostream>
using namespace std;
template<class T1, class T2>
class Person {
    // 全局函数类内实现
    // friend void display(Person<T1,T2> p) {
    //     cout << p.name << endl;
    //     cout << p.age;
    // }
    // 全局函数类外实现,需要加空模板参数列表
    friend void display<>(Person<T1,T2> p);
public:
    Person(T1 name,T2 age);
    T1 name;
    T2 age;
};
// 全局函数类外实现
template<class T1, class T2>
void display(Person<T1,T2> p) {
    cout << p.name << endl;
    cout << p.age;
}

如果不加<>会被编译器解释为声明一个普通函数的友元，使用<>明确告诉编译器这是针对模板实例的友元声明

STL

标准模板库（Standard Template Library，STL）

STL几乎所有代码都采用了模板

STL 分为多个组件，包括容器、算法、迭代器、函数对象和适配器等

容器和算法通过迭代器无缝连接

组件	描述
容器(Containers)	各种数据结构，包括向量(vector)、链表(list)、队列(queue)、栈(stack)、集合(set)、映射(map)等，用于存放数据
算法(Algorithms)	各种常见算法，如sort, find, copy, move, for_each等
迭代器(iterators)	用于遍历容器中的元素，允许以统一的方式访问容器中的元素

STL中一级容器是指, 容器元素本身是基本类型, 非组合类型

容器分为序列式容器和关联式容器两种：

序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置
关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系

举例，一个数组13542，序列式容器内就是13542，在关联式容器内是12345

容器的构造函数：

构造函数：(以vector为例)

vector<T> v; 采用模板，默认构造函数
vector(v.begin(), v.end()); 将[begin,end)区间中的元素拷贝给本身
vector(const vector &vec); 拷贝构造函数

算法分为：质变算法和非质变算法

质变算法：运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

序列式容器

vector

vector 是一种序列容器，用于存储动态大小的数组，允许用户在容器的末尾快速地添加或删除元素

vector与普通数组区别：

数组是静态空间，而vector可以动态扩展
动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

常用操作：

函数	功能	时间复杂度
`push_back()`	尾部插入元素	均摊 O(1)
`pop_back()`	删除尾部元素	O(1)
`insert()`	指定位置插入	O(n)
`erase()`	删除指定位置	O(n)
`operator[]`	随机访问元素	O(1)
`at()`	带边界检查的访问	O(1)
`size()`	返回元素数量	O(1)
`clear()`	清空容器	O(n)

之后出现的push都可以用emplace; emplace直接在内存上构造对象，省去移动的过程

拓展操作：

函数	说明
`front()`	返回容器中第一个元素
`back()`	返回容器中最后一个元素
`swap(vec)`	互换两个容器
`resize(num, (elem))`	size变为num，变多填充默认/(elem)值变小则超出部分删除，容量不变
`capacity()`	返回容器容量(vevtor特有)
`reserve(num)`	预留容量空间(vector特有)，避免频繁分配内存

vector容器capacity比size大(自适应)，但在resize后capacity不变，为了节省内存，c++11之前可以自交换，c++11以上建议使用shrink_to_fit()

起始迭代器，指向容器中第一个元素

1 2	vector<T> v; vector<T>::iterator itBegin = v.begin();

结束迭代器，指向容器中最后一个元素的下一个位置

1	vector<T>::iterator itEnd = v.end();

遍历方式：

// 第一种遍历
for (vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
    cout << *it << endl;
}
// 第二种遍历
for_each(v.begin(), v.end(), [](T i){cout << i << endl;});

在写的过程中vector<T>::iterator可以auto

deque

双端数组：允许在两端进行高效的插入和删除操作，适用于需要频繁插入和删除元素的场景

deque与vector区别:

deque对头部的插入删除速度比vector快
deque支持[]访问但慢于vector

deque的构造和赋值操作和vector基本一样，少了内存管理的函数，因为它的内存结构是分段的

特有的：插入删除增加头部操作

函数	功能	时间复杂度
`push_front()`	头部插入元素	O(1)
`pop_front()`	删除头部元素	O(1)

stack

堆栈是一种后进先出（LIFO, Last In First Out）的数据结构，默认基于deque

非常适合于需要”最后添加的元素最先被移除”的场景

栈的元素是线性排列的，但只允许在一端(栈顶)进行添加和移除操作，另一端是封闭的(栈底)

只能访问栈顶元素，因此栈不允许有遍历的行为

常用操作：

函数	功能	时间复杂度
`push()`	在栈顶添加一个元素(入栈)	O(1)
`pop()`	移除栈顶元素(出栈)	O(1)
`top()`	查看栈顶元素	O(1)
`size()`	返回元素数量	O(1)
`empty()`	检查栈是否为空	O(1)

栈没有clear()方法，清空栈需要循环出栈

queue

队列是一种先进先出（First In First Out，FIFO）的数据结构

它遵循以下规则：

元素只能从队尾添加
元素只能从队首移除

类比：在超市收银台前排队结账，这就是一个典型的队列，先来的人先结账（先进先出）

只有队头和队尾可以访问，因此不允许有遍历行为

常用操作：

函数	功能	时间复杂度
`push()`	元素入队尾	O(1)
`pop()`	队头元素出队	O(1)
`front()`	访问队头元素	O(1)
`back()`	访问队尾元素	O(1)
`size()`	返回元素数量	O(1)
`empty()`	检查队列是否为空	O(1)

队列没有clear()方法，清空队列需要循环出队

priority_queue

底层容器默认 vector，也可用 deque（需支持随机访问迭代器）

顶部元素始终为优先级最高者（默认最大元素），但整体无序，设计上只允许访问顶部元素

和stack以及queue相同，不支持遍历

函数	操作	时间复杂度
`push()`	插入元素	O(log n)
`pop()`	删除顶部元素	O(log n)
`top()`	访问顶部元素	O(1)
`size()`	大小检查	O(1)
`empty()`	判空检查	O(1)

优先选择场景：

只需访问当前最高优先级元素
数据动态插入且需高效维护优先级

list

list 是一种序列容器，允许在容器的任意位置快速插入和删除元素，双向链表

由于链表的存储方式并不是连续的内存空间，迭代器只支持前移和后移，属于双向迭代器(支持++与–，不支持+n)

常用操作：

函数	功能	时间复杂度
`front()`	返回链表第一个元素	O(1)
`back()`	返回链表最后一个元素	O(1)
`push_front()`	头部插入元素	O(1)
`push_back()`	尾部插入元素	O(1)
`insert()`	指定位置插入	O(1)
`pop_back()`	删除尾部元素	O(1)
`pop_front()`	删除头部元素	O(1)
`erase()`	删除指定位置	O(1)
`remove()`	删除所有等于指定值的元素	O(n)
`unique()`	删除连续重复元素	O(n)
`size()`	返回元素数量	O(1)
sort()	排序链表	O(n log n)
merge(list)	合并另一个链表(置于链头) 两个链表必须按相同规则排序（默认小→大）	O(m+n)
splice(it,list)	移动另一个链表到此链表的指定位置
reverse()	反转链表	O(n)

对list来说，merge和sort需要使用自己的成员函数

splice() 仅修改节点的指针（next/prev），不复制或移动节点数据，使得被移动节点的迭代器/引用保持有效

操作代价极低，性能远超”复制数据+删除原节点”的方式

关联式容器

set

set是一种关联容器，它存储了一组唯一的元素，所有元素在插入时自动被排序(默认小→大)，底层结构是用二叉树实现(如果不需要排序，可以用unordered_set)

set容器中存储的元素类型必须满足以下条件：

元素类型必须可以比较大小，默认使用严格弱序的比较规则（即 std::less<T>），这等价于 operator<

对于自定义类型的数据需要重载<，如果需要(大→小)需要增加谓词
1
set<int, greater<int>> mySet;
元素类型必须可以被复制和赋值

常用操作：

函数	功能	时间复杂度
`insert()`	插入元素	O(log n)
`erase()`	删除元素	O(log n)
`find()`	查找元素	O(log n)
`count()`	统计元素出现次数（0/1）	O(log n)
`lower_bound()`	返回首个≥key的迭代器	O(log n)
`upper_bound()`	返回首个>key的迭代器	O(log n)
`size()`	返回元素数量	O(1)

在set中元素不允许重复插入，但multiset允许重复插入

注意：在multiset中需要erase(find(x))实现只删除一个元素（如果直接 erase(x)，会删除所有 x）

map

map是一种关联容器，所有元素都是键值对(pair)

在创建pair对象时，必须提供两个类型名，两个类型不必相同

pair中第一个元素为key(键值)起到索引作用，第二个元素为value(实值)

(默认键值小→大) (如果不需要排序，可以用unordered_map)

map的指针指向first和second分别对应pair的两个值

1	pair<T1, T2> p = make_pair(T1 val, T2 val);

函数	功能	时间复杂度
`insert()`	插入键值对	O(log n)
`erase()`	删除键值对	O(log n)
`find()`	查找键	O(log n)
`operator[]`	访问/添加键对应的值	O(log n)
`count()`	检查键是否存在	O(log n)
`lower_bound()`	返回首个键≥key的迭代器	O(log n)
`size()`	返回键值对数量	O(1)

map不允许容器有重复的key值，multimap允许

容器对比

容器	底层结构	元素唯一性	随机访问	插入/删除效率
vector	动态数组	允许重复	✔️	尾部高效，中间/头部低效
deque	分块数组	允许重复	✔️	头尾高效，中间低效
list	双向链表	允许重复	❌	任意位置高效
stack	适配器（默认deque）	允许重复	❌	仅栈顶操作（高效）
queue	适配器（默认deque）	允许重复	❌	仅队头/队尾操作（高效）
set	红黑树	唯一	❌	高效（O(log n)）
map	红黑树	键唯一	❌	高效（O(log n)）

随机访问支持（O(1)）：vector、deque：通过下标[]或at()直接访问

不同情况效率：

头尾操作高效：deque（O(1)）、list（O(1)）、stack/queue（适配器，O(1)）
中间操作高效：list（O(1)）
排序容器高效：set/map（O(log n)）

一般在algorithm中的算法，关联式容器自带有

sort和find函数支持：

容器	`sort()` 成员函数	`find()` 成员函数	是否支持 `std::sort`	是否支持 `std::find`
vector	❌	❌	✔️ (需随机访问)O(nlog n)	✔️ (线性查找)O(n)
deque	❌	❌	✔️ (需随机访问)O(nlog n)	✔️ (线性查找)O(n)
stack	❌	❌	❌ (无迭代器)	❌ (无迭代器)
queue	❌	❌	❌ (无迭代器)	❌ (无迭代器)
list	✔️ O(nlog n)	❌	❌ (需随机访问)	✔️ (线性查找)O(n)
set	❌ (始终有序)	✔️ O(log n)	❌ (不可修改顺序)	✔️ (成员函数更优)
map	❌ (始终按键有序)	✔️ 按键查找 O(log n)	❌ (不可修改顺序)	❌ 不适用

std::sort 要求随机访问迭代器

stack 和 queue（容器适配器）不提供迭代器，无法直接排序或查找

解决方案：转存到 vector/deque 操作后重新构造适配器

序列容器需要采用sort排序()，关联容器无需排序
序列容器采用std::find线性查找，关联容器采用成员函数find，复杂度更低

遍历通用原则：

迭代器模式：所有支持遍历的容器都提供begin()和end()迭代器
关联容器（set/map）：遍历顺序按键升序排列

容器	是否可遍历	支持索引访问	迭代器类型	顺序
`vector`	✅	✅	随机访问迭代器	插入顺序
`deque`	✅	✅	随机访问迭代器	插入顺序
`list`	✅	❌	双向迭代器	插入顺序
`set`	✅	❌	双向迭代器	键升序（可自定义）
`map`	✅	❌	双向迭代器	键升序（可自定义）
`stack`	❌	❌	—	—
`queue`	❌	❌	—	—

常用场景对比：

容器	优先选择	避免
`vector`	随机访问频繁尾部操作为主数据规模变化不大内存连续性要求高	频繁在头部/中部插入删除
`deque`	高频头尾操作中等规模数据随机访问滑动窗口算法(如LeetCode滑动窗口最大值) 替代`vector`防扩容失效	超大规模数据随机访问
`list`	任意位置高频插入删除避免vector/deque移动开销插入删除不失效特殊操作(sort,merge,splice)	随机访问或内存紧凑性要求高
`stack`	函数调用栈、括号匹配 DFS算法：递归转非递归实现表达式求值：中缀转后缀	需遍历或随机访问元素
`queue`	BFS算法、消息缓冲生产者-消费者模型：任务队列按到达顺序处理：如网络请求排队	需遍历或中间访问元素
`priority_queue`	动态优先级管理：实时系统任务调度 Top-K问题：海量数据中找最大/小的K个值贪心算法：Dijkstra/Huffman编码只需访问最高优先级元素	需遍历或修改非顶部元素
`set`	元素唯一且需自动排序存在性检查频繁find()(O(log n)) 范围查询：`lower_bound()`/`upper_bound()` 需要有序遍历	仅需插入删除不关心顺序
`map`	键值对存储且按键排序：字典/配置文件键查找频繁：`find()` (O(log n)) 键范围查询：如时间区间检索需要有序键遍历	仅需哈希式快速查找（用`unordered_map`）

unordered_set/unordered_map在不需要顺序时始终优于set/map

graph TD
    A[需求分析] --> B{需键值对?}
    B -->|Yes| C{需按键排序?}
    C -->|Yes| D[map]
    C -->|No| E[unordered_map]
    B -->|No| F{需快速查找?}
    F -->|Yes| G{元素唯一?}
    G -->|Yes| H[set]
    G -->|No| I[unordered_set]
    F -->|No| J{访问模式?}
    J -->|LIFO| K[stack]
    J -->|FIFO| L[queue]
    J -->|优先级驱动| M[priority_queue]
    J -->|其他| N{操作位置}
    N -->|尾部为主| O[vector]
    N -->|头尾兼顾| P[deque]
    N -->|任意位置| Q[list]

内建函数对象

函数对象是那些重载了 operator() 的对象，它们可以像普通函数一样被调用

<functional> 头文件提供了一些函数对象

主要分为算术仿函数、关系仿函数、逻辑仿函数

最常用：透明比较器std::less<>、std::greater<>（排序和容器比较）

现代替代：Lambda表达式简化临时操作（如std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; })）

常用算法

算法主要由由头文件<algorithm>, <functional>, <numeric>组成

algorithm是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等
numeric体积很小，只包括几个在序列上面进行简单数学运算的模板函数
functional定义了一些模板类用以声明函数对象

begin和end都是iterator类型，以下不赘述

遍历算法

for_each 遍历容器

1	std::for_each(vec.begin(), vec.end(), [](T i){cout << i << endl;}); // 遍历显示

查找算法

如果是自定义类，需要重载==

find() 在容器中查找与给定值匹配的第一个元素
find_if() 根据bool型仿函数(谓词)的条件返回第一个满足的迭代器位置
1
auto it = find_if(vec.begin(), vec.end(), _Pred())
adjacent_find() 在容器中寻找相邻重复元素，返回前一个的迭代器位置
1
auto it = adjacent_find(vec.begin(), vec.end());
binary_search() 查找指定的元素，查到返回true否则false
1
bool binary_search(vec.begin(), vec.end(), value);
要求序列有序，在无序序列中不可用，使用前先sort

count() 查找元素个数

1	int n = count(vec.begin(), vec.end(), value);

count_if() 查找满足bool型仿函数的条件的元素个数
1
int n = count_if(vec.begin(), vec.end(), _Pred());

排序算法

如果是自定义类的排序，需要重载<

sort() 对容器内的元素进行排序，谓词非必须，默认小→大
1
sort(vec.begin(), vec.end()(, _Pred()));
对于支持随机访问的迭代器的容器(vector,deque)，可以用sort算法直接进行排序
shuffle() 对指定范围内的元素随机调整次序
1
shuffle(vec.begin(), vec.end(), random_device());
nth_element() 序列中找出第 n 小的元素（nth元素），并将其放置在正确的位置上，部分排序
1
2
auto mid = vec.begin() + vec.size()/2; // 快速按照中位数划分
nth_element(vec.begin(), mid, vec.end());

修改序列算法

copy() 将容器内指定范围的元素拷贝到另一容器中
1
copy(vec.begin(), vec.end(), dest.begin());
fill() 向容器中填充指定元素
1
fill(vec.begin(), vec.end(), val)

transform() 对指定范围内元素做操作，存入新容器

1	transform(vec.begin(), vec.end(), dest.begin(), [](int x) {return x * 2;});

replace() 将容器内指定范围的元素修改为新元素
1
replace(vec.begin(), vec.end(), oldvalue, newvalue);
replace_if 将区间内满足条件的元素，替换成指定元素
1
replace_if(vec.begin(), vec.end(), _Pred(), newvalue);
swap 互换两个同种类型的容器
1
swap(container c1, container c2);
merge 将两个容器的元素合并存储到另一个容器，注意，两个容器必须有序(同升/同降)
1
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), dest.begin());
reverse 对容器内元素进行反转，颠倒其顺序
1
reverse(vec.begin(), vec.end());

删除和去重算法

remove() 移除所有的特定值

1 2	auto new_end = remove(vec.begin(), vec.end(), value); vec.erease(new_end, vec.end());

unique() 去重相邻重复元素(去重前需要排序)
1
2
auto new_end = unique(vec.begin(), vec.end());
vec.erase(new_end, vec.end());
remove和unique都是把不需要的元素放到尾部，要结合erase()函数去除

算术生成算法

属于小型算法，需要包含<numeric>

accumulate 计算容器内累加和

1	accumulate(iterator beg, iterator end, init_val)

1	accumulate(iterator beg, iterator end, 1, [](int a, int b) { return a * b; }); // 获得累乘

inner_product 计算两个容器中对应元素乘积的总和

1	inner_product(iterator beg1, iterator end1, iterator beg2, iterator end2, init_val)

adjacent_difference 计算容器中相邻元素的差值，并将结果存储在另一个容器中
1
adjacent_difference(iterator beg, iterator end, iterator dest);
partial_sum() 计算前缀和，并将结果存储在另一个容器中
1
partial_sum(iterator beg, iterator end, iterator dest);

集合算法

以下算法都要求容器内元素有序，并且唯一 sort 配合 unique

set_intersection 计算两个容器的交集

1 2	dest.resize(min(container1.size(),container2.size())); // 容量设为较小值 set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, back_inserter(dest));

set_union 计算两个容器的并集

1 2	dest.resize(container1.size() + container2.size()); // 容量设为和 set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, back_inserter(dest));

set_difference 计算两个容器的差集

1 2	dest.resize(max(container1.size(),container2.size())); // 容量设为较大值 set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, back_inserter(dest));

谁在前就是找后一个没有的元素