1.基本知识

1.1变量

1. 定义方法

int a = 10

1.2常量

#define Day 30 // 宏常量
const int a = 20; // 常量

1.3数据类型

1.3.1整型

数据类型	占用空间(bit)
short	2
int	4
long	4/8(linux)
long long	8

注：使用sizeof()函数可以判断数据类型

1.3.2浮点数

• float

• double

区别：float类型数字后缀必须以f结尾，如果两者相互赋值会发生隐式类型转化

1.3.3字符型

char c = "a";
cout << (int)ch << endl; // 可以得到对应的ascii编码

常见转义字符：

转义字符	含义	ASCII码（十进制）
\\	反斜杠	92
\'	单引号	39
\"	双引号	34
\?	问号（用于避免 ?? 被解释）	63
\a	响铃（警告声）	7
\b	退格	8
\f	换页	12
\n	换行	10
\r	回车	13
\t	水平制表符（Tab）	9
\v	垂直制表符	11
\ooo	八进制表示的字符（ooo为1~3位）	0~255（视值而定）
\xhh	十六进制表示的字符（hh为1~2位或更多）	0~255+（视值而定）

1.3.4字符串型

char c[] = "abc"; 
string s = "abc";

项目	char c[] = "abc";	std::string s = "abc";
类型	C 风格字符串（字符数组）	C++ 的 std::string 类
存储内容	{'a', 'b', 'c', '\0'}（含空字符）	内部存储字符序列，不必手动加 \0
长度	必须通过 strlen(c) 计算	通过 s.size() 或 s.length() 获取
可变性	可修改单个字符，如 c[0] = 'x';	支持修改、追加、删除等操作
运算支持	无法直接使用 +, .append() 等	支持 +, .append(), .substr() 等
内存管理	静态或自动分配，手动管理（危险）	自动管理内存，支持动态扩展
安全性	容易越界、无越界检查	较安全，有越界检查
标准库支持	少，主要是 C 标准库函数	丰富，完整的字符串操作方法

1.3.5bool类型

bool flag = true; // 存储为0 和 1

布尔值	实际存储的整数值
false	0
true	1

1.4常见运算符

