C++相关基础知识总结笔记

前言

以下内容相关均为面试中碰到的问题，或牛客知乎B站上，面经总结。

其中部分回答是询问AI回答得知，若有差错谬误，还望指出。

以后如果写的多了，会分块，目前先全部放在一起。

基础相关

#include<...>和include"..."的区别

当使用<...>

尖括号形式时，预处理器会在标准系统目录中搜索头文件。这种方式主要用于包含标准库提供的头文件，如 <iostream>、<vector> 等。

当使用"..."

双引号形式时，预处理器首先会在当前源文件所在的目录中搜索头文件。如果没有找到，则会继续在标准系统目录中搜索。这种方式主要用于包含用户自定义的头文件，如项目内的头文件或第三方库的头文件。

extern "C"的作用

• 在函数前面添加 将C 风格的函数，编译为C风格、函数重载会无效

指针常量和常量指针的区别

• 指针常量：指针指向的数据不能被修改，但指针本身的值可以改变。
• 常量指针：指针本身的值不能被改变，但指针指向的数据可以被修改。

代码语言：cpp复制

#include <iostream>

int main() {
    int value1 = 10;
    int value2 = 20;

    // 指针常量
    const int* ptrConst = &value1;
    std::cout << "Value through const pointer: " << *ptrConst << std::endl;

    // 常量指针
    int* const ptr = &value1;
    std::cout << "Value through constant pointer: " << *ptr << std::endl;

    // 通过常量指针修改数据
    *ptr = 30;
    std::cout << "New value through constant pointer: " << *ptr << std::endl;

    // 尝试改变常量指针的值
    // ptr = &value2;  // 编译错误

    return 0;
}

函数中的引用

• 屏蔽开发人员造成的一些误解，和解决阅读理解问题
• 引用可以减少函数传递参数时的开销，不会产生新的变量
• 引用会修改传递参数的原始值，需要添加const解决，声明为不可修改

代码语言：cpp复制

void Swap(int& a, int& b)
{
	int t = a;
	a = b;
	b = t;
}

int main(int argc, char** argv)
{
	int a, b;
	a = 200;
	b = 300;
	Swap(a, b);
	printf("%d %dn", a, b);
	return 0;
}

引用的本质

引用的本质在c 内部实现是一个指针常量.

代码语言：javascript复制

数据类型 * const ref = &value;

内联函数

• 内联函数是向编译器建议使用，编译器可以不接受
• 内联函数是空间换时间
• 必须声明和实现在一起，否则无效
• 在类的内部定义的函数默认是内联函数
• 如果你不添加内联关键字，编译器也可以自动转换为内联

代码语言：javascript复制

inline 返回值类型 函数名(){函数体}

内存存储区域

编译器把内存分为三个部分：

1.静态存储区域：主要保存全局变量和静态变量。生存期：整个程序。

2.堆：存储动态生成的变量。生存期：自己来决定。

3.栈：存储调用函数相关的变量和地址等。生存期：所处的语句块（既{}的范围）

堆和栈

1、申请方式的不同。栈由系统自动分配，而堆是人为申请开辟;

2、申请大小的不同。栈获得的空间较小，而堆获得的空间较大;

3、申请效率的不同。栈由系统自动分配，速度较快，而堆一般速度比较慢;

4、存储内容的不同。栈在函数调用时，函数调用语句的下一条可执行语句的地址第一个进栈，然后函数的各个参数进栈，其中静态变量是不入栈的。而堆一般是在头部用一个字节存放堆的大小，堆中的具体内容是人为安排;

5、底层不同。栈是连续的空间，而堆是不连续的空间。

栈的大小是有限制的，在编译时可以设置默认值

指针函数与函数指针的区别

指针函数和函数指针是两种不同的概念，它们在C/C 编程中扮演着重要的角色。下面是这两者之间的主要区别：

指针函数

指针函数是一种特殊的函数，它的返回值是一个指针。这种函数通常用于动态内存分配（如malloc、calloc等）或者是为了返回某个特定类型的指针给调用者。指针函数的定义包括了返回类型（指针类型），函数名称，以及参数列表。

例如，一个返回指向整数的指针的指针函数可以这样定义：

代码语言：javascript复制

int* createInt(int value) {
    int *ptr = malloc(sizeof(int));
    if(ptr!= NULL) {
        *ptr = value;
    }
    return ptr;
}

在这个例子中，createInt函数接受一个整数值作为参数，并返回一个指向该整数的指针。

函数指针

函数指针是一种变量，其值为另一个函数的地址。函数指针允许你将函数作为参数传递给其他函数，或者存储函数的引用以便稍后调用。函数指针的定义包括了函数的原型（返回类型、函数名和参数列表）。

例如，定义一个函数指针来指向一个接受两个整数并返回一个整数的函数：

代码语言：javascript复制

int add(int a, int b) {
    return a   b;
}
​
int (*funcPtr)(int, int) = add;

在这个例子中，funcPtr是一个函数指针，它指向add函数。通过funcPtr，你可以调用add函数，就像直接调用add函数一样。

总结来说，指针函数关注于返回一个指针，而函数指针关注于存储或传递函数的引用。指针函数通常用于动态内存管理或返回特定类型的指针，而函数指针提供了一种灵活的方式来操作函数，允许你将函数作为参数传递或存储函数引用以便稍后调用。

联合体和结构体有什么区别

联合体（union）和结构体（struct）都是C/C 中用于组合多个不同类型的数据的数据结构，但它们在使用和行为上的主要区别如下：

结构体（struct）

• 定义：结构体是一种用户定义的数据类型，它可以包含任意数量的不同类型的成员。结构体的每个成员都有自己的名字和类型，并且可以独立地存储和访问。
• 内存布局：结构体的成员按声明顺序存储在连续的内存位置中，每个成员占据其对应类型大小的内存空间。结构体的大小等于其所有成员大小的总和。
• 使用：结构体通常用于组织相关的数据项，方便管理和访问。由于结构体的成员可以有不同的类型，因此它非常适合用于表示具有不同属性的复杂数据类型。

联合体（union）

• 定义：联合体类似于结构体，但所有成员共享同一块内存空间。因此，联合体的大小等于其最大成员大小。
• 内存布局：联合体的所有成员共享同一块内存区域，只能存储其中的一个成员的值。选择哪个成员存储在内存中是通过偏移量来实现的。
• 使用：联合体通常用于节省内存，当需要存储不同类型的数据但又只有一个数据项存在时。由于联合体的成员共享同一块内存，因此只能存储其中的一个成员的值。

主要区别

• 内存使用：结构体的成员各自占用内存空间，而联合体的成员共享同一块内存空间。
• 数据存储：结构体可以同时存储多个成员的值，而联合体只能存储其中一个成员的值。
• 使用场景：结构体适用于需要同时存储多个不同类型的数据项的情况；联合体适用于需要根据不同的条件存储不同类型的数据项，但一次只能存储一种情况下的数据项。

示例

结构体示例

代码语言：javascript复制

struct Person {
    char name[50];
    int age;
    float salary;
};

联合体示例

代码语言：javascript复制

union Data {
    char c;
    int i;
    float f;
};

在这个联合体示例中，Data可以存储一个字符、一个整数或一个浮点数，但任何时候只能存储其中一种类型的数据。

进程和线程有什么区别

进程和线程是计算机操作系统中两种基本的执行单位，它们在功能、资源分配和执行方式上有一些关键的区别。

进程

• 定义：进程是操作系统资源分配的基本单位，一个进程包含了执行程序的代码、运行时的数据、打开文件描述符、进程控制块（PCB）等信息。每个进程都有自己的独立内存空间，包括代码段、数据段和堆栈段。
• 资源分配：每个进程都有独立的代码和数据空间，程序之间的切换会有较大的开销。
• 并发执行：操作系统可以同时运行多个进程，这些进程可以并发执行。

线程

• 定义：线程是任务调度和执行的基本单位，线程是依赖于进程的，负责当前进程中程序的执行。一个进程中至少有一个线程（单线程程序），但可以有多个线程（多线程程序）。
• 资源共享：同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。
• 并发执行：在同一个进程中，多个线程可以并发执行，提高了程序的执行效率。

主要区别

• 资源分配：进程是操作系统资源分配的基本单位，每个进程都有自己的独立内存空间；线程是任务调度和执行的基本单位，同一类线程共享代码和数据空间。
• 开销：进程之间的切换会有较大的开销，因为每个进程都有自己的独立内存空间；线程之间的切换开销小，因为线程共享大部分资源。
• 并发执行：操作系统可以同时运行多个进程；在同一个进程中，多个线程可以并发执行。

总结来说，进程和线程都是计算机操作系统中执行程序的基本单位，但它们在资源分配、执行方式和开销上有明显的区别。进程提供了隔离的执行环境，而线程则允许在同一进程内并发执行多个任务，提高了程序的执行效率。

a是线程安全的吗？

• 对于基本类型（如 int）， a 操作在多线程环境下不是线程安全的，因为它是非原子的。
• 对于原子类型（如 std::atomic<int>）， a 操作是线程安全的，因为它是原子性的。
• 对于自定义类型，如果 操作符重载涉及复杂的逻辑或多个成员变量的修改，你需要显式地使用同步机制来确保线程安全。

什么是原子操作

原子操作是在多线程或多处理器环境中保证数据一致性和完整性的重要手段。

详细描述编译链接的过程

‘编译链接过程是将人类可读的源代码转换为机器可执行的程序的关键步骤。在C语言编程中，这个过程通常分为四个主要阶段：预处理、编译、汇编和链接。以下是每个阶段的详细说明：

预处理（Preprocessing）

• 目的：预处理阶段处理源代码中的预处理指令，如#include、#define等，展开宏、处理条件编译等。
• 输出：预处理后的代码保存为.i文件。

