前言

经过了许久的实习，暑期加秋招也面了五六十场了，基本上都是有名的大中厂，面过腾讯，字节，阿里控股，淘天，高德，蚂蚁，网易，米哈游，oppo，拼多多，华为，灵犀互娱，钉钉，莉莉丝，同花顺。都是面的C++，所以也勉强算一个有C++面试经验的人了，那么也运气很好拿过阿里控股，字节，米哈游，网易，莉莉丝，华为的offer。面的岗位有游戏服务器，网关流量，基架开发，客户端，安全岗，系统开发等等。在这些面试中，也是总结了许多面试的经验和八股出来，刚好现在面完了，写一篇博客记录一下这些基础的八股吧，也刚好可以给后续的校招生去参考参考。在这个里面我会穿插着一些面试的技巧，可能面多了，聊多了自然而然会总结一些技巧吧。

建议每一场面试都录屏，然后之后做好面经并复盘，由于受限于隐私保护，我不会公开任何一场面试视频或者面经。把面试次数提上来，自然而然会有面试经验和面试技巧，也自然而然会收获offer的。在网上其实看到了很多投了上百家公司，小几百家公司，但是没有太多面试，那也是很难拿到offer的。重点在于，多面，总结，再面。我也统计了我的一些面试和offer数量，OC时刻在面试次数的时间点。我还记得第一个offer是在我面了16场面试之后才拿到，此时的我是 16 次/offer，之后我的offer就越来越顺利了，然后秋招面了二十多次，面了三次线下。但是也拿了4-5个offer，这是因为华为还没开奖，只打了保温电话。

那么，在开始你的面试之旅之前，先看看C++的八股有哪些吧！本文只要讲八股，可能会穿插着少量场景题，但是更多是注重于八股。以下内容，不需要从头往后看，只需要选择自己想看的看即可，并没有太多连续性。

STL

概括

毫无疑问，STL包括四个方面，容器、迭代器、函数、算法。其中，对于算法就不在C++的八股内，因为任何语言都会问算法，比如快排，堆排问的比较多，我觉得这个不属于C++特有的。对于迭代器，问的不多，因为C++迭代器其实比较容易理解，并且迭代器属于设计模式。那么就剩下两个了

对于函数，可能会涉及部分lambda表达式，函数包装器之类的。总体上内容不算多，但是可以稍微了解了解，还有一个过时的std::bind也可以稍微了解了解。具体可以看STL_Function，这是我之前写过的一篇博客。

下面还是展开容器讲讲吧！

线性容器

这里主要包括三个部分，vector, array 和 list，主要是 vector 比较频繁。

vector ：

  • size, capacity, ptr，那么其中 size 是表示该容器的元素数量，capacity 表示的是当前指针指向的容量，ptr 指向了当前数组起始位置。
  • 预申请机制，一般来说会申请向上取整的容量（一般是8的倍数），然后每次增加元素都会看看剩余空间是否足够，不够的话，则需要扩容。
  • 扩容机制就是，开辟一块新的空间，然后把原来的拷贝过来。那么采用什么拷贝呢？根据std::is_nothrow_move_constructible<T>::value==true，则使用移动拷贝，否则采用复制拷贝，不支持拷贝则未定义行为，编译器报错。其实这个很好理解，就是存在移动构造，则使用移动构造，否则查看是否存在拷贝构造，如果不可构造直接报错。
  • 删除元素，删除元素不会缩容。包括resize,reserve往小了变不会缩容，往大了变会扩容。那么此时内存是没有被释放的，所以这个其实会造成内存泄漏，因为一部分内存没有什么用了。
  • 可以使用shrink_to_fit()去缩容，这是释放多余内存，但是不一定强制释放的，取决于实现。

array：

  • 这个其实是c++中，为了弥补C语言中的数组而设计的，支持越界检查，支持size。它的用法是array<T, Size>，比如array<int, 4>，那就类似于int a[4]

list：

  • 这个常常被用来和vector比较，list底层实现是一个双向链表，其实在平时开发中，用的可能会比较少
  • 比较点常常有，随机访问性，效率性，查找删除。总之，数据结构中应该接触了挺多数组和链表的区别，答案就是那些
  • 增删效率，在数据结构这门课中，我们是知道，list的效率高于vector，但是实际上并不一定。因为这是逻辑效率高，并不是实际效率高。原因在于，CPU是存在缓存的，而list中前后两个元素都是分布在不同物理内存空间，但是vector中的两个元素大概率是分布在同一个物理内存空间区域，所以在加载缓存的时候，CPU是按照【cache line】来加载缓存的，约 64B。对于一个 vector<int>，那么会一次性加载16个元素进CPU缓存，所以更改就会在缓存在更改，这会大大加快vector的增删效率。所以面试的时候，一定要分两部分说，说说两者的优缺点，具体情况要具体分析。