类别	运算符	名称/作用	示例	说明
算术运算	+ - * / %	加 减 乘 除 取余	a + b	用于数值计算
赋值运算	= += -= *= /= %=	赋值与复合赋值	a += 5	相当于 a = a + 5
递增递减	++ --	自增 自减（前/后缀）	a++, --b	整数或迭代器增加/减少
比较运算	== != < > <= >=	等于 不等于 大小比较	a != b, a < b	结果为布尔值（true/false）
逻辑运算	&&		!	与 或 非
位运算	&	^` `~` `<<` `>>`	与 或 异或 取反 左移 右移	a & b, a << 1
条件运算	?:	三目运算符	a > b ? a : b	根据条件选择值
指针运算	* &	解引用 取地址	*ptr, &var	* 获取值，& 获取地址
成员运算	. -> ::	成员访问，作用域解析	obj.x, p->x	:: 用于命名空间或类作用域
类型运算	sizeof typeid static_cast 等	类型信息与转换	sizeof(int)	用于类型相关操作
其他	, [] ()	逗号运算、数组访问、函数调用	a[i], f(x)	常用于表达式和控制结构

1.5选择结构

结构类型	语法格式	示例代码	说明
if 语句	if (条件) { 语句 }	if (a > b) { cout << "a大"; }	条件为真时执行语句块
if-else	if (条件) { 语句1 } else { 语句2 }	if (a > b) { ... } else { ... }	条件为真执行语句1，否则执行语句2
if-else if	if (...) {...} else if (...) {...} else {...}	if (x==1) {...} else if (x==2) {...} else {...}	多个分支的条件判断
三目运算符 ?:	条件 ? 表达式1 : 表达式2	int max = (a > b) ? a : b;	条件为真返回表达式1，否则返回表达式2
switch 语句	switch (变量) { case 值: ... break; default: ... }	switch (x) { case 1: ...; break; default: ...; }	用于对整型/枚举变量进行多分支判断（不能判断字符串等）

1.6循环结构

结构类型	语法格式	示例代码	说明及适用场景
while 循环	while (条件) { 循环体 }	while (i < 10) { cout << i++; }	先判断条件，条件为真执行；可能一次不执行
do-while 循环	do { 循环体 } while (条件);	do { cout << i++; } while (i < 10);	先执行一次再判断；至少执行一次
for 循环	for (初始化; 条件; 更新) { 循环体 }	for (int i = 0; i < 10; i++) { cout << i; }	最常用，结构清晰，适合已知循环次数
范围 for 循环	for (类型 变量 : 容器) { 循环体 }	for (int x : vec) { cout << x; }	C++11 起支持，适合遍历 STL 容器（如 vector、array 等）
无限循环	while (true) / for (;;)	while (true) { ... } 或 for (;;) { ... }	通常与 break 配合实现 手动退出条件

1.7数组

类别	说明	示例代码 / 补充说明
定义数组	固定长度，类型一致	int arr[5];
初始化数组	可指定部分或全部元素	int arr[5] = {1, 2}; // 剩余元素为 0
推导长度	用初始化内容自动推导数组长度	int arr[] = {1, 2, 3}; // 长度为 3
多维数组	支持二维及以上数组	int arr[2][3] = {{1,2,3}, {4,5,6}};
访问元素（下标）	使用下标访问	arr[0] = 10;
访问元素（指针）	通过指针偏移访问元素	*(arr + 1) = 20; 等价于 arr[1] = 20;
指针遍历	可通过指针遍历数组	for (int* p = arr; p < arr + 5; ++p) cout << *p;
数组名与指针	数组名是首元素地址（指针常量）	int* p = arr; 等价于 p = &arr[0];
sizeof 数组	返回整个数组占用字节数（指针除外）	sizeof(arr) 是元素总大小；sizeof(p) 是指针大小
传递到函数	实际上传递的是指针（数组退化）	void func(int arr[]) 等价于 void func(int* arr)
字符数组	可用于存储字符串，需考虑结尾的 \0	char str[6] = "hello";
std::array	C++11 的固定长度数组容器	std::array<int, 5> arr = {1,2,3,4,5}; 需 <array> 头文件
std::vector	动态数组容器，长度可变	std::vector<int> v = {1,2,3}; 需 <vector> 头文件
C数组 vs STL容器	STL容器更安全，支持更多操作	推荐使用 std::vector 或 std::array 替代原始数组

1.8函数

类别	说明	示例代码 / 补充说明
函数定义与声明	声明在头部，定义包含实现代码	int add(int a, int b); int add(int a, int b) { return a + b; }
返回类型	可为基本类型、自定义类型、引用、指针等	void 表示无返回值；也可以返回 int, double, string 等
参数传值	将实参复制一份传入	void foo(int x) { x = 5; } // 实参不会变
参数引用传递	使用引用修改调用者变量	void foo(int &x) { x = 5; } // 实参会被改变
参数指针传递	使用指针传入变量地址	void foo(int* x) { *x = 5; }
默认参数	可以给参数设置默认值（必须从右往左）	void greet(string name = "Guest");
函数重载	函数名相同，参数类型/个数不同	int max(int a, int b); double max(double a, double b);
内联函数 (inline)	编译期展开，避免函数调用开销	inline int square(int x) { return x * x; }
函数指针	可传函数名作为参数	int (*fp)(int, int) = add;
lambda 表达式	匿名函数，用于回调/函数式编程等	auto f = [](int x) { return x + 1; };
函数模板（泛型函数）	使用模板支持不同类型的调用	template<typename T> T add(T a, T b) { return a + b; }
可变参数模板（C++11）	可处理任意多个参数	template<typename... Args> void log(Args... args);
函数返回引用	返回变量引用时，需确保变量生命周期	int& getRef(int& x) { return x; }
main 函数	程序入口，返回类型为 int	int main() { return 0; } 可接收参数：int main(int argc, char* argv[])
递归函数	函数调用自身	int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
命名空间函数调用	函数在 namespace 中定义时调用方式不同	namespace ns { void f(); } 调用：ns::f();
静态函数（文件作用域）	static 限定函数只在当前文件可见	static void helper() {}
constexpr 函数（编译期）	在编译期求值的函数（C++11 起）	constexpr int square(int x) { return x * x; }

1.9指针

类别	说明	示例代码 / 补充说明
指针定义	存储变量地址的变量	int* p; 表示指向 int 的指针
取地址符 &	获取变量地址	int a = 10; int* p = &a;
解引用符 *	访问指针所指向的值	*p = 20; 将地址所指变量改为 20
空指针 nullptr	指针初始化为不指向任何地址（C++11）	int* p = nullptr;
指针与数组	数组名是首元素地址；支持指针偏移访问	*(arr + 1) 等价于 arr[1]
指针运算	支持 +, -, ++, -- 等操作	p++ 指向下一个元素
指针与函数	可以定义指向函数的指针	int (*fptr)(int, int) = add;
指针作为函数参数	支持修改传入的变量内容	void foo(int* p) { *p = 5; }
多级指针	指向指针的指针	int** pp;
const 与指针	限定指针或所指数据不可修改	const int* p; / int* const p;
指针与引用区别	指针可为 null，可改变指向；引用必须绑定初始对象且不可更换	int& r = a; int* p = &a;
函数返回指针	返回局部变量指针会导致未定义行为	应返回动态分配的地址或传入参数的地址
指针与动态内存	使用 new / delete 管理堆内存	int* p = new int(10); delete p;
指针数组	每个元素是指针	int* arr[3]; 表示有3个指向 int 的指针
数组指针	指向整个数组	int (*p)[5]; 表示指向 int[5] 的指针
函数指针数组	每个元素是函数指针	void (*funcs[2])();
智能指针（C++11）	自动管理资源，避免手动释放	std::unique_ptr<int>、std::shared_ptr<int> 需要 <memory> 头文件

注意：

int& func() {
    int x = 42;
    return x; // ❌ 错误：x 是局部变量，函数返回后 x 的地址就无效了
}

1.10结构体

类别	说明	示例代码 / 补充说明
定义结构体	聚合多个不同类型的变量	struct Person { string name; int age; };
创建结构体变量	定义后可直接创建变量	Person p;
初始化结构体	支持聚合初始化（C++11 起支持花括号初始化）	Person p = {"Tom", 20};
访问成员	使用点运算符访问成员	p.name = "Tom"; cout << p.age;
结构体指针访问成员	使用箭头运算符 ->	Person* ptr = &p; ptr->age = 21;
嵌套结构体	结构体中可以包含其他结构体	struct Student { Person info; int score; };
结构体数组	支持结构体类型数组	Person people[3];
结构体作为函数参数	可按值、引用、指针传递	void print(Person p); / void print(const Person& p);
匿名结构体（不常用）	结构体中嵌套无需命名的子结构体	struct { int x; int y; } point;
成员函数（类似类）	C++ 支持结构体中定义函数（与类一致）	void greet() { cout << name; }
构造函数/析构函数	可定义构造函数、析构函数（C++ struct 默认是 public）	Person(string n, int a) { name = n; age = a; }
结构体与类的区别	默认成员访问权限不同（struct 默认 public，class 默认 private）	实际语法几乎一致
默认初始化	没有显式构造函数时支持 {} 初始化	Person p{}; 所有成员初始化为 0 或空字符串
位域（Bit Fields）	可精细控制成员所占位数	struct Flags { unsigned int a:1; unsigned int b:2; };
与 typedef 结合使用	C 风格中常用 typedef 简化结构体名	typedef struct { int x, y; } Point;
与 std::tuple 区别	struct 是命名字段，tuple 是位置访问	struct 更清晰，tuple 更灵活

1.11变量的存储类型

变量类型	举例	存储区域	生命周期	说明
全局变量	int g = 0;	数据段（静态区）	程序启动到结束	无论是否加 static，都存储在静态区
静态局部变量	static int s = 1;	数据段（静态区）	程序启动到结束	即使在函数中定义，也不存栈，多次调用一个函数状态修改的状态会被保持
局部变量	int a = 3;（函数内部）	栈（Stack）	所在代码块执行时	调用函数时分配，退出时销毁
函数参数	void foo(int x)	栈（Stack）	函数调用期间	与局部变量相同
动态分配变量	int* p = new int(5);	堆（Heap）	手动释放（delete）前	new/malloc 分配，需手动 delete/free
常量	const int c = 10;	栈或数据段	视作用域而定	局部常量在栈，全局常量在只读数据段
字符串字面量	"hello"	只读数据段	程序运行期间	字符串字面量是只读的
临时变量	std::string("temp")	栈（通常）	表达式求值期间	编译器可能优化到寄存器

1.12引用

特性	描述
定义方式	int &ref = var;
必须初始化	✅ 是，声明时必须立即绑定一个对象
是否可为 null	❌ 否（引用必须引用一个实际存在的对象）
是否可重新绑定	❌ 不可以，一旦绑定就不能更改引用的对象
实际作用	被绑定对象的别名，操作引用就是操作原对象
内存消耗	无额外内存（通常由编译器优化处理）
访问方式	像普通变量一样直接使用
修改原对象	✅ 可以通过引用修改原对象
常用于	函数参数传递、返回值、简化语法
与指针的比较	更安全、更简洁，但不如指针灵活
常引用（const &）	✅ 用于避免拷贝、只读访问，如 const std::string& s
应用场景示例	void func(int &x) { x = 5; } 调用者变量会被修改

注意：

int& func() {
    int x = 42;
    return x; // ❌ 错误：x 是局部变量，函数返回后 x 的地址就无效了
}

1.13构造函数和析构函数

项目	构造函数（Constructor）	析构函数（Destructor）
定义位置	类的内部	类的内部
函数名称	与类名相同	~类名
是否有返回值	没有（也不能写 void）	没有（也不能写 void）
调用时机	对象创建时自动调用	对象销毁时自动调用
参数	可以有多个参数，可重载	无参数，不能重载
是否可重载	可以（根据参数不同）	不可以
常见类型	默认构造、参数构造、拷贝构造、移动构造	默认析构、虚析构
是否支持继承多态	不涉及虚函数即可	推荐使用 virtual 支持多态删除
构造/析构顺序	先父类构造，再子类构造	先子类析构，再父类析构
常见用法	初始化成员变量、资源分配	释放资源、日志输出
默认生成	如果没有定义，编译器会自动生成	同上
推荐实践	使用初始化列表初始化成员	RAII 设计模式、虚析构用于继承

常见用途：

类型	定义示例	用途说明
默认构造函数	ClassName();	创建对象时使用无参构造，常用于默认初始化成员变量。如：ClassName obj;。如果类中没有定义任何构造函数，编译器会自动生成一个默认构造函数。
参数构造函数	ClassName(int x, string y);	允许在创建对象时传入参数，自定义初始化成员变量。适用于需要在创建时指定初始状态的情况。如：ClassName obj(42, "hello");。
拷贝构造函数	ClassName(const ClassName& other);	用于通过已有对象创建新对象（复制），如对象按值传递、返回或显式复制时。默认执行“浅拷贝”，如需“深拷贝”需自定义实现。示例：ClassName obj2 = obj1;
移动构造函数	ClassName(ClassName&& other);	用于资源所有权的转移（如堆内存、文件句柄等），避免不必要的拷贝，提升性能。常用于右值（临时对象）的初始化，如：ClassName obj2 = std::move(obj1);（C++11 起支持）。
析构函数	~ClassName();	当对象生命周期结束时自动调用，用于释放资源（如内存、文件、网络等）、清理操作。通常不需要手动调用，除非使用 delete 删除动态分配的对象。

示例：拷贝 vs 移动构造函数

#include <iostream>
#include <cstring>

class Buffer {
private:
    int* data;
    size_t size;

public:
    // 默认构造函数
    Buffer(size_t s = 10) : size(s) {
        data = new int[size];
        std::cout << "Constructed Buffer of size " << size << std::endl;
    }

    // 拷贝构造函数（深拷贝）
    Buffer(const Buffer& other) : size(other.size) {
        data = new int[size];
        std::memcpy(data, other.data, size * sizeof(int));
        std::cout << "Copied Buffer\n";
    }

    // 移动构造函数
    Buffer(Buffer&& other) noexcept : data(other.data), size(other.size) {
        other.data = nullptr;  // 转移所有权
        other.size = 0;
        std::cout << "Moved Buffer\n";
    }

    // 析构函数
    ~Buffer() {
        delete[] data;
        std::cout << "Destroyed Buffer\n";
    }
};

// 测试函数：返回临时对象
Buffer createBuffer() {
    Buffer temp(100);
    return temp;  // 触发移动构造（返回右值）
}

int main() {
    std::cout << "--- b1 ---\n";
    Buffer b1 = createBuffer();  // 使用移动构造函数

    std::cout << "--- b2 ---\n";
    Buffer b2(b1);  // 使用拷贝构造函数

    std::cout << "--- end ---\n";
    return 0;
}

总结：如果定义了拷贝构造函数，在返回时就会进行拷贝，在定义了移动构造函数时，就会发生所有权转移

1.14类对象 vs POD 对象：返回时的差异

类型	返回局部变量是否安全	是否需要构造函数支持	是否触发移动优化
int / double	✅ 安全（复制值）	❌ 不需要	⛔ 不适用
自定义类对象	✅ 安全（复制或移动）	✅ 至少要有可用构造函数	✅ 可能触发移动或 RVO
int& / T*	❌ 不安全（指向局部）	❌ 不需要	⛔ 不适用

1.15类初始化成员变量的几种方式

方式	支持 const/ref 成员	性能	推荐使用
初始化列表	✅	高	✅ 推荐
构造函数体赋值	❌	低	❌ 尽量避免
类内默认初始化	✅	高	✅ 辅助使用
委托构造函数	✅	高	✅ 可用于重构
聚合初始化	✅	高	✅ 简洁但局限

1.15.1构造函数初始化列表（推荐）

class MyClass {
    int a;
    double b;
public:
    MyClass(int x, double y) : a(x), b(y) {}
};

• 效率高：变量在创建时直接初始化，避免了先默认构造再赋值。
• 必须使用：对于 const 成员、引用成员、没有默认构造函数的成员，只能用初始化列表。

1.15.2构造函数体内赋值

class MyClass {
    int a;
    double b;
public:
    MyClass(int x, double y) {
        a = x;
        b = y;
    }
};

缺点：

• 成员变量在构造函数调用前会先默认初始化（或者零初始化），然后再赋值，效率较低。
• 无法用于 const 或 reference 成员。

1.15.3类内默认初始化（C++11 起）

class MyClass {
    int a = 10;
    double b{3.14};
public:
    MyClass() = default;
};

或者结合构造函数：

class MyClass {
    int a = 10;
    double b = 3.14;
public:
    MyClass(int x) : a(x) {}  // b 会用默认值 3.14
};

优点：

• 为默认构造和部分构造函数提供默认值。
• 简化代码逻辑。

1.15.4使用委托构造函数（C++11 起）

class MyClass {
    int a;
    double b;
public:
    MyClass() : MyClass(0, 0.0) {}  // 委托给另一个构造函数
    MyClass(int x, double y) : a(x), b(y) {}
};

优点：

• 减少重复代码。
• 多个构造函数共享初始化逻辑。

1.15.5使用聚合初始化（C++11 起）

适用于 struct 或无显式构造函数的类：

struct MyStruct {
    int a;
    double b;
};

MyStruct s{1, 3.14};  // 聚合初始化

1.16静态成员

静态成员	说明	是否需要对象	是否可以访问非静态成员
静态变量	所有对象共享	否	否
静态函数	没有 this 指针	否	否

1.16.1静态成员变量

特点：

• 所有对象共享一份内存。
• 必须在类外定义（初始化）。
• 可以在不创建对象的情况下通过类名访问。

class MyClass {
public:
    static int count;
};

int MyClass::count = 0;  // 必须在类外定义和初始化

int main() {
    MyClass::count = 10;  // 通过类访问
}

---

1.16.2 静态成员函数（Static Member Function）

特点：

• 没有 this 指针，不能访问非静态成员变量或函数。
• 可以通过类名或对象访问。
• 常用于操作静态成员变量或工具函数。

class MyClass {
public:
    static int count;

    static void increment() {
        ++count;
    }
};

int MyClass::count = 0;

int main() {
    MyClass::increment();
}

使用场景

场景	说明
计数器	跟踪创建的对象数量
工具函数	与对象状态无关的功能函数
单例模式	静态成员指针保存实例
全局配置	静态变量作为类级配置项

注意事项

事项	说明
初始化	静态变量必须在类外定义和初始化（除非是 constexpr 从 C++17 起）
访问权限	静态成员也受 public / private 修饰
模板类	静态成员变量模板实例各有一份
const static 整型	可以在类内初始化（C++11 以前仅限于整型）

示例：

class Config {
public:
    static const int version = 1;  // OK，整型 const 可类内初始化
};

1.16.3内联静态变量（C++17）

class MyClass {
public:
    inline static int value = 0;  // 类内初始化，不再需要类外定义
};

1.17this指针

• this 是一个指向当前对象的指针。
• 类型是：ClassName* const this（即：指针是常量，不能修改）。
• 只能在非静态成员函数中使用，静态函数中没有 this。

特性	说明
类型	ClassName* const
使用场景	区分成员变量、链式调用、返回自身引用、指针比较
限制	不能用于静态成员函数
*this	返回当前对象引用
const 成员中	this 是 const ClassName*

注：

• 构造函数中 this 指向正在构建的对象，但对象还未完全构建。
• 不要在构造/析构中把 this 传给外部或调用虚函数，因为可能行为未定义。

1.17.1访问当前对象的成员

class MyClass {
public:
    int value;
    void setValue(int value) {
        this->value = value;  // 区分成员变量和形参
    }
};

1.17.2返回当前对象（支持链式调用）

class MyClass {
public:
    MyClass& setA() { /*...*/ return *this; }
    MyClass& setB() { /*...*/ return *this; }
};

// 使用
MyClass obj;
obj.setA().setB();

1.17.3与指针比较（判断是否是自己）

bool isSameObject(const MyClass* other) {
    return this == other;
}

---

1.17.4相关语法扩展

*this

• 表示当前对象的引用。
• 可用于返回当前对象的副本或引用。

return *this;  // 当前对象本身

const this

在 const 成员函数中，this 的类型变为 const ClassName* const：

class MyClass {
    int val;
public:
    int getVal() const {
        // this 是 const MyClass* 类型
        return this->val;
    }
};

静态成员函数没有 this

class MyClass {
public:
    static void func() {
        // this; // ❌ 错误：static 成员没有 this
    }
};

1.17.4 C++11 的 = delete 和 this

配合 this 限制函数使用：

MyClass& operator=(const MyClass& other) {
    if (this == &other) return *this;  // 防止自赋值
    // 赋值逻辑
    return *this;
}

1.18类实例为空指针

在 C++ 中，即使一个类对象指针是空指针（nullptr），调用非静态成员函数可能不会立即崩溃，只要函数体中没有访问成员变量。这是 C++ 的一个容易误解但很有价值的点。

情况	是否可调用	是否安全	说明
空指针调用不访问成员的非静态函数	✅	❌ 不推荐（未定义行为）
空指针调用访问成员的函数	❌	❌ 崩溃
空指针调用静态函数	✅	✅ 安全
函数中访问 this / 成员变量	✅	❌ 若 this 是 nullptr 会崩溃

1.18.1 空指针可以调用非静态成员函数，但有前提

class MyClass {
public:
    void sayHello() {
        std::cout << "Hello\n";
    }
};

int main() {
    MyClass* obj = nullptr;
    obj->sayHello();  // ✅ 合法，但极度危险！
}

1.18.2 空指针调用访问成员变量的函数会崩溃

class MyClass {
    int val = 42;
public:
    void print() {
        std::cout << val << std::endl;  // ⚠️ 访问成员变量
    }
};

int main() {
    MyClass* obj = nullptr;
    obj->print();  // ❌ 段错误（访问空指针的成员）
}

原因：成员函数是隐式传入 this 指针

obj->func();  // 等价于 MyClass::func(obj);

所以如果 obj == nullptr，那 this == nullptr。
只要函数内部没有使用 this，可能不会出错，但这依赖于实现细节，属于未定义行为（UB）。

1.18.3成员函数中访问 this 的几种形式（都会崩溃）：

• 成员变量：this->x
• 调用另一个成员函数：this->otherFunc()
• 返回自身引用：return *this;

1.18.4特别说明：静态成员函数和空指针无关

class MyClass {
public:
    static void staticFunc() {
        std::cout << "Static function\n";
    }
};

int main() {
    MyClass* obj = nullptr;
    obj->staticFunc();  // ✅ 合法：静态函数与 this 无关
}

1.19const修饰成员

用法	修饰对象	特点或约束
const int x;	成员变量	必须在初始化列表中初始化
int get() const;	成员函数	不可修改成员变量，只能调用 const 函数
const MyClass obj;	对象	只能调用 const 成员函数
mutable int x;	成员变量	可在 const 函数中修改
static const int val = 10;	类常量成员	整型常量可在类内初始化

1.19.1const 成员变量（常量成员）

class MyClass {
    const int id;
public:
    MyClass(int i) : id(i) {}  // ✅ 只能用初始化列表初始化
};

特点：

• 只能通过构造函数初始化列表赋值。
• 每个对象一份（不同于 static）。
• 不能被修改。

注意：

• 如果不初始化，编译错误。
• 不能在构造函数体内赋值！

1.19.2const 成员函数（常函数）

定义方式：

class MyClass {
    int value;
public:
    int getValue() const {
        return value;
    }
};

特点：

• 表示该函数不会修改成员变量。
• this 指针变为 const MyClass* const this。
• 只能调用其他 const 成员函数。

注：若尝试修改成员变量会编译错误：

void setValue(int v) const {
    value = v;  // ❌ 编译错误
}

常用于 get、打印、只读逻辑等：

std::string toString() const;

1.19.3const 修饰成员对象

const MyClass obj(5);  // 成员函数只能调用 const 成员函数

特性：

• 对象一旦为 const，就只能调用 const 成员函数。
• 不能修改成员变量。

---

1.19.4mutable：打破 const 限制（C++ 提供的“例外”）

class MyClass {
    mutable int cachedValue;  // 即使在 const 函数中也可修改
public:
    int getCached() const {
        cachedValue++;  // ✅ 合法
        return cachedValue;
    }
};

用途：

• 缓存、中间结果、调试计数器等。
• 在 const 对象中需要“可变”的变量。

1.19.5const static 成员变量

用于类内常量声明：

class MyClass {
public:
    static const int maxCount = 100;  // ✅ 可类内初始化（整型）
};

若为非整型，则必须在类外定义

1.20运算符重载

1.20.1基本语法

ReturnType operator符号(参数列表);

• 通常作为成员函数或友元函数实现。
• 对于大多数运算符，建议使用成员函数；某些需要双目对称性（如 +, ==）的可以使用友元函数。

1.20.2可重载的运算符

类别	运算符
算术	+ - * / %
关系	== != < > <= >=
逻辑	`&&
赋值	= += -= *= /= %=
位运算	`&
自增自减	++ --
下标	[]
函数调用	()
指针访问	-> * ->
其他	new delete new[] delete[]

❗不能重载：.（成员访问）、::（作用域解析）、sizeof、typeid、?:、.∗

1.20.3成员函数 vs 非成员函数（友元）

• 成员函数： 左操作数必须是当前类对象

  class A {
  public:
      A operator+(const A& other);
  };
  

• 非成员函数（友元）：可用于左右两边都是类对象或混合类型

  class A {
      friend A operator+(const A& a, const A& b);
  };
  
  A operator+(const A& a, const A& b){
      
  }
  

1.20.4特殊重载

1.20.4.1自增 / 自减

// 前置 ++
Point& operator++();        

// 后置 ++
Point operator++(int);      // 注意参数是 int 占位

1.20.4.2下标运算符 []

int& operator[](int index);
const int& operator[](int index) const;

1.20.4.3函数调用运算符 ()

int operator()(int a, int b) {
    return a + b;
}

1.20.4.4流操作符（推荐用友元函数）

friend std::ostream& operator<<(std::ostream& os, const Point& p);
friend std::istream& operator>>(std::istream& is, Point& p);

1.21继承

1.21.1继承的基本语法

class Base {
public:
    void sayHello() { std::cout << "Hello from Base\n"; }
};

class Derived : public Base {
    // 继承了 Base 的成员
};

1.21.2继承方式（访问控制）

class Derived : public Base {};   // 公有继承（常用）
class Derived : protected Base {}; // 保护继承
class Derived : private Base {};  // 私有继承

继承方式	基类 public 成员在派生类中	基类 protected 成员	基类 private 成员
public	public	protected	不可访问
protected	protected	protected	不可访问
private	private	private	不可访问

1.21.3构造函数与析构函数调用顺序

1. 创建子类对象时：
   • 先调用基类构造函数，再调用子类构造函数。
2. 析构对象时：
   • 先调用子类析构函数，再调用基类析构函数。

class Base {
public:
    Base() { std::cout << "Base constructor\n"; }
    ~Base() { std::cout << "Base destructor\n"; }
};

class Derived : public Base {
public:
    Derived() { std::cout << "Derived constructor\n"; }
    ~Derived() { std::cout << "Derived destructor\n"; }
};

1.21.4重写（Override）与隐藏（Hiding）

1.21.4.1虚函数与重写

class Base {
public:
    virtual void speak() { std::cout << "Base\n"; }
};

class Derived : public Base {
public:
    void speak() override { std::cout << "Derived\n"; }
};

• 使用 override 明确说明重写，避免错误。
• 基类指针或引用调用子类方法，称为多态。

1.21.4.2非虚函数的“隐藏”

如果子类定义了与基类同名的函数（但参数不同），基类版本会被隐藏，需要使用 using 恢复。

class Base {
public:
    void func(int);
};

class Derived : public Base {
public:
    void func(double);  // 隐藏了 Base::func
    using Base::func;   // 恢复 Base::func
};

1.21.5多重继承（Multiple Inheritance）

一个类可以继承多个基类：

class A { };
class B { };
class C : public A, public B { };

问题：二义性问题，可能导致多个同名成员冲突。

1.21.6虚继承（Virtual Inheritance）

解决菱形继承的问题（同一个基类被多次继承）：

class A { };
class B : virtual public A { };
class C : virtual public A { };
class D : public B, public C { }; // 只存在一份 A

1.21.7访问控制总结

成员定义方式	同类访问	派生类访问	外部访问
public	✅	✅（继承方式决定）	✅
protected	✅	✅（继承方式决定）	❌
private	✅	❌	❌

1.22多态

class Base {
public:
    virtual void show() { cout << "Base" << endl; }
    virtual ~Base() {} // 必须
};

class Derived : public Base {
public:
    void show() override { cout << "Derived" << endl; }
};

void func(Base* b) {
    b->show(); // 运行时决定调用哪个 show
}

1.22.1编译时多态（静态多态）

也称为 函数重载 和 运算符重载，在编译期间就确定了调用的函数版本。

1.22.1.1函数重载（Function Overloading）

同一个函数名，参数列表不同。

void print(int x) { }
void print(double y) { }

1.22.1.2 运算符重载（Operator Overloading）

自定义类型的运算符行为。

class Vec2 {
public:
    int x, y;
    Vec2 operator+(const Vec2& other) {
        return {x + other.x, y + other.y};
    }
};

---

1.22.2运行时多态（动态多态）

通过 虚函数 和 继承 实现，运行时才决定调用哪个函数版本。

1.22.2.1基类指针/引用调用虚函数

class Animal {
public:
    virtual void speak() { cout << "Animal speaks" << endl; }
};

class Dog : public Animal {
public:
    void speak() override { cout << "Dog barks" << endl; }
};

Animal* a = new Dog();
a->speak();  // 输出 "Dog barks"

1.22.2.2 使用 virtual 关键字

• virtual 定义的函数才能被子类重写。
• override 是 C++11 加入的，用来显式标记重写函数。
• 如果析构函数不是 virtual 的，可能导致子类析构不完全（内存泄漏）。

1.22.2.3 虚函数表（vtable）

运行时多态通过 虚函数表（vtable） 实现：

• 每个含虚函数的类有一个虚函数表。
• 每个对象有一个指向对应类 vtable 的指针。
• 通过这个表，在运行时确定调用哪个函数。

---

1.22.3注意事项

• 只有通过基类指针或引用调用虚函数，才体现出运行时多态。
• 构造函数中调用虚函数不会表现出多态（因为此时派生类尚未构造完成）。
• 虚函数会增加一定的内存和调用开销，但换来更强的灵活性。

1.22.4虚析构和纯析构

特性	虚析构（virtual ~Base()）	纯虚析构（virtual ~Base() = 0）
是否可实例化	可以	不可以（类变为抽象类）
是否必须实现	否	是（必须提供定义，否则链接错误）
用于多态析构	✅ 是	✅ 是
用途	多态安全释放	作为抽象接口基类，同时安全析构派生类对象

1.22.4.1虚析构函数（virtual destructor）

确保通过基类指针删除派生类对象时能正确调用派生类的析构函数，防止资源泄漏。

class Base {
public:
    virtual ~Base() {
        std::cout << "Base destructor\n";
    }
};

class Derived : public Base {
public:
    ~Derived() {
        std::cout << "Derived destructor\n";
    }
};

int main() {
    Base* b = new Derived();
    delete b;  // 会先调用 Derived 析构，再调用 Base 析构
    return 0;
}

输出：

Derived destructor
Base destructor

没有设置为 virtual 会怎样？

class Base {
public:
    ~Base() {
        std::cout << "Base destructor\n";
    }
};

如果你这样写，然后用 delete b，只会调用 Base::~Base()，不会调用 Derived::~Derived()，从而导致资源泄漏。

1.22.4.2纯虚析构函数（pure virtual destructor）

class Base {
public:
    virtual ~Base() = 0;  // 纯虚析构函数声明
};

Base::~Base() {
    std::cout << "Base destructor (pure virtual implemented)\n";
}

⚠️ 注：纯虚析构函数必须提供定义，否则链接时报错！

用途：

• 通常用于抽象基类，表示不允许直接实例化该类。
• 纯虚析构函数的主要意义是让类变成抽象类，但仍需要有实现，因为析构时会被调用。

示例：

class Abstract {
public:
    virtual ~Abstract() = 0;
};

Abstract::~Abstract() {
    std::cout << "Abstract destructor\n";
}

派生类：

class Concrete : public Abstract {
public:
    ~Concrete() {
        std::cout << "Concrete destructor\n";
    }
};

调用：

int main() {
    Abstract* a = new Concrete();
    delete a;
    return 0;
}

输出：

Concrete destructor
Abstract destructor

1.23模板

1.23.1函数模板

1.23.1.1函数模板定义语法

template <typename T>
T max(T a, T b) {
    return (a > b) ? a : b;
}

• template <typename T>：声明一个类型参数 T。
• 函数 max 使用 T 作为参数和返回值类型。
• typename 可以用 class 代替（含义相同）。

1.23.1.2使用函数模板

int a = 10, b = 20;
std::cout << max(a, b);        // 自动推导为 int 版本

double x = 3.14, y = 2.71;
std::cout << max(x, y);        // 自动推导为 double 版本

也可以显式指定模板参数：

std::cout << max<int>(a, b);

1.23.1.3模板的特点

特点	描述
编译时生成	编译时根据调用的类型生成具体函数版本
类型安全	比宏更安全（有类型检查）
避免代码重复	不用为每种类型写一份逻辑
支持多个模板参数	可同时定义多个泛型参数

1.23.1.4多个模板参数

template <typename T1, typename T2>
void printPair(T1 a, T2 b) {
    std::cout << a << " - " << b << std::endl;
}

1.23.1.5模板与函数重载

模板函数可以与普通函数或其他模板重载共存，编译器会根据匹配优先级选择最合适的版本。

void show(int x) {
    std::cout << "Normal function: " << x << std::endl;
}

template <typename T>
void show(T x) {
    std::cout << "Template function: " << x << std::endl;
}

调用：

show(5);        // 调用普通函数
show(3.14);     // 调用模板函数

1.23.1.6模板的限制（经典问题）

1. 不能将模板代码写在 .cpp 文件中单独编译，通常应写在 .h 文件中（因为编译时才生成具体函数）。
2. 错误信息复杂，模板实例化失败时的错误较难读。
3. 不支持运行时类型决定，模板是纯编译时机制。

1.23.1.7 C++17 之后的改进

• 模板参数自动推导增强（CTAD）
• if constexpr 分支优化模板逻辑
• Concepts（C++20）：约束模板类型，提高错误提示可读性

---

1. if constexpr（C++17 新特性）

用于在模板中根据类型或常量条件进行编译期分支判断，避免非法代码实例化，提升可读性和效率。

例子：打印指针或值

#include <iostream>
#include <type_traits>

template <typename T>
void print(const T& val) {
    if constexpr (std::is_pointer_v<T>) {
        std::cout << "Pointer: " << *val << "\n";
    } else {
        std::cout << "Value: " << val << "\n";
    }
}

int main() {
    int x = 42;
    int* p = &x;
    print(x);   // 输出 Value: 42
    print(p);   // 输出 Pointer: 42
}

好处：

• 编译时判断条件，未触发的分支不会实例化，不会报错。
• 替代 enable_if 更清晰。

---

2. 类模板参数推导（CTAD, C++17）

在 C++17 中，类模板也支持像函数模板一样的自动类型推导（函数模板早就支持了）。

例子：使用 std::pair 的推导

#include <utility>
#include <string>
#include <iostream>

int main() {
    std::pair p(1, std::string("hello")); // 自动推导为 std::pair<int, std::string>
    std::cout << p.second << std::endl;
}

在 C++14 中，必须显式写出 std::pair<int, std::string> p(1, "hello");

3. auto 用于模板参数（C++17）

C++17 允许你写出更简单的函数模板，用 auto 自动推导参数类型。

例子：

template <auto N>
void repeat() {
    for (int i = 0; i < N; ++i)
        std::cout << i << " ";
}

int main() {
    repeat<5>();  // 输出 0 1 2 3 4
}

这里模板参数不是类型，而是一个 值（非类型模板参数），并用 auto 进行自动类型推导。

4. template <typename T> auto func(T val) + decltype(auto)

C++14/17 引入了 decltype(auto) 和更强的 auto 类型推导能力，模板代码可以更精准保留值类别（左值/右值）。

template <typename T>
decltype(auto) forwardVal(T&& val) {
    return std::forward<T>(val);
}

5. constexpr 与模板结合（C++17 强化 constexpr）

可以编写 constexpr 的模板函数，用于编译期计算。

例子：编译期阶乘计算

template <int N>
constexpr int factorial() {
    if constexpr (N <= 1)
        return 1;
    else
        return N * factorial<N - 1>();
}

int main() {
    constexpr int val = factorial<5>();  // 编译期计算
    std::cout << val << std::endl;       // 输出 120
}

总结

特性	版本	优势
if constexpr	C++17	编译期条件判断，替代 SFINAE
CTAD（类模板推导）	C++17	自动推导模板类构造类型
auto 非类型参数	C++17	简化非类型模板参数定义
强化 constexpr	C++17	支持更复杂模板函数在编译期计算
decltype(auto)	C++14/17	精准保留返回值类型和引用性

1.24STL标准库

1.24.1string

1.24.1.1基本介绍

• std::string 是 std::basic_string<char> 的 typedef。
• 自动管理内存，动态增长。
• 支持拷贝、赋值、比较等操作。

#include <string>
#include <iostream>

std::string s = "Hello, world!";

1.24.1.2常用构造函数

std::string s1;                         // 空字符串
std::string s2("hello");               // 从C字符串构造
std::string s3(s2);                    // 拷贝构造
std::string s4(5, 'a');                // "aaaaa"
std::string s5 = s2.substr(0, 3);      // "hel"

1.24.1.3常用方法

1.访问

s[i]          // 下标访问（不检查越界）
s.at(i)       // 安全访问，越界会抛异常
s.front()     // 第一个字符
s.back()      // 最后一个字符

2.查找

s.find("lo")        // 返回第一次出现的位置
s.rfind("o")        // 返回最后一次出现的位置
s.find_first_of("aeiou") // 找到第一个元音
s.find_last_of("aeiou")

3.修改

s.append(" world"); // 追加
s += "!";           // 同上
s.insert(5, ",");   // 插入
s.erase(0, 6);      // 删除
s.replace(0, 5, "Hi"); // 替换

4.长度与清空

s.size() / s.length()   // 获取长度
s.empty()               // 是否为空
s.clear()               // 清空

5.子串与比较

s.substr(0, 5);         // 截取前5个字符
s == "hello"            // 字符串比较
s.compare("abc")        // 负数/0/正数

1.24.1.4遍历方式

for (char c : s) {
    std::cout << c;
}

for (size_t i = 0; i < s.size(); ++i) {
    std::cout << s[i];
}

1.24.1.5与 C 字符串互转

const char* c_str = s.c_str();     // 转为 const char*
char* copy = strdup(s.c_str());    // 拷贝一份 C 字符串

std::string s2 = std::string("hello"); // 从 C 字符串创建

注意事项

• std::string 是值语义（copy-by-value），可通过引用或移动优化性能。
• 注意 c_str() 返回的指针只在字符串未修改前有效。
• 访问非法下标未定义行为，建议用 at()。

1.24.1.6C++11+ 增强特性

• 支持移动语义
• 支持 std::to_string() 和 std::stoi() 等函数

std::string num = std::to_string(123);  // "123"
int i = std::stoi("456");              // 456

1.24.2vector

1.24.2.1基本特性

特性	描述
动态扩容	容器空间会自动扩展，无需手动管理内存
顺序存储	元素在内存中是连续排列的，支持随机访问
支持泛型	可以存储任意类型（包括用户自定义类型）
拷贝与移动语义	拷贝构造、移动构造都有良好支持

1.24.2.2常用操作

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

vector<int> v = {1, 2, 3};

// 添加元素
v.push_back(4);     // 末尾插入
v.insert(v.begin(), 0); // 指定位置插入

// 删除元素
v.pop_back();       // 删除末尾元素
v.erase(v.begin()); // 删除指定位置的元素
v.clear();          // 清空所有元素

// 访问元素
v[0];               // 下标访问，不越界检查
v.at(0);            // 下标访问，有越界检查
v.front();          // 第一个元素
v.back();           // 最后一个元素

// 遍历
for (int x : v) {
    cout << x << " ";
}

// 大小相关
v.size();           // 当前元素个数
v.capacity();       // 当前分配的容量
v.empty();          // 是否为空

// 其他
v.resize(10);       // 重新设置大小
v.reserve(100);     // 提前分配容量

1.24.2.3性能注意事项

操作	时间复杂度	说明
push_back	均摊 O(1)	扩容时是 O(n)
pop_back	O(1)	高效
insert/erase	O(n)	非尾部位置插入/删除需移动元素
随机访问	O(1)	和数组一致

1.24.2.4扩容机制简述

• 默认扩容策略通常是 当前容量的 2 倍。
• 每次扩容都会 重新分配内存，并 拷贝原有元素。
• 因此建议：提前调用 reserve() 可减少不必要的拷贝。

1.24.2.5使用建议

• 若需要频繁在中间插入/删除，请使用 std::list 或 std::deque。
• 若关注性能，尽量使用 reserve 来避免重复扩容。
• 可以与 emplace_back 搭配使用来原地构造对象（避免拷贝）。

v.emplace_back(1, 2); // 在末尾原地构造

示例代码

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

struct Person {
    string name;
    int age;

    Person(string n, int a) : name(n), age(a) {
        cout << "Construct: " << name << endl;
    }
};

int main() {
    vector<Person> people;

    // push_back: 创建临时对象，再拷贝/移动到 vector 中
    people.push_back(Person("Alice", 30));

    // emplace_back: 直接在 vector 中构造对象
    people.emplace_back("Bob", 25);

    return 0;
}

方法	构造方式	性能
push_back(obj)	先构造临时对象，再拷贝/移动进容器	有额外的拷贝/移动成本
emplace_back(args...)	直接在容器末尾 原地构造	无额外开销，更高效

1.24.2.6缩容

v.swap(v); 或 std::vector<T>(v).swap(v); 是 C++ 中一个常用的技巧，用于 释放 vector 占用的内存，也叫“释放 capacity 的技巧”。

背景知识：vector 的内存不会自动收缩

当你调用 v.clear() 删除所有元素时：

• size() 变为 0 ✅
• 但 capacity() 不会减少 ❌
  • 原有内存仍然占用
  • 适用于重复使用时避免频繁分配，但如果不再使用就浪费内存

1. 正确释放 memory 的写法：

std::vector<int> v = {1, 2, 3, 4, 5};

v.clear();              // 清空元素，内存仍然保留
std::vector<int>(v).swap(v);  // 释放多余内存

2. 工作原理：

std::vector<T>(v).swap(v);

• std::vector<T>(v) 会 复制一个临时 vector，仅包含 v 的有效元素（这里是 0 个）
• 然后和原来的 v 做 交换
• 原来的 v 被替换成了一个空 vector，临时对象析构时释放旧内存 ✂️

3. 总结

写法	作用
v.clear()	删除元素，不释放内存
std::vector<T>(v).swap(v)	删除元素，释放多余内存
v.shrink_to_fit()	请求释放内存（但不强制，非所有实现支持）

1.24.3deque

特性	描述
双端插入删除	支持 push_front 和 push_back
随机访问	支持下标访问 []、at()，时间复杂度 O(1)
动态增长	自动扩容，不需要手动分配内存
内部结构	内存非连续（分块数组/分段列表）

1.24.3.1常用操作

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

deque<int> dq = {1, 2, 3};

// 插入
dq.push_back(4);     // 尾部插入
dq.push_front(0);    // 头部插入
dq.insert(dq.begin() + 2, 99); // 中间插入

// 删除
dq.pop_back();       // 删除尾部
dq.pop_front();      // 删除头部
dq.erase(dq.begin() + 1); // 删除中间

// 访问
dq[0];               // 无越界检查
dq.at(0);            // 有越界检查
dq.front();          // 获取头部元素
dq.back();           // 获取尾部元素

// 其他
dq.size();
dq.empty();
dq.clear();

1.24.3.2内部实现原理（与 vector 最大不同）

容器	内存布局	插入性能
vector	连续内存	仅尾部高效
deque	分块结构	头尾都高效

• deque 的实现通常为块状数组 + 中央控制器指针数组
• 优点：头部插入不会导致整体移动
• 缺点：不适合指针操作或与底层数组交互

1.24.3.3与vector性能对比（复杂度）

操作	vector	deque
push_back	O(1) 均摊	O(1)
push_front	O(n)	O(1)
insert middle	O(n)	O(n)
random access []	O(1)	O(1)
内存连续性	是	否

1.24.3.4使用场景

1. 适合用 deque 的场景：

   • 双端进出队（如滑动窗口、单调队列等算法）

   • 插入/删除频繁且不只限于尾部

   • 内存使用不需要连续（如系统队列、消息队列）

2. 不推荐使用 deque 的场景：

   • 需要指针操作、数组地址连续性（如与 C API 交互）

   • 高性能计算、大量随机访问（vector 更快）

3. 示例：单调队列（滑动窗口最值）

deque<int> dq;
for (int i = 0; i < n; ++i) {
    while (!dq.empty() && nums[dq.back()] < nums[i])
        dq.pop_back();
    dq.push_back(i);
    if (dq.front() <= i - k)
        dq.pop_front();
    result.push_back(nums[dq.front()]);
}

1.24.4stack

1.24.4.1常用操作汇总

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

stack<int> s;

// 入栈
s.push(10);
s.push(20);

// 出栈
s.pop(); // 删除栈顶（不返回值）

// 访问栈顶
cout << s.top(); // 输出 10

// 判空 / 大小
s.empty(); // 是否为空
s.size();  // 当前元素个数

1.24.4.2接口说明

方法	含义	复杂度
push(x)	将元素 x 压入栈顶	O(1)
pop()	移除栈顶元素（不返回）	O(1)
top()	返回栈顶元素（不删除）	O(1)
empty()	是否为空	O(1)
size()	当前元素数量	O(1)

1.24.4.3底层容器适配器原理

std::stack 默认使用 std::deque 作为底层容器：

template<
    class T,
    class Container = std::deque<T>
> class stack;

你也可以自定义容器：

std::stack<int, std::vector<int>> s2;

容器要求支持以下操作：

• back(), push_back(), pop_back()

1.24.4.4使用场景

场景	用法简述
括号匹配、语法解析	括号入栈出栈
DFS（深度优先搜索）	使用 stack 模拟递归
表达式求值（逆波兰）	操作数和运算符压栈
撤销操作	操作记录入栈

示例：括号匹配

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(')');
        else if (c == '[') st.push(']');
        else if (c == '{') st.push('}');
        else if (st.empty() || st.top() != c) return false;
        else st.pop();
    }
    return st.empty();
}

1.24.4.5注意事项

限制	说明
无法遍历 stack 元素	只能访问栈顶
pop() 不返回值	如果要取出栈顶并移除，需要手动 top(); pop();
非线程安全	多线程中需加锁

1.24.4.6总结

功能项	std::stack 特点
数据结构	后进先出 LIFO
底层容器	默认 deque，可自定义
支持遍历	❌ 不支持
支持随机访问	❌ 不支持
常用操作	push, pop, top, empty
使用场景	DFS、匹配、表达式计算等

1.24.5queue

std::queue 是一个先进先出（FIFO）队列容器适配器，只允许：

• 从队尾（back）入队
• 从队首（front）出队

它封装了底层容器（默认是 std::deque），屏蔽了不必要的接口。

1.24.5.1常用操作

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

queue<int> q;

// 入队
q.push(10);
q.push(20);

// 出队（不返回值）
q.pop();

// 访问队首队尾
cout << q.front();  // 20
cout << q.back();   // 20

// 判空 / 大小
q.empty();
q.size();

1.24.5.2接口说明

方法	含义	时间复杂度
push(x)	将元素加入队尾	O(1)
pop()	移除队首元素（不返回）	O(1)
front()	获取队首元素	O(1)
back()	获取队尾元素	O(1)
empty()	检查是否为空	O(1)
size()	获取元素个数	O(1)

1.24.5.3底层容器支持

std::queue 的底层默认是 std::deque，但也可以使用 std::list 等：

std::queue<int> q;  // 默认 deque
std::queue<int, std::list<int>> q2;  // 使用 list

注意：不支持 vector（因为 vector 头部操作慢）

使用示例：广度优先搜索（BFS）

void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";

        for (int v : graph[u]) {
            if (!visited[v]) {
                q.push(v);
                visited[v] = true;
            }
        }
    }
}

1.24.5.4使用场景

场景	说明
广度优先搜索（BFS）	图搜索经典应用
多任务排队 / 消息队列	任务先进先处理
滑动窗口 / 队列优化	使用 deque 配合处理
操作记录	排队等待处理

1.24.5.5注意事项

限制	说明
不支持遍历元素	只能访问首尾元素
pop() 不返回值	要先 front() 再 pop()
非线程安全	多线程需加锁处理

1.24.5.6queue vs stack vs deque 对比

操作/容器	queue	stack	deque
添加元素	末尾	栈顶	两端均可
删除元素	首部	栈顶	两端均可
支持遍历	❌	❌	✅
随机访问	❌	❌	✅
底层结构	默认 deque	默认 deque	自身容器

1.24.6list

std::list 是一个**双向链表（doubly linked list）**容器，提供快速的插入和删除操作，尤其适合在序列中间频繁修改元素的场景。

1.24.6.1特点

特性	说明
结构	双向链表，非连续内存
插入/删除	任意位置均为 O(1)
访问	不支持随机访问（无 operator[]）
迭代器	双向迭代器，可前后遍历
内存占用	较大（每个节点需额外指针）
适合场景	频繁插入/删除，中间操作

1.24.6.2常用接口

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

list<int> lst = {1, 2, 3};

// 插入
lst.push_back(4);
lst.push_front(0);
auto it = lst.begin();
advance(it, 2);
lst.insert(it, 99);

// 删除
lst.pop_back();
lst.pop_front();
lst.erase(it);

// 访问（需通过迭代器）
for (int v : lst) {
    cout << v << " ";
}

1.24.6.3复杂度

操作	复杂度
访问元素	O(n)
插入/删除元素	O(1) (已知位置)
查找元素	O(n)
大小获取	O(1)

1.24.6.4典型用法

• 频繁中间插入删除，避免 vector 可能引发的大规模元素移动
• 稳定迭代器，删除元素不影响其他迭代器
• 合并两个链表：lst1.splice(...)
• 排序和去重：lst.sort(), lst.unique()

1.24.6.5特殊成员函数

函数	说明
splice()	连接/转移元素到另一个 list
remove(val)	删除所有等于 val 的元素
unique()	删除相邻重复元素
sort()	链表内部排序
merge()	合并两个已排序链表

1.24.6.6与其他容器对比

容器	访问效率	插入/删除效率	内存占用	使用场景
vector	高 (O(1))	低 (中间 O(n))	低	随机访问、少插入删除
deque	高 (O(1))	中 (头尾快)	中	头尾插入删除、多端操作
list	低 (O(n))	高 (O(1))	高	频繁中间插入删除、稳定迭代器

1.24.6.7示例：使用 splice 连接两个链表

list<int> a = {1, 2, 3};
list<int> b = {4, 5, 6};

a.splice(a.end(), b); // 将 b 全部元素接到 a 尾部，b 变空

for (int v : a) cout << v << " "; // 输出 1 2 3 4 5 6
cout << "\n";
cout << b.size(); // 输出 0

1.24.7set

std::set 是一个有序集合容器，内部基于**平衡二叉搜索树（通常是红黑树）*实现，保证元素*唯一且有序。

1.24.7.2特点

特性	说明
元素唯一	自动去重
有序排列	默认升序排列（可自定义比较器）
底层实现	红黑树（自平衡二叉搜索树）
访问方式	不支持随机访问，支持迭代器遍历
插入/删除	平均 O(log n)
查找	平均 O(log n)

1.24.7.3常用接口

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

set<int> s;

// 插入
s.insert(10);
s.insert(5);
s.insert(10);  // 不会插入重复元素

// 查找
auto it = s.find(5);
if (it != s.end())
    cout << *it << "\n";

// 删除
s.erase(5);

// 遍历
for (int x : s)
    cout << x << " ";

1.24.7.4重要操作及复杂度

操作	复杂度	说明
insert	O(log n)	插入元素（自动排序）
erase	O(log n)	删除元素
find	O(log n)	查找元素
count	O(log n)	元素出现次数（0 或 1）
迭代遍历	O(n)	顺序访问所有元素

1.24.7.5示例：查找和插入

set<int> s = {3, 1, 4};

if (s.find(2) == s.end()) {
    s.insert(2);
}

for (auto x : s)
    cout << x << " "; // 输出：1 2 3 4

1.24.7.6自定义排序规则

struct Compare {
    bool operator()(int a, int b) const {
        return a > b; // 降序排序
    }
};

set<int, Compare> s;
s.insert(10);
s.insert(5);
s.insert(7);

for (auto x : s)
    cout << x << " "; // 输出：10 7 5

1.24.7.7与其他关联容器对比

容器	元素是否有序	是否允许重复	平均查找复杂度	备注
std::set	是	否	O(log n)	元素唯一，自动排序
std::multiset	是	是	O(log n)	允许重复元素
std::unordered_set	否	否	O(1) 平均	基于哈希，无序
std::unordered_multiset	否	是	O(1) 平均	允许重复，无序

1.24.7.8使用场景

• 需要自动排序且元素唯一的集合
• 查找、插入、删除操作频繁且需要保证有序
• 去重场景，比如统计不重复元素

1.24.7.9总结

• std::set 是基于红黑树的有序唯一集合
• 插入、删除、查找平均时间复杂度为 O(log n)
• 支持遍历，元素自动排序
• 可以自定义排序规则实现降序或自定义排序

1.24.8pair

std::pair 是标准库中一个模板结构，用来存储两个数据元素的组合。它可以存储任意类型的两个值，常用来返回两个相关联的值或者作为容器（如 map）的键值对。

1.24.8.1定义和初始化

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

pair<int, string> p1;                   // 默认构造，元素未初始化
pair<int, string> p2(10, "hello");     // 直接初始化
auto p3 = make_pair(20, "world");      // 使用工厂函数，类型自动推导

cout << p2.first << ", " << p2.second << "\n";  // 输出：10, hello
cout << p3.first << ", " << p3.second << "\n";  // 输出：20, world

1.24.8.2访问成员

• first ：访问第一个元素
• second：访问第二个元素

pair<int, string> p(1, "one");
cout << p.first << endl;   // 1
cout << p.second << endl;  // one

1.24.8.3常见用法示例

1. 作为函数返回多个值

pair<int, int> minMax(int a[], int n) {
    int mn = a[0], mx = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] < mn) mn = a[i];
        if (a[i] > mx) mx = a[i];
    }
    return make_pair(mn, mx);
}

int main() {
    int arr[] = {5, 2, 9, 1, 7};
    auto res = minMax(arr, 5);
    cout << "Min: " << res.first << ", Max: " << res.second << endl;
}

2. 作为 map 的键值对类型

#include <map>
map<pair<int,int>, string> mp;
mp[make_pair(1,2)] = "Point A";
cout << mp[{1,2}] << endl;  // 输出：Point A

1.24.8.4其他操作

• 支持比较操作（默认按 first，然后按 second）
• 可以用结构化绑定（C++17）

auto p = make_pair(3, "three");
auto [num, str] = p;
cout << num << ", " << str << endl;  // 3, three

1.24.8.5总结

特点	说明
模板类型	pair<T1, T2>，存储两个不同类型的值
访问方式	.first 和 .second
常用场景	函数返回多个值、键值对、简单组合数据
支持比较	按字典序比较，方便排序和查找
工厂函数	make_pair，方便类型自动推导

1.24.8.6与set结合使用

在 std::set 中，std::pair 本身不是容器的一部分，但它常常用来作为 set 的元素类型，尤其当你想存储一对相关的值，并且希望这对值作为整体参与排序和唯一性判断时非常有用。

1. set 中使用 pair 的场景

• 存储二维坐标点，如 set<pair<int,int>>，自动按字典序（先比较 .first，再比较 .second）排序，方便快速查找、去重。
• 存储组合键，比如 (用户ID, 时间戳)，支持快速检索和有序遍历。
• 作为复杂数据的简易结构，不用自己定义结构体。

2. 示例代码

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

int main() {
    set<pair<int, int>> s;

    s.insert({1, 5});
    s.insert({2, 3});
    s.insert({1, 5});  // 重复，不会插入

    for (auto& p : s) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    // 输出: (1, 5) (2, 3)
}

这里元素是 pair<int,int>，set 会自动按照 (first, second) 字典序排列。

3. 自定义排序

你也可以给 set 提供自定义的比较函数，比如只按 .second 排序：

struct Compare {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
        return a.second < b.second;
    }
};

set<pair<int,int>, Compare> s;
s.insert({1, 5});
s.insert({2, 3});
s.insert({3, 4});

for (auto& p : s) {
    cout << "(" << p.first << ", " << p.second << ") ";
}
// 输出: (2, 3) (3, 4) (1, 5)

4. 总结

优势	说明
方便存储和比较两相关联的值	省去自定义结构体麻烦
默认按字典序排序	(first, second) 顺序比较
支持自定义排序	可以按任意规则排序
适合存储复合键	例如 (id, timestamp)、(x,y) 等

1.24.9map

std::map 是一个关联式容器，以键值对（key-value）*形式存储元素，且*键唯一且有序。
底层通常基于红黑树（自平衡二叉搜索树）**实现，支持快速查找、插入和删除。

1.24.9.1主要特点

特性	说明
以键值对形式存储	每个元素是 std::pair<const Key, T>
键唯一且有序	默认按键的升序排列
底层实现	红黑树（平衡二叉搜索树）
查找/插入/删除	平均时间复杂度 O(log n)
不支持随机访问	只能通过迭代器顺序访问

1.24.9.2常用接口

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

map<int, string> m;

// 插入元素
m.insert({1, "one"});
m[2] = "two";             // 也可用下标访问插入/修改
m.emplace(3, "three");    // 直接构造插入

// 访问元素
cout << m[1] << endl;    // 输出：one
cout << m.at(2) << endl; // 输出：two

// 查找
auto it = m.find(3);
if (it != m.end())
    cout << it->second << endl;  // 输出：three

// 删除
m.erase(1);

// 遍历
for (auto& p : m) {
    cout << p.first << " => " << p.second << endl;
}

1.24.9.3复杂度分析

操作	复杂度
查找 (find)	O(log n)
插入 (insert)	O(log n)
删除 (erase)	O(log n)
访问 (operator[]、at)	O(log n)

1.24.9.4细节说明

• operator[]：如果键不存在，会自动插入默认值（T()），然后返回对应值的引用
• at()：访问元素，键不存在时会抛出异常 std::out_of_range
• 键类型必须支持 < 比较操作（或自定义比较器）
• 元素以键排序，默认使用 std::less<Key>
• 键不可修改（是 const Key）

1.24.9.5自定义比较器示例

struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b;  // 降序排序
    }
};

map<int, string, Compare> m;
m[1] = "one";
m[2] = "two";

for (auto& p : m)
    cout << p.first << " => " << p.second << endl;
// 输出：2 => two
//       1 => one

1.24.9.6使用场景

• 需要键值对映射的数据结构
• 需要按键排序的数据
• 快速查找、插入和删除操作
• 统计、频率统计（key：元素，value：计数）
• 缓存和字典结构

1.24.9.7与其他关联容器对比

容器	元素唯一	有序	底层结构	查找复杂度
std::map	是	是	红黑树	O(log n)
std::multimap	否	是	红黑树	O(log n)
std::unordered_map	是	否	哈希表	平均 O(1)
std::unordered_multimap	否	否	哈希表	平均 O(1)

1.24.9.8总结

• std::map 是一个有序、键唯一的键值对容器，基于红黑树实现
• 支持高效的查找、插入和删除操作，时间复杂度均为 O(log n)
• 支持自定义排序规则
• 适合需要键排序或者顺序访问的场景

1.24.10函数对象（仿函数）

1.24.10.1什么是函数对象？

函数对象（又称仿函数，functor）是一个重载了 operator() 的类或结构体实例，看起来像函数，可以像函数一样被调用。它们可以携带状态，灵活且高效。

1.24.10.2主要特点

• 表现为可以调用的对象，调用形式：obj(args...)
• 可以保存状态（不同于普通函数指针）
• 可以用于 STL 算法的自定义行为，如排序、比较、操作等
• 通常通过类或结构体实现 operator() 来定义行为

1.24.10.3常见函数对象示例

1. 标准库提供的函数对象（<functional>）

函数对象类型	功能说明
std::less<T>	小于比较（默认排序）
std::greater<T>	大于比较
std::equal_to<T>	等于比较
std::not_equal_to<T>	不等于比较
std::plus<T>	加法操作
std::minus<T>	减法操作
std::multiplies<T>	乘法操作
std::divides<T>	除法操作
std::negate<T>	取负操作

2. 自定义函数对象

struct MyCompare {
    bool operator()(int a, int b) const {
        return a > b;  // 降序排序
    }
};

使用示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>  // 标准函数对象头文件

using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1};

    // 使用 std::less（默认）
    sort(v.begin(), v.end());  // 升序排序

    // 使用 std::greater 进行降序排序
    sort(v.begin(), v.end(), std::greater<int>());

    // 使用自定义函数对象
    struct Compare {
        bool operator()(int a, int b) const {
            return a % 10 < b % 10;  // 按个位数字排序
        }
    };
    sort(v.begin(), v.end(), Compare());

    for (auto i : v) cout << i << " ";

    return 0;
}

1.24.10.4函数对象 vs 函数指针 vs Lambda

特性	函数对象	函数指针	Lambda
可携带状态	可以	不可以	可以
运行时开销	编译期内联	运行时调用	编译期内联
语法灵活	需定义类/结构体	简单	简单灵活
适用场景	需要自定义逻辑且高效	简单回调	现代简洁代码

1.24.10.5总结

• 函数对象是重载了 operator() 的类/结构体实例，行为类似函数
• STL 提供了大量常用的标准函数对象，方便自定义算法行为
• 自定义函数对象可保存状态，适合复杂逻辑和高性能场景
• 现代 C++ 中，lambda 表达式常作为函数对象的轻量替代

1.24.10.6谓词

谓词 是一种返回布尔值（bool）的函数或函数对象，用于判断条件是否成立。简单说，就是对输入做“是”或“否”判断的函数。

1. 在 C++ STL 中谓词的作用

STL 中很多算法都接受谓词作为参数，用来定义“筛选”、“比较”、“判定”等规则。例如：

• std::sort 可以传入比较谓词，决定排序规则
• std::find_if 用谓词判断元素是否满足条件
• std::count_if 用谓词统计满足条件的元素数量

2. 谓词分类

类型	说明	示例
一元谓词	接受一个参数，返回 bool，判断单个元素	bool isEven(int x)
二元谓词	接受两个参数，返回 bool，用于比较两个元素	bool less(int a, int b)

3. 示例

• 一元谓词示例

bool isEven(int x) {
    return x % 2 == 0;
}

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::find_if(v.begin(), v.end(), isEven);
if (it != v.end()) {
    std::cout << "第一个偶数是: " << *it << std::endl;
}

• 二元谓词示例（自定义比较）

bool myCompare(int a, int b) {
    return a > b;  // 降序排序
}

std::vector<int> v = {1, 3, 2, 5, 4};
std::sort(v.begin(), v.end(), myCompare);

4. 现代 C++ 中的谓词

• 函数对象（重载了 operator() 的类）常用作谓词
• Lambda 表达式 是写谓词最方便的方式

std::sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;  // 升序排序
});

5. 总结

关键词	解释
谓词	返回 bool 的函数或函数对象
一元谓词	对单个元素做判断
二元谓词	对两个元素做比较或判断
用途	用于算法的条件判断、筛选、排序

1.24.10.7算术仿函数（Arithmetic Function Objects）

1. 定义

算术仿函数是重载了 operator() 的函数对象，实现了基本的算术操作。

2. 主要类型（定义在 <functional> 中）

类型	功能
std::plus<T>	加法 a + b
std::minus<T>	减法 a - b
std::multiplies<T>	乘法 a * b
std::divides<T>	除法 a / b
std::modulus<T>	取模 a % b
std::negate<T>	取负 -a

3. 示例

#include <functional>
#include <iostream>

int main() {
    std::plus<int> add;
    std::cout << add(3, 4) << "\n";  // 输出 7

    std::negate<int> neg;
    std::cout << neg(5) << "\n";     // 输出 -5
}

1.24.10.8 关系仿函数（Relational Function Objects）

1. 定义

关系仿函数实现了常见的比较操作，返回布尔值。

2. 主要类型（定义在 <functional> 中）

类型	功能
std::equal_to<T>	等于 a == b
std::not_equal_to<T>	不等于 a != b
std::greater<T>	大于 a > b
std::less<T>	小于 a < b
std::greater_equal<T>	大于等于 a >= b
std::less_equal<T>	小于等于 a <= b

3. 示例

std::less<int> less;
bool res = less(3, 5);  // true，因为 3 < 5

1.24.10.8 逻辑仿函数（Logical Function Objects）

1. 定义

逻辑仿函数实现了逻辑运算符，返回布尔值。

2. 主要类型（定义在 <functional> 中）

类型	功能
std::logical_and<T>	逻辑与 a && b
std::logical_or<T>	逻辑或 `a
std::logical_not<T>	逻辑非 !a