编译（Compilation）

• 目的：编译阶段将预处理后的代码进行词法分析、语法分析、语义分析和优化，生成汇编代码。
• 输出：汇编代码保存为.s文件。

汇编（Assembly）

• 目的：汇编器将汇编代码转换为机器指令，生成目标文件（.o文件）。
• 输出：二进制文件（.o文件）。

链接（Linking）

• 目的：链接阶段将多个目标文件、操作系统的启动代码和库文件进行组织，最终生成可执行文件。这一步骤可能涉及到动态链接和静态链接。
• 输出：可执行文件（.exe或.out等）。

总结来说，编译链接过程是将源代码转换为可执行程序的关键步骤，包括预处理、编译、汇编和链接四个阶段。预处理阶段处理源代码中的预处理指令；编译阶段将预处理后的代码转换为汇编代码；汇编阶段将汇编代码转换为机器指令；链接阶段将多个目标文件、操作系统的启动代码和库文件组织成最终的可执行文件。链接过程中可能涉及到动态链接和静态链接，根据需要选择合适的链接方式。

动态链接（Dynamic Linking）与静态链接（Static Linking）

• 动态链接：在运行时加载所需的库文件，减少了可执行文件的大小。
• 静态链接：将所有必要的库文件链接到可执行文件中，生成一个独立的可执行文件。

动态链接（Dynamic Linking）

优点

• 体积较小：
  • 动态链接的可执行文件体积较小，因为库文件的内容不会被嵌入到可执行文件中。
  • 这使得可执行文件更加轻便，便于分发和传输。
• 易于更新：
  • 如果库文件更新了，只需要更新库文件即可，无需重新编译和链接应用程序。
  • 这使得应用程序能够快速地利用最新的库版本，而不需要频繁地重新发布应用程序。
• 节省资源：
  • 多个应用程序可以共享相同的库文件，从而节省存储空间和内存资源。
  • 特别是在服务器环境中，共享库可以显著减少内存占用。
• 延迟加载：
  • 动态链接支持延迟加载（Lazy Loading），即只有在真正需要时才加载特定的库文件。
  • 这可以进一步提高程序的启动速度和资源利用率。

缺点

• 依赖外部库：
  • 动态链接的应用程序依赖于外部库文件的存在，如果缺少必要的库文件，程序将无法运行。
  • 这要求用户或系统管理员确保目标系统上有正确的库文件版本。
• 跨平台问题：
  • 动态链接的应用程序在跨平台部署时需要考虑不同平台上的库文件差异。
  • 如果目标平台没有相应的库文件，程序将无法运行。
• 加载时间：
  • 在程序启动时，需要加载和链接库文件，可能会增加程序的启动时间。
  • 虽然延迟加载可以缓解这个问题，但对于某些实时或高性能应用来说，这仍然是一个潜在的性能瓶颈。

静态链接（Static Linking）

优点

• 独立性强：
  • 静态链接的应用程序是一个独立的可执行文件，不需要依赖外部库文件。
  • 这使得应用程序可以在没有外部库文件的情况下运行。
• 部署简单：
  • 静态链接的应用程序可以更容易地在不同的计算机上部署，因为不需要额外的库文件。
  • 这简化了部署流程，特别是在缺乏网络连接或资源受限的环境下。
• 即时可用：
  • 应用程序在启动时不需要加载额外的库文件，因此启动速度相对较快。

缺点

• 体积较大：
  • 静态链接的应用程序通常体积较大，因为包含了所有库文件的内容。
  • 这增加了存储和传输的成本。
• 更新困难：
  • 如果库文件有更新，需要重新编译和链接应用程序才能利用最新的库版本。
  • 这使得应用程序难以及时获得库文件的更新。
• 资源浪费：
  • 如果多个应用程序静态链接了相同的库文件，那么这些库代码会在每个程序中重复，造成资源浪费。

动态链接的应用？动态加载（Dynamic Linked Content, DLC）

动态加载（DLC）通常指的是动态链接的内容，尤其是在游戏和其他软件中，动态加载的内容可以是游戏关卡、皮肤、扩展包等。这些内容通常不是程序的核心部分，而是可以单独下载和安装的附加内容。

为什么 DLC 加载一般采用动态链接？

• 可扩展性：
  • 动态链接允许在不重新编译核心程序的情况下添加新的内容或功能。
  • 这使得游戏或软件可以在发布后继续扩展和更新，而无需重新下载整个程序。
• 节省空间：
  • 动态加载的内容只有在需要时才会加载到内存中，而不是一开始就加载所有内容。
  • 这可以显著减少内存占用，并提高程序的性能。
• 易于管理：
  • 用户可以根据需要选择下载和安装哪些内容，而不是被迫下载所有内容。
  • 这使得内容管理更加灵活和便捷。

总结

动态链接和静态链接各有优缺点，选择哪种链接方式取决于具体的应用场景和需求：

• 动态链接适用于需要频繁更新、节省资源和跨平台的应用程序。
• 静态链接适用于需要独立性强、部署简单的应用程序。

用宏定义写出swap(x,y)

代码语言：cpp复制

#define SWAP(a, b) do { int temp = (a); (a) = (b); (b) = temp; } while(0)

//这里涉及到do while(false)的妙用

用宏定义写出min(x,y)

代码语言：javascript复制

#define min(x, y) (((x) < (y)) ? (x) : (y))

C 11新特性和应用介绍

1. 自动类型推导 (auto)

允许使用auto关键字来自动推导变量的类型，这在处理复杂的类型或模板类型时非常有用。

应用：

代码语言：cpp复制

std::vector<int> v = {1, 2, 3};
auto it = v.begin(); // 编译器推断it为std::vector<int>::iterator

2. 基于范围的 for 循环

提供了一种简洁的方式来遍历容器。

应用：

代码语言：cpp复制

std::vector<int> numbers = {1, 2, 3};
for (auto& num : numbers) {
    std::cout << num << std::endl;
}

3. 智能指针 (std::shared_ptr, std::unique_ptr, std::weak_ptr)

用于自动管理动态分配的内存，防止内存泄漏。

应用：

代码语言：cpp复制

std::unique_ptr<int> uptr(new int(10));
std::shared_ptr<int> sptr(new int(20));
std::weak_ptr<int> wptr(sptr);

4. Lambda 表达式

允许开发者在需要的地方快速定义匿名函数。

应用：

代码语言：cpp复制

std::vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end(), [](int a, int b){ return a > b; });

5. 右值引用和移动语义

允许更高效的资源管理，特别是在对象的复制和移动操作中。

应用：

代码语言：cpp复制

class MyClass {
public:
    MyClass(MyClass&& other) noexcept : value(other.value) {
        other.value = 0; // 夺取other的资源
    }
private:
    int value;
};

6. nullptr

替代了旧的NULL宏定义，提供一个明确的空指针类型。

应用：

代码语言：cpp复制

int* ptr = nullptr;

7. constexpr

允许在编译时计算函数的结果。

应用：

代码语言：cpp复制

constexpr int square(int x) { return x * x; }
static_assert(square(5) == 25); // 在编译时期就能知道结果

8. 初始化列表

简化了对象的初始化。

应用：

代码语言：cpp复制

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
};
Point p{1.0, 2.0}; // 统一初始化

9. 多线程支持 (<thread>, <mutex>, <condition_variable>)

提供了标准的多线程支持，简化了并发编程。

应用：

代码语言：cpp复制

#include <thread>
void hello() { std::cout << "Hello from thread" << std::endl; }
int main() {
    std::thread t(hello);
    t.join();
    return 0;
}

10. 默认删除 =delete

应用：

代码语言：cpp复制

class NoCopy {
public:
    NoCopy() {} // 默认构造函数

    // 删除拷贝构造函数
    NoCopy(const NoCopy&) = delete;

    // 删除拷贝赋值运算符
    NoCopy& operator=(const NoCopy&) = delete;
};

// 下面的代码会导致编译错误
// NoCopy obj1;
// NoCopy obj2 = obj1; // 尝试调用已删除的拷贝构造函数

11. 其他特性

还有许多其他有用的特性，比如static_assert、noexcept、统一初始化、扩展的Unicode字符串字面量、alignof、noexcept运算符、override和final关键字等等。

建议挑几个好记的记，可以从其延伸回答，并且问的多的。

Lambda表达式

Lambda 表达式是 C 11 引入的一种简洁的定义匿名函数的方法。Lambda 表达式允许你在代码中定义并使用一次性函数，而不必显式地定义一个函数。

Lambda 表达式的语法

Lambda 表达式的语法如下：

代码语言：cpp复制

[lambdacapture] (parameters) mutable -> returntype { body }

• [capture]：捕获列表，用于指定哪些变量可以被 lambda 函数捕获。
• (parameters)：参数列表。
• mutable：可选关键字，用于指定 lambda 函数是否可以修改捕获的变量。
• -> returntype：可选的返回类型指定。
• { body }：函数体。

示例

代码语言：cpp复制

#include <iostream>

int main() 
{
    int x = 10;

    // 定义一个 lambda 函数
    auto lambda = [x]() mutable { x  = 10; std::cout << "x = " << x << std::endl; };

    lambda();  // 输出：x = 20
    std::cout << "Original x = " << x << std::endl;  // 输出：Original x = 10

    return 0;
}

用auto定义一个变量接收一个lambda表达式，对这个变量求sizeof是什么结果？

代码语言：cpp复制

#include <iostream>

