仓库源文，站点原文

title: 面试复习（C++） date: 2021-02-22 14:23:24 categories: 学习笔记 tag:

面试准备 math: true

C++的特性与轨迹

C++ 的特性（C++11及以上）
- 需要在不同的平台上进行编译
- 编译后的程序可以在操作系统上直接运行
- 可以面对过程和面对对象两种设计方式
- 可以直接操作本地的系统库
- 可以直接使用操作系统提供的接口
- 编译后仅对变量的类型进行了存储，不可以进行类似反射的操作
- 支持无符号整型
- 变量类型的字节长度受操作系统影响
- 支持指针、引用、值传递
- 没有默认提供的 GC 系统
- 由程序员负责管理变量所储存的位置
- 严格的 RAII
- 支持重写、重载，包括运算符的重载
- 多重继承
- 支持预编译，编译宏定义
- 支持函数指针，函数对象，lambda 表达式
C++ 11 新增的特性
- foreach
- auto 自动类型推断
- lambda 匿名函数
- 后置返回类型
- override 关键字
- nullptr 代替原来的 NULL
  - 当存在 void a(int x); 和 void a(char *x) 时，若使用 a(NULL) 则会调用前者，这与通常的理解不同，而使用 a(nullptr) 则会明确的调用后者
- 元组 tuple，可以使用 get<>() 取出其中的一个值，或者使用 tie() 装包或解包

struct 和 class

区别
- struct 默认使用 public 而 class 默认使用 private
- struct 可以直接使用 {} 进行初始化，而 class 则需要所有成员变量都是 public 的时候才可以使用

堆和栈的区别

操作系统角度
- 堆是操作系统为进程所分配的空间，在 C、C++ 语言中用来存放全局变量。由程序员管理，主动申请以及释放的空间，可能会出现内存泄漏。在进程结束后，由操作系统回收
- 栈是由编译器进行管理，由编译器进行申请，释放的空间，通常比堆要小很多，在 C、C++ 语言中，当调用一个函数时会创建一个栈，当函数结束时则会回收栈的空间
数据结构的角度
- 堆是一棵完全二叉树，常见的有最大堆和最小堆，以最大堆为例，其满足二叉树中的任意一个节点的孩子节点都比此节点小。通常用来实现优先队列的效果，插入和删除的复杂度均为 O(logN)
- 栈是一种线性数据结构，满足先进后出的特点，即最先进入的数据最后离开，常见于 DFS 中。也可以通过单调栈的方式求解一些问题。插入和删除的复杂度均为 O(1)

虚函数

虚函数
- 虚函数由 virtual 标记
- 普通的虚函数仍然需要进行实现，所有继承此类的派生类可以重新实现此函数也可以不实现
纯虚函数
- 纯虚函数在普通的虚函数后，加上 =0
- 当一个类拥有纯虚函数后，则此类变成抽象类，不可以进行实例化
- 纯虚函数不需要实现，且所有继承自此类的派生类必须实现此函数，否则派生类也是抽象类，不可以实例化
虚函数的实现原理
- 在类中保存一张虚函数表，表内保存了函数所在的代码段
- 当其他类继承自此类时，复制一份此虚函数表。当其中的虚函数进行实现后，将虚函数表中此函数的指针指向新的函数的地址
- 定义类的实例的时候，在类的开头保存了一个指向此虚函数表的指针，当需要调用此函数的时候，通过此指针找到对应的函数地址

静态函数和虚函数

静态函数和虚函数的区别
- 静态函数在编译时就确定了运行的时机，而虚函数则是在运行的过程中动态的得知虚函数地址

vector

扩容规则
- 当空间不足的时候，vector 会扩容至当前空间的 2(GCC下)/1.5(MSVC)
为什么这样扩容
- 以两倍空间为例，当扩容次数为 30 次左右时，vector 的空间达到 1e9 （十亿）而通常每次扩容，都会需要在堆上重新分配空间，需要重新移动整个数组到新的空间。由此，可以得出重新分配空间的次数越少越好，同时也要节约内存的占用，因为按照此增长，其内存的重复的分配次数始终在常数范围内，所以采用了上述的扩容方式。
MSVC下的 1.5 倍的空间相对于 GCC 下的 2 倍有什么好处和坏处
- 好处：因为 2 倍空间下，任意一个空间都大于之前所有分配过的空间之和，这就意味着每次进行扩容的时候都需要分配一个新的空间。而在 1.5 倍下，可以重复使用之前的空间，1.5 倍相对会节约内存
- 坏处： 1.5 倍下的重新分配次数更多，也就意味着需要更多的重新分配空间和重新移动的次数，更加浪费时间
clear 的复杂度
- 复杂度与已有的元素数量成线性，因为每个元素都需要析构
- clear 后，并不会改变 vector 的容量上限，只会更新 vector 内的 size 大小