3. 示例

std::logical_and<bool> land;
bool res = land(true, false);  // false，因为 true && false == false

4. 总结表

类型	头文件	功能描述	返回值类型
算术仿函数	<functional>	加减乘除等算术运算	T
关系仿函数	<functional>	大小、等于、不等于等比较运算	bool
逻辑仿函数	<functional>	逻辑与、或、非运算	bool

1.24.11lambda

Lambda 表达式是 C++11 引入的一种匿名函数（匿名函数对象），可以在定义时直接写出函数体，并且可以捕获外部变量，用来简洁地定义内联的可调用代码块。

1.24.11.1语法结构

[capture](parameters) -> return_type {
    // 函数体
};

• capture：捕获外部变量的方式（值捕获、引用捕获等）
• parameters：参数列表（类似普通函数）
• return_type（可选）：返回类型，编译器可自动推导
• 函数体：代码块

1.24.11.2捕获方式

捕获符号	说明
[]	不捕获任何外部变量
[=]	以值传递捕获所有外部变量
[&]	以引用捕获所有外部变量
[x, &y]	捕获变量 x（值），变量 y（引用）
[this]	捕获当前对象的 this 指针

1.24.11.3示例

int x = 10, y = 20;

// 值捕获
auto f1 = [=]() { return x + y; };
cout << f1() << endl;  // 输出 30