int main()
{
	int x = 10;
	int a = 5;
	// 定义一个 lambda 表达式，并使用 auto 接收
	auto lambda = []() { return 0; };
	auto lambdaX = [x]() { return x; };
	auto lambdaXA = [a, x]() { return x   a; };
	auto lambdaXA_BC = [a, x](int b, int c) {return a   x   b   c; };

	// 求 lambda 变量的大小
	std::cout << "Size of lambda: " << sizeof(lambda) << " bytes" << std::endl; //输出为1bytes 可以看作函数指针的大小

	std::cout << "lambdaX: " << sizeof(lambdaX) << std::endl; //输出为4bytes
	std::cout << "lambdaXA: " << sizeof(lambdaXA) << std::endl;//输出为8bytes
	std::cout << "lambdaXA_BC: " << sizeof(lambdaXA_BC(1, 2)) << std::endl; //输出为4byt是因为lambdaXA_BC(1,2)的返回值是int类型
	return 0;
}

输出结果可能因编译器和平台的不同而有所不同。

解释

• 无捕获的 lambda (lambda)
  • lambda 是一个没有捕获任何变量的 lambda 表达式。
  • 这种情况下，编译器可能会生成一个非常小的闭包对象，甚至可能是一个简单的函数指针。
  • 因此，sizeof(lambda) 的结果可能是非常小的，如 1 字节，这通常表示一个函数指针的大小。
  • 实际上，1 字节的大小可能是因为编译器的优化，将无捕获的 lambda 视为一个函数指针。
• 按值捕获一个 int 变量 (lambdaX)
  • lambdaX 捕获了一个 int 类型的变量 x。
  • int 类型在大多数平台上是 4 字节（对于 32 位系统）或 8 字节（对于 64 位系统）。
  • 因此，sizeof(lambdaX) 的结果为 4 字节，表示闭包对象包含了一个 int 类型的变量。
• 按值捕获两个 int 变量 (lambdaXA)
  • lambdaXA 捕获了两个 int 类型的变量 a 和 x。
  • 每个 int 类型的大小为 4 字节，因此总共需要 8 字节来存储这两个变量。
  • 因此，sizeof(lambdaXA) 的结果为 8 字节。

编译器优化

需要注意的是，编译器可能会对 lambda 表达式进行优化。例如，对于无捕获的 lambda，编译器可能会将其优化为一个简单的函数指针，因此 sizeof(lambda) 的结果可能非常小。

typdef 别名

typedef为C语言的关键字，作用是为一种数据类型(基本类型或自定义数据类型)定义一个新名字，不能创建新类型。

• 与#define不同，typedef仅限于数据类型，而不是能是表达式或具体的值
• #define发生在预处理，typedef发生在编译阶段

三种传递（值传递，引用传递，指针传递）

• 值传递：传递参数的副本，函数内部对形参的修改不会影响到实参。
• 引用传递：传递参数的引用地址（变量的别名），函数内部对形参的修改会影响到实参。
• 指针传递：传递指向传入值的地址，函数内部对形参的修改会影响到实参。

char*和char[]的区别

char* 和 char[] 的区别

• 类型不同：
  • char* 表示一个指向字符的指针，它可以指向任何地方的字符数据。
  • char[] 是一个字符数组，它在声明时分配了一段连续的内存空间来存储一系列字符。
• 分配内存方式：
  • char* 可以指向动态分配的内存（例如通过 new 或者 malloc()），也可以指向静态字符串。
  • char[] 在栈上分配固定大小的内存，大小由数组定义时确定。
• 使用场景
  • char* 适合需要频繁改变所指内存地址的情况。
  • char[] 适用于不需要改变数组本身地址的情况，并且数组长度固定。

函数参数中的 char* 和 char[] 的区别

当作为函数参数时，char* 和 char[] 都会被退化为指向第一个元素的指针类型。因此，它们在形式上看起来是相同的。但是，从语义上来讲，它们表示的是不同的东西：

• char* param 表明参数是一个指向字符的指针。
• char param[] 虽然编译器处理成 char* param，但它暗示参数是一个字符数组。

实际使用时，通常根据习惯或者意图来选择哪种写法。例如，如果你希望强调这是一个数组，那么可能会使用 char[] 形式；如果强调这是个指针，则使用 char* 形式。

智能指针

智能指针是一种具有自动资源管理功能的指针，如 std::unique_ptr, std::shared_ptr，std::weak_ptr能够自动管理内存生命周期。

为什么unique_ptr比auto_ptr（C 98标准，已过时）更安全？

unique_ptr相比auto_ptr禁用了拷贝构造，采用了移动赋值来进行所有权的转移

1. 所有权语义明确

• 独占所有权：std::unique_ptr 明确表示了独占所有权，意味着一个 std::unique_ptr 对象不能被复制，只能通过移动语义来转移所有权。这减少了由于意外的拷贝而导致的资源管理错误。
• 没有意外的拷贝：与 std::auto_ptr 不同，std::unique_ptr 不可被拷贝，因此不会有意外的资源所有权转移。如果需要转移所有权，必须显式地使用移动语义（通过 std::move）。

2. 线程安全性

• 线程安全：std::unique_ptr 在内部使用了线程安全的方式来管理资源，特别是当涉及到析构和释放资源时。而 std::auto_ptr 在某些情况下可能会有线程安全问题，尤其是在析构函数的调用顺序上。

介绍一下三种智能指针

1. std::unique_ptr

std::unique_ptr 是一种独占所有权的智能指针，它确保同一时间内只有一个 std::unique_ptr 对象拥有某个资源。这意味着：

• 不可复制：std::unique_ptr 不能被复制，以确保任何时候都只有一个对象拥有资源的所有权。
• 可移动：std::unique_ptr 可以通过移动语义来转移所有权。这意味着可以通过 std::move 将一个 std::unique_ptr 的所有权转移到另一个 std::unique_ptr。
• 自动释放资源：当 std::unique_ptr 对象超出作用域或被显式销毁时，它所管理的资源会被自动释放。
• 删除器：std::unique_ptr 支持自定义删除器，可以用来执行额外的清理工作，如关闭文件句柄等。

代码语言：cpp复制

#include <memory>
#include <iostream>

int main() 
{
   std::unique_ptr<int> ptr(new int(10)); // 创建一个 unique_ptr 指向整型
   std::cout << *ptr << std::endl; // 输出: 10
       // ptr 不可复制，但可以通过移动语义转移所有权
    std::unique_ptr<int> anotherPtr = std::move(ptr);
    std::cout << *anotherPtr << std::endl; // 输出: 10
    // 当 anotherPtr 超出作用域时，其所指向的整型会被自动删除
    return 0;
}

2. std::shared_ptr

std::shared_ptr 是一种共享所有权的智能指针，它可以允许多个 std::shared_ptr 对象共享同一个资源。它通过引用计数来跟踪有多少个 std::shared_ptr 正在使用同一个资源：

• 可复制：std::shared_ptr 可以被复制，每复制一次就会增加引用计数。
• 自动释放资源：当引用计数降为零时，std::shared_ptr 管理的资源会被释放。
• 循环引用问题：如果多个 std::shared_ptr 彼此相互持有对方，则可能会导致引用计数永远不降为零，从而导致内存泄漏。此时可以使用 std::weak_ptr 来打破循环引用。

代码语言：cpp复制

#include <memory>
#include <iostream>

class A
{
public:
    std::shared_ptr<B> b;
    ~A() { std::cout << "A destructed" << std::endl; }
};

class B 
{
public:
    std::shared_ptr<A> a;
    ~B() { std::cout << "B destructed" << std::endl; }
};

int main() 
{
    auto a = std::make_shared<A>();
    auto b = std::make_shared<B>();
    a->b = b;
    b->a = a;
    // 由于循环引用，如果没有 weak_ptr，这两个对象都不会被删除
    // 使用 std::weak_ptr 可以解决这个问题
    return 0;
}

另外：

• std::shared_ptr的引用计数操作是线程安全的，这意味着你可以安全地在多个线程中创建、赋值和拷贝std::shared_ptr
• 但是，当你通过 std::shared_ptr 访问或修改其所指向的对象时，你需要自己负责同步，以避免数据竞争和不一致性问题。

std::weak_ptr ：

是一种弱引用的智能指针，它不增加引用计数，主要用于解决 std::shared_ptr 导致的循环引用问题：

• 无所有权：std::weak_ptr 不拥有资源，也不会增加资源的引用计数。
• 检测有效性：可以使用 std::weak_ptr::expired() 方法来检查是否还有 std::shared_ptr 持有资源。
• 获取 std::shared_ptr：如果资源仍然存在，可以使用 std::weak_ptr::lock() 方法来获取一个 std::shared_ptr。

代码语言：cpp复制

#include <memory>
#include <iostream>

class Node 
{
public:
    std::shared_ptr<Node> next;
   std::weak_ptr<Node> prev;
    ~Node() { std::cout << "Node destructed" << std::endl; }
};

int main() 
{
    auto head = std::make_shared<Node>();
    auto tail = std::make_shared<Node>();
    head->next = tail;
    tail->prev = head;
    // 使用 weak_ptr 避免循环引用
    return 0;
}

总结

• std::unique_ptr 用于独占资源管理，确保任何时候只有一个拥有者。
• std::shared_ptr 用于共享资源管理，允许多个拥有者，但可能会导致循环引用。
• std::weak_ptr 用于辅助解决 std::shared_ptr 的循环引用问题，不增加引用计数。

合理选择和使用这三种智能指针可以有效地帮助管理内存，避免内存泄漏和其他与手动管理内存相关的错误。

volatile关键字的作用

volatile 关键字主要用于多线程环境中，用于标记一个变量，使得对该变量的读写操作不会被编译器或处理器优化而存储在寄存器中，而是每次都强制从主内存中加载最新的值。