队列和堆栈的模拟

用两个堆栈模拟队列
- 将两个堆栈命名为 A、B
- 若 B 堆栈为空，则将 A 堆栈的所有值都推入 B 中
- 若需要推入，则推入到 A 中
- 若需要推出，则从 B 中推出
用两个队列模拟堆栈
- 将两个队列命名为 A、B
- 若需要推入，则推入到 A 中
- 若需要弹出，则将 A 中的值除了最后一个，其他都推入到 B 中，且仅留下一个值，然后弹出这个值，并将 A、B 队列命名为 B、A 队列

四个类型转换

转换	特点
static_cast	普通的转换，与普通的 C 语言的强制类型转换相同，在编译期间进行转换，所以会检查转换是否合法
const_cast	去除 const 属性，但是不能去除其本身的 const 属性
reinterpret_cast	无条件强制转换
dynamic_cast	将基类转换为派生类

三个访问限制

	描述
private	私有的，仅此类可以访问此属性
protect	保护的，仅此类已经此类的派生类可以访问此属性
public	公有的，任意对象和方法可以访问此属性

下面这段代码最终结果是

main () {
    printf("xxx");
    fork();
}

为 xxxxxx
由于有输出缓存，实际上在 fork 的时候，并没有输出至屏幕，而是保存在缓存中，当程序结束时，将缓存中的值输出至终端，所以得到 xxxxxx

static

static 变量的特点
- 该变量在全局数据区分配内存
- 未经初始化的静态全局变量会被程序自动初始化为0（自动变量的值是随机的，除非它被显式初始化）
- 静态全局变量在声明它的整个文件都是可见的，而在文件之外是不可见的

指针和引用

指针和引用的区别
- 指针有自己的内存空间，是一个变量类型，而引用没有占用内存空间，只是一个别名
- 使用 sizeof 可以求得在 32 位操作系统下，指针的大小为 $4$ 个字节，而引用则为原对象的大小
- 指针可以初始化为任意正整数值，而引用必须初始化为一个已经存在的变量
- 参数传递时，指针需要先进行指针转为引用然后再使用，而引用可以直接操作原对象
- 指针可以有 const 属性，而引用没有 const 属性
- 指针可以重新赋值，而引用不可以更改
- 指针可以进行多级指针，而引用只有一级
- 指针可以引用进行 ++（自增）操作的逻辑和结果都不同
- 当需要返回动态内存分配的对象时，需要使用指针而不是引用，因为引用可能会产生内存泄漏

平面几何问题

判断一个点是否在一个三角形内
- 定义三角形为 $ \vartriangle ABC$，点为 $P$，计算 $ S{\vartriangle ABC} = S{\vartriangle ABP} + S{\vartriangle ACP} + S{\vartriangle BCP}$ 是否成立。而三角形面积可以通过割补法或者叉积求

c++智能指针

auto_ptr（已弃用）
- 采用所有权模式，任何一个 new 的对象只能由一个 auto_ptr 来指向，进行赋值操作会使得原来的指针丢失指向的对象
unique_ptr
- 与 auto_ptr 相同，但是进行赋值操作时，会直接报错，而 auto_ptr 不会
shared_ptr
- 共享指针，允许多个指针指向此对象，同时当所有指向此对象的指针都被析构后，此对象将会被删除
weak_ptr
- 弱共享指针，允许指向其他的 shared_ptr 对象，此指针不会影响 shared_ptr 的析构行为，通常用来避免相互指向问题

构造函数

构造函数有哪些特征
- 名字和类名相同
- 没有返回值
- 生成类的自动执行，不需要调用
为什么构造函数不可以是虚函数
- 因为虚函数表指针是在构造函数期间创建的，没有虚函数表就没有办法调用虚函数

析构函数

