C/C++面试知识点总结

1. 指针

（1）危险的指针：

1. 野指针：指针指向的位置是不可知的。
2. 悬空指针：指针最初指向的内存已经被释放了的⼀种指针。

（2）两种指针都指向无效内存空间，即不安全不可控。需要在定义指针后且在使用之前完成初始化或者使用智能指针来避免。想更加深入了解指针见博客《指针的进阶》。

1.1 智能指针

（1）智能指针的作用就是管理指针，避免使用普通指针申请的空间在函数结束时忘记释放，造成内存泄漏。因为智能指针是⼀个类，当超出类的作用域时，类会自动调用析构函数，析构函数有释放资源的操作。具体包含的类型如下：

• auto_ptr 采用所有权模式（在C++11已弃用），使得⼀个该类型指针可以剥夺另⼀个该类型指针的所有权，使得被剥夺所有权的指针失效，缺点是使用被剥夺的指针存在潜在的内存崩溃问题。
• unique_ptr 实现独占式拥有，保证同⼀时间内只有⼀个智能指针可以指向该对象，避免上述内存崩溃的出现。只能通过 new 来创建。
• shared_ptr 实现共享式拥有，可以用 new 来构造，还可以引入其他智能指针来构造。多个智能指针可以指向相同的对象，该对象和其相关资源会在最后⼀个引用（use_count() 查看引用数）被销毁时释放。当调用 release() 时，当前指针会释放资源所有权，计数减⼀。当计数等于0 时，资源会被释放。资源消耗大，因为创建时会调用两次new（其中⼀次是引用计数对象）。
• weak_ptr 是⼀种不控制对象生命周期的智能指针，它指向⼀个 shared_ptr 管理的对象。进行该对象内存管理的是 shared_ptr，weak_ptr 只是提供了对管理对象的⼀个访问方法，目的是为了协助shared_ptr 工作，它只可以从⼀个 shared_ptr 或另⼀个 weak_ptr 对象构造，且不会引起引用计数值的变化。主要用来解决 空悬指针 和 循环引用 问题。空悬指针是两个共享指针同时引用同⼀个对象，但是其中⼀个指针将该对象销毁，另⼀个指针会指向为空，可通过使用 weak_ptr 来判断指向对象是否有效；循环引用是指两个对象之间相互引用，则引用计数将⽆法减为0，而其中一方改为 weak_ptr 则可检测是否有效，且能将有效的指向对象转换为共享指针进行操作。

（2）智能指针的实现以及原理可以参考博客《智能指针》。

1.2 指针和引用的区别

• 指针和引用都是⼀种内存地址的概念，但是指针是一个实体，可以声明为 void；引用只是⼀个别名，不能为 void。
• 引用内部其实是⼀个指针，引用比指针更安全；相对的，引用没有指针灵活。
• 引用和指针都可以作为参数传递给函数，用于更改函数作用域外的变量，在传递大对象时避免复制，提升效率。作为参数时也有不同，传递指针的实质是传值，传递的值是指针的地址；传引用的实质是传地址，传递的是变量的地址。
• 指针可以有多级指向，但是引用只能有一级引用。
• 引用是一块内存的别名，在添加到符号表时，是将“引用变量名-引用对象的地址”添加到符号表中，符号表一经完成不能改变，所以引用只能在定义时被绑定到一块内存上，后续不能更改引用对象。指针指向一块内存，其值是所指向的内存的地址，在编译的时候，则是将“指针变量名-指针变量的地址”添加到符号表中，所以指针包含的内容是可以改变的，允许拷贝和赋值。

1.3 数组和指针的区别

1. 数组存放的是数据，是直接访问数据的；指针存放的是变量的地址，是间接访问数据的；
2. 数组通常存储在静态存储区或栈上；指针可以随时地指向任意类型的内存块；
3. 用运算符 sizeof 可以计算出数组的容量（字节数）；sizeof§ 得到的是⼀个指针变量 p 的字节数，而不是 p 指针所指向的内存容量；
4. char a[] = “hello” 数组指向每个数组元素；char *p = “hello” 而 p 指向字符串首地址；

1.4 数组指针和指针数组的区别

（1）数组指针（指向数组的指针）：

1. 数组在内存中的表示：创建⼀个数组就是在内存里面开辟⼀块连续的空间；

int a[2][2] = {1,2,3,4}; //这是⼀个2*2的⼆维数组
int (*p)[2]; //数组指针
p = a; //令p指向数组a

（2）指针数组（存放指针的数组）。指针数组的好处：

1.5 迭代器和指针的区别

1. 迭代器：用于提供⼀种方法顺序访问⼀个聚合对象中各个元素，而又无需暴露该对象的内部表示。
2. 迭代器和指针区别：迭代器不是指针，是类模板，表现的像指针，其本质是封装了原生指针，提供了比指针更高级的行为，相当于⼀种智能指针，可以根据不同类型的数据结构来实现递增、递减等操作。迭
   代器返回的是对象引用而不是对象的值。

1.6 strcpy 和 memcpy 的区别

• 复制的内容不同。strcpy 只能复制字符串，而 memcpy 可以复制任意内容，例如字符数组、整型、结构体、类等；
• 复制的方法不同。strcpy 不需要指定长度，它遇到被复制字符串的结束符 “\0” 才结束，所以容易溢出。memcpy 则是根据其第 3 个参数决定复制的长度；
• 用途不同。通常在复制字符串时用 strcpy，而需要复制其他类型数据时则⼀般用 memcpy。

2. 内存管理与分配

2.1 内存分配与存储区

（1）C/C++内存分配有三种方式：

• 从静态存储区分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。
• 从栈上分配。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。分配的内存容量有限。
• 从堆上分配，亦称动态内存分配。程序在运行的时候用 malloc 或 new 申请任意大小的内存，程序员自己负责在何时用 free 或 delete 释放内存。

（2）C/C++程序编译时内存分为5大存储区：