• 禁止编译器优化：volatile 关键字告诉编译器不要对这个变量进行优化，比如不要把多次使用的变量值缓存在寄存器中而不刷新回内存，这样可以保证每次读取都是最新的值。
• 内存可见性：在多线程环境中，volatile 可以确保一个线程修改了一个变量的值后，其他线程能够看到这个修改。然而，值得注意的是，volatile 并不能保证操作的原子性，也就是说，它不能防止多个线程同时访问和修改同一个变量而导致的数据不一致的问题。
• 有序性：volatile 变量可以提供一定程度上的内存排序（happens-before语义），即对一个volatile变量的写入先发生于随后对该变量的读取。这意味着如果线程A写入了一个volatile变量，然后线程B读取了这个变量，那么线程A的写入操作发生在线程B的读取操作之前。 需要注意的是，虽然volatile能够提供内存可见性和一定程度的有序性，但它并不提供原子性。对于复合操作（如先读取再写入），仅使用volatile并不能保证正确的行为，通常还需要配合其他同步手段，如synchronized块或Lock对象等。

总结，volatile关键字的主要目的是禁止编译器优化，解决内存可见性和有序性问题，但volatile不能保证线程安全，得上锁。

静态变量Static的作用及其衍生问题

1.static的作用

• 静态全局变量：在全局作用域中，static关键字使得变量仅在定义它的源文件中可见。
• 静态局部变量：在函数体内，static关键字使得变量在整个程序运行期间只初始化一次，并且在函数退出后仍保留其值。
• 静态成员变量：在类中，static关键字使得变量属于整个类而不是类的某个实例。
• 静态成员函数：在类中，static关键字使得函数不依赖于类的实例，可以直接通过类名调用。

2.函数内static变量的初始化

函数内static变量是否只会初始化一次

函数内的static变量在整个程序运行期间只初始化一次。这意味着无论函数被调用多少次，static变量只会被初始化一次，并且在函数退出后保留其值。

静态成员变量相关

• 静态成员变量的作用：静态成员变量是类级别的变量，它属于整个类而不是单个对象。这意味着无论创建了多少个对象，静态成员变量只有一个副本。静态成员变量通常用于以下用途：
  • 共享资源：当多个对象需要共享某个资源时，可以使用静态成员变量。
  • 计数器：用于跟踪类的实例数量或其他统计信息。
  • 配置信息：存储类的全局配置信息或常量
• 静态成员变量是否需要在类外初始化？ 静态成员变量需要在类外进行初始化。这是因为静态成员变量实际上是全局变量，它们在全局命名空间中分配内存。因此，必须在类外部提供初始化声明。

代码语言：cpp复制

#include <iostream>

class MyClass {
public:
    static int counter;  // 声明静态成员变量
    
    MyClass() {
        counter  ;  // 自增
    }
    
    static int getCounter() {
        return counter;  // 使用静态成员变量
    }
};

// 类外部初始化
int MyClass::counter = 0;

int main() {
    MyClass obj1;
    MyClass obj2;
    std::cout << "Counter: " << MyClass::getCounter() << std::endl;  // 输出：Counter: 2
    return 0;
}

• 静态成员变量是否可以是 const？ 静态成员变量可以是 const 类型。const 静态成员变量在类外部初始化时必须提供初始值，并且一旦初始化就不能改变。
• 静态成员变量是否可以是引用类型？ 不可以。静态成员变量不能是引用类型。引用必须在声明时初始化，并且不能重新绑定。因此，引用不能作为静态成员变量。
• 静态成员变量是否可以在构造函数中初始化？ 不可以。静态成员变量在构造函数之前就已经初始化了。构造函数用于初始化对象的非静态成员变量，而静态成员变量在类的所有对象创建之前就已经存在。
• 静态成员变量的生命周期是怎样的？ 静态成员变量的生命周期从程序启动到程序结束。它们在整个程序运行期间都存在，即使没有创建任何类的对象。静态成员变量在全局命名空间中分配内存，因此它们的生命周期与全局变量相同。
• 静态成员变量的线程安全性如何保证？ 静态成员变量在多线程环境下的访问需要特别注意线程安全性。如果多个线程同时访问同一个静态成员变量，可能会导致竞态条件。可以通过加锁机制（如互斥锁 std::mutex）来确保线程安全。

静态成员函数相关

• 静态成员函数的特点
  • 没有this指针：静态成员函数不隐式地接收this指针，因此它不能直接访问类的非静态成员变量或调用非静态成员函数。（可以通过传递类的实例给静态成员函数间接访问）
  • 访问静态成员变量：静态成员函数可以访问类的静态成员变量。
  • 调用静态成员函数：静态成员函数可以调用类的其他静态成员函数。
• 静态成员函数是否可以是虚函数？ 不可以。虚函数是与对象关联的，而静态成员变量是类级别的。因此，静态成员变量不能是虚函

---

STL容器相关

stl容器基础知识

1. 容器分类

STL 容器大致可以分为以下几类：

• 序列容器（Sequence Containers）：如 vector, list, deque。
• 关联容器（Associative Containers）：如 set, map, multiset, multimap。
• 容器适配器（Container Adapters）：如 stack, queue, priority_queue。
• 无序容器（Unordered Associative Containers）：如 unordered_set, unordered_map, unordered_multiset, unordered_multimap。

2. 序列容器

2.1 vector

• 特点：动态数组，提供随机访问，元素连续存储。
• 插入和删除：在尾部插入和删除效率较高，中间和头部插入删除效率较低。
• 内存管理：每次扩容时通常加倍，以减少内存重新分配的次数。

2.2 list

• 特点：双向链表，提供双向迭代，元素非连续存储。
• 插入和删除：在任何位置插入和删除都非常高效。
• 内存管理：每个节点单独分配，没有连续性要求。

2.3 deque

• 特点：双端队列，提供双向访问，两端都可以高效插入和删除。
• 内存管理：使用分段数组实现，每一段是一个连续块，整体不连续。

3. 关联容器

3.1 set 和 multiset

• 特点：基于红黑树实现，提供有序存储，支持快速查找。
• 插入和删除：插入和删除效率较高，但比不上 list。
• 唯一性：set 中的元素唯一，multiset 中可以有重复元素。

3.2 map 和 multimap

• 特点：基于红黑树实现，提供键值对存储，支持快速查找。
• 插入和删除：插入和删除效率较高，但比不上 list。
• 唯一性：map 中的键唯一，multimap 中可以有重复的键。

4. 容器适配器

4.1 stack

• 特点：后进先出（LIFO）数据结构。
• 实现：通常基于 vector 或 deque 实现。

4.2 queue

• 特点：先进先出（FIFO）数据结构。
• 实现：通常基于 deque 实现。

4.3 priority_queue

• 特点：优先级队列，总是弹出优先级最高的元素。
• 实现：通常基于堆（Heap）实现。

5. 无序容器

5.1 unordered_set 和 unordered_multiset

• 特点：基于哈希表实现，提供无序存储，支持快速查找。
• 插入和删除：插入和删除效率较高，但可能有哈希冲突。
• 唯一性：unordered_set 中的元素唯一，unordered_multiset 中可以有重复元素。

5.2 unordered_map 和 unordered_multimap

• 特点：基于哈希表实现，提供键值对存储，支持快速查找。
• 插入和删除：插入和删除效率较高，但可能有哈希冲突。
• 唯一性：unordered_map 中的键唯一，unordered_multimap 中可以有重复的键。

6. 容器操作

• 插入：push_back, push_front, insert。
• 删除：pop_back, pop_front, erase。
• 查找：find, count, equal_range。
• 遍历：begin, end, cbegin, cend。
• 排序：sort, stable_sort。
• 反转：reverse。
• 清空：clear。

7. 迭代器

• 类型：iterator, const_iterator, reverse_iterator, const_reverse_iterator。
• 操作：operator*, operator->, operator , operator--。

8. 容器的比较

• 性能：vector 在尾部插入和删除最快，list 在任意位置插入和删除最快。
• 内存：vector 内存连续，list 内存分散。
• 查找：set 和 map 查找较快，unordered_set 和 unordered_map 查找更快（平均 O(1)）。

9. 容器的使用场景

• vector：适合需要随机访问且元素数量频繁变化的场景。
• list：适合需要频繁插入和删除元素的场景。
• deque：适合需要两端高效插入和删除元素的场景。
• set 和 map：适合需要有序存储且查找效率较高的场景。
• unordered_set 和 unordered_map：适合需要快速查找但不要求顺序存储的场景。

10. 容器的复杂度

• vector：插入 O(n)，删除 O(n)，查找 O(n)。
• list：插入 O(1)，删除 O(1)，查找 O(n)。
• deque：插入 O(1)，删除 O(1)，查找 O(n)。
• set 和 map：插入 O(log n)，删除 O(log n)，查找 O(log n)。
• unordered_set 和 unordered_map：插入 O(1)，删除 O(1)，查找 O(1)（平均情况下）。

C 什么情况下迭代器会失效？

在 C 中，迭代器失效通常发生在容器的状态发生改变，导致迭代器不再指向有效的元素或者其指向的元素的位置发生了变化。

以下是一些常见的迭代器失效的情况：

1. 序列式容器（如 vector, deque）

对于序列式容器：

• 删除元素：当从容器中删除元素时，删除位置之后的所有迭代器都会失效，因为删除操作会导致后面的元素向前移动。
  • 例如，std::vector::erase 会使被删除元素之后的所有迭代器失效。
• 插入元素：当插入元素时，插入位置之后的所有迭代器都会失效，因为插入操作会导致后面的元素向后移动。
  • 例如，std::vector::insert 会使插入位置之后的所有迭代器失效。
• 容器容量改变：当容器的容量改变时，如 std::vector::resize 或 std::vector::reserve，可能导致迭代器失效。
• 清空容器：使用 clear() 清空容器会使所有迭代器失效。

2. 关联式容器（如 map, set, multiset）

对于关联式容器，由于它们通常基于红黑树实现，因此插入和删除操作不会导致其他元素的位置发生改变。但是：