析构函数的作用
- 如果一个类中有指针，且这个指针指向了一段由此类的实例请求分配的空间，那么需要由析构函数来实现对这块区域的释放，否则会造成内存泄漏
C++ 为什么习惯把析构函数定义为虚函数
- 当这个类需要作为父类派生的时候，如果程序得到的是此父类的指针，那么此时就无法析构子类，出现内存泄漏
C++ 为什么默认的析构函数不是虚函数
- 虚函数需要额外的虚函数表和虚函数表指针，对于不会派生的类而言，浪费空间

重载和覆盖

重载和覆盖的区别
- 重载：两个相同的函数名，但是参数列表不同
- 覆盖：父类创建的虚函数，派生类重新定义

锁

C++ 中的锁类型
- 互斥锁：对于同一个变量只允许一个线程进行读写，若不满足时则会进入阻塞，并且 CPU 不会进入忙等
- 条件锁：当满足某个条件时，再唤醒此线程，否则一直处于阻塞状态
- 自旋锁：不断的检查锁是否满足条件，不释放 CPU，比较耗费 CPU
- 读写锁：允许有读锁的时候再加读锁，但是有写锁时不再能加任何锁
- 递归锁：允许同一个线程对同一个锁进行多次加锁

new和malloc

new 和 malloc 的区别
- new 是一个 c++ 关键字，不需要头文件支持，而 malloc 是一个函数，需要头文件支持
- malloc 需要给出需要的空间大小，而 new 不需要
- new 返回的是对象的指针，而 malloc 返回的是 void* 类型的指针
- new 分配失败时会抛出错误，而 malloc 失败时返回空指针
- new 会调用被构造的类型的构造函数，而 malloc 只是分配内存空间
- 可以重载 new 操作，但是不能重载 malloc 操作
delete 和 free 的区别
- delete 会调用析构函数，而 free 直接回收空间

C++ 编译

从源文件到可执行文件的过程
- 预处理，宏定义替换
- 编译，生成汇编代码
- 汇编，将汇编代码转为机器代码，生成目标文件
- 链接，将多个目标文件连接成最终可执行文件

内存管理

C++ 的内存分布
- 代码段：存储机器代码和字符串常量
- 数据段：存储程序中已初始化的全局变量和静态变量
- BSS段：存储未初始化的全局变量和静态变量，以及所有被初始化为 0 的全局变量和静态变量
- 堆区：调用 new/malloc 函数时动态管理分配的内存，同时需要用 delete/free 来手动释放
- 栈区：使用栈空间存储的函数的变量和返回值等
- 映射区：存储动态链接库以及调用 mmap 函数进行的文件映射
C++ 内存泄漏检查
- 通过 valgrind 检查一个调试程序
- valgrind 可以检查出内存泄漏、越界访问、未初始化内存

静态方法

静态方法和实例方法有何不同
- 调用时，静态方法既可以用 类名.方法名 和 对象名.方法名，而实例方法只能用后者
- 静态方法只能访问静态变量，而实例方法可以访问静态变量和成员变量

右值引用

如何确定一个值是左值还是右值
- 提供了地址的为左值，左值可以没有值，但是一定有地址
- 提供了值的为右值，右值可以没有地址，但是一定有值
右值引用的功能
- 移动语句
- 完美转发
更详细的内容见此处

C++ hash

C++ 的内置 hash 函数的实现
- 对于基础变量，hash 函数返回值为此变量的值，不做修改
- 对于 string，hash 函数对每四个字节(64位操作系统下)进行位运算最终得到结果，实际的内部过程使用了两个特殊的固定值，下面是 C++ 的字符串 hash 函数的实际内部实现（C++11） ```cpp inline std::size_t unaligned_load(const char *p) { std::size_t result; __builtin_memcpy(&result, p, sizeof(result)); return result; }

size_t _Hash_bytes(const void ptr, size_t len, size_t seed = 0xc70f6907UL) { const size_t m = 0x5bd1e995; size_t hash = seed ^len; const char buf = static_cast<const char *>(ptr);

// Mix 4 bytes at a time into the hash.
while (len >= 4) {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
}

// Handle the last few bytes of the input array.
switch (len) {
    case 3:
        hash ^= static_cast<unsigned char>(buf[2]) << 16;
        [[gnu::fallthrough]];
    case 2:
        hash ^= static_cast<unsigned char>(buf[1]) << 8;
        [[gnu::fallthrough]];
    case 1:
        hash ^= static_cast<unsigned char>(buf[0]);
        hash *= m;
};

// Do a few final mixes of the hash.
hash ^= hash >> 13;
hash *= m;
hash ^= hash >> 15;
return hash;

} ```