面试复习（C++）

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公有的，任意对象和方法可以访问此属性

下面这段代码最终结果是

1
2
3
4
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）
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      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;
      }
学习笔记
#面试准备
面试复习（C++）
https://blog.mauve.icu/2021/02/22/interview/cpp/
作者
Shiroha
发布于
2021年2月22日
许可协议