算法岗常问的一些C++基础知识

前言

算法岗面试的时候，面试官除了会问你机器学习和深度学习的相关知识外，往往还会考察你的编程基础、开发相关的知识，因为现在公司招聘的算法岗位大都属于业务型算法岗，研究型算法岗属于少数。业务型算法岗除了要求算法模型能力过关以外，还要求具备一定的开发能力，因为模型训练好后还需要部署上线。

很多深度学习框架底层都是由 C/C++ 语言编写的，这样可以保证模型训练的速度和效率。所以，如果你熟悉 C/C++，在面试的时候会有一定的加分。我总结了一些算法岗常问的一些C++基础知识，大家可以参考下：

C++的相关特性

C++的三大特性分别是封装、继承、多态。封装可以使得代码模块化，继承可以扩展已存在的代码，而多态的目的则是为了接口重用。

C++多态性

多态通俗的说就是一个接口可以有多个实现方式，允许将子类类型的指针赋值给父类类型的指针。多态性分两种：编译时多态性，运行时多态性。
编译时多态性（静态多态）：通过重载函数实现
运行时多态性（动态多态）：通过虚函数实现
作用：接口重用（函数参数中类型写为基类，调用函数时自动识别派生类并调用对应的实现）。

虚函数

虚函数：允许被其子类重新定义的成员函数，实现成员函数的动态覆盖。
纯虚函数：在基类只有声明没有定义的虚函数，要求所有派生类自己定义实现方法，在函数后面加上“=0”。
抽象类：包含纯虚函数的类，不能进行实例化。
作用：用于实现多态，可以通过基类指针来访问基类和派生类中的同名函数。有些基类实例化是不合理的，而包含纯虚函数的抽象类不能实例化。

C++的静态库和动态库

库：现有的、成熟的、可复用的代码，所谓静态动态是指链接。
静态库（.a、.lib）:在程序编译时会被链接到目标代码中，程序运行时不再需要静态库，因此体积大，不方便更新（一个改动，全量更新）。
动态库（.so、.dll）:在程序运行时才被载入，所以运行时需要动态库的存在，因此体积较小，方便更新部署（增量更新）。

将一个程序编译成可执行程序的步骤如下图所示：

C++类中的静态成员

静态成员：在前面加上static修饰符，先于类的声明而存在于内存，且始终存在于内存，非静态成员必须实例化以后才会分配内存，生存周期取决于类的生存周期。
静态变量：在变量前加上static，不能被其他文件使用。
静态函数：只在声明它的文件中可见，不能被其他文件调用。
类中的静态成员：静态数据成员只有一份拷贝，被该类（及派生类）所有对象共享。静态成员函数不与任何对象相关联，因为不具有this指针，也无法访问类对象的非静态数据。

C++的STL（标准模板类）

STL包含六大组件：容器、迭代器、算法、仿函数、容器适配器、分配器。
容器：自动申请和释放内存，无需new和delete
序列式容器：vector、deque、list，每个元素有固定位置，取决于插入时间和地点。
关联式容器：set/multiset、map/multimap，元素位置取决于排序准则，和插入顺序无关。
迭代器：使用迭代器可以按一定顺序（有iterator提供的方法）访问对象中的各个元素。
适配器：queue、priority_queue、stack。通过对容器进行包装，使其表现出另一种行为。比如stack内部是使用vector来存储数据。
Vector机制：当容量已经不能放进数据，则重新申请一块内存，内存空间为原来的2倍，把之前内存的数据复制到新的内存中。Vector占用的内存只增不减，erase和clear操作后占用空间也不会变。预设长度比push_back更高效。
Set和Map机制：set中每个值唯一，且自动排序。他们内部都采用平衡二叉查找树——红黑树。插入删除操作比序列式容器快，因为只要调整指针，不需要移动内存。插入节点后iterator依然有效，因为指针指向内存，而内存没有发生改变。插入节点时间复杂度 $O(logn)$

C++函数传递方式

值传递：需要把形参复制到函数所属的栈，降低了程序的效率。
指针传递：同样把形参复制到函数所属栈，但复制内容是固定为4字节的地址。
引用传递：相当于一个数据的别名，与目标变量公用内存空间，效率更高。
引用和指针的区别：
指针指向某块内存，而引用是某块内存的别名，即指针是一个变量的地址，引用是一个变量的别名。引用必须被初始化，指针可以随时初始化。引用初始化后不可变，指针可以改变所指的对象。引用不能为空，指针可以为空。程序为指针分配内存空间，引用不需要。指针可以有多级，引用只能是一级。

链表和数组的区别

数组在内存中是一块连续的区域，使用前需要先申请占内存的大小，不方便拓展。可能会造成浪费，插入和删除操作都是O(n)比较低效，但随即存取效率高O(1)。链表不要求连续，内存利用率高，不会浪费，插入和删除效率高O(1)，但是不能随即访问，读取效率O(n)，方便拓展。

深拷贝和浅拷贝的区别

对一个对象进行拷贝，会调用拷贝构造函数，如果用户没有自定义拷贝构造函数，就会调用默认拷贝构造函数，默认拷贝构造函数进行的是浅拷贝。
浅拷贝：对指针的拷贝，拷贝后两个指针指向同一个内存空间。
深拷贝：对指针指向的内容拷贝，拷贝后是两个指向不同内存的指针。
应使用深拷贝的情况：（1）对含有指针成员的对象进行拷贝。（2）函数的参数为对象（形参有一个拷贝过程）。（3）函数返回值是一个对象（返回的是对象的一个拷贝）。