// 引用捕获
auto f2 = [&]() { x += 5; };
f2();
cout << x << endl;     // 输出 15

// 指定捕获
auto f3 = [x]() { return x * 2; };
cout << f3() << endl;  // 输出 20

// 带参数和返回值
auto f4 = [](int a, int b) -> int {
    return a + b;
};
cout << f4(3, 4) << endl;  // 输出 7

1.24.11.4常见用法

• 作为算法的回调函数

vector<int> v = {3, 1, 4, 2};
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // 降序排序
});

• 立即调用（IIFE）

int result = [](int a, int b) { return a + b; }(5, 7);
cout << result << endl;  // 12

• 保存状态（可变 lambda）

int count = 0;
auto counter = [count]() mutable {
    return ++count;
};
cout << counter() << endl;  // 1
cout << counter() << endl;  // 2

1.24.11.5细节补充

• mutable：允许修改捕获的变量副本（值捕获时默认是 const）
• 返回类型省略：如果函数体只有一条 return 语句，编译器会自动推导返回类型
• lambda 是闭包类型：编译器会为每个 lambda 生成一个唯一的匿名类

1.24.11.6总结

优点	说明
语法简洁	内联定义函数，减少代码量
支持捕获外部变量	灵活访问作用域外数据
可以作为回调和算法参数	提高代码可读性和复用性
支持修改捕获变量（mutable）	控制值捕获变量的可变性
编译器优化好	无额外函数调用开销