栈与队列

栈的话比较简单了，本质是对vector的再一次封装，但是栈的概念我想我这里不需要再展开了，这可以参考数据结构里面的概念。

队列的话，c++分为queue和deque两种，queue是基于deque的，而deque则是采用的一个二级数组的结构。

存在一个 T** p1，然后这个指向了一个T*数组，这个数组的每个元素都是一个T* p2，这个p2指向了一个T数组。那么如果在队头和队尾增删都是非常简单的，只需要额外在前面在插入一个T数组，就能够实现非常快速的队头插入，队尾插入也非常简单。

集合和映射

主要包括四个类，unordered_map, map, unordered_set, set，包括两种数据结构，哈希和红黑树（RBT）。我想对于映射和集合，其实是很容易明白这两者的区别的。一个是单值，一个是key–value对，那么他们的主要区别在于哈希和RBT了。

  • 哈希：
    • STL中为一些常用的数据类型都实现了哈希函数
    • 自定义的类需要自己实现一个哈希函数和等于运算符才能使用STL的哈希结构
    • STL中的哈希是采用链式法解决冲突，所以每个哈希桶都是一个链表
    • STL的哈希结构非常高效的，一开始并不会占用多少空间，而是会有一个扩容过程，并且是一步一步扩容的，不会发生一次性扩容导致某一次的时间过长的情况
    • 而与探测法相比优缺点有：
      • 优点：删除会比较容易一点，然后扩容简单高效
      • 缺点：由于使用链表，不能很好利用CPU效率，并且还多了一步找地址的过程
      • 频繁查询，则使用探测法好一些，频繁增删则使用链式法好一些。链式法也是平均下来，效率比较高的。
      • 可以自行思考思考，在频繁增删的情况下，探测法的缺点
  • 红黑树：
    • 自定义类需要实现比较运算符和等于运算符才能使用STL的哈希结构
    • 红黑树是有序的，并且增删，查询的平均复杂度都是O(\log n)
    • 红黑树左右子树高度差最多两倍
    • 与平衡二叉树（AVL）的区别：
      • AVL的查找是比RBT快的，但是增删会耗费更多的时间复杂度
      • RBT占用空间也会多一点，毕竟需要记录节点染色
      • 频繁查询用AVL，频繁增删用RBT。平均下来，还是RBT的速度比较快。

堆

在STL中，叫做优先队列（默认是大顶堆）。其用法为如下：

  • 大顶堆：priority_queue<int>
  • 小顶堆：priority_queue<int, vector<int>, greater<int>>

那么，对于优先队列这一个没啥好说的，常用top(), pop()两个成员函数，至于堆的话，要不还是放到算法那边讲吧。

排序算法

排序算法主要需要注重的是：快排/堆排，归并排，基本上必会才行，这是因为笔试经常出现，然后基于快排思想和堆的手撕和八股也会经常出现的。

简单说说快排和堆排的思路，至于归并排序的话，一般只会在写代码中用到，而且归排的思路比较简单，更多的是码力题。

  • 快排：
    • 使用第一个当作基准元素，比基准元素小的放一边，比基准元素大的放另一边。这就是一趟排序了，排完这一趟之后，进行递归，对左边和右边分别进行快排
    • 时间复杂度，平均O(n\log n)，最坏O(n^2)（当基本有序的情况下，复杂度比较高，当元素都相同的情况下，复杂度比较高）。空间复杂度，那就是递归调用栈O(\log n)
    • STL中的排序实现，是短数组使用插入排序，长数组使用快排，快排时递归深度太大则使用堆排。短数组指的是存在一个长度阈值，这个阈值是16或者32。称STL中的排序叫做 混合排序算法（Introsort, Introspective sort）
  • 堆排：
    • 分为建堆过程和排序过程，需要额外实现一个函数，就是使得某个区间的元素能够大堆化或者小堆化的函数，称之为堆化函数吧。
    • 堆逻辑上是一个完全二叉树，父节点会大于（或小于）两个子节点，子节点之间并没有大小之分，称之为大顶堆（或小顶堆）。但在实现中，往往使用数组来表示堆，从父节点（下标i）算左右子节点下标就是（2i+1, 2i+2）。从子节点（下标i）算父节点的下表就是
    • 建队过程，从最后一个非叶子节点开始（n/2-1），从后往前依次调用堆化函数即可
    • 堆化函数，本质上是一个下沉过程，自上而下的将堆顶元素下沉。