• 栈区（stack）。编译器自动分配与释放，主要存放函数的参数值，局部变量值等，连续的内存空间，由高地址向低地址扩展。
• 堆区（heap） 。由程序员分配与释放；不连续的空间，通过空闲链表进行连接。堆是低地址向高地址扩展，空间较大。频繁地分配和释放不同大小的堆空间将会产生堆内碎块。
• 静态存储区。存放全局变量和静态变量；分为全局初始化区和全局未初始化区。
• 常量存储区。存放常量字符串；对于全局常量，编译器⼀般不分配内存，放在符号表中以提高访问效率。
• 程序代码区。存放函数体的⼆进制代码。

（3）详细的内存分配介绍见博客《动态内存管理》和《C/C++内存管理》。

2.2 malloc / free

（1）malloc 申请内存的方式：

1. 通过 brk() 系统调用从堆分配内存：如果用户分配的内存小于 128 KB，就是通过 brk() 函数将「堆顶」指针向高地址移动，获得新的内存空间。free 释放内存的时候，并不会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用；
2. 通过 mmap() 系统调用在文件映射区域分配内存。free 释放内存的时候，会把内存归还给操作系统，内存得到真正的释放。

（2）malloc() 分配的是物理内存吗？

• 并不是的，malloc() 分配的是虚拟内存。如果分配后的虚拟内存没有被访问的话，是不会将虚拟内存映射到物理内存，这样就不会占用物理内存了。只有在访问已分配的虚拟地址空间的时候，操作系统通过查找页表，发现虚拟内存对应的页没有在物理内存中，就会触发缺页中断，然后操作系统会建立虚拟内存和物理内存之间的映射关系。程序地址空间的详细介绍见博客《Linux进程概念》的第七节。

（3）malloc(1) 会分配多大的虚拟内存？

• malloc() 在分配内存的时候，并不是按用户预期申请的字节数来分配内存空间大小，而是会预分配更大的空间。具体会预分配多大的空间，跟 malloc 使用的内存管理器有关。

（4）new/delete、malloc/free的区别：

• 都可以分配和回收空间，new/delete 是运算符，malloc/free 是库函数。new得到的是经过初始化的空间，而malloc得到的是未初始化的空间。
• 执行new有两个过程：
  1. 分配未初始化的内存空间（malloc）。若出现问题则抛出异常。
  2. 使用对象的构造函数进行初始化。若出现异常则自动调用delete释放内存
• 执行delete有两个过程：
  1. 使用析构函数对对象进行析构。
  2. 回收内存空间（free）。

2.3 volatile和extern的区别

（1）volatile：

1. 数据重新从内存中读取。
2. 告诉编译器，不要对这个变量做优化，保证其顺序性。

（2）extern：

1. 用在变量或函数的声明前，说明此变量/函数是在别处定义的，要在此处引用。
2. 在 C++ 中调用 C 库函数，需要在 C++ 程序中用 extern “C” 声明要引用的函数，告诉链接器在链接的时候用 C 语言规范来链接。主要原因是 C++ 和 C 程序编译完成后在目标代码中命名规则不同，以此来解决名字匹配的问题。

2.4 拷贝构造函数

（1）类的对象需要拷贝时，会调用拷贝构造函数。

• 在未定义显式拷贝构造函数的情况下，系统会调用默认的拷贝函数（浅拷贝），它能够完成成员的⼀⼀复制。但当数据成员中有指针时，如果采用简单的浅拷贝，则两类中的两个指针指向同⼀个地址，当对象快要结束时，会调用两次析构函数。深拷贝和浅拷贝的区别 就在于深拷贝会在堆内存中另外申请空间来存储数据，从而解决悬空指针的问题。
• 简而言之，当数据成员中有指针时，必须要深拷贝才安全。
• 详细的拷贝构造函数见博客《类与对象(二)》。

（2）有三种情况会需要拷贝构造函数：

1. ⼀个对象以值传递的方式传入函数体，需要拷贝构造函数创建⼀个临时对象压入到栈空间。
2. ⼀个对象以值传递的方式从函数返回，需要拷贝构造函数创建⼀个临时对象作为返回值。
3. ⼀个对象需要通过另⼀个对象进行初始化。

（3）为什么拷贝构造函数必须是引用传递？

• 防止递归调用。当⼀个对象需要以值方式传递时，编译器会生成代码调用它的拷贝构造函生成⼀个副本，如果该类的拷贝构造函数的参数不是引用传递，而是值传递，那么就需要创建传递给拷贝构造函数参数的临时对象，而又一次调用该类的拷贝构造函数，这就是⼀个无限递归。

2.5 预处理、编译、汇编、链接

1. 预处理阶段：预处理器根据 # 开头的命令，修改原始的程序，如把文件插入到程序文本中，删除所有的注释等。
2. 编译阶段：编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析等，最终产生相应的汇编语言文件，不同的高级语言翻译的汇编语言相同。编译是对源文件分别进行的，每个源文件都产生一个目标文件。
3. 汇编阶段：把汇编语言代码翻译成目标机器指令。
4. 链接阶段：将有关的目标文件和库文件相连接，使得所有的这些文件成为⼀个能够被操作系统装入执行的统⼀整体。链接处理可分为两种：
   • 静态链接：函数的代码将从其所在的静态链接库中被拷贝到最终的可执行文件中。这样程序在被执行时会将其装入到该进程的虚拟地址空间中。静态链接库实际上是⼀个目标文件的集合，其中的每个文件含有库中的⼀个或者⼀组相关函数的代码。
   • 动态链接：函数的代码被放到称作是动态链接库或共享对象的某个目标⽂件中。链接程序要做的只是在最终的可执行文件中记录下相对应的信息。在可执行文件被执行时，根据可执行程序中记录的信息，将动态链接库的全部内容映射到相应运行进程的虚拟地址空间上。

（2）对于可执行文件中的函数调用，可分别采用动态链接或静态链接的方法。使用动态链接能够使最终的可执行文件比较短小，并且当共享对象被多个进程使用时能节约⼀些内存，因为在内存中只需要保存⼀份此共享对象的代码。但并不是使用动态链接就⼀定比使用静态链接要优越。详细的编译过程见博客《程序环境和预处理》。

2.6 define/const/typedef/inline 的区别

	const	#define	typedef	inline