1.24.11.7C++20改进

1. 模板化 Lambda（泛型 Lambda 的增强）

C++14 就支持了泛型 lambda，参数使用 auto，但 C++20 允许直接声明模板参数，写法更清晰，支持模板约束。

auto lambda = []<typename T>(T a) {
    return a;
};

cout << lambda(42) << endl;    // 42
cout << lambda("hello") << endl; // hello

• 你甚至可以写模板参数约束：

auto lambda = []<typename T>(T a) requires std::is_integral_v<T> {
    return a * 2;
};

2. 默认构造的 lambda（隐式默认构造）

在 C++20 中，如果 lambda 捕获的变量都支持默认构造，lambda 本身也变得可以默认构造（以前的标准不支持）。

3. lambda 可以在 unevaluated context 使用

这使得你可以在 decltype 等不求值上下文中使用 lambda 类型，方便类型推导和模板编程。

4. lambda 的捕获扩展

C++20 允许更灵活的捕获语法：

• 支持捕获模板参数：

template<typename T>
void foo(T val) {
    auto lam = [val]() {
        return val;
    };
}

• 还有“捕获包”（capture pack）：

template<typename... Args>
auto lam = [args = std::tuple<Args...>{}]() {
    // 使用捕获的参数包
};

5. constexpr lambda