• 删除元素：删除当前迭代器指向的元素会使该迭代器失效。但删除操作不会影响其他迭代器的有效性。
  • 例如，std::map::erase 会使被删除元素的迭代器失效，但不影响其他迭代器。
• 清空容器：使用 clear() 清空容器会使所有迭代器失效。

3. 链表式容器（如 list）

对于链表式容器：

• 删除元素：删除元素会使指向被删除元素的迭代器失效，但不会影响其他迭代器。
• 插入元素：插入元素不会导致迭代器失效。
• 清空容器：使用 clear() 清空容器会使所有迭代器失效。

如何避免迭代器失效

为了避免迭代器失效带来的问题，可以采取以下措施：

1. 使用返回值：某些容器的成员函数会返回有效的迭代器，例如 std::vector::erase 返回下一个有效迭代器。
2. 备份迭代器：在修改容器之前，可以备份当前有效的迭代器。
3. 使用范围迭代：尽可能使用范围迭代（如 for-each 循环），而不是逐个迭代器操作。
4. 检查迭代器的有效性：在使用迭代器之前，检查其是否仍然有效。

示例代码

以下是一个简单的示例，展示迭代器失效的情况：

代码语言：javascript复制

#include <iostream>
#include <vector>
#include <map>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::map<int, int> m = {{1, 10}, {2, 20}, {3, 30}};

    // vector 的迭代器失效
    auto it_vec = vec.begin();
    vec.erase(it_vec); // 删除第一个元素后，it_vec 失效
    std::cout << "After erasing first element, vec: ";
    for (auto it = vec.begin(); it != vec.end();   it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // map 的迭代器失效
    auto it_map = m.find(2);
    m.erase(it_map); // 删除迭代器指向的元素后，it_map 失效
    std::cout << "After erasing element with key 2, map: ";
    for (const auto &pair : m) {
        std::cout << "(" << pair.first << ", " << pair.second << ") ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，可以看到在删除元素后，迭代器失效的情况。在实际编程中，应始终留意迭代器是否仍然有效，并采取适当的措施来避免由此引发的问题。

四大类型转换

static_cast(静态转换)

1、父类到子类的转换，（ 进行下行转换，把基类的指针或引用转换为派生类表示）不保证安全。

2、子类到父类的转换，（进行上行转换，把派生类的指针或引用转换成基类表示）保证安全。

3、基本数据类型之间的转换，是否正确需要开发人员来保证。

4、void 类型的空指针，转换成其他类型空指针。

5、可以把任何类型的表达式 转换为 void类型。

static_cast不能转换掉表达式的const、volitale属性。

代码语言：cpp复制

int i = 10;
float f = static_cast<float>(i); // 将 int 转换为 float

dynamic_cast(动态转换)

dynamic 支持运行指针时，识别指针类型或所引用的对象。

换句话说，它可以在执行期决定真正的类型，如果基类指针真的指向了子类对象，它便返回指子类对象的指针值，否则，则返回空指针。（所以说到底，他就是比static_cast多了个类型检查）

1、其他三种都是编译时完成的，dynamic_cast是运行时处理的。

2、不能用于基本数据类型的转换。

3、dynamic_cast转换如果成功的话返回的是指向类的指针或引用，转换失败的话则会返回NULL。

4、使用dynamic_cast进行转换的，基类中一定要有虚函数，否则编译不通过，类中存在虚函数，就说明它有想要让基类指针或引用指向派生类对象的情况，此时转换才有意义。

5、在类的转换时，在类层次间进行上行转换时，dynamic_cast和static_cast的效果是一样的。在进行下行转换时，dynamic_cast具有类型检查的功能，比static_cast更安全。

代码语言：cpp复制

class Base {
public:
    virtual ~Base() {}
};

class Derived : public Base {};

int main() {
    Base* basePtr = new Derived();
    Derived* derivedPtr = dynamic_cast<Derived*>(basePtr); // 安全转换
    if (derivedPtr != nullptr) {
        // 转换成功
    } else {
        // 转换失败
    }
    delete basePtr;
    return 0;
}

const_cast（常量转换）

const_cast用于强制去掉const 特性，但需要特别注意的是const_cast不是用于去除变量的常量性，而是去除指向常数对象的指针或引用的常量性，其去除常量性的对象必须为指针或引用

1、该运算符用来修改类型的const或volatile属性。除了const 或volatile修饰之外， type_id和expression的类型是一样的。

2、常量指针被转化成非常量指针，并且仍然指向原来的对象；

3、常量引用被转换成非常量引用，并且仍然指向原来的对象；

4、常量对象被转换成非常量对象。

代码语言：cpp复制

const int ci = 10;
int* pi = const_cast<int*>(&ci); // 去除 const 属性

reinterpret_cast(重解释)

它可以把一个指针转换成一个整数，也可以把一个整数转换成一个指针（先把一个指针转换成一个整数，再把该整数转换成原类型的指针，还可以得到原先的指针值）。

在使用reinterpret_cast强制转换过程仅仅只是比特位的拷贝，也不会进行类型检查，因此在使用过程中需要特别谨慎！

1、改变指针或引用的类型

2、将指针或引用转换为一个足够长度的整型

3、将整型转换为指针或引用类型

代码语言：cpp复制

char* charPtr = "Hello";
int* intPtr = reinterpret_cast<int*>(charPtr); // 危险的转换

类系列

struct 和 class 的区别?

struct 默认权限为 public ， class 默认权限为 private

类的构造相关

默认情况下,c 编译器至少为我们写的类增加3个函数 :

1．默认构造函数(无参,函数体为空)

2．默认析构函数(无参,函数体为空)

3．默认拷贝构造函数， 对类中非静态成员属性简单值拷贝

如果用户定义拷贝构造函数,c 不会再提供任何默认构造函数

如果用户定义了普通构造(非拷贝),c 不在提供默认无参构造,但是会提供默认拷贝构造

类的访问权限

• private：只有类的成员函数可以访问。
• protected：类的成员函数以及派生类的成员函数可以访问。
• public：任何人都可以访问。

构造函数和析构函数

构造函数

构造函数是一种特殊的成员函数，用于初始化类的对象。构造函数的名字与类名相同，并且没有返回类型。

• 构造函数的基本特点
  • 名称：构造函数的名称必须与类名完全相同。
  • 返回类型：构造函数没有返回类型，即使是void类型也不允许指定。
  • 自动调用：每当创建一个新对象时，构造函数会自动被调用。
  • 可以有多个：一个类可以有多个构造函数，这被称为构造函数重载（constructor overloading）。
• 构造函数的类型
  • 默认构造函数：不带任何参数的构造函数。如果类中没有任何构造函数，编译器会自动生成一个默认构造函数。
  • 带参数的构造函数：带有参数的构造函数可以用来初始化对象的成员变量。
  • 拷贝构造函数：用于创建一个新对象作为现有对象的副本。拷贝构造函数接受一个同类型对象的引用作为参数。
  • 移动构造函数：用于创建一个新对象作为另一个对象的移动（move）。移动构造函数接受一个同类型对象的右值引用作为参数。
• 构造函数的调用顺序 当一个类继承自另一个类时，基类的构造函数会在派生类的构造函数之前被调用。如果派生类的构造函数没有显式调用基类的构造函数，那么编译器会自动调用基类的默认构造函数（如果有的话）。如果基类没有默认构造函数，或者需要传递参数给基类构造函数，可以在派生类的构造函数初始化列表中显式调用基类的构造函数。
• 构造函数的规则
  • 如果类中定义了任何构造函数，编译器就不会自动生成默认构造函数。
  • 如果类中定义了拷贝构造函数或移动构造函数，编译器就不会自动生成相应的默认构造函数。
  • 如果类中定义了任何构造函数，但没有定义拷贝构造函数或移动构造函数，编译器会自动生成默认的拷贝构造函数和移动构造函数。
• 构造函数的应用场景
  • 初始化成员变量：确保对象在使用前处于有效状态。（初始化列表，赋值效率更高）
  • 执行必要的资源分配：例如，分配内存或其他资源。
  • 对象的复制和移动：确保复制和移动操作的正确性。

析构函数

析构函数是一种特殊的成员函数，用于清理类的对象。析构函数的名字是类名前面加上波浪号 ~。

析构函数的基本特点

• 名称：析构函数的名称是在类名前面加上波浪号 ~。
  • 例如，类 MyClass 的析构函数为 ~MyClass。
• 返回类型：析构函数没有返回类型，即使是 void 也不允许指定。
• 自动调用：当对象的生命期结束时（例如，对象离开作用域或删除动态分配的对象），析构函数会自动调用。
  • 对于栈上的对象，析构函数在其作用域结束时调用。
  • 对于堆上的对象，析构函数在其被 delete 时调用。
  • 对于静态或全局对象，析构函数在程序结束时调用。
• 不能重载：每个类只能有一个析构函数。这意味着不能有多个具有不同参数列表的析构函数。
• 不能带参数：析构函数不能带有任何参数。

析构函数的类型

• 默认析构函数：如果类中没有显式定义析构函数，编译器会自动生成一个默认析构函数。默认析构函数不执行任何操作。
• 用户定义的析构函数：如果需要在对象销毁时执行特定的操作，可以显式定义析构函数。

析构函数的调用顺序

• 局部对象：在函数退出时，局部对象的析构函数按照构造的逆序被调用。
  • 例如，如果在一个函数中先后创建了 obj1 和 obj2，则 obj2 的析构函数先被调用，然后是 obj1 的析构函数。
• 全局对象：在程序结束时，全局对象的析构函数按照构造的逆序被调用。
  • 例如，如果全局对象 obj1 在 obj2 之前构造，则 obj2 的析构函数先被调用，然后是 obj1 的析构函数。
• 派生类和基类：当一个类继承自另一个类时，派生类的析构函数会在基类的析构函数之前被调用。
  • 如果派生类的析构函数没有显式调用基类的析构函数，则默认调用基类的析构函数。
  • 如果基类的析构函数是虚析构函数（virtual destructor），则派生类的析构函数会正确调用基类的析构函数。

析构函数的规则

• 虚析构函数：如果希望在派生类中正确调用基类的析构函数，可以将基类的析构函数声明为虚析构函数。
  • 例如，virtual ~BaseClass();。
• 默认析构函数：如果类中没有显式定义析构函数，编译器会自动生成一个默认析构函数。如果类中有成员需要显式清理，则应显式定义析构函数。
• 成员清理：析构函数通常用于释放对象中分配的资源，例如释放动态分配的内存、关闭文件、撤销网络连接等。

析构函数的应用场景

• 释放资源：析构函数用于释放对象在构造时分配的资源。
  • 例如，释放动态分配的内存、关闭打开的文件描述符等。
• 清理工作：析构函数用于执行对象销毁前的清理工作。
  • 例如，取消注册的事件监听器、释放互斥锁等。
• 保证对象的完整性：析构函数确保对象在销毁时处于一个完整且一致的状态。
  • 例如，释放持有的锁，避免资源泄露。

什么时候必须要用初始化列表初始化？

必须使用初始化列表的情况

• 引用成员变量（Reference Member Variables）
  • 引用必须在声明时绑定到一个对象，并且在绑定后不能重新绑定。
  • 因此，引用成员变量必须在构造函数的初始化列表中初始化。

代码语言：cpp复制

class MyClass {
public:
    MyClass(int& ref) : refMember(ref) {}
private:
    int& refMember;  // 引用成员变量
};

• 常量成员变量（Constant Member Variables）
  • 常量成员变量（const 成员变量）必须在构造函数的初始化列表中初始化。
  • 这是因为常量成员变量不能在构造函数体内进行赋值。

代码语言：cpp复制

class MyClass {
public:
    MyClass(int const val) : constMember(val) {}
private:
    int const constMember;  // 常量成员变量
};

• 基类构造函数（Base Class Constructors）
  • 如果一个类继承自另一个类，并且基类的构造函数需要参数，那么必须在派生类的构造函数初始化列表中显式调用基类构造函数。

代码语言：cpp复制

class Base 
{
public:
    Base(int val) : value(val) {}
private:
    int value;
};

class Derived : public Base 
{
public:
    Derived(int baseVal, int derivedVal) : Base(baseVal), derivedValue(derivedVal) {}
private:
    int derivedValue;
};

• 需要显式调用构造函数的成员变量（Members Requiring Explicit Construction）
  • 有些成员变量（如 std::vector 或者自定义类型的对象）需要显式调用构造函数来初始化。
  • 这些成员变量在初始化列表中通过传递构造函数的参数来初始化，而不是通过赋值。

代码语言：cpp复制

class MyClass 
{
public:
    MyClass(const std::vector<int>& vec) : data(vec.begin(), vec.end()) {}
private:
    std::vector<int> data;
};

• 成员变量初始化顺序要求（Initialization Order Requirements）
  • 如果成员变量之间存在依赖关系，必须按照一定的顺序初始化，这时初始化列表可以明确指定初始化顺序。

代码语言：cpp复制

class MyClass 
{
public:
    MyClass(int val1, int val2) : member1(val1), member2(member1   val2) {}
private:
    int member1;
    int member2;
};

总结

使用初始化列表的情况包括但不限于：

1. 引用成员变量（Reference Member Variables）。
2. 常量成员变量（Constant Member Variables）。
3. 基类构造函数（Base Class Constructors）。
4. 需要显式调用构造函数的成员变量（Members Requiring Explicit Construction）。
5. 成员变量初始化顺序要求（Initialization Order Requirements）。

什么时候需要类的拷贝构造函数（什么时候需要深拷贝）？

• 对象作为函数参数传递：当对象作为函数参数传递时，默认情况下会调用拷贝构造函数来创建一个临时对象。
• 对象作为函数返回值：当函数返回一个对象时，默认情况下会调用拷贝构造函数来创建一个临时对象。
• 对象初始化另一个对象：当使用一个对象初始化另一个对象时，会调用拷贝构造函数。
• 容器或STL算法：当使用容器（如std::vector、std::list等）或STL算法（如std::sort、std::copy等）时，通常需要拷贝构造函数来创建对象的副本。

拷贝构造和赋值运算符的区别？

主要区别

• 调用时机：
  • 拷贝构造函数在创建新对象时调用。
  • 赋值运算符在已有对象的状态需要被改变时调用。
• 对象状态：
  • 使用拷贝构造函数创建的对象是新的独立实体。
  • 使用赋值运算符的对象已经是存在的，并且可能会覆盖现有的状态。
• 资源管理：
  • 拷贝构造函数通常需要管理新对象的内存分配。
  • 赋值运算符可能需要释放旧资源，并可能重新分配新资源。

拷贝构造函数

拷贝构造函数是一种特殊的构造函数，用于创建一个新对象作为已存在对象的副本。它被调用的情况包括：

• 当一个新对象通过已存在的对象初始化时；
• 当一个函数参数通过引用传递，并且该函数被调用时；
• 当一个函数返回的对象通过值返回时；
• 当一个对象用于初始化另一个对象时。 拷贝构造函数的一个重要特征是在对象被创建时就被调用，它负责“深拷贝”，即不仅复制对象的数据成员，还复制它们指向的资源。

赋值运算符

赋值运算符是一个成员函数，用于更新已存在的对象，使其与另一个对象相等。它通常被重载以实现类的赋值操作，并且通常遵循“返回 *this”的约定以便支持连续赋值。

赋值运算符被调用的情况包括：

• 当一个已存在的对象需要被设置为另一个对象的状态时。 赋值运算符的一个重要特征是在对象已经存在的情况下被调用，并且通常执行“浅拷贝”除非特别设计成“深拷贝”。

---

虚函数系列-多态相关

什么是虚继承？

虚继承的主要目的是确保在多重继承的情况下，基类的对象只被继承一次，而不是多次。这有助于避免基类成员的多份副本带来的数据不一致问题。

虚继承的应用场景

1. 单一实例的需求：当你希望在多重继承的情况下，确保基类的对象在派生类中只有一个实例时，使用虚继承是有意义的。
2. 避免菱形继承问题：在多重继承中，如果一个派生类继承自两个或更多共同继承同一个基类的类，则会出现菱形继承问题。虚继承可以解决这个问题，确保基类只被继承一次。

多态基本概念

c 支持编译时多态(静态多态)和运行时多态(动态多态) 运算符重载和函数 重载就是编译时多态

• 编译时多态（静态多态）：
  • 这种多态通常是通过函数重载（Overloading）和运算符重载（Operator Overloading）实现的。
  • 函数重载允许在一个作用域中定义多个同名函数，只要它们的参数列表不同即可。
  • 运算符重载则是为已有的运算符提供自定义的行为，使其适用于用户定义的类型。
• 运行时多态（动态多态）：
  • 运行时多态是通过继承和虚函数（Virtual Functions）实现的。
  • 当一个基类指针或引用指向派生类对象，并且调用虚函数时，实际调用的是该派生类所覆盖的函数版本，而不是基类中的版本。
  • 要实现这一点，必须在基类中声明虚函数，并且在派生类中可以重写这些虚函数。

虚函数和纯虚函数

虚函数是一种成员函数，它允许基类指针或引用来调用派生类中的对应函数，从而实现多态性。

特点：

• 多态性：通过基类指针或引用调用虚函数时，会调用派生类中重写的函数（如果有的话）。
• 可选实现：基类可以提供虚函数的一个实现，派生类可以选择覆盖这个实现，也可以选择不覆盖而使用基类的实现。
• 虚表：编译器会在运行时生成一个虚表（vtable），用于存储虚函数的地址。对象中会有一个指向虚表的指针（vptr），用于查找虚函数的地址并调用。

纯虚函数是一种特殊的虚函数，它在基类中只有声明而没有定义。纯虚函数用于强制派生类必须实现这个函数，否则派生类也不能实例化。

特点：

• 声明形式：纯虚函数在声明时使用= 0来表示。
• 抽象类：含有纯虚函数的类称为抽象类，抽象类不能被实例化。
• 强制实现：派生类必须实现纯虚函数，否则派生类仍然是抽象类，也不能被实例化。

虚表

虚函数表（Vtable）：每个含有虚函数的类都有一个虚函数表（Vtable），它是一个指向该类所有虚函数的指针数组。

虚表指针（Vptr）：每个对象都有一个虚表指针（Vptr），指向其所属类的虚函数表。

动态绑定：当调用一个虚函数时，编译器会通过对象的虚表指针找到正确的函数地址并调用，而不是在编译时就确定调用哪个函数。这就是动态绑定。

虚函数表指针

• 虚表是属于类的，而不是属于某个具体的对象，一个类只有一个虚表。
• 同一个类的所有对象都使用同一个虚表。
• 虚表是动态绑定的，它是在创建时进行绑定的,需要注意的是如果在析构时，先调用子类析构，然后还原到父类的析构函数。
• 如果继承多个类，就会生成多个虚表

是否存在多个虚表指针的情况

在 C 中，通常一个对象只有一个虚表指针（vptr）。但是，在某些特殊情况下，确实可能会有多个虚表指针的情况：

• 多重继承：
• 如果一个类有多个基类，并且这些基类中有虚函数，那么这个类可能会有多个虚表指针，每个基类对应一个虚表指针。
• 虚继承：
• 在虚继承的情况下，编译器可能会生成额外的虚表指针来解决多个基类的虚继承问题。

虚函数指针（Vptr）

除了虚函数表之外，每个对象还有一个虚函数指针（Virtual Pointer，简称 vptr），它指向该对象所属类的虚函数表。

这个指针通常是一个void*类型的指针，会占用一定大小的空间（通常为 4 字节或 8 字节，取决于平台的指针大小）。因为虚函数表本身不直接属于对象，但它存储了虚函数的地址信息，所以对于每个对象来说，指向虚函数表的指针是必要的。

• 对象布局：
  • 对象通常包含一个额外的字段，用于存储虚函数指针（vptr）。
  • 这个字段通常位于对象的起始位置。
  • 通过这个指针，可以访问虚函数表中的虚函数。

下面是一个简单的示例，展示虚函数表和虚函数指针的工作原理：

代码语言：cpp复制

#include <iostream>

class Base {
public:
    virtual void print() {
        std::cout << "Base::print()" << std::endl;
    }

    virtual ~Base() {
        std::cout << "Base::~Base()" << std::endl;
    }
};

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

    ~Derived() {
        std::cout << "Derived::~Derived()" << std::endl;
    }
};

int main() {
    Base* basePtr = new Derived();
    basePtr->print();  // 动态绑定，调用 Derived::print()
    delete basePtr;    // 调用 Derived 的析构函数

    return 0;
}

为什么构造函数不可以是虚函数？

构造函数的调用是在编译时确定的，而虚函数的调用是在运行时确定的。如果构造函数是虚函数，那么在派生类中重写构造函数时，编译器将无法知道应该调用哪个构造函数，这会导致编译错误或运行时错误。

虚析构函数的作用，没有虚析构会导致什么后果

• 虚析构函数（Virtual Destructor）是一个虚函数，用于确保当通过基类指针删除派生类对象时，派生类的析构函数也能被正确调用，没有虚析构会导致资源泄露
• 正确释放资源：确保派生类中的资源能够被正确释放。
• 避免资源泄露：避免由于派生类的析构函数没有被调用而导致的资源泄露问题。

抽象类的使用

抽象类，即纯虚类，类的内部成员函数全部是纯虚函数。

• 抽象类不能直接被实例化
• 抽象类不与具体的事物相联系, 而只是表达一种抽象的概念

// 使用抽象类，不需要关心子类的具体实现细节，只需要知道，该接口函数调用后

// 会达到预取的效果即可，它就可以为以后开发，提供丰富的可变性

---

内存相关

内存泄露

内存泄露是指程序在动态分配内存后未能正确释放，导致这部分内存无法被回收。内存泄露可能导致程序消耗越来越多的内存，最终可能导致性能下降甚至崩溃。以下是一些常见的内存泄露场景：

• 忘记释放内存：分配内存后忘记调用delete或free来释放内存。
• 多次释放同一块内存：释放内存后再次尝试释放同一块内存。
• 循环引用：在使用智能指针时，如果没有正确处理循环引用，可能会导致内存无法被正确释放。

内存对齐->结构体大小计算

一句话总结:内存对齐是为了提高数据访问效率，确保数据在特定的边界上开始，一般边界定义为4/8字节做分割

什么是内存对齐？

内存对齐是指数据在内存中的起始地址满足某种特定的要求，通常是要求数据的地址能够被其自然对齐值（Natural Alignment）整除。自然对齐值通常等于数据类型的大小，但有时也可能更大。

为什么需要内存对齐？

• 硬件需求：许多处理器在访问未对齐的数据时会产生额外的开销。例如，如果一个 4 字节的整数不在 4 字节边界上，处理器可能需要两次内存访问来读取完整的数据，这会降低性能。
• 性能优化：对齐的数据可以让处理器更高效地读取和写入数据。这是因为处理器通常能够更快地处理对齐的数据。
• 缓存优化：对齐的数据有助于优化缓存的使用，因为缓存行通常也遵循一定的对齐规则。

内存对齐的一个优化例子

这里笔者采用的是VS编译器

不同的编译器结果可能不同，仅供参考

代码语言：cpp复制

struct S1
{
	int b;
	char a;
	char c;
};

struct S2
{
	char a;
	int b;
	char c;
};

struct S3
{
	char a;
	char c;
	int b;
};

int main()
{
	printf("%dn", sizeof(S1)); 输出 8
    printf("%dn", sizeof(S2)); 输出 12 
    printf("%dn", sizeof(S3)); 输出 8
	return 0;
}

注意S2 因为 char int char

变成了 4 4 4的字节占据空间，为什么会这样请读者自行思考内存对齐或者查询ai可知

void*占多少字节？

在 32 位系统上，void* 占用 4 字节。

在 64 位系统上，void* 占用 8 字节。

一个结构体大小计算练习

这里笔者采用的是VS编译器

不同的编译器结果可能不同，仅供参考

代码语言：cpp复制

#include <iostream>
#include <vector>


struct MyStruct {
	int i;        // 4 字节
	short s;      // 2 字节
	void* ptr;    // 4 字节（32 位）或 8 字节（64 位）
	bool b;       // 1 字节
};

int main()
{
#ifdef _WIN64
	std::cout << "64-bit Windows detected" << std::endl;
	std::cout << "Size of MyStruct (64-bit): " << sizeof(MyStruct) << " bytes" << std::endl;   //输出为24
#else
	std::cout << "32-bit Windows detected" << std::endl;
	std::cout << "Size of MyStruct (32-bit): " << sizeof(MyStruct) << " bytes" << std::endl;   //输出为16
#endif
	return 0;
}

在 64 位系统上，void* 指针的大小为 8 字节。我们来逐步分析 MyStruct 的成员对齐情况：

• int i: 占 4 字节
• short s: 占 2 字节，为了对齐 void* ptr，需要 2 字节的填充
• void* ptr: 占 8 字节
• bool b: 占 1 字节，为了对齐到 8 字节边界，需要 7 字节的填充

因此，整个 MyStruct 的大小为 24 字节。

深拷贝和浅拷贝

• 浅拷贝是指在复制对象时，仅仅复制对象的成员变量的值，而不复制成员变量指向的数据。如果成员变量是指针或引用，则浅拷贝只会复制指针或引用本身，而不是指针所指向的数据。这意味着原始对象和复制对象会共享同一块内存区域。
• 深拷贝是指在复制对象时，不仅复制对象的成员变量的值，还会复制成员变量指向的数据。这意味着原始对象和复制对象各自拥有一份独立的数据拷贝。

总结:

• 浅拷贝：仅仅复制指针的值，不复制指针指向的数据。容易导致数据不一致和内存泄漏。
• 深拷贝：不仅复制指针的值，还复制指针指向的数据。避免了数据不一致和内存泄漏。

堆栈溢出

堆栈溢出一般是什么原因导致的堆栈溢出通常是由以下几种原因导致的：

1. 函数调用层次太深：在函数递归调用时，每次调用都会在栈中保存函数调用时的现场和产生的变量。如果递归调用太深，会耗尽栈的空间，从而导致栈溢出。这时，递归无法正常返回，也可能是因为函数调用层次过深，导致栈无法容纳所有的返回地址，从而引发栈溢出2。
2. 动态申请空间使用之后没有释放：在C语言中，没有垃圾资源自动回收机制，因此需要程序主动释放已经不再使用的动态地址空间。虽然动态空间使用的是堆空间，而不是栈空间，但如果不正确管理，仍然可能导致内存泄漏，间接影响到栈的空间。
3. 数组访问越界：C语言没有提供数组下标越界检查，如果程序中出现数组下标访问超出数组范围的情况，可能会导致内存访问错误，从而影响到栈的安全性2。
4. 指针非法访问：如果指针保存了一个非法的地址，通过这样的指针访问所指向的地址时，会产生内存访问错误，这也可能间接导致栈的稳定性受到影响2。

解决堆栈溢出的方法包括：

• 避免过深的递归调用，尝试使用迭代替代递归，或用尾递归优化。
• 及时释放不再使用的动态内存空间，减少内存泄漏。
• 检查数组访问是否越界，确保内存访问的安全性。
• 正确管理指针，避免非法访问。

通过以上措施，可以有效降低堆栈溢出的风险，保证程序的稳定运行。

递归和尾递归

递归（Recursion）

递归是一种函数调用自身的编程技术。在递归函数中，函数会不断地调用自身来解决问题的一部分，直到达到基本情况（base case）为止。递归函数的一个典型例子是计算阶乘。

递归的原理

• 基本情况（Base Case）：
  • 确定递归何时停止，通常是最简单的情况，可以直接求解。
• 递归情况（Recursive Case）：
  • 递归函数调用自身来解决更小规模的问题，并逐步逼近基本情况。

递归的例子

计算阶乘 n!：

代码语言：javascript复制

int factorial(int n) {
    if (n == 0) {
        return 1;  // 基本情况
    } else {
        return n * factorial(n - 1);  // 递归情况
    }
}

递归的缺点

• 栈溢出：
  • 递归深度较深时，每次函数调用都会在栈上分配内存，可能导致栈溢出（stack overflow）。
• 效率低下：
  • 递归函数通常会产生大量的函数调用开销，包括参数传递、返回地址保存等。

尾递归（Tail Recursion）

尾递归是一种特殊的递归形式，其中递归调用是函数中的最后一个操作。这意味着递归调用之后不再有其他的操作需要执行。尾递归函数可以被优化，使得每次递归调用都不会增加额外的栈空间。

尾递归的原理

• 尾调用：
  • 递归调用是函数中的最后一个操作，递归调用之后没有其他的操作。
• 优化：
  • 编译器可以优化尾递归，将其转换为迭代形式，避免栈溢出。

尾递归的例子

计算阶乘 n!n! 的尾递归版本：

代码语言：javascript复制

int tailFactorial(int n, int accumulator = 1) {
    if (n == 0) {
        return accumulator;  // 基本情况
    } else {
        return tailFactorial(n - 1, n * accumulator);  // 尾递归情况
    }
}

在这个例子中，tailFactorial 函数的递归调用是函数中的最后一个操作，因此它是尾递归。

尾递归的优点

• 防止栈溢出：
  • 由于尾递归可以被优化成迭代形式，因此可以避免栈溢出的问题。
• 效率更高：
  • 相比普通递归，尾递归可以减少函数调用的开销，提高效率。

尾递归优化

并不是所有的编程语言都支持尾递归优化。例如，C 编译器通常会支持尾递归优化，而 Python 则不支持尾递归优化。

尾递归优化的原理

尾递归优化的原理是将递归调用转换为迭代操作。每次递归调用时，编译器会用一个新的参数值替换当前的参数值，而不是在栈上分配新的空间。这样可以避免栈溢出。

示例对比

普通递归

代码语言：javascript复制

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int result = factorial(10000);  // 可能导致栈溢出
    return 0;
}