执行/作用时间	编译阶段、链接阶段	预处理阶段（文本替换）	编译阶段	编译阶段（复制）
类型检查	有	没有	有	有
功能	定义常量，无法重定义	定义类型别名、定义常量/变量、定义编译开关、可重定义（#undef）定义	类型别名	解决⼀些频繁调⽤的函数大量消耗栈空间（栈内存）的问题
作用域	\	没有	有	\

2.7 const和static的区别

（1）static：控制变量的存储方式和可见性

1. 修饰局部变量：将存放在栈区且生命周期在包含语句块执行结束时便销毁的局部变量改变为存放在静态存储区，且生命周期会⼀直延续到整个程序执行结束，但是作用域还是限制在其语句块。
2. 修饰全局变量/函数：对于全局变量，既可以在本文件中被访问，也可以被在同一工程中的其他源文件访问（添加 extern 进行声明）。用 static 进行修饰改变了其作用域范围，由原来整个工程可见变为了本文件可见。
3. 修饰类函数：表示该函数属于⼀个类而非实例；若对类中某变量修饰，则表示该变量被所有该类实例所共有，static修饰的类变量先于对象存在，所以其要在类外初始化

（2）const：定义常量

1. 修饰基本数据类型：修饰符 const 可在类型说明符前或后，其结果是⼀样的。在使用时不可以改变这些变量的值。
2. 修饰指针：

// 指针常量：常量，指向的地址不能被改变，但是可以改变地址内的内容。
int a，b；
int * const p=&a; //指针常量
*p = 9; //操作成功
p = &b; //操作错误// 常量指针：指向常量的指针。可以改变其指向的（常量/⾮常量）地址
int a，b；
const int *p = &a; //常量指针
*p = 9; //操作错误
p = &b; //操作成功

3. 类中的用法：const成员变量，只在某个对象生命周期内是常量，而对于整个类而言是可以改变的。因为类可以创建多个对象，不同的对象其const数据成员值可以不同。const数据成员的初始化只能在类的构造函数的初始化列表中进行。const成员函数（在参数列表后加const，此时对this隐式加const）的主要目的是防止成员函数修改对象的内容。常量对象只能调用常量函数。

2.8 声明和定义的区别

• 变量/函数可以声明多次，变量/函数的定义只能⼀次。
• 声明不会分配内存，定义会分配内存。
• 声明是告诉编译器变量或函数的类型和名称等，定义是告诉编译器变量的值，函数具体干什么。
• 更加详细的介绍见博客《声明和定义的区别》。

3. 编程语言的特性

3.1 C++11新增的特性

1. 空指针nullptr：目的是为了替代NULL，用来区分空指针和0，能够隐式转换为任何指针的类型，也能和他们进行相等判断。由于传统C++会把NULL和0视为同⼀种东西，这取决于编译器如何定义NULL，有些编译器会将NULL定义为 ((void)0)，有些会直接将其定义为0。C++不允许直接将 void隐式转换到其他类型，但如果NULL被定义为前者，那么当编译 char *ch = NULL 时，NULL只好被定义为0。而这依然会产生问题，这导致了C++中重载特性会发生混乱。
2. 智能指针。
3. Lambda表达式：利用lambda表达式可以编写内嵌的匿名函数，用以替换独立函数或者函数对象，并且使代码更可读，有值捕获和引用捕获两种方式获取外部对象。
4. 右值引用：右值引用特性允许我们对右值进行修改，借此可以实现move，即从右值中直接拿数据过来初始化或修改左值，而不需要重新构造左值后再析构右值。
5. constexpr ：constexpr 告诉编译器这是⼀个编译期常量，使得定义的变量（⽆需加const）也可以作为数组大小的表示。甚至可以把⼀个函数声明为编译期常量表达式。
6. 统⼀的初始化方法：均可使用 {} 进行初始化变量。
7. 类型推导：提供 auto 和 decltype 来静态推导类型。decltype 用于获取⼀个表达式的类型，而不对表达式求值

const std::vector<int> v(1);
const int&& foo(); 		// 返回临终值：⽣命周期已结束但内存还未拿⾛
auto a = v[0]; 			// a 为 int
decltype(v[0]) b = 0; 	// b 为 const int&
auto c = 0; 			// c, d 均为 int
auto d = c;
decltype(c) e; 			// e 为 int，即 c 的类型
decltype((c)) f = e; 	// f 为 int&，因为 c 是左值
decltype(0) g; 			// g 为 int，因为 0 是右值

8. 基于范围的 for 循环。
9. final 和 override：提供 final 来禁止虚函数被重写/禁止类被继承，override 来显式地重写虚函数。
10. default 和 delete：可以显式地指定和禁止编译器为类自动生成构造或析构函数等。
11. 静态断言：static_assert 关键字可在编译期进行使用，而之前的assert仅在运行期起作用（模板检查在编译期）。
12. 初始化列表：提供 initializer_list 来接受变长的对象初始化列表。
13. 正则表达式。
14. C++11相关功能的详细介绍见博客《C++11》。

3.2 C 和 C++ 的区别

• C 是面向过程的，C++ 是面向对象的。因此C++语言中有类和对象、继承和多态这样的OOP语言必备的内容，此外C++还支持模板，运算符重载以及STL；
• 在输入输出方式上，C 是 printf/scanf 库函数，C++ 是 cout/cin，即 ostream和 istream 类型的对象；
• 在动态内存管理上，C 语言通过 malloc/free 来进行堆内存的分配和释放，而 C++ 是通过new/delete 来管理堆内存；
• 在强制类型转换上，C 的强制类型转换使用小括号里面加类型进行强转，而 C++ 可以使用const_cast，static_cast，reinterpret_cast 和 dynamic_cast 进行强转；
• 在C++中，struct 关键字不仅可以用来定义结构体，也可以用来定义类；
• C++不仅支持指针，还支持更安全的引用。不过在汇编代码上，指针和引用的操作是⼀样的；
• C++支持自定义命名空间，而 C 不支持。

3.3 C++ 和 Java 的区别