C++20 标准允许 lambda 完全是 constexpr，意味着你可以在编译期执行 lambda 函数。

constexpr auto lam = [](int x) {
    return x * x;
};

static_assert(lam(5) == 25);

6. 额外补充

• 改进的闭包类型：C++20 标准中 lambda 的闭包类型更规范，允许更多编译期推导和优化。
• 模板 lambda 支持折叠表达式和概念，让模板元编程更强大灵活。

特性	说明
模板化 lambda	直接写模板参数，支持约束
默认构造 lambda	捕获支持默认构造时，lambda 可默认构造
unevaluated context	可在 decltype 等上下文使用
捕获扩展	支持模板参数捕获及捕获包
constexpr lambda	lambda 支持 constexpr，可编译期执行

1.24.12常用遍历算法

算法	功能描述	使用示例
std::for_each	遍历区间中的每个元素并执行操作	输出、累加、修改等
std::transform	元素转换，结果写入另一容器	乘2、转大小写、类型转换
std::find	查找第一个等于某值的元素	find(v.begin(), v.end(), 10)
std::find_if	查找第一个满足谓词的元素	find_if(v.begin(), v.end(), ...)
std::count	统计等于某值的元素数量	count(v.begin(), v.end(), 5)
std::count_if	统计满足条件的元素数量	count_if(v.begin(), v.end(), ...)
std::all_of	所有元素都满足条件	全部大于0？
std::any_of	有任意一个元素满足条件	有偶数？
std::none_of	所有元素都不满足条件	都不是负数？