尾递归

代码语言：javascript复制

int tailFactorial(int n, int accumulator = 1) {
    if (n == 0) {
        return accumulator;
    } else {
        return tailFactorial(n - 1, n * accumulator);
    }
}

int main() {
    int result = tailFactorial(10000);  // 不会导致栈溢出
    return 0;
}

总结

递归和尾递归都是解决递归问题的有效方法，但尾递归通常更加高效和安全，因为它可以避免栈溢出，并减少函数调用的开销。尾递归可以通过编译器优化来转换为迭代形式，从而提高程序的性能。

new了一个int类型的数组，new的前后发现进程中的内存占用是没有变化的，可能是什么原因导致的？

• 延迟分配（Lazy Allocation）：
  • 当使用 new 分配内存时，操作系统可能只是标记了一块虚拟内存区域，但是并没有实际分配物理内存。只有当访问这块内存中的某个地址时，操作系统才会触发 缺页中断（page fault），从而分配物理内存页。
• 内存压缩（Memory Compression）：
  • 在一些操作系统中，例如 macOS，内存会被压缩存放在物理内存中。这意味着即使分配了内存，操作系统也可能暂时不分配物理内存页，而是将数据压缩存放。
• 内存交换（Memory Paging/Swapping）：
  • 如果操作系统有足够的虚拟内存空间，但是物理内存紧张，操作系统可能会将一些不常用的页面交换到磁盘上的交换分区（swap space），从而腾出物理内存供新分配的内存使用。