• 指针：Java虚拟机内部用到了指针，程序员无法直接访问内存，无指针概念。
• 多重继承：C++支持多重继承但Java不支持，Java支持⼀个类实现多个接口。
• 自动内存管理：Java自动进行无用内存回收，而C++必须程序员释放内存资源。
• 重载运算符：Java不支持。
• 类型转换：C++可隐含转换，Java必须强制转换。
• 字符串：C++中字符串是以NULL终止符代表字符串的结束；Java是用类对象实现的。
• 预处理：Java不支持预处理功能，C++在编译过程中会有⼀个预编译阶段，Java没有预处理器，但提供了import与C++预处理器有类似的功能。

3.4 C++ 和 Python 的区别

• C++为编译型语言；python为解释型的脚本语言。
• C++运行效率高。Python是解释执行的，和物理机CPU之间多了解释器这层，而C++是编译执行的，直接就是机器码，编译的时候编译器又可以进行⼀些优化。
• 开发效率上，Python要比C++快很多。
• 代码形式上差别也很大。

4 类与面向对象

（1）详细的面向对象介绍见博客《类和对象(一)》、《类和对象(二)》、《类和对象(三)》。

4.1 初始化

（1）在C++语言中，初始化和赋值是两个完全不同的操作。初始化和赋值的区别事关底层效率问题。

• 初始化：创建变量时赋予其⼀个初始值。
• 赋值：把对象的当前值删除，并赋予⼀个新的值。

（2）如果在变量初始化时没有指定初始值，则变量进行默认初始化，默认值是由变量类型和位置决定的。内置类型的初始值由定义的位置决定：

• 定义在函数体之外的变量被初始化为0。
• 定义在函数体内部的局部变量则未定义。
• 对于函数体内部的局部静态变量，如果没有显式初始化，它将执⾏默认值初始化。

（3）类内成员的默认初始值由类自己决定：

• 在默认构造函数中进行了赋值，则初始化值为默认构造函数的值。
• 在默认构造函数中没有赋值，但是该数据成员提供了类内初始值，则创建对象时，其初始值就是类内初始值。
• 若上述都无，对于内置类型，则其值未定义；对于类类型则调用其默认构造函数，如果没有默认构造函数，则不能进行值初始化。

（4）若某个类有⼀个类成员是类类型，那么：

• 若类通过在构造函数体内初始化，会先调用成员类的默认无参构造函数，再调用类的赋值运算符；
• 若类通过在初始化列表去初始化，则只调用成员类的拷贝构造函数。
• 另外，虽然对于成员类型是内置类型的情况，通过上述两种情况去初始化是相同的，但是为了标准化，推荐使用初始化列表。

（5）必须使用初始化列表去初始化类成员的情况：

• 成员类型是引用 / 常量；
• 成员类型是对象，并且这个对象没有⽆参数的构造函数；
• 子类初始化父类的私有成员。

（6）类成员的初始化顺序不是按照初始化列表的顺序来的，而是按照类成员的声明顺序。

4.2 重载、重写以及重定义的区别

（1）如下表所示：

	重载	重写（函数体）	重定义
同名函数	是	是	是
参数列表	参数个数、参数类型或参数顺序三者中必须⾄少有⼀种不同	同	可以不同
返回类型有关	可以相同，也可以不相同	同	可以不同
用于	同⼀作用域	父类虚函数	父类非虚函数

• 重载：函数名相同，函数的参数个数、参数类型或参数顺序三者中必须至少有⼀种不同。函数返回值的类型可以相同，也可以不相同。发生在⼀个作用域内。
• 重写：也叫覆盖(override)，⼀般发生在子类和父类继承关系之间。子类重写父类中有相同名称和参数的虚函数。
• 重定义：子类重新定义父类中有相同名称的非虚函数 ( 参数列表可以不同 ) ，派生类的函数屏蔽了与其同名的基类函数。如果⼀个派生类，存在重定义的函数，那么，这个类将会隐藏其父类的方法，除非在调用的时候，强制转换为父类类型，才能调用到父类方法。否则试图对子类和父类做类似重载的调用是不能成功的。这也就是多态的实现，多态实现的原理见博客《C++多态》。

（2）重写需要注意：

1. 被重写的函数必须是 virtual 的；
2. 重写函数必须有相同的类型，名称和参数列表；
3. 重写函数的访问修饰符可以不同。

（3）重定义需要注意：

• 如果派生类的函数与基类的函数同名，但是参数不同，此时，不管有无 virtual，基类的函数被隐藏。
• 如果派生类的函数与基类的函数同名，参数也相同，但是基类函数没有 vitual 关键字，此时，基类的函数被隐藏（如果有 Virtual 就是重写覆盖了）。

4.3 四种强制类型转换以及结构体和类的区别

（1）四种强制类型转换：

• static_cast：明确指出类型转换，⼀般建议将隐式转换都替换成显示转换，因为没有动态类型检查，派生类转基类安全，反之不安全，所以主要执行非多态的转换。
• dynamic_cast：专门用于派生类之间的转换。当类型不⼀致时转换过来的是空指针，而 static_cast 当类型不⼀致时转换过来的是错误的指针，可能造成非法访问等问题
• const_cast：专门用于const属性的转换，主要用来去除 const 和 volatile 限定符。具体用法是用于指针或引用，间接操作被const修饰的变量。
• reinterpret_cast：从底层对数据进行重新解释，依赖具体的平台，可移植性差。
• 类型转换详细的介绍见博客《C++的类型转换》。

（2）结构体和类的区别：

• 默认继承、成员访问权限不⼀样。
• 是否支持类模板。

4.4 类的大小与内存对齐

（1）利用sizeof计算类的大小：

class A{}; 					// sizeof(A) = 1 （标识这是⼀个类）
class A{virtual Fun()}; 	// sizeof(A) = 8 （64位，有⼀个指向虚函数表的指针）
class A{static int a;}; 	// sizeof(A) = 1 （静态变量存储在静态存储区，不占类空间）
class A{int a;} 			// sizeof(A) = 4
class A{int a; char c;} 	// sizeof(A) = 8
class A{Fun()}; 			// sizeof(A) = 1 (普通函数不占空间)