看下面两个面试题：

  • 寻找一个无序数组中第k大的数

    第一反应可能是用优先队列，或者直接排序。那这显然不是面试官最满意的答案，前面两个思路我就不展开了，只说说面试官希望听到的思路。

    借助快排的思路，依次查找某个值，比它小的放左边，比它大的放右边，那么是可以知道这个元素在有序数组中的下标的。

    然后比较这个下标和k的关系，查看是在左边继续更新还是在右边继续更新

  • 建堆的过程以及时间复杂度

    复杂度可以从建堆的过程来逐步计算一下
    T(n) = \sum\limits_{i=0}^h\left(\frac{n}{2^{i+1}}\right)O(i)
    最终这个是O(n)复杂度

资源管理

这一节，应该是C++最最最重要的一部分了，C++的资源管理主要是对象和内存管理，对于其他的资源（IO等）都是抽象成一个对象，由这个对象进行管理。先暂时回顾一下Linux中内存管理，Linux中使用虚拟内存和物理内存作为内存管理，按照页（4k）为单位，依次将虚拟内存映射到物理内存上面，如果页不存在，就会发生缺页中断。映射采用的是硬件电路进行映射的，叫做MMU。而Linux进程的内存，实际上是虚拟空间，申请的是虚拟空间，只有当真正使用内存，才会映射到物理空间。Linux进程逻辑上分为若干个段，代码段、静态存储段、常量段、堆段、文件映射段和栈段，这个叫做用户空间，还有一部分称之为内核空间。

然后关于malloc/free中，申请的时候是填了大小的，释放的时候不需要填大小，这是因为，申请的内存会额外申请两个字节，这两个字节保存着后面内存的大小，然后返回两个字节之后的内存。释放的时候，会先去读取前面两个字节的内容，然后对后面内存进行释放。

RAII

RAII（Resource Acquisition Is Initialization，资源获取即初始化）是C++重要的一个思想，也就是说，把资源的管理绑定到对象生命周期的管理上面来，包括流资源，文件描述符资源，甚至是内存资源等等。

通俗说来就是，在构造函数中获取资源，在析构函数中释放资源。这是比较常见的，正式一点说来就是：“对象构造时申请资源，对象析构时释放资源，资源的生命周期跟随对象的生命周期”。

举一些例子，比如文件描述符，一般是在构造函数中打开，当然也有很多不在构造函数中打开的，但是一般都会在析构函数中关闭。与此类似的，TCP连接等。

那么有些资源是可复制，有些资源是不可复制（但是可转移，即资源只能有一份比如文件描述符，比如TCP socket等等），那就需要结合复制和移动语义来做到了。

复制和移动

现代C++中，增加了移动语义，具体说来就是多了一个右值以及右值引用的概念。那这是一个什么东西呢？先参考另一篇博客：左右值引用

那其实这里最重要的就是，弄清楚 移动构造/赋值函数 和 拷贝构造/赋值函数 两者应该怎么写了。

往往来说，拷贝意味着，传进来的对象，归属权不是这个函数可以随意操作的，所以一般通过常左引用的方式传递。那么移动的意思就是，这个函数是可以拥有这个对象的所属权的，是可以随意操作它，尽管不操作他，出了这个函数之后，他也会被释放的。

智能指针

这一个应该是非常经典的一个资源管理的对象了，或者说他是专门管理内存这一个资源的。在现代C++的STL中，总共有三种智能指针，这里暂时不考虑C++11之前的那个智能指针，它并不完善。关于智能指针的基本知识，可以去看看我的另一篇博客：智能指针

unique_ptr的实现比较简单，并没有太多需要展开的。在这里，我只想补充说明一下shared_ptr,weak_ptr的，有关内存资源的问题：

  • 一个智能指针其实是有两个对象的，一个是待管理的类对象，一个是智能指针对象本身，两个对象都是需要管理其所在内存的
  • 分为两种情况，一种情况是，两片内存同时申请，另一种情况是，两片内存分开申请。
  • 现在把待管理的类对象称之为 资源对象，把智能指针本身称之为 控制块。强引用计数控制资源对象的生命周期，强+弱引用计数管理控制块的生命周期
  • 如果使用make_shared，那么就会只申请一片内存，如果是传入指针的，那么两次内存申请是分开的
  • 下面比较一下一次申请和两次申请的优缺点：
    • 一次申请比两次申请减少了系统调用次数，频繁申请内存的时候能够节省一倍的时间，然后释放的时候也会一次性释放。
    • 一次申请没法分开释放，但是两次申请理论上是可以分开释放的。有时候对象的资源对象的生命周期到了，也析构了，但是控制块的生命周期没到。由于内存是一起申请的，所以释放必须得等控制块的生命周期到了才能一起释放
    • 一次申请并不灵活，一般是通过make_shared进行申请，对于复杂的一些资源，需要一些繁琐的步骤才能构建，那么一次申请就显得不那么灵活了。但是两次申请，是需要自己预先申请资源，new 出对象，也可以自定义析构函数和内存释放函数等，更为灵活。

