关于变量
常量
1
2
3
4
5
|
const typename var = val; 声明常量
char * const p 表示指针 p 指向的位置不能改变，但是指向的内容（一个 char）可以改变
const char *p 表示指针 p 指向的内容不能改变，但是指向的位置可以改变
char const *p 同理等价
const char * const p p 指向的位置和内容都不能修改
|
动态内存
使用 new 分配，创建对象，返回指针
1
2
3
|
T *p = new T[N] 分配 N 个 T 类型的对象，返回指向第一个对象的指针
delete p 释放 p 指向的内存 p 本身不会变为 NULL
delete[] p 释放 p 指向的内存
|
关于类
-C++ 中 class 和 struct 并无本质区别，只是默认的访问权限不同（class 默认 private，struct 默认 public）
:: 称为域解析器（resolver），前面什么都不带则解析到自由变量 / 函数（即全局作用域内）
成员函数直接在类内部定义的话默认为 inline（不推荐）
权限有三种：
public：公有
private：私有（只有同类可以访问）
注意边界是类不是对象，成员函数中可以访问同一类的其他对象的私有成员
protected：保护（只有同类和子类可以访问）
构造函数
-
命名与类名完全相同
构造函数名称必须与类名一致，无返回值（包括 void）。
-
自动调用
对象创建时由编译器自动调用，无需显式调用。
-
可重载
支持多个构造函数，通过参数列表（类型、数量、顺序）区分。
-
访问控制
可设为 public、protected 或 private，影响对象创建方式（如单例模式）。
-
语法
以冒号 : 开头，后跟成员变量及其初始化表达式：
1
2
3
4
5
6
7
|
class Student {
public:
Student(int id, const string& name) : studentId(id), studentName(name) {}
private:
const int studentId; // 必须使用初始化列表
string studentName;
};
|
必要性
- 对const成员、引用成员、无默认构造函数的类成员必须使用初始化列表。
- 提高性能：避免先默认初始化再赋值的额外开销。
运算符重载
运算符重载通过定义operator函数实现，支持大部分内置运算符（如+、-、==等），但部分运算符（如.、::、?:）不可重载。
示例：
1
2
3
4
5
6
|
class Complex {
public:
Complex operator+(const Complex& other) {
return Complex(real + other.real, imag + other.imag);
}
};
|
若不是类对象之间的相加时，可以通过以下方法实现：
1
2
3
4
5
6
|
class Complex {
public:
Complex operator+(int num) {
return Complex(this->real + num);
}
};
|
该方法可以实现int在右侧相加，若int在左侧时则需通过全局函数或友元函数重载，因成员函数无法让int作为左操作数
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class MyClass {
public:
int value;
MyClass(int v) : value(v) {}
// 声明友元函数以访问私有成员（如果需要）
friend MyClass operator+(int num, const MyClass& obj);
};
// 全局函数重载：处理 int + MyClass
MyClass operator+(int num, const MyClass& obj) {
return MyClass(num + obj.value);
}
// 使用示例
MyClass c = 3 + a; // 调用全局函数
|
处理自增自减时格式略有不同，但是不难理解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Number {
public:
int value;
Number(int v = 0) : value(v) {}
// 前置++
Number& operator++() {
++value;
return *this;
}
// 后置++
Number operator++(int) {
Number temp = *this;
++value;
return temp;
}
};
|
流运算符重载
流运算符用于自定义类型与输入输出流的交互，使对象可直接通过cout输出或cin输入。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Point {
public:
friend ostream& operator<<(ostream& os, const Point& p) {
os << "(" << p.x << ", " << p.y << ")";
return os;
}
friend istream& operator>>(istream& is, Point& p) {
is >> p.x >> p.y;
return is;
}
private:
int x, y;
};
|
虚函数
学的时候感觉挺简单的，好久不用搞忘了，还是写点笔记吧。
虚函数主要提供 运行时多态，它让 C++ 程序能够根据对象的实际类型来调用函数，而不是根据指针/引用的静态类型。
换句话说：
这样，我们可以写出通用接口，在不同子类里实现不同的行为。
多态
比如基类 Shape 定义 draw()，不同子类（Circle、Rectangle）都可以重写自己的 draw()，运行时调用时自动选择正确的函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
using namespace std;
class Shape {
public:
virtual void draw() { cout << "Draw Shape\n"; }
};
class Circle : public Shape {
public:
void draw() override { cout << "Draw Circle\n"; } //override用来标记“派生类中的虚函数是对基类虚函数的重写”
};
class Rectangle : public Shape {
public:
void draw() override { cout << "Draw Rectangle\n"; }
};
int main() {
Shape* s1 = new Circle();
Shape* s2 = new Rectangle();
s1->draw(); // Draw Circle
s2->draw(); // Draw Rectangle
delete s1;
delete s2;
}
|
抽象接口（纯虚函数）
虚函数可以被定义为 纯虚函数（=0），使类变为 抽象类，只能作为接口存在，不能直接实例化。
派生类必须实现纯虚函数。
1
2
3
4
5
6
7
8
9
|
class Animal {
public:
virtual void speak() = 0; // 纯虚函数
};
class Dog : public Animal {
public:
void speak() override { cout << "Woof!\n"; }
};
|
正确的析构函数调用
如果基类的析构函数是虚函数，那么通过基类指针删除派生类对象时，会 先调用派生类析构，再调用基类析构 ，避免资源泄漏。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Base {
public:
virtual ~Base() { cout << "Base destroyed\n"; }
};
class Derived : public Base {
public:
~Derived() { cout << "Derived destroyed\n"; }
};
int main() {
Base* b = new Derived();
delete b;
}
|
如果析构函数不是虚函数，只会调用 Base::~Base，导致 Derived 部分资源泄露。
哈希表
严格意义上来说不算c++的版块，但是刷题的时候碰到了，就顺便记一下。
哈希表是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数。
哈希表通常使用一个数组作为底层存储，数组的每个元素称为一个桶（bucket），它的核心思想是 用空间换时间,所以它的 插入、删除、查找操作的平均时间复杂度都是 O(1)。在实际应用中，C++ STL 提供的 std::unordered_map 和 std::unordered_set 已经实现了高效、健壮的哈希表，通常不需要我们自己去实现。
简单一点的实现是：
std::unordered_set (集合)
用于快速查找一个元素是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#include <string>
#include <unordered_set> // 引入unordered_set
int main() {
// 1. 创建一个空的 unordered_set，存储字符
std::unordered_set<char> brokenSet;
// 2. 插入元素 (相当于添加学号)
brokenSet.insert('a');
brokenSet.insert('b');
brokenSet.insert('c');
brokenSet.insert('a'); // 重复插入 'a'，但 set 只会保留一个 'a'
// 3. 检查元素是否存在
char letterToFind = 'b';
if (brokenSet.count(letterToFind)) { // count() 返回 1 如果存在, 0 如果不存在
std::cout << "'" << letterToFind << "' 存在于集合中。" << std::endl;
} else {
std::cout << "'" << letterToFind << "' 不存在于集合中。" << std::endl;
}
letterToFind = 'd';
if (brokenSet.count(letterToFind)) {
std::cout << "'" << letterToFind << "' 存在于集合中。" << std::endl;
} else {
std::cout << "'" << letterToFind << "' 不存在于集合中。" << std::endl;
}
// 4. 用一个字符串初始化 set
std::string brokenLetters = "xyz";
std::unordered_set<char> brokenSetFromString(brokenLetters.begin(), brokenLetters.end());
if (brokenSetFromString.count('y')) {
std::cout << "'y' 存在于从字符串创建的集合中。" << std::endl;
}
return 0;
}
|
std::unordered_map (键值对映射)
用于根据一个键快速查找对应的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <string>
#include <unordered_map> // 引入unordered_map
int main() {
// 1. 创建一个空的 unordered_map，存储 string 到 int 的映射
std::unordered_map<std::string, int> studentScores;
// 2. 插入键值对
studentScores.insert({"Alice", 95});
studentScores["Bob"] = 88; // 另一种插入方式
studentScores["Charlie"] = 92;
// 3. 通过键查找值
std::string studentName = "Alice";
// 使用 find() 查找，它返回一个迭代器
auto it = studentScores.find(studentName);
if (it != studentScores.end()) { // 如果找到了 (迭代器不是指向末尾)
std::cout << studentName << " 的分数是: " << it->second << std::endl; // it->second 是值
} else {
std::cout << studentName << " 不存在。" << std::endl;
}
studentName = "David";
if (studentScores.find(studentName) != studentScores.end()) {
std::cout << studentName << " 的分数是: " << studentScores[studentName] << std::endl; // studentName.score 也可以直接访问
} else {
std::cout << studentName << " 不存在。" << std::endl;
}
// 4. 尝试访问不存在的键（如果用 [] 访问）
// 注意：如果键不存在，[] 会自动创建一个键值对，值是默认初始化的（int是0）
// std::cout << "David 的分数 (创建后): " << studentScores["David"] << std::endl; // 这行会使 David 出现，分数为 0
return 0;
}
|
一些小tips
实在没招了，不记要忘。。。
读取输入
一般来说读取字符串用 getline() 就行，如果想要读到一个整型数组，还需要进行输入流处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main() {
string line;
getline(cin, line); // 读取一整行，例如：2 3 1 4 5 6
istringstream iss(line); // 把字符串当作输入流来处理
vector<int> nums;
int x;
while (iss >> x) { // 跳过空格等分隔符取整数，直到取完
nums.push_back(x);
}
// 测试输出
cout << "输入的数组: ";
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}
|
内存分区
在 C++ 中，内存分区是绕不开的核心概念之一。通常情况下，程序的内存空间会被划分为四个主要区域（由低地址到高地址）：
- 代码区
- 数据区
- 堆区
- 栈区
栈区（Stack）
- 分配方式：由程序自动向操作系统申请和回收，速度快、使用方便，但程序员无法直接控制。
- 空间大小：一般在几 MB ~ 几十 MB。若递归过深或数组过大，可能触发 栈溢出（stack overflow）。
- 遵循原则：后进先出（LIFO）。
存储内容包括：
const 局部变量- 函数参数
- 函数返回地址
- 保存的寄存器（如返回地址、帧指针等）
生命周期管理：
当变量进入作用域时，系统会在栈上为其申请空间；当变量生命周期结束，系统会自动释放这部分内存。
堆区（Heap）
- 分配方式：由程序员手动申请（如
new、malloc），并且需要手动释放（delete、free）。
- 空间大小：通常远大于栈，可达 MB ~ GB 级，一般是能申请多少就有多少，实际可用大小取决于操作系统和物理内存。
- 存储结构：不像栈是连续空间，堆的分配通过 链表/空闲块表 管理，因此可能产生 内存碎片。
如果忘记释放，容易导致 内存泄漏。
数据区（Data Segment）
分为两部分：
-
已初始化数据区
存放 已显式初始化 的全局变量和静态变量。
1
2
|
int g1 = 10; // 已初始化全局变量
static int s1 = 20; // 已初始化静态变量
|
-
未初始化数据区（BSS 段）
存放 未初始化 的全局变量和静态变量，程序运行时会自动初始化为 0。
1
2
|
int g2; // 未初始化全局变量
static int s2; // 未初始化静态变量
|
代码区（Code/Text Segment）
- 存放内容：程序的可执行代码（机器指令）。
- 只读属性：大多数系统中，代码区是只读的，防止程序意外修改自身指令。
- 共享机制：相同程序的多个进程可以共享代码区，提高效率。
💡 关于 常量：
有些实现会将只读常量放在单独的常量区（位于代码区和数据区之间）；也有实现直接把常量划归到代码区。无论哪种方式，常量区都是只读的。
示例图：
内存参考链接
算法
本人实在懒得开新贴了，还是在这里写吧。
KMP
一个人能能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。 ——KMP (from 高赞回答)
KMP算法是一种用于字符串匹配的高效算法，其基本思想是利用已经匹配的部分信息来避免不必要的回退。
先给出代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
std::vector<int> build_next(const std::string& patt) {
// 功能：计算 KMP 算法所需的 next 数组（部分匹配表）
std::vector<int> next;
next.push_back(0); // next 数组 (初值元素一个 0)
int prefix_len = 0; // 当前共同前后缀的长度
int i = 1;
while (i < patt.length()) {
if (patt[prefix_len] == patt[i]) {
prefix_len += 1;
next.push_back(prefix_len);
i += 1;
} else {
if (prefix_len == 0) {
next.push_back(0);
i += 1;
} else {
// 关键：回溯，寻找更短的共同前后缀
prefix_len = next[prefix_len - 1];
}
}
}
return next;
}
int kmp_search(const std::string& text, const std::string& patt) {
// 功能：在主串(text)中查找子串(patt)的第一次出现的位置
if (patt.empty()) {
return 0;
}
if (text.length() < patt.length()) {
return -1;
}
std::vector<int> next = build_next(patt);
int i = 0; // 主串中的指针
int j = 0; // 子串中的指针
while (i < text.length()) {
if (text[i] == patt[j]) { // 字符匹配，指针后移
i += 1;
j += 1;
} else if (j > 0) { // 字符失配，根据 next 跳过子串前面的一些字符
j = next[j - 1];
} else { // 子串第一个字符就失配
i += 1;
}
if (j == patt.length()) { // 匹配成功
return i - j;
}
}
return -1; // 遍历完主串后仍未找到，返回 -1
}
|
不过要注意的是不同的资料对next的定义可能略有不同，我上面写的是我自己觉得好理解的算法，仅供参考。
本人的拙见：首先next存储的是子串每个下标截止的最长相同前后缀，比如ABA，next[2]为1，同时next存储的也是主函数中能跳过字符的个数，能跳过的原因也是因为相同前后缀，比如在ABABABCAA中寻找ABABC，对应的next数组为[0,0,1,2,0],第一次回溯时，j从4变为2，这是因为主串和字串中同有ABAB的形式，因此可以跳过两个字符串
快速排序和归并排序
前者平均时间复杂度为 O(Nlog N) ，最坏 O(N^2)；后者稳定 O(Nlog N)。
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <vector>
#include <algorithm> // 包含 std::swap
/**
* 分区函数：选择一个基准值（这里选择最右边的元素,实际应用应该是随机选择数组内的数），
* 并将所有小于等于它的元素移到左边，大于它的元素移到右边。
* 最后将基准值放在正确的位置，并返回其索引。
*
* @param arr 待排序数组
* @param low 分区范围的起始索引
* @param high 分区范围的结束索引
* @return 基准值最终的索引
*/
int partition(std::vector<int>& arr, int low, int high) {
// 1. 选择最右边的元素作为基准值 (Pivot)
int pivot = arr[high];
// i 是较小元素的索引，用于指示小于或等于基准值的元素的“尾部”
int i = (low - 1);
// 2. 遍历当前范围内的元素
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准值
if (arr[j] <= pivot) {
i++; // 增加较小元素的索引
std::swap(arr[i], arr[j]);
}
}
// 3. 将基准值（arr[high]）放到正确的位置 (i+1)
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
/**
* 快速排序主函数
*
* @param arr 待排序数组
* @param low 排序范围的起始索引
* @param high 排序范围的结束索引
*/
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
// 1. 分区：获取基准值的最终位置
int pi = partition(arr, low, high);
// 2. 递归：对左子序列进行快速排序
quickSort(arr, low, pi - 1);
// 3. 递归：对右子序列进行快速排序
quickSort(arr, pi + 1, high);
}
}
|
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include <iostream>
#include <vector>
#include <algorithm> // 包含 std::copy
/**
* 归并函数：将两个有序子数组 arr[l..m] 和 arr[m+1..r] 合并成一个有序数组。
*
* @param arr 待排序数组
* @param l 左子数组的起始索引
* @param m 中点索引（左子数组的结束索引）
* @param r 右子数组的结束索引
*/
void merge(std::vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1; // 左子数组的大小
int n2 = r - m; // 右子数组的大小
// 1. 创建临时子数组 L 和 R
std::vector<int> L(n1);
std::vector<int> R(n2);
// 拷贝数据到临时数组 L 和 R
for (int i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
// 2. 合并临时数组回到 arr[l..r],并且排序
int i = 0; // L 的初始索引
int j = 0; // R 的初始索引
int k = l; // 合并后数组的初始索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 3. 拷贝 L 数组中剩余的元素（如果有）
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 4. 拷贝 R 数组中剩余的元素（如果有）
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/**
* 归并排序主函数（采用分治法）
*
* @param arr 待排序数组
* @param l 排序范围的起始索引
* @param r 排序范围的结束索引
*/
void mergeSort(std::vector<int>& arr, int l, int r) {
if (l < r) {
// 1. 分割：找到中点
int m = l + (r - l) / 2;
// 2. 递归：对左半部分进行排序
mergeSort(arr, l, m);
// 3. 递归：对右半部分进行排序
mergeSort(arr, m + 1, r);
// 4. 归并：合并两个已排序的子数组
merge(arr, l, m, r);
}
}
|
可以看出两个排序核心都离不开递归，不过前者是先排序再递归，后者是先递归到底再排序。
树
为什么不是数据结构？因为本人懒~。~
构建
最常见的树：
1
2
3
4
5
6
|
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
|
遍历
前中后浅显一点就是对根节点处理操作对应的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void preOrder(TreeNode* root, vector<int>& result) {
// 递归终止条件：节点为空
if (root == nullptr) {
return;
}
// 1. 访问根节点 (Root)
result.push_back(root->val);
// 2. 递归遍历左子树 (Left)
preOrder(root->left, result);
// 3. 递归遍历右子树 (Right)
preOrder(root->right, result);
}
|
层序遍历：
也叫广度优先遍历 (BFS)。它使用 队列 std::queue 来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
std::vector<int> levelOrder(TreeNode* root) {
std::vector<int> result;
if (root == nullptr) {
return result;
}
// 使用队列存储待访问的节点
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
// 1. 取出队首节点并访问
TreeNode* current = q.front();
q.pop();
result.push_back(current->val);
// 2. 如果有左子节点，入队
if (current->left != nullptr) {
q.push(current->left);
}
// 3. 如果有右子节点，入队
if (current->right != nullptr) {
q.push(current->right);
}
}
return result;
}
|
按层级从上到下，每层从左到右访问节点。