（2）为什么进行内存对齐？

• 内存访问次数影响：为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要⼀次访问。
• 硬件平台⽀持问题：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
• 空间消耗问题：没有进行内存对齐的结构体或类会浪费⼀定的空间，当创建对象越多时，消耗的空间越多。

4.5 面向对象的三大特征

（1）封装：

• 把客观事物封装成抽象的类。⼀个类就是⼀个封装了数据以及操作这些数据的逻辑实现，其中某些代码或者数据是有不同的访问权限，以防止程序被意外改变或使用对象的私有部分。

（2）继承：

• 指可以让某个类型的对象获得另⼀个类型对象属性的方法。可以使用现有类的所有功能，并在无需重新编写原来类的情况下对这些功能进行扩展。
• 继承分为 实现继承 和 接口继承 两种，实现继承是指直接使用基类的属性和方法而无需额外编码的能力；接口继承是指仅使用属性和方法的名称，但是派生类必须提供其实现。
• C++还支持多继承也就是一个子类可以继承多个父类。但是多继承会衍生出菱形继承的问题，即会产生二义性和冗余的问题。为了解决菱形继承的问题C++提出了菱形虚拟继承，简单简述就是内存只会保留一个父类的父类。子类只需要记录与该位置的偏移量就可以找到此空间的内容。但是建议尽量不要使用多继承。详细的继承介绍和菱形继承的问题见博客《C++继承》。

（3）多态：

• 就是向不同的对象发送同⼀个消息，不同对象在接收时会产生不同的行为（即方法），即⼀个接口可以实现多种方法。
• 多态和非多态的实质区别是函数地址是早绑定还是晚绑定（早绑定 是在编译器编译期间就可以确定函数的调用地址，并产生代码，是静态的）。详细的多态介绍见博客《C++多态》。
• 在继承中要构成多态还有两个条件：
  1. 必须通过基类的指针或者引用调用虚函数
  2. 被调用的函数必须是虚函数，且派生类必须对基类的虚函数进行重写

4.6 虚函数

（1）哪些函数不能是虚函数？？？

1. 构造函数。
2. 内联函数：内联函数在编译阶段进行函数体的替换操作，而虚函数在运行期间进行类型确定，所以不能是虚函数。
3. 静态函数：不属于对象属于类，静态成员函数没有 this 指针，设置为虚函数没有意义。
4. 友元函数：不属于类的成员函数，不能被继承。
5. 普通函数：不属于类的成员函数，不能被继承。

（2）虚函数表 与 虚函数内部实现原理：（更加详细的介绍见博客《C++多态》的第四节内容）

• 每个拥有虚函数的类都至少有⼀个虚函数指针，所有的虚函数都是通过虚函数指针在虚函数表中调用的，虚函数表会记录这个类中所有的虚函数的地址。对于派生类来说，编译器（编译期创建）建立虚函数表的过程分为三步：
  1. 拷贝基类的虚函数表，如果是多继承，则拷贝每个有虚函数基类的虚函数表。
  2. 选取继承的第⼀个基类函数表，将该类虚函数表与其合并来共用⼀个虚函数表（⼀个虚函数表对应⼀个虚函数指针）。
  3. 检测该类中是否有重写基类中的虚函数，若有则替换成已重写的虚函数地址。

（3）基类析构函数为什么要使用虚函数？？？

• 当不使用多态时，可正常运行并析构对象；
• 当使用多态时，如不将基类析构设置为虚函数，则当对象销毁时派生类无法正常析构，仅仅只有基类被析构。

class F 
{
public:F() { cout << "分配 f" << endl; }// 基类析构不是虚函数，则⽆法正常析构派⽣类~F() { cout << "析构 f" << endl; }
};class A : public F 
{
public:A() { cout << "分配 a" << endl; }~A() { cout << "析构 a" << endl; }
};int main() 
{cout << "不使⽤多态: " << endl;{ A a; }cout << "使⽤多态: " << endl;{F *f = new A();delete f;}return 0;
}

（4）虚函数、虚函数表、虚函数指针存在内存的哪个区域？？？

• 虚函数位于代码段（代码区）。
• 虚函数表位于只读数据段（常量数据区）。
• 虚函数指针与对象存储的位置相同（堆或者栈）。

（5）虚函数表是在什么阶段生成的？？？

• 虚函数表的内容在编译器编译的时候生成的。

（6）虚函数表指针是在什么阶段生成的？？？

• 类对象构造的时候，在构造函数将虚函数表的地址赋值给对象vptr。
• 如果类没有构造函数，则编译器自动生成构造函数，从而为类对象初始化vptr。
• 继承下虚函数表指针赋值过程如下：
  1. 调用基类构造函数的时候，先将基类的虚函数表地址赋值给vptr。
  2. 接着调用子类构造函数的时候，又将子类的虚函数表地址赋值给vptr。

4.7 纯虚函数

（1）纯虚函数的概念：

• 在虚函数的后面写上 = 0 ，则这个函数为纯虚函数。包含纯虚函数的类叫做抽象类（也叫接口类），抽象类不能实例化出对象。派生类继承后也不能实例化出对象，只有重写纯虚函数，派生类才能实例化出对象。
• 纯虚函数规范了派生类必须重写，另外纯虚函数更体现出了接口继承。

（2）纯虚函数和虚函数的区别：

1. 重写的强制性：虚函数的派生类可以选择是否重写。若不重写，则调用基类的默认实现。而纯虚函数的派生类必须重写，否则派生类也会成为抽象类，无法实例化。
2. 基类的实例化能力：虚函数的基类可以独立实例化（除非被其他条件限制）。而包含纯虚函数的基类是抽象类，无法直接实例化。

4.8 override 和 final

（1）C++对函数重写的要求比较严格，但是有些情况下由于疏忽，可能会导致函数名字母次序写反而无法构成重载，而这种错误在编译期间是不会报出的，只有在程序运行时没有得到预期结果才来debug会得不偿失，因此：C++11 提供了override和final两个关键字，可以帮助用户检测是否重写。

• final：修饰虚函数，表示该虚函数不能再被重写