• 内存重用（Memory Reuse）：
  • 如果之前有释放的内存块，操作系统可能会重用这块内存，而不是分配新的物理内存页。因此，从外部工具来看，内存占用可能没有变化。

---

排序

放几个常用的排序写法

快排

代码语言：cpp复制

#include<iostream>

void QuickSort(int* arr, int begin, int end)
{
	// 只有一个数或区间不存在
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	// 选左边为key
	int keyi = begin;
	int pivot = arr[keyi];  // 添加pivot变量来存储基准值

	while (begin < end)
	{
		// 右边选小于pivot的值
		while (arr[end] >= pivot && begin < end)
		{
			--end;
		}
		// 左边选大于pivot的值
		while (arr[begin] <= pivot && begin < end)
		{
			  begin;
		}
		// 小的换到右边，大的换到左边
		int temp = arr[begin];
		arr[begin] = arr[end];
		arr[end] = temp;
	}

	// 把基准值放到正确的位置
	int temp = arr[keyi];
	arr[keyi] = arr[begin];
	arr[begin] = temp;
	keyi = begin;

	// 分别对左右两个子数组进行递归排序
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi   1, right);
}

int main()
{
	int a[] = { 80,30,60,40,20,10,50,70 };
	int ilen = sizeof(a) / sizeof(a[0]);

	cout << "before sort: ";
	for (int i = 0; i < ilen; i  )
	{
		cout << a[i] << " ";
	}
	cout << endl;

	QuickSort(a, 0, ilen - 1); 

	cout << "after  sort: ";
	for (int i = 0; i < ilen; i  )
	{
		cout << a[i] << " ";
	}
	cout << endl;

	return 0;
}