内存与对象监测

如何对自己写的C++工程进行内存监测呢？那就可以从两方面入手，第一是内存本身，第二是对象本身。然后更多的还是倾向于监测堆上空间，因为栈空间是有上限的，而且会自己释放，不释放往往是函数深度过深导致的。所以监测内存，一般是监测动态内存，因为这个需要手动释放的。

内存本身

内存本身底层调用都是malloc/free函数，那么对这两个函数进行hook之后，记录一下内存的申请和释放的数值即可。当然，也可以自己实现一些hook之类的。然后对new/delete进行全局重载，也是可以记录这个内存的。

对象本身

对new/delete进行重载，也是可以记录每个对象本身调用过多少次new，调用过多少次delete的，不过需要对每个对象都重载一次new/delete，比较麻烦。

然后一般都会使用智能指针管理对象，这在一般的c++工程中是非常常见的，那么可以直接自定义一个make_shared之类的函数，也能统计对象信息。

现代C++

现代C++的东西可太广泛了，有些东西放到后面去提了，这里看看一些比较好用的特性吧，至少是我觉得工作中往往会用到的

lambda 表达式

lambda表达式 是用来替换 function_bind，这两篇都可以稍微看看。

至于 lambda 的起源，是来源于匿名函数——lambda演算的，这个偏向于数学理论了，所以可以了解了解。

字符串

见字符与字符串

GDB调试

这个感觉不能算在现代C++里面，但肯定是C++程序员必备的，见GDB学习简单记录

除此以外还需要了解学习一下coredump, AddressSanitizer等

面向对象

面向对象最重要的是封装、继承和多态。

封装和继承

封装容易理解，继承的话也非常容易理解。

不过值得注意的是，C++继承的时候，在内存分布上是这样的：

基类1 基类2 ... 基类n 本身内存

所以其实内存上看来，继承就是把所以基类的内存copy了一份，但是从逻辑或者抽象上来说，子类就是基类的一种，而不是包含基类。这在go语言上也明显的看得出了，回归本质了属于是。

多态

多态其实分为静态多态和动态多态

静态多态

静态多态指的是模板，然后模板的话还是比较简单的。需要注意的点有：模板的优缺点、基于模板的一种设计模式、

模板的优缺点：

  • 优点：运行高效，生成的代码是不需要运行时查找任何信息的，在编译时就可以查找了
  • 缺点：编译慢，编译出来的体积大，造成了许多代码的重复

基于模板的一种设计模式CRTP，CRTP（编译时多态，Compile-time polymorphism），是通过在派生类传入自身类型作为模板参数传入基类——即“好奇地递归使用模板”：

template <typename Derived>
class BaseClass{
public:
    void interface() {
        static_cast<Derived*>(this)->implementation();
    }
};

class DerivedClass : BaseClass<DerivedClass> {
    void implementation() { /* ... */ }
}

它的常见用途有：替代运行时多态，减少了查表次数，当然其实本质上只是在编译器把一些查询操作给做了而已；做编译器类型检查；计数等等

  1. 替代运行时多态
#include <iostream>

template<typename Derived>
struct Shape {
    void draw() const {
        // 静态分派到 Derived::draw_impl()
        static_cast<const Derived*>(this)->draw_impl();
    }
};

struct Circle : Shape<Circle> {
    void draw_impl() const { std::cout << "Circle\n"; }
};

struct Square : Shape<Square> {
    void draw_impl() const { std::cout << "Square\n"; }
};

int main() {
    Circle c;
    Square s;
    c.draw(); // 输出 "Circle"
    s.draw(); // 输出 "Square"
}
  1. 编译期接口检查
#include <type_traits>

template<typename Derived>
struct InterfaceEnforcer {
    void call_impl() {
        // 检查 Derived 必须有 member named 'impl' 可被调用
        static_cast<void>(decltype(std::declval<Derived>().impl())());
        static_cast<Derived*>(this)->impl();
    }
};
  1. 计数，为每个派生类提供计数
#include <cstddef>

template <typename T>
struct InstanceCounter {
    static std::size_t count;
    InstanceCounter() { ++count; }
    ~InstanceCounter() { --count; }
    static std::size_t live() { return count; }
};

template<typename T>
std::size_t InstanceCounter<T>::count = 0;

struct A : InstanceCounter<A> {};
struct B : InstanceCounter<B> {};

动态多态

这可以参考我的另一篇博客：多态