class Car
{
public:virtual void Drive() final {}
};
class Benz :public Car
{
public://这里会报错virtual void Drive() { cout << "Benz-舒适" << endl; }
};

• override：检查派生类虚函数是否重写了基类某个虚函数，如果没有重写编译报错。

class Car {
public:virtual void Drive() {}
};class Benz :public Car {
public:virtual void Drive() override { cout << "Benz-舒适" << endl; }
};

5. 基础概念

（1）回调函数：当发生某种事件时，系统或其他函数将会自动调用定义的⼀段函数。回调函数就是⼀个通过函数指针调用的函数，如果把函数的指针（地址）作为参数传递给另⼀个函数，当这个指针被调用时，我们就说这是回调函数。

（2）简述 fork/wait/exec 函数：

• fork：将父进程复制⼀份给子进程，子进程从 fork 调用处继续执行，之后的代码在父子进程中各自执行⼀遍。最终父进程的 fork 返回子进程的 pid，子进程的 fork 返回 0 表示创建成功。所以看起来仿佛fork 有两个返回值，其实是两个进程的 fork 各自的返回值。
• exec：函数族可以根据指定的文件名或目录名找到可执行文件，并用它取代原调用进程的数据段、代码段和堆栈段。在执行完后，原调用进程除了进程号外，其他全部被新程序的内容替换。
• wait：会暂时停止当前进程的执行，直到有信号或子进程结束。如果子进程已经结束，则 wait 会立即返回子进程结束状态值。

6. STL库

6.1 模板

（1）模板底层实现：编译器会对函数模板进行两次编译，在声明的地方对模板代码本身进行编译，在调用的地方对参数替换后的代码进行编译。

（2）模板传参分析如下图所示：

（3）模板重载：

6.2 vector

（1）vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。vector 的数据结构其实就是三个迭代器构成的，⼀个指向目前使用的空间头，⼀个指向目前使用空间尾，⼀个指向目前可用的空间尾。当有新元素插⼊时，如果目前容量够用则直接插入；若不够则容量扩充至两倍，依次类推。扩充的过程是重新申请⼀块连续空间，将原有数据拷贝到新空间，再释放原有空间，扩充后原有的迭代器会失效。

（2）remove() 的实现原理：在遍历容器中的元素时，⼀旦遇到目标元素，就做上标记，然后继续遍历，直到找到⼀个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。remove() 不会改变其容量大小，而 erase() 可以改变其容量大小，通常将 remove() 返回的迭代器传入 erase() 中清除后续无用元素。

（3）注意事项：

• 插入和删除元素后，如果由于内存重分配则会导致迭代器全部失效；没有重分配则插⼊和删除之后的迭代器失效。
• 清空 vector 数据时，如果保存的数据项是指针类型，需要逐项 delete，否则会造成内存泄漏
• 频繁调用 push_back 影响：向vector 的尾部添加元素，很有可能引起整个对象存储空间的重新分配，这个过程是耗时耗力的。C++11之后，新增 emplace_back 方法，都是添加元素，但是该方法效率更高。emplace_back 在内存优化方面和运行效率方面有改进，内存优化方面主要体现在就地构造（直接在容器内构造对象，不用拷贝⼀个再使用）+强制类型转换，在运行效率方面，由于省去了拷贝构造，因此有提高。
• 详细的vector介绍见博客《vector类》。

6.3 list

• STL中的 list 是⼀个双向循环链表，相比双向链表结构的好处是在构建 list 容器时，只需借助⼀个指针即可轻松表示 list 容器的首尾元素。详细的list介绍见博客《list类》。

6.4 deque

（1）支持从头尾两端进行元素的插入和删除操作，没有容量的概念，因为它是动态地以 分段连续空间 组合而成，随时可以增加⼀段新的空间并连接起来，但是拥有复杂的迭代器结构。deque 采用一块所谓的map 作为主控，这里的 map 实际就是⼀块大小连续的空间，其中每⼀个元素称为节点 node，都指向了另⼀段连续线性空间，该空间是 deque 真正的存储空间。

（2）deque 实现原理：

1. 迭代器是⼀个类，其中迭代器中的 node 变量指向 map 的⼀个单元，而 map 中的每个单元指向当前迭代器对应的数据（缓冲区），如下图所示。map 的实现为 vector。
2. 当某个数据缓冲区头部或尾部已满时，将回到 map 中定位到相邻的数据缓冲区。内部 分段连续 实现。
3. 当插⼊元素时，当前位置位于首部或尾部时，直接插入；否则比较当前元素距离首部近还是尾部近，距离哪边近则将当前位置那段的元素整体移动，再插⼊当前元素。
4. 和堆 和 栈 的实现原理有点类似。

6.5 priority_queue

• 优先队列（STL为⼤顶堆），每个节点大于其子节点，采用 vector 实现。

6.6 map 和 set

（1）map 和 set 都是C++的关联容器，其底层实现都是红黑树。set、multiset 使用红黑树的迭代器是 const 类型的。map、multimap 使用红黑树的迭代器不是 const 类型的。（key、val在内部是存储在⼀个元素中，因此set、map底层实现⼀样）

（2）红黑树（平衡二叉搜索树）详细的介绍见博客《二叉搜索树》、《map类和set类》：

（3）红黑树的定义：

• 每个节点不是红色就是黑色。
• 根节点必须是黑色，相邻节点颜色不⼀样。
• 从根节点到叶子节点的黑色节点个数是⼀样的。

（4）实现：

• 有个虚拟头结点，左右指针分别指向红黑树最左侧和最右侧节点，便于最大最小值查找。每个节点都有左右指针、父节点指针和K-V值（还有颜色值）。
• 新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点。
• 此时需要对红黑树分情况来讨论：约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。一共有三种情况进行旋转（详细的过程以及图解见博客《map类和set类》的4.2小节）：
  1. cur为红，p为红，g为黑，u存在且为红
  2. cur为红，p为红，g为黑，u不存在/u存在且为黑
  3. cur为红，p为红，g为黑，u不存在/u存在且为黑

（5）为什么采用红黑树实现：

• ⼆叉树在某些情况下可能会退化为 O(N) 的时间复杂度；
• AVL树左右子树高度差最⼤为1，红黑树不遵循高度差条件，为的是减少旋转的次数

6.7 哈希表

（1）hash 转换（哈希表的详细介绍见博客《哈希表》）：

1. 整数值直接作为 hash 值。
2. 字符串各字符处理（只要够乱就可）作为 hash 值。

（2）哈希表扩充：当元素个数大于 buckets 大小时，将会进行哈希表扩充（约2倍数扩充），并重新分配所有元素。

（3）碰撞处理：同⼀位置用链表存储。

（4）实现unordered_set、unordered_map。STL 底层实现：

• 只有一个链表的头结点。
• 每个桶指向上⼀个有效桶的最后⼀个节点（即上⼀个节点）。

7. 算法

7.1 memcpy的实现

void mymemcpy(void* dst, const void* src, size_t num) 
{assert((dst != nullptr) && (src != nullptr));const char* psrc = (const char*)src; //因为void*是⽆法完成 '++' 或 '--'的char* pdst = (char*)dst;if (pdst > psrc && pdst < psrc + num) {for (size_t i = num - 1; i >= 0 && i < num; --i) {pdst[i] = psrc[i];}}else {for (size_t i = 0; i < num; ++i) {pdst[i] = psrc[i];}}
}

7.2 读写锁

class ReadWriteLock 
{
private:std::mutex write;std::shared_mutex read; // C++14int readCnt;
public:ReadWriteLock() : readCnt(0) {}void readLock() {read.lock();if (++readCnt == 1) {write.lock();}read.unlock();}void unreadLock() {read.lock();if (--readCnt == 0) {write.unlock();}read.unlock();}void writeLock() {write.lock();}void unwriteLock() {write.unlock();}
}

7.3 死锁复现代码

#include <iostream>
#include <thread>
#include <mutex>
#include <unistd.h>using namespace std;
int data = 1;
mutex mt1, mt2;void a2() 
{mt2.lock();sleep(1);data = data * data;mt1.lock(); //此时a1已经对mt1上锁，所以要等待cout << data << endl;mt1.unlock();mt2.unlock();
}void a1() 
{mt1.lock();sleep(1);data = data + 1;mt2.lock(); //此时a2已经对mt2上锁，所以要等待cout << data << endl;mt2.unlock();mt1.unlock();
}int main() 
{thread t2(a2);thread t1(a1);t1.join();t2.join();cout << "main here" << endl; //要t1线程、t2线程都执⾏完毕后才会执⾏return 0;
}

7.4 二叉树序列号与反序列化

（1）原题链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/

// 序列化
void serializeSub(TreeNode* node, string& res)
{if (!node) {res += "NULL,";}else {res += to_string(node->val) + ",";serializeSub(node->left, res);serializeSub(node->right, res);}
}string serialize(TreeNode* root) 
{string res = "";serializeSub(root, res);return res;
}// 反序列化
TreeNode* deserializeSub(queue<string>& q) 
{string cur = q.front();q.pop();if (cur == "NULL") {return nullptr;}else {TreeNode* node = new TreeNode(stoi(cur));node->left = deserializeSub(q);node->right = deserializeSub(q);return node;}
}TreeNode* deserialize(string data) 
{queue<string> q;string cur = "";for (char c : data) {if (c != ',') {cur += c;}else {q.push(cur);cur.clear();}}return deserializeSub(q);
}

7.5 生产者消费者模式

（1）变形题：轮流打印A/B。

#include <iostream>
#include <thread>
#include <vector>
#include <queue>
#include <mutex>
#include <condition_variable>
using namespace std;#define PRODUCT_SIZE 2
#define CUSTUM_SIZE 2
#define POOL_SIZE 3mutex m;
condition_variable cv;
queue<int> que;
int num = 0;void producter() 
{while (true) {std::unique_lock<std::mutex> lck(m);while (que.size() >= POOL_SIZE) {cv.wait(lck);}int data = num++;que.push(data);cout << this_thread::get_id() << "⽣产了" << data << endl;cv.notify_all();}
}void customer() 
{while (true) {std::unique_lock<std::mutex> lck(m);while (que.empty()) {cv.wait(lck);}cout << this_thread::get_id() << "消费了" << que.front() << endl;que.pop();cv.notify_all();}
}int main()
{vector<thread> pools;for (int i = 0; i < PRODUCT_SIZE; ++i) {pools.push_back(thread(producter));}for (int i = 0; i < CUSTUM_SIZE; ++i) {pools.push_back(thread(customer));}for (int i = 0; i < PRODUCT_SIZE + CUSTUM_SIZE; ++i) {pools[i].join();}return 0;
}

7.6 二叉树-前中后迭代算法模板

vector<int> inorderTraversal(TreeNode* root) 
{vector<int> res;stack<pair<TreeNode*, bool>> st;st.push({ root, false }); // root 节点未被访问while (!st.empty()) {auto tmp = st.top();st.pop();if (!tmp.first) continue;if (!tmp.second) {TreeNode* node = tmp.first;// 对于其他顺序遍历，仅改变下⾯三⾏代码即可（遍历逆序）st.push({ node->right, false });st.push({ node, true });st.push({ node->left, false });}else {res.emplace_back(tmp.first->val);}}return res;
}

7.7 手写智能指针

#include <iostream>
#include <cstdlib> // 智能指针头⽂件
#include <utility> // 智能指针头⽂件
#include <memory> // 智能指针头⽂件template<typename T>
class SmartPtr 
{
private:size_t* _count;T* _ptr;
public:// 构造函数SmartPtr(T* ptr = nullptr) : _ptr(ptr) {if (ptr) {_count = new size_t(1);}else {_count = new size_t(0);}}// 析构函数~SmartPtr() {if ((*_count) > 0) {--(*_count);}if ((*_count) == 0) {delete _ptr;delete _count;_ptr = nullptr;_count = nullptr;}}// 拷⻉构造函数SmartPtr(const SmartPtr& ptr) {if (this == &ptr) {return;}_ptr = ptr._ptr;_count = ptr._count;(*_count)++;}// 拷⻉赋值运算符SmartPtr& operator=(const SmartPtr& ptr) {if (_ptr == ptr._ptr) {return *this;}_ptr = ptr._ptr;_count = ptr._count;(*_count)++;return *this;} T& operator*() const { return *_ptr; }T* operator->() const { return _ptr; }operator bool() const { return _ptr; }size_t use_count() const { return *_count; }
};int main() 
{std::shared_ptr<int> p1(new int(3));std::cout << p1.use_count() << std::endl; // 1std::shared_ptr<int> p2(p1);std::cout << p1.use_count() << std::endl; // 2std::cout << p2.use_count() << std::endl; // 2std::shared_ptr<int> p3;std::cout << p3.use_count() << std::endl; // 0p3 = p2;std::cout << p2.use_count() << std::endl; // 3std::cout << p3.use_count() << std::endl; // 3std::shared_ptr<int> p4 = p3;std::cout << p3.use_count() << std::endl; // 4std::cout << p4.use_count() << std::endl; // 4std::cout << std::endl << std::endl;///SmartPtr<int> sp1(new int(3));std::cout << sp1.use_count() << std::endl; // 1SmartPtr<int> sp2(sp1);std::cout << sp1.use_count() << std::endl; // 2std::cout << sp2.use_count() << std::endl; // 2SmartPtr<int> sp3;std::cout << sp3.use_count() << std::endl; // 0sp3 = sp2;std::cout << sp2.use_count() << std::endl; // 3std::cout << sp3.use_count() << std::endl; // 3SmartPtr<int> sp4 = sp3;std::cout << sp3.use_count() << std::endl; // 4std::cout << sp4.use_count() << std::endl; // 4return 0;
}

7.8 十大排序算法

（1）稳定排序：冒泡排序、插入排序、归并排序。

• 冒泡排序：N个数需要进行N-1次冒泡，每次冒泡确定⼀个最大值位置。元素交换次数为原数组逆序度。

void bubbleSort(std::vector<int>& nums, int n) 
{for (int i = 1; i < n; ++i) { // 冒泡次数bool is_swap = false;for (int j = 1; j < n - i + 1; ++j) {if (nums[j] < nums[j - 1]) {std::swap(nums[j], nums[j - 1]);is_swap = true;}}if (!is_swap) break;}
}

• 插入排序：分为已排序和未排序，初始化已排序区间只有数组第⼀个元素。遍历未排序的每⼀个元素，倒序比较与已排序区间的大小关系，确定当前未排序元素的位置。元素交换次数为原数组逆序度。

void insertSort(std::vector<int>& nums, int n) 
{for (int i = 1; i < n; ++ i) {for (int j = i; j > 0 && nums[j] < nums[j - 1]; -- j) {std::swap(nums[j], nums[j - 1]);}}
}

• 选择排序：从头开始遍历数组，然后将该元素与其后面的区间进行比较，选择最小的元素并交换。

void selectSort(std::vector<int>& nums, int n) 
{for (int i = 0; i < n - 1; ++i) {int k = i;for (int j = i + 1; j < n; ++j) {if (nums[j] < nums[k]){k = j;}}std::swap(nums[k], nums[i]);}
}

• 快速排序：先找到⼀个枢纽，然后在当前数组中把比这个枢纽小的元素放左边，大的元素放右边，两部分数据依次递归排序下去直到有序。

void quickSort(std::vector<int>& nums, int l, int r) 
{if (l >= r) return;int left = l, right = r, key = nums[l];while (left < right) {while (left < right && nums[right] >= key) --right;while (left < right && nums[left] <= key) ++left;if (left < right) {std::swap(nums[left], nums[right]);}}std::swap(nums[left], nums[l]);quickSort(nums, l, left - 1);quickSort(nums, left + 1, r);
}// 快速排序的改进版博客链接：https://blog.csdn.net/qq_37194492/article/details/88779150

• 归并排序：首先将数组等分递归排序，然后通过⼀个临时数组，比较两个数组的大小从而合并两个数组。

void mergeSort(std::vector<int>& nums, int l, int r) 
{if (l < r) {int mid = l + (r - l) / 2;mergeSort(nums, l, mid);mergeSort(nums, mid + 1, r);vector<int> tmp(r - l + 1);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r) {if (nums[i] < nums[j]) {tmp[k++] = nums[i++];}else {tmp[k++] = nums[j++];}}while (i <= mid) { tmp[k++] = nums[i++]; }while (j <= r) { tmp[k++] = nums[j++]; }for (int p = 0; p < k; ++p) {nums[l + p] = tmp[p];}}
}

• 堆排序：从最后⼀个父节点逆序构建最大堆（根节点/0下标值为最大），然后循环N-1次，不断将0下标与最后下标数交换，并调整堆（其中堆越来越小）。

void heapify(vector<int>& nums, int f, int n) 
{int left = f * 2 + 1;int right = left + 1;while (left < n) {int index = f;if (nums[index] < nums[left]) index = left;if (right < n && nums[index] < nums[right]) index = right;if (index == f) {break;}else {swap(nums[f], nums[index]);f = index;left = f * 2 + 1;right = left + 1;}}
}void heapSort(std::vector<int>& nums, int n) 
{if (n < 2) return;// 从最后⼀个⽗节点调整为最⼤堆for (int i = n / 2 - 1; i >= 0; --i) {heapify(nums, i, n);}// 最⼤值放最后，将剩下调整为堆for (int i = n - 1; i > 0; --i) {std::swap(nums[0], nums[i]);heapify(nums, 0, i);}
}

• 桶排序：将数据分到有限数量的桶里，然后每个桶分别排序（可能使用其他排序算法），最后每个桶内数据合并。
• 计数排序：获取数组最大manV和最小值mixV，然后生成manV-mixV+1大小的数组，分别计数对应值的次数，然后再恢复数值输出结果。
• 基数排序：针对正整数排序，对每⼀个数补齐最长位数，然后从低位开始排序，排序的过程类似于多次桶排序。
• 希尔排序：从 len/2 步长开始排序，每次步长取半，直到最后成为插入排序。