1.24.12.1 std::for_each

std::vector<int> v = {1, 2, 3, 4};
std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
});

✅ 优点：代码简洁、适配 lambda，很适合输出、打印等。

---

1.24.12.2std::transform

std::vector<int> v = {1, 2, 3};
std::vector<int> result(v.size());

std::transform(v.begin(), v.end(), result.begin(), [](int x) {
    return x * x;
});

✅ 将一个容器映射成另一个容器，是“映射变换”的代表。

1.24.12.3 std::find

auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) std::cout << "找到了：" << *it;

1.24.12.4std::find_if

auto it = std::find_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});

✅ 用谓词找满足条件的元素

1.24.12.5std::count / std::count_if

int cnt = std::count(v.begin(), v.end(), 2);  // 统计值为 2 的个数

int even = std::count_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});

1.24.12.6std::all_of / std::any_of / std::none_of

bool allPositive = std::all_of(v.begin(), v.end(), [](int x) {
    return x > 0;
});

bool hasZero = std::any_of(v.begin(), v.end(), [](int x) {
    return x == 0;
});

bool noneNegative = std::none_of(v.begin(), v.end(), [](int x) {
    return x < 0;
});

✅ 这类函数通常用于快速做“是否满足条件”的判断。

1.24.12.7适配器补充（配合遍历使用）

• std::back_inserter：用于 transform 时向空容器插入元素
• std::bind / std::function / lambda：可生成自定义谓词

1.24.13常用查找算法

1.24.13.1通用查找算法

算法	用法示例	时间复杂度	说明
std::find	std::find(v.begin(), v.end(), x)	O(n)	顺序查找，适用于所有容器
std::find_if	std::find_if(v.begin(), v.end(), pred)	O(n)	带条件的查找
std::find_if_not	std::find_if_not(v.begin(), v.end(), pred)	O(n)	找第一个不满足条件的
std::binary_search	std::binary_search(v.begin(), v.end(), x)	O(log n)	二分查找，要求已排序
std::lower_bound	std::lower_bound(v.begin(), v.end(), x)	O(log n)	返回 ≥ x 的第一个位置
std::upper_bound	std::upper_bound(v.begin(), v.end(), x)	O(log n)	返回 > x 的第一个位置
std::equal_range	std::equal_range(v.begin(), v.end(), x)	O(log n)	返回一对迭代器 [lower, upper)

1.24.13.2关联容器（自动排序的，如 set, map）

容器	方法	时间复杂度	说明
std::set, std::map	s.find(x)	O(log n)	二叉平衡树，返回迭代器
	s.count(x)	O(log n)	是否存在（多重容器可统计数量）
	s.lower_bound(x)	O(log n)	≥ x 的迭代器
	s.upper_bound(x)	O(log n)	> x 的迭代器
	s.equal_range(x)	O(log n)	返回 pair<lower, upper>

1.24.13.3无序关联容器（哈希表，如 unordered_map）

容器	方法	时间复杂度（平均）	说明
std::unordered_map, std::unordered_set	m.find(x)	O(1)	哈希查找，最快
	m.count(x)	O(1)	判断是否存在
	m.contains(x) (C++20+)	O(1)	更简洁地判断是否存在

1.24.13.4其他 STL 容器查找（如 vector, deque, list）

• std::vector, std::deque：
  • 使用 std::find 进行顺序查找；
  • 如果排序了，可以用 std::binary_search、lower_bound 等。
• std::list：
  • 只能顺序查找（不支持随机访问），使用 std::find；
  • 不适合做二分查找。

1.24.13.5小结对比表

场景	推荐算法	要求
无序数组中找某值	std::find	无需排序
查找第一个满足条件的元素	std::find_if	可自定义谓词
有序容器中判断是否存在	std::binary_search	要求排序
有序容器中找插入位置	std::lower_bound / std::upper_bound	要求排序
set/map 查找元素	.find()	自动平衡树
unordered_map 查找元素	.find() / .contains()	哈希，最快

1.24.14常用排序算法

算法	用法示例	时间复杂度	稳定性	说明
std::sort	std::sort(v.begin(), v.end())	O(n log n)	❌ 不稳定	默认排序算法，基于 IntroSort（快速+堆+插排）
std::stable_sort	std::stable_sort(v.begin(), v.end())	O(n log² n) 最坏 / O(n log n) 平均	✅ 稳定	基于 MergeSort，保留相等元素相对顺序
std::partial_sort	std::partial_sort(v.begin(), v.begin()+k, v.end())	O(n log k)	❌ 不稳定	把前 k 个元素排序，其余部分无序
std::partial_sort_copy	std::partial_sort_copy(src.begin(), src.end(), dst.begin(), dst.end())	O(n log k)	❌ 不稳定	拷贝并排序前 k 个最小值到另一个容器
std::nth_element	std::nth_element(v.begin(), v.begin()+k, v.end())	O(n) 平均 / O(n²) 最坏	❌ 不稳定	将第 k 小的元素放在正确位置，左边比它小，右边比它大，但左右未排序
std::is_sorted	std::is_sorted(v.begin(), v.end())	O(n)	-	判断是否已排序
std::is_sorted_until	std::is_sorted_until(v.begin(), v.end())	O(n)	-	返回未排序的第一个位置

1.24.14.1说明与建议

std::sort

• 最快通用排序，底层是 IntroSort：快速排序 + HeapSort + 插入排序。
• 默认使用 <，可传入比较器（如 std::greater<int>() 变为降序）。

std::stable_sort

• 相等元素顺序不会变，适合按多条件排序（如先按成绩，成绩相同再按名字）。
• 稳定但比 std::sort 慢。

std::partial_sort

• 常用于只需前 K 个最小（或最大）元素排序，效率高于完整排序。

std::nth_element

• 不排序整个数组，仅找出第 n 小的元素，适合Top-K 场景。
• 比如快速找第 K 大成绩，不需要完整排序。

1.24.14.2示例代码片段

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {7, 2, 5, 3, 9, 1};

    std::sort(v.begin(), v.end()); // 升序排序

    std::stable_sort(v.begin(), v.end()); // 稳定排序

    std::nth_element(v.begin(), v.begin() + 2, v.end()); // 找第3小的元素

    std::partial_sort(v.begin(), v.begin() + 3, v.end()); // 前3个最小值排序
}

1.24.14.3使用场景

目的 / 场景	推荐算法
完整排序、速度优先	std::sort
完整排序、保留相对顺序	std::stable_sort
获取前 k 个最小值（且排序）	std::partial_sort
获取第 k 小的元素（无序也可）	std::nth_element
判断是否已排序	std::is_sorted

1.24.15常用拷贝和替换算法

1.24.15.1STL 常用拷贝和替换算法

算法	用法	时间复杂度	功能说明
std::copy	copy(src.begin(), src.end(), dst.begin())	O(n)	将区间元素复制到目标位置
std::copy_if	copy_if(src.begin(), src.end(), dst.begin(), pred)	O(n)	满足条件的元素复制
std::copy_n	copy_n(src.begin(), n, dst.begin())	O(n)	拷贝指定个数元素
std::move	move(src.begin(), src.end(), dst.begin())	O(n)	移动语义，可减少拷贝开销
std::swap	swap(a, b)	O(1)	两个变量/容器交换值
std::swap_ranges	swap_ranges(a.begin(), a.end(), b.begin())	O(n)	两个范围元素对应交换
std::replace	replace(v.begin(), v.end(), old_val, new_val)	O(n)	替换所有等于某值的元素
std::replace_if	replace_if(v.begin(), v.end(), pred, new_val)	O(n)	满足条件的元素被替换
std::replace_copy	replace_copy(src.begin(), src.end(), dst.begin(), old_val, new_val)	O(n)	拷贝 + 替换（不修改原容器）
std::replace_copy_if	replace_copy_if(src.begin(), src.end(), dst.begin(), pred, new_val)	O(n)	条件替换+拷贝

1.24.15.2示例代码片段

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    std::vector<int> dst(6);

    std::copy(v.begin(), v.end(), dst.begin());             // 拷贝
    std::copy_if(v.begin(), v.end(), dst.begin(), [](int x){ return x % 2 == 0; }); // 拷贝偶数

    std::replace(v.begin(), v.end(), 2, 20);                 // 替换值 2 -> 20
    std::replace_if(v.begin(), v.end(), [](int x){ return x > 4; }, 99); // 条件替换

    std::replace_copy(v.begin(), v.end(), dst.begin(), 1, 100); // 拷贝 + 替换
}

1.24.15.3使用建议

需求	推荐算法
复制整个序列	std::copy
条件复制	std::copy_if
拷贝前 N 项	std::copy_n
移动对象所有权（如 std::string）	std::move
替换某个值	std::replace
条件替换	std::replace_if
替换的同时保留原序列	std::replace_copy / replace_copy_if

1.24.15.4特别说明：copy vs move

特点	std::copy	std::move
行为	拷贝元素（复制构造）	移动元素（移动构造）
是否清空原对象	❌ 否	✅ 是（原对象变为空）
用途	保留源数据	转移所有权以优化性能

1.24.16常用算术生成算法

