C/C++笔记
一、cmake:
1. 什么是 CMake？它的作用是什么？
CMake是一个开源的跨平台构建工具，用于管理C++的构建过程，生成Makefile文件。
2. CMAKE常用函数
| 函数 | 用途 |
|---|---|
| add_executable() | 添加源文件 |
| set() | 定义变量 |
| link_directories() | 添加库 |
| include_directories() | 添加头文件 |
| add_compile_options() | 添加参数 |
| add_subdirectory() | 将目录下所有源文件<br/>存入变量 |
| CMAKE_C_FLAGS CMAKE_CXX_FLAGS | 设置C和C++标志位 |
| CMAKE_C_COMPILER<br/>CMAKE_CXX_COMPILER | 指定编译器 |
| find_package | 查找第三方库 |
二、C++
2.1 C++新特性
2.1.1 智能指针
| 指针 | 用法 |
|---|---|
| std::shared_ptr | |
| std::unique_ptr | |
| std::weak_ptr |
2.2.2 auto、decltype和decltype(auto)的用法
auto推断类型，deltype推断类型（只想用类型）2.2 内存管理
2.2.1 内存的分区：
| 内容 | 说明 |
|---|---|
| 栈区 | 局部变量 |
| 堆区 | new分配 |
| 全局/静态存储区 | static和全局变量 |
| 常量存储区 | 常量字符串（虚函数表） |
| 代码区 | 存函数的（虚函数） |
2.2.2 new、delete、malloc、free关系？
相同点
- 都可用于内存的动态申请和释放
不同点
- 前者是C++运算符，后者是C/C++语言标准库函数
- new自动计算要分配的空间大小，malloc需要手工计算
- new是类型安全的，malloc不是。例如：
- new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。
- new是封装了malloc，直接free不会报错，但是这只是释放内存，而不会析构对象
2.3 C++的容器STL
C++ STL从广义来讲包括了三类：算法，容器和迭代器。（容器分序列式容器和关联式容器（底层是二叉树）（键值对））
- 算法包括排序，复制等常用算法，以及不同容器特定的算法。
- 容器就是数据的存放形式，包括序列式容器和关联式容器，序列式容器就是list，vector等，关联式容器就是set，map等。
- 迭代器就是在不暴露容器内部结构的情况下对容器的遍历。
容器包括：vector（底层应该是动态空间，空间不够了就进行复制和动态扩展），deque双端数组，stack栈，queue队列，list链表，set和map（红黑树）
2.3.2 hashtable中解决冲突有哪些方法？
线性探测：使用hash函数计算出的位置如果已经有元素占用了，则向后依次寻找，找到表尾则回到表头，直到找到一个空位
开链：每个表格维护一个list，如果hash函数计算出的格子相同，则按书序在这个list中
再散列：发生冲突时使用另一种hash函数再计算一个地址，直到不冲突
二次探测：使用hash函数计算出来的元素占用了，按照各自平方的步长依次寻找。
公共溢出区：一旦hash函数计算的结果相同，就再放入公共一出去。
2.4 C++多态/继承
2.4.1 什么是多态？
多态是C++的三大特性之一，直白的说，就是“一种接口，多种实现”。具体表现是调用同一种函数名时，函数的实现不同。
2.4.2 什么是编译时多态和运行时多态
C++中实现多态有两种方式，编译时多态和运行时多态。编译时多态是通过函数重载，运算符重载和模板实现的，在编译阶段就能决定调用哪个函数。运行时多态是通过虚函数实现的，使用方法就是基类的指针或者引用指向和引用派生类的对象时，调用时派生类的虚函数，在运行时才能决定调用哪个虚函数。
2.4.3 为什么运行时多态在运行时才能决定要调用哪个函数？
当通过基类指针调用虚函数时，在编译阶段并不能确定这个指针指向的是基类的对象或者是某个派生类的对象。只有在运行时，用户指定了这个对象的类型，才能确定调用这个对象的虚函数。
2.4.4 虚函数的实现原理？【重要】
虚函数的特性是通过虚函数表来实现的，每个有虚函数的类都会包含一张虚函数表，实际上是个函数指针数组，保存的是虚函数的地址。类声明的对象中会保存这个表的指针。C++编译器会在对象占用内存空间的初始地方保存这个指针，这样就可以通过对象的地址得到虚函数表，通过遍历虚函数表得到虚函数地址。
当子类继承父类时，也会继承这张虚函数表。子类对基类的虚函数没有重写时，子类的虚表指针指向基类的虚表；当子类对基类的虚函数重写时，子的虚表指针指向自身的虚表；当子类中有自己的虚函数时，将此虚函数地址添加在虚函数表后面。
在C++多继承中，子类继承了几个基类就会有几个虚表。如果类c继承了类a和类b，则c对象有两个虚函数表指针指向两个虚函数表。c中覆盖的虚函数会替换掉两个表中同名的虚函数指针位置。新添加的虚函数的地址会附加到第一个虚函数表后面。
2.4.5 虚函数类型
构造函数、静态函数，友元函数，内联函数都不可以是虚函数，但是析构函数可以是虚函数。
为什么基类析构函数最好是虚函数：如果创建基函数的指针指向派生类对象，在delete的时候会只析构基类不析构派生类。
2.4.6 什么是纯虚函数
纯虚函数没有函数体，只有函数声明，在虚函数声明的结尾加上=0，表明此函数为纯虚函数。包含纯虚函数的类称为抽象类，抽象类无法创建对象。
例如动物，它本身就不能是对象。但是猫可以是。
2.4.7 C++模板是什么，你知道底层怎么实现的吗？
- 编译器并不是把函数模板处理成能够处理任意类的函数；编译器从函数模板通过具体类型产生不同的函数；编译器会对函数模板进行两次编译：在声明的地方对模板代码本身进行编译，在调用的地方对参数替换后的代码进行编译。
- 这是因为函数模板要被实例化后才能成为真正的函数，在使用函数模板的源文件中包含函数模板的头文件，如果该头文件中只有声明，没有定义，那编译器无法实例化该模板，最终导致链接错误。
2.4.8 构造函数、拷贝构造函数和赋值操作符的区别
构造函数
对象不存在，没用别的对象初始化，在创建一个新的对象时调用构造函数
拷贝构造函数
对象不存在，但是使用别的已经存在的对象来进行初始化
赋值运算符
对象存在，用别的对象给它赋值，这属于重载“=”号运算符的范畴，“=”号两侧的对象都是已存在的
2.4.9 内存对齐
所谓的内存对齐，就是为了让内存存取更加有效率而采取的一种优化手段，对齐的结果是使得内存中数据的首地址是CPU单次获取数据大小的整数倍。
只要在代码前添加关键字 #pragma pack(n) 即可
二、设计模式
三、操作系统
3.1 进程间通信的方式是什么？
进程之间的通信方式一般有管道、FIFO、消息队列、信号量和共享内存五种。
管道指的是无名管道，是UNIX 系统IPC最古老的形式。其特点如下：
（1）它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
（2）它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。
（3）它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。
FIFO是命名管道，是一种文件类型。其特点如下：
（1）FIFO可以在无关的进程之间交换数据，与无名管道不同。
（2）FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
消息队列是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。其特点如下：
（1）消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
（2）消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
（3）消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
信号量是一个计数器，用于实现进程间的互斥和同步，其特点如下：
（1）信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。
（2）信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
（3）每次对信号量的 PV 操作不仅限于对信号量值加1或减1，而且可以加减任意正整数。
（4）支持信号量组。
共享内存指的是两个或多个进程共享一个给定的存储区，其特点如下：
（1）共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
（2）因为多个进程可以同时操作，所以需要进行同步。
（3）信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。
3.2 线程之间的通信方式是什么？
3.3 进程调度算法你了解多少？
四、计算机网络
五、数据结构
5.1 二叉树
5.1.1 BFS和DFS的区别是什么？
BFS是广度优先搜索，其特点是：
（1）BFS从根节点开始搜索，并根据树级别模式探索所有邻居根。
（2）它使用队列数据结构来记住下一个节点访问。
（3）BFS比DFS需要更多的内存。
（4）它是使用FIFO列表应用的。
（5）寻找最短路径的理想选择。
（6）该算法用于查找两个节点之间的最短路径，发现图中的所有连接组件，分析图是否为二部图等。
DFS是深度优先搜索，其特点是：
（1）DFS从根节点开始搜索，并从根节点尽可能远地探索这些节点。
（2）使用堆栈数据结构来记住下一个节点访问。
（3）DFS所需的内存少于BFS所需的内存。
（4）它是通过LIFO列表应用的。
（5）寻找最短距离的理想选择。
（6）该算法用于解决问题，拓扑排序，需要对图进行回溯，识别图中的循环以及发现两个节点之间的路径等。