冒泡排序

代码语言：cpp复制

#include <iostream>

void bubbleSort(int arr[], int n)
{
    bool swapped;
    for (int i = 0; i < n - 1; i  ) 
    {
        swapped = false;
        // 每一轮将未排序的最大元素冒泡到正确的位置
        for (int j = 0; j < n - 1 - i; j  ) 
        {
            if (arr[j] > arr[j   1]) 
            {
                // 交换 arr[j] 和 arr[j   1]
                std::swap(arr[j], arr[j   1]);
                swapped = true;
            }
        }
        // 如果没有发生任何交换，那么数组已经有序
        if (!swapped)
            break;
    }
}

int main()
{
    int a[] = { 80, 30, 60, 40, 20, 10, 50, 70 };
    int ilen = sizeof(a) / sizeof(a[0]);

    std::cout << "Before sort: ";
    for (int i = 0; i < ilen; i  ) 
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    bubbleSort(a, ilen);

    std::cout << "After sort: ";
    for (int i = 0; i < ilen; i  ) 
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

一个简单的最大堆排序实现基于数组

代码语言：cpp复制

#include <iostream>

// 函数原型声明
void heapify(int arr[], int n, int i);
void heapSort(int arr[], int n);

int main()
{
    int a[] = { 80, 30, 60, 40, 20, 10, 50, 70 };
    int ilen = sizeof(a) / sizeof(a[0]);

    std::cout << "Before sort: ";
    for (int i = 0; i < ilen; i  ) {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    heapSort(a, ilen);

    std::cout << "After sort: ";
    for (int i = 0; i < ilen; i  ) {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

// 该函数用于维护最大堆的性质
void heapify(int arr[], int n, int i)
{
    int largest = i;  // 初始化最大值为根
    int left = 2 * i   1;  // 左子节点
    int right = 2 * i   2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i)
    {
        std::swap(arr[i], arr[largest]);

        // 递归地修复受影响的子树
        heapify(arr, n, largest);
    }
}

// 主要的堆排序函数
void heapSort(int arr[], int n)
{
    // 建立最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i >= 0; i--)
    {
        // 将当前根节点与末尾交换
        std::swap(arr[0], arr[i]);

        // 调用最大堆修复函数
        heapify(arr, i, 0);
    }
}

菜鸟编程

10000个人，将其按照0~100的得分从高到低（得分有相等）排序，最少需要排序多少次？为什么

对于确定排序所需的最小比较次数，我们需要了解一些关于排序理论的基础知识。根据比较排序的原理，在最坏的情况下，任何基于比较的排序算法至少需要 O(n log n) 比较次数来完成对 n 个元素的排序。这里的 "O" 表示大O符号，用来描述算法的时间复杂度上限。

对于 10,000 个人进行排序，如果得分是从 0 到 100 的整数，那么一共有 101 种可能的得分。在最好的情况下（即，如果我们可以利用这些得分的离散性），我们可以使用计数排序、桶排序或者基数排序这类线性时间复杂度的算法。对于这种特定情况，如果我们使用计数排序的话，时间复杂度可以降低为 O(n k)，其中 n 是人数（10,000），k 是可能的得分种类数（101）。在这种情况下，算法的运行时间主要取决于列表的长度，而不是得分范围。

但是，如果必须使用基于比较的排序算法（如快速排序、归并排序等），那么即使所有人的得分都相同，也需要至少 O(n log n) 的比较次数来确认这一点。对于 10,000 个人来说，这意味着至少需要大约 10,000 * log2(10,000) ≈ 133,000 次比较。

总结来说：

• 如果可以使用非比较排序算法（例如计数排序），则可以更快地完成排序。
• 如果必须使用基于比较的排序算法，则在最坏的情况下，需要至少 O(n log n) 的比较次数。

进阶的一些知识

设计一个栈的数据结构，要求入栈、出栈和返回栈中最小元素这三个方法的时间复杂度都为O(1)，怎么实现

为了实现一个栈，使得入栈、出栈和返回栈中最小元素的操作时间复杂度均为 O(1)，我们可以采用两个栈的方法：一个主栈用于存储所有的元素，另一个辅助栈用于跟踪当前栈中的最小元素。

具体实现如下：

1. 主栈（Main Stack）：用于存储所有的元素。
2. 辅助栈（Min Stack）：用于存储当前栈中的最小元素。每当有新的元素入栈时，检查这个元素是否小于辅助栈顶部的元素。如果是，则将这个元素压入辅助栈；如果不是，则不改变辅助栈顶部的元素。

代码语言：cpp复制

class MinStack {
private:
    std::stack<int> mainStack;  // 存储所有元素
    std::stack<int> minStack;   // 存储当前最小元素

public:
    // 入栈操作
    void push(int x) {
        mainStack.push(x);
        // 如果辅助栈为空，或者新元素小于等于辅助栈的顶部元素，则将其推入辅助栈
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    // 出栈操作
    void pop() {
        if (mainStack.empty()) {
            throw std::runtime_error("Stack is empty.");
        }
        // 如果要弹出的元素等于辅助栈的顶部元素，则同时弹出辅助栈的顶部元素
        if (mainStack.top() == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
    }

    // 获取栈顶元素
    int top() {
        if (mainStack.empty()) {
            throw std::runtime_error("Stack is empty.");
        }
        return mainStack.top();
    }

    // 获取栈中的最小元素
    int getMin() {
        if (minStack.empty()) {
            throw std::runtime_error("Stack is empty.");
        }
        return minStack.top();
    }
};

待补充部分-->建议关键字检索其它博客

各类树

例如：

avl树->性质->旋转规律

红黑树->性质->旋转规律

跳表->实现跳表

定时器->实现一个定时器类

时间轮的定时器->实现一个时间轮的定时器类

学习笔记 腾讯技术创作特训营S9 c++ 面试

0 人点赞