算法	用法	头文件	时间复杂度	功能说明
std::accumulate	accumulate(v.begin(), v.end(), init)	<numeric>	O(n)	累加求和或自定义二元操作
std::inner_product	inner_product(a.begin(), a.end(), b.begin(), init)	<numeric>	O(n)	求两个序列的点积
std::adjacent_difference	adjacent_difference(v.begin(), v.end(), out.begin())	<numeric>	O(n)	邻接差值（前后元素之差）
std::partial_sum	partial_sum(v.begin(), v.end(), out.begin())	<numeric>	O(n)	前缀和（累加序列）
std::iota	iota(v.begin(), v.end(), start_val)	<numeric>	O(n)	用连续递增值填充容器
std::generate	generate(v.begin(), v.end(), gen)	<algorithm>	O(n)	使用生成器函数填充容器
std::generate_n	generate_n(out.begin(), n, gen)	<algorithm>	O(n)	调用生成器函数 n 次填充数据
std::transform	transform(src.begin(), src.end(), dst.begin(), op)	<algorithm>	O(n)	对每个元素应用函数，写入结果
std::transform (双输入)	transform(a.begin(), a.end(), b.begin(), dst.begin(), op)	<algorithm>	O(n)	元素对组合处理（如加法）

1.24.16.1示例代码

#include <iostream>
#include <vector>
#include <numeric>      // accumulate, iota, inner_product, partial_sum
#include <algorithm>    // generate, transform

int main() {
    std::vector<int> v(5);

    std::iota(v.begin(), v.end(), 1);   // v = [1, 2, 3, 4, 5]

    int sum = std::accumulate(v.begin(), v.end(), 0); // sum = 15

    std::vector<int> prefix(v.size());
    std::partial_sum(v.begin(), v.end(), prefix.begin()); // prefix = [1, 3, 6, 10, 15]

    std::vector<int> diff(v.size());
    std::adjacent_difference(v.begin(), v.end(), diff.begin()); // diff = [1, 1, 1, 1, 1]

    std::vector<int> squares(5);
    std::generate(squares.begin(), squares.end(), [n = 1]() mutable { return n * n++; }); // [1,4,9,16,25]

    std::vector<int> result(5);
    std::transform(v.begin(), v.end(), result.begin(), [](int x) { return x * 10; }); // 每个 *10
}

1.24.16.2使用建议总结

场景	推荐算法
累加求和	std::accumulate
累乘、字符串拼接、复杂计算	accumulate + 自定义 lambda
点积（如数学向量）	std::inner_product
求前缀和	std::partial_sum
求相邻差	std::adjacent_difference
填充顺序数字	std::iota
自动生成数据（如随机数）	std::generate, generate_n
元素变换（如平方）	std::transform
两数组元素对处理	std::transform（双输入）

1.24.16.3注意事项

• std::accumulate 默认操作是加法，可以改为乘法或其他二元操作。
• std::iota 填充的是值，不支持生成表达式；想生成自定义数据请用 std::generate。
• std::transform 是 map 操作的 STL 实现，效率高于手写 for 循环。

1.24.17常用集合算法

1.24.17.1STL 常用集合算法一览

算法	作用	时间复杂度	要求
std::set_union	并集 A ∪ B	O(n)	两个区间都已排序
std::set_intersection	交集 A ∩ B	O(n)	两个区间都已排序
std::set_difference	差集 A − B	O(n)	两个区间都已排序
std::set_symmetric_difference	对称差 (A ∪ B) − (A ∩ B)	O(n)	两个区间都已排序
std::includes	判断包含关系 (B ⊆ A)	O(n)	都已排序
std::equal	判断两个区间内容相等	O(n)	可无序
std::lexicographical_compare	字典序比较	O(n)	常用于排序嵌套集合

✅ 所有以 set_ 开头的算法都不要求容器是 std::set，但要求输入区间已排序！

1.24.17.2示例代码（以 vector<int> 为例）

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> B = {3, 4, 5, 6, 7};
    std::vector<int> result;

    // 并集
    result.clear();
    std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result));
    // result: [1,2,3,4,5,6,7]

    // 交集
    result.clear();
    std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result));
    // result: [3,4,5]

    // 差集 A - B
    result.clear();
    std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result));
    // result: [1,2]

    // 对称差
    result.clear();
    std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result));
    // result: [1,2,6,7]

    // 判断 B 是否包含于 A（false）
    bool isSubset = std::includes(A.begin(), A.end(), B.begin(), B.end());
}

1.24.17.3使用建议

需求	推荐算法	是否排序要求
求并集	std::set_union	✅ 需要排序
求交集	std::set_intersection	✅
求差集	std::set_difference	✅
求对称差	std::set_symmetric_difference	✅
判断子集	std::includes	✅
判断内容一致	std::equal	❌（元素顺序必须一致）
字典序比较	std::lexicographical_compare	✅

1.24.17.4注意事项

• 所有 set_* 算法都只适用于已排序区间。无序容器（如 unordered_set）不能直接使用，除非先排序。
• 输出容器需要事先 reserve 或使用 std::back_inserter 等输出迭代器。
• 自定义类型需提供 < 运算符或传入比较函数。

1.24.17.5扩展建议

• 想处理实际 std::set / std::unordered_set 结构，可以用它们的成员函数或转换成 vector 并排序后使用这些算法。
• 你也可以使用 std::ranges::set_*（C++20）版本，更安全易读。

2.CMakeLists项目配置

2.1使用vcpkg包管理器

vcpkg.json

{
  "name": "test",
  "version-string": "0.1.0",
  "dependencies": [
    "boost",
    "libmariadb"
  ],
  "builtin-baseline": "984f9232b2fe0eb94f5e9f161d6c632c581fff0c"
}

添加builtin-baseline：

vcpkg x-add-version

builtin-baseline作用：

用于指定 vcpkg 仓库的某个提交（commit SHA），保证团队每次安装的依赖版本都是一致的

2.2CMakePresets.json

{
    "version": 3,
    "configurePresets": [
        {
            "name": "windows-base",
            "hidden": true,
            "generator": "Ninja",
            "binaryDir": "${sourceDir}/out/build/${presetName}",
            "installDir": "${sourceDir}/out/install/${presetName}",
          "cacheVariables": {
            "CMAKE_C_COMPILER": "cl.exe",
            "CMAKE_CXX_COMPILER": "cl.exe",
            "CMAKE_TOOLCHAIN_FILE": "C:/Program Files/Microsoft Visual Studio/2022/Community/VC/vcpkg/scripts/buildsystems/vcpkg.cmake",
            "VCPKG_TARGET_TRIPLET": "x64-windows"
          },
            "condition": {
                "type": "equals",
                "lhs": "${hostSystemName}",
                "rhs": "Windows"
            }
        },
        {
            "name": "x64-debug",
            "displayName": "x64 Debug",
            "inherits": "windows-base",
            "architecture": {
                "value": "x64",
                "strategy": "external"
            },
          "cacheVariables": {
            "CMAKE_BUILD_TYPE": "Debug"
          }
        },
        {
            "name": "x64-release",
            "displayName": "x64 Release",
            "inherits": "x64-debug",
            "cacheVariables": {
                "CMAKE_BUILD_TYPE": "Release"
            }
        },
        {
            "name": "x86-debug",
            "displayName": "x86 Debug",
            "inherits": "windows-base",
            "architecture": {
                "value": "x86",
                "strategy": "external"
            },
            "cacheVariables": {
                "CMAKE_BUILD_TYPE": "Debug"
            }
        },
        {
            "name": "x86-release",
            "displayName": "x86 Release",
            "inherits": "x86-debug",
            "cacheVariables": {
                "CMAKE_BUILD_TYPE": "Release"
            }
        },
        {
            "name": "linux-debug",
            "displayName": "Linux Debug",
            "generator": "Ninja",
            "binaryDir": "${sourceDir}/out/build/${presetName}",
            "installDir": "${sourceDir}/out/install/${presetName}",
            "cacheVariables": {
                "CMAKE_BUILD_TYPE": "Debug"
            },
            "condition": {
                "type": "equals",
                "lhs": "${hostSystemName}",
                "rhs": "Linux"
            },
            "vendor": {
                "microsoft.com/VisualStudioRemoteSettings/CMake/1.0": {
                    "sourceDir": "$env{HOME}/.vs/$ms{projectDirName}"
                }
            }
        },
        {
            "name": "macos-debug",
            "displayName": "macOS Debug",
            "generator": "Ninja",
            "binaryDir": "${sourceDir}/out/build/${presetName}",
            "installDir": "${sourceDir}/out/install/${presetName}",
            "cacheVariables": {
                "CMAKE_BUILD_TYPE": "Debug"
            },
            "condition": {
                "type": "equals",
                "lhs": "${hostSystemName}",
                "rhs": "Darwin"
            },
            "vendor": {
                "microsoft.com/VisualStudioRemoteSettings/CMake/1.0": {
                    "sourceDir": "$env{HOME}/.vs/$ms{projectDirName}"
                }
            }
        }
    ]
}

2.2.1使用方式

2.2.1.1配置（生成构建文件）

cmake --preset default

这等价于运行：

cmake -S . -B out/build/default -G Ninja \
  -DCMAKE_BUILD_TYPE=Debug \
  -DCMAKE_TOOLCHAIN_FILE=.../vcpkg.cmake

2.2.1.2编译（构建项目）

cmake --build --preset default

等价于：

cmake --build out/build/default

2.2.1.3安装（如果你写了 install）

cmake --install --preset default

2.2.1.4查看所有预设

cmake --list-presets

2.2.1.5 VS 支持

Visual Studio 2022 原生支持 CMakePresets.json：

• 打开 CMake 项目时，它会自动识别该文件。
• 你可以在「配置」下拉中看到每个 preset，比如 x64-debug、linux-debug 等。

2.2.1.6配合 vcpkg.json 使用

没问题，完全支持。只要你 preset 中加入：

"cacheVariables": {
  "CMAKE_TOOLCHAIN_FILE": "path/to/vcpkg/scripts/buildsystems/vcpkg.cmake",
  "VCPKG_TARGET_TRIPLET": "x64-windows"
}

2.3CMakeLists.txt配置

cmake_minimum_required(VERSION 3.20)  # 提升版本，兼容新策略和功能

project(CMakeProject2 LANGUAGES CXX)

# 解决 FindBoost 模块废弃的警告
cmake_policy(SET CMP0167 NEW)

# MSVC 热重载设置（保持原有逻辑）
if (POLICY CMP0141)
  cmake_policy(SET CMP0141 NEW)
  set(CMAKE_MSVC_DEBUG_INFORMATION_FORMAT
    "$<IF:$<AND:$<C_COMPILER_ID:MSVC>,$<CXX_COMPILER_ID:MSVC>>,
       $<$<CONFIG:Debug,RelWithDebInfo>:EditAndContinue>,
       $<$<CONFIG:Debug,RelWithDebInfo>:ProgramDatabase>>")
endif()


message(STATUS "Boost_INCLUDE_DIRS: ${Boost_INCLUDE_DIRS}")
message(STATUS "Boost_LIBRARIES: ${Boost_LIBRARIES}")

# 让 find_package 用 vcpkg 的 config 模式找 Boost
# 这样能自动找到 vcpkg 安装路径和头文件库文件
find_package(Boost CONFIG REQUIRED COMPONENTS program_options)

add_executable(CMakeProject2)

# 搜集源文件
file(GLOB_RECURSE CPP_LIST src/*.cpp)
target_sources(CMakeProject2 PRIVATE ${CPP_LIST})

# 头文件路径（vcpkg 会自动处理 Boost_INCLUDE_DIRS，但你自定义的 src 目录要加）
target_include_directories(CMakeProject2 PRIVATE ${CMAKE_SOURCE_DIR}/src)

# 链接 Boost 库，使用命名目标
target_link_libraries(CMakeProject2 PRIVATE Boost::program_options)

# 设置 C++ 标准
set_property(TARGET CMakeProject2 PROPERTY CXX_STANDARD 20)
set_property(TARGET CMakeProject2 PROPERTY CXX_STANDARD_REQUIRED ON)
set_property(TARGET CMakeProject2 PROPERTY CXX_EXTENSIONS OFF)

2.4执行过程

1. cmake使用CMakePresets.json生成cmake命令行参数

2. 读取DCMAKE_TOOLCHAIN_FILE使用vcpkg.json安装依赖

3. 执行CMakeLists.txt构建make命令

4. 项目构建