阿Q技术站

深浅色

网易互娱游戏研发面经+时间线 - 参考答案 ​

1、自我介绍 ​

自我介绍是面试的开场白，也是你给面试官留下第一印象的关键。一个好的自我介绍应该简洁、有条理，并突出你的核心优势和与岗位相关的经验。通常，自我介绍应控制在1-3分钟。

自我介绍的结构建议：

  1. 基本信息： 姓名、学校、专业、学历。
  2. 求职意向： 明确你申请的岗位（例如：C++游戏研发工程师）。
  3. 核心优势/技能： 突出你与岗位最相关的技能和经验。对于C++游戏研发，可以强调：
    • 扎实的C++基础（面向对象、内存管理、多线程、STL等）。
    • 数据结构与算法能力。
    • 游戏开发相关经验（如游戏引擎使用、图形学基础、物理模拟、网络编程等）。
    • 解决问题的能力、学习能力。
  4. 项目经验（重点）： 简要介绍1-2个最能体现你能力和与岗位相关的项目。说明你在项目中的角色、负责的工作、遇到的挑战以及如何解决的、取得了什么成果。
  5. 实习经验（如有）： 介绍你在实习期间的职责、学到的东西和贡献。
  6. 个人特质/兴趣： 简要提及你的性格特点（如热爱技术、积极主动、团队协作能力强）或与游戏相关的兴趣爱好，表明你对游戏行业的热情。
  7. 展望： 表达你对加入公司的渴望和未来的发展期望。

示例（C++游戏研发工程师）：

“面试官您好，我叫[你的名字]，来自[你的学校]，专业是[你的专业]，是一名[本科/硕士]毕业生。我目前正在寻找C++游戏研发工程师的岗位。

在校期间，我专注于C++语言的学习和实践，对面向对象编程、数据结构与算法有扎实的基础，熟悉Linux开发环境和多线程编程。我尤其对游戏开发充满热情，深入学习了[例如：图形学基础、游戏引擎（如Unreal Engine/Unity）的使用、网络同步等]。

我最引以为傲的项目是[项目名称]，这是一个[类型，如：基于C++和OpenGL实现的小型3D游戏引擎/多人在线对战游戏]。在这个项目中，我主要负责[你的职责，如：图形渲染模块的开发/网络通信模块的实现/物理碰撞检测]。期间，我遇到了[挑战，如：如何优化渲染效率/如何解决网络延迟问题]，通过[解决方案，如：采用视锥体裁剪和LOD技术/使用UDP进行帧同步并结合预测回滚]，最终使游戏的[成果，如：帧率提升了30%/网络延迟降低到XXms]。

我渴望将我的C++编程技能和对游戏的热情投入到实际工作中，我相信我具备快速学习和解决问题的能力，能够为团队带来价值。谢谢！”

2、C++结构体的内存对齐题两道，问占多少字节的存储空间，如果要优化它的内存空间应该怎么优化？ ​

内存对齐概念： 内存对齐是指编译器在为结构体（或类）的成员变量分配内存时，会按照一定的规则，使得每个成员变量在内存中的起始地址都是其自身大小（或某个倍数）的整数倍。同时，整个结构体的大小也会是其最大成员变量大小（或指定对齐字节数）的整数倍。

内存对齐规则：

  1. 结构体成员对齐： 每个成员变量的起始地址必须是其自身大小（或指定对齐字节数n的较小值）的整数倍。
  2. 结构体总大小对齐： 整个结构体的大小必须是其最大成员变量大小（或指定对齐字节数n的较小值）的整数倍。

示例1：

cpp
struct S1 {
    char c1;    // 1字节
    int i;      // 4字节
    char c2;    // 1字节
};

假设默认对齐字节数为8字节（或4字节，取决于编译器和平台，这里以4字节为例，因为int是4字节）。

  • c1：偏移量0，占用1字节。下一个可用地址是1。
  • i：int是4字节，需要4字节对齐。从地址1开始，需要填充3字节，i从地址4开始，占用4字节。下一个可用地址是8。
  • c2：char是1字节，需要1字节对齐。从地址8开始，占用1字节。下一个可用地址是9。
  • 结构体总大小： 9字节。但结构体总大小必须是最大成员（int，4字节）的整数倍。所以需要填充3字节，总大小为12字节。
  • sizeof(S1) = 12字节。

示例2：

cpp
struct S2 {
    char c1;    // 1字节
    char c2;    // 1字节
    int i;      // 4字节
};

假设默认对齐字节数为4字节。

  • c1：偏移量0，占用1字节。下一个可用地址是1。
  • c2：偏移量1，占用1字节。下一个可用地址是2。
  • i：int是4字节，需要4字节对齐。从地址2开始，需要填充2字节，i从地址4开始，占用4字节。下一个可用地址是8。
  • 结构体总大小： 8字节。是最大成员（int，4字节）的整数倍。无需额外填充。
  • sizeof(S2) = 8字节。

如何优化内存空间？

优化内存空间（减少填充字节）的主要方法是合理安排结构体成员的顺序，将小尺寸的成员放在一起，或者将大尺寸的成员放在前面。

对于S1，如果将成员重新排序为S2的形式，就可以将大小从12字节优化到8字节。

更通用的优化原则：

  • 将相同大小的成员放在一起。
  • 将较小的成员放在较大的成员之后。 最好是按照成员大小递减的顺序排列。
  • 使用#pragma pack(n)或alignas： 在某些特定场景下，如果需要更严格或更宽松的对齐，可以使用编译器特定的#pragma pack(n)（如#pragma pack(1)可以完全取消对齐，使成员紧密排列）或C++11标准引入的alignas关键字来控制对齐。但通常不推荐随意修改默认对齐，除非有明确的需求（如与硬件交互、网络协议）。

3、内存对齐的好处是什么 ​

  1. 提高CPU访问效率：

    • CPU在访问内存时，通常是按字（word）或双字（double word）为单位进行存取的。如果数据没有对齐，一个数据可能跨越两个内存访问周期，导致CPU需要进行两次内存访问，然后进行额外的位操作来拼接数据，这会大大降低访问效率。
    • 对齐后，CPU可以在一个内存周期内直接读取整个数据，提高访问速度。

  2. 平台兼容性：

    某些硬件平台（如一些RISC处理器）对内存访问有严格的对齐要求。如果数据不对齐，可能会导致硬件异常（如总线错误、段错误）或程序崩溃。

  3. 缓存效率：

    CPU缓存通常以缓存行（Cache Line）为单位进行数据传输。如果数据对齐，可以确保一个数据结构尽可能地完整地存储在一个或少数几个缓存行中，减少缓存未命中，提高缓存利用率。

  4. 原子操作：

    对于某些需要原子性操作的数据（如多线程中的共享变量），如果不对齐，原子操作可能无法正确执行，或者需要更复杂的机制来保证原子性。

总之，内存对齐是编译器为了硬件效率和兼容性而采取的一种策略，它用空间换取了时间，确保了程序在不同硬件平台上的正确性和高性能。

4、int func() const;是什么？ ​

int func() const; 是C++中一个const成员函数的声明。

  • int： 表示函数的返回值类型是int。
  • func()： 是函数的名称和参数列表（这里没有参数）。
  • const： 这是关键所在。它修饰的是成员函数，表示这个函数是一个const成员函数。

const成员函数的作用和规则：

  1. 不能修改非mutable成员变量： 在const成员函数内部，不能修改类的任何非mutable成员变量。这是const成员函数最核心的特性，它保证了调用该函数不会改变对象的状态。
  2. 可以读取所有成员变量： const成员函数可以读取（访问）类的所有成员变量，无论是const还是非const的。
  3. 可以调用其他const成员函数： const成员函数可以调用同一个类的其他const成员函数。
  4. 不能调用非const成员函数： const成员函数不能调用同一个类的非const成员函数，因为非const成员函数可能会修改对象的状态，这与const成员函数的承诺相悖。
  5. mutable关键字： 如果确实需要在const成员函数中修改某个成员变量（例如，用于缓存计算结果或统计函数调用次数，这些修改不影响对象的逻辑状态），可以将该成员变量声明为mutable。mutable成员变量可以在const成员函数中被修改。
  6. const对象只能调用const成员函数： 对于一个const对象（或const引用、const指针），它只能调用其类的const成员函数。这是const正确性（const-correctness）的重要体现。

目的： const成员函数的主要目的是为了实现常量正确性。它向使用者承诺，调用这个函数不会改变对象的状态。这对于设计清晰、健壮的接口非常重要，尤其是在多线程环境中，const成员函数通常是线程安全的（至少在不修改共享状态的情况下）。

示例：

cpp
class MyClass {
private:
    int value_;
    mutable int call_count_; // mutable成员，可以在const函数中修改
public:
    MyClass(int v) : value_(v), call_count_(0) {}

    // const成员函数：承诺不修改对象状态
    int getValue() const {
        call_count_++; // 可以修改mutable成员
        // value_ = 10; // 错误：不能修改非mutable成员
        // setValue(20); // 错误：不能调用非const成员函数
        return value_;
    }

    // 非const成员函数：可以修改对象状态
    void setValue(int v) {
        value_ = v;
    }

    int getCallCount() const {
        return call_count_;
    }
};

int main() {
    MyClass obj(10);
    const MyClass const_obj(20);

    std::cout << obj.getValue() << std::endl; // 10
    obj.setValue(15);
    std::cout << obj.getValue() << std::endl; // 15

    std::cout << const_obj.getValue() << std::endl; // 20
    // const_obj.setValue(25); // 错误：const对象不能调用非const成员函数

    std::cout << "obj call count: " << obj.getCallCount() << std::endl; // 2
    std::cout << "const_obj call count: " << const_obj.getCallCount() << std::endl; // 1

    return 0;
}

5、map的底层数据结构？ ​

std::map在C++标准库中通常是基于红黑树（Red-Black Tree）实现的。

红黑树的特点：

  • 自平衡二叉搜索树： 红黑树是一种特殊的二叉搜索树，它在插入和删除操作后通过一系列的旋转和颜色调整来保持树的平衡，从而保证了最坏情况下的查找、插入和删除操作的时间复杂度为O(log N)。
  • 有序性： 红黑树中的所有元素都按照键（key）的顺序存储，因此std::map中的元素也是有序的。
  • 节点结构： 每个节点包含键、值、指向左右子节点的指针以及一个颜色属性（红色或黑色）。

std::map基于红黑树的优势：

  1. 有序性： 能够保持键的有序性，这使得std::map可以进行范围查询（如lower_bound、upper_bound）和有序遍历。
  2. 高效的查找、插入和删除： 所有操作的最坏时间复杂度都是O(log N)，其中N是map中元素的数量。这比无序容器（如std::unordered_map）在最坏情况下的O(N)性能要好。
  3. 内存效率： 相对于哈希表，红黑树的内存开销通常更可预测，没有哈希表可能存在的额外桶空间或链表节点开销。

总结： std::map使用红黑树作为底层数据结构，提供了键值对的有序存储和高效的对数时间复杂度的查找、插入和删除操作。

6、讲讲红黑树？红黑树怎么进行插入、调整？删除时最多旋转红黑树几次 ​

6.1、红黑树 (Red-Black Tree) 概述：

红黑树是一种自平衡二叉搜索树，它在每个节点上增加了一个颜色属性（红色或黑色），并通过遵循以下五条规则来确保树的平衡，从而保证了查找、插入和删除操作的最坏时间复杂度为O(log N)。

红黑树的五条性质：

  • 节点颜色： 每个节点要么是红色，要么是黑色。
  • 根节点： 根节点是黑色的。
  • 叶节点： 所有叶节点（NIL节点，通常是虚拟节点）都是黑色的。
  • 红色子节点： 如果一个节点是红色的，则它的两个子节点都是黑色的（即不能有两个连续的红色节点）。
  • 黑色高度： 从任意节点到其所有叶子节点的所有路径都包含相同数量的黑色节点。

6.2、红黑树的插入和调整：

插入操作首先像普通二叉搜索树一样，将新节点插入到合适的位置。新插入的节点总是被着色为红色。插入后，可能会破坏红黑树的性质（主要是性质4：不能有两个连续的红色节点）。为了恢复这些性质，需要进行一系列的调整，包括变色和旋转。

插入调整的常见情况（以新节点N为红色，其父节点P为红色为例）：

  • 情况1：叔叔节点U是红色。
    • 将父节点P和叔叔节点U都变为黑色。
    • 将祖父节点G变为红色。
    • 将当前节点N指向祖父节点G，继续向上检查。
  • 情况2：叔叔节点U是黑色，且N是P的右孩子（P是G的左孩子）或N是P的左孩子（P是G的右孩子）。
    • 进行一次旋转（左旋或右旋），将N和P的位置互换，使N成为P的父节点。
    • 此时转换为情况3。
  • 情况3：叔叔节点U是黑色，且N是P的左孩子（P是G的左孩子）或N是P的右孩子（P是G的右孩子）。
    • 将父节点P变为黑色，祖父节点G变为红色。
    • 进行一次旋转（右旋或左旋），以祖父节点G为轴进行旋转。
    • 此时红黑树性质恢复。

6.3、红黑树的删除和调整：

删除操作比插入复杂。首先找到要删除的节点，然后将其替换为它的后继节点（如果存在）。删除后，如果删除的节点是红色，则不会破坏红黑树的性质。但如果删除的节点是黑色，则可能会破坏性质（主要是性质5：黑色高度）。为了恢复性质，同样需要进行变色和旋转。

删除调整的复杂性在于需要处理多种情况，例如被删除节点是黑色且其兄弟节点是红色、兄弟节点是黑色且其子节点都是黑色、兄弟节点是黑色且其一个子节点是红色等。每种情况都需要特定的变色和旋转操作。

删除时最多旋转红黑树几次？

在红黑树的删除操作中，为了恢复平衡，最多需要进行三次旋转。这三次旋转可能发生在不同的节点上，以确保树的性质得到维护。具体来说，删除一个黑色节点后，可能会导致路径上的黑色节点数量减少，需要通过一系列的变色和旋转来弥补。

总结： 红黑树通过巧妙的颜色规则和局部调整（变色和旋转）来维持平衡，确保了高效的动态操作。理解其插入和删除的调整过程是掌握红黑树的关键。

7、了解AVL树吗？AVL树和红黑树的区别是什么 ​

7.1、AVL树概述：

AVL树是最早被发明的自平衡二叉搜索树。它通过严格控制左右子树的高度差来保持平衡，确保任何节点的左右子树高度差的绝对值不超过1。这个高度差被称为平衡因子（Balance Factor）。

AVL树的平衡因子：

  • 左子树高度 - 右子树高度
  • 平衡因子只能是 -1, 0, 1。

AVL树的平衡调整： 当插入或删除节点导致平衡因子超出范围时，AVL树会通过四种基本旋转操作（LL、RR、LR、RL）来恢复平衡。

7.2、AVL树和红黑树的区别：

特性AVL树红黑树
平衡条件任何节点的左右子树高度差的绝对值不超过1。通过颜色规则（红黑性质）来保持平衡。
平衡严格性严格平衡。对平衡的要求更严格。弱平衡。对平衡的要求相对宽松，允许一定程度的不平衡。
查找效率更高。由于更严格的平衡，树的高度更小，查找路径更短。略低于AVL树，但仍是O(log N)。
插入/删除效率较低。为了维持严格平衡，插入和删除操作可能需要更多的旋转和调整。较高。相对宽松的平衡条件使得插入和删除操作所需的旋转和调整次数通常更少。
实现复杂度相对复杂，需要维护每个节点的高度或平衡因子。相对复杂，需要维护每个节点的颜色，插入和删除的调整规则也较多。
应用场景适用于查找操作远多于插入/删除操作的场景，如数据库索引。适用于查找、插入、删除操作都比较频繁的场景，如std::map、std::set、Linux内核的进程调度等。

总结：

  • AVL树追求更严格的平衡，因此在查找性能上略优，但插入和删除的开销可能更大。
  • 红黑树追求操作的平均性能，在查找、插入和删除操作上都提供了稳定的O(log N)性能，且实现相对AVL树在工程上更易于接受，因此在实际应用中更为广泛。

8、快排和归并排序的过程？时间复杂度各是多少？最坏情况下会退化至多少？ ​

8.1、快速排序 (Quick Sort)：

过程：

  1. 选择基准 (Pivot)： 从待排序的数组中选择一个元素作为基准（pivot）。
  2. 分区 (Partition)： 重新排列数组，将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（相等的元素可以放到任意一边）。在这个分区结束之后，该基准就处于数组的最终位置。
  3. 递归排序： 递归地对基准前后的两个子数组进行快速排序。
  4. 终止条件： 子数组的长度为0或1时，递归终止。

时间复杂度：

  • 平均情况： O(N log N)

  • 最好情况： O(N log N) (每次分区都将数组分成大致相等的两部分)

  • 最坏情况： O(N^2)

  • 最坏情况下退化： 当每次分区都产生一个空子数组和一个N-1长度的子数组时（例如，数组已经有序或逆序，并且每次都选择第一个或最后一个元素作为基准），快速排序会退化为O(N^2)。

8.2、归并排序 (Merge Sort)：

过程：

  1. 分解： 将待排序的数组从中间一分为二，得到两个子数组。
  2. 递归排序： 递归地对这两个子数组进行归并排序，直到子数组只包含一个元素（一个元素被认为是自然有序的）。
  3. 合并： 将两个已排序的子数组合并成一个更大的有序数组。

  • 时间复杂度：

    • 平均情况： O(N log N)
    • 最好情况： O(N log N)
    • 最坏情况： O(N log N)

  • 最坏情况下退化： 归并排序在任何情况下都不会退化，其时间复杂度始终保持在O(N log N)。

总结对比：

特性快速排序 (Quick Sort)归并排序 (Merge Sort)
思想分治法，通过基准分区，递归排序子数组。分治法，递归分解，然后合并已排序的子数组。
稳定性不稳定 (相等元素的相对顺序可能改变)。稳定 (相等元素的相对顺序保持不变)。
空间复杂度O(log N) (递归栈空间，最坏O(N))。O(N) (需要额外的空间存储合并后的数组)。
时间复杂度平均O(N log N)，最坏O(N^2)。始终O(N log N)。
是否原地排序是 (大部分实现)。否 (需要额外空间)。

9、快排什么时候会退化至最坏情况？有什么方法能够避免这个最坏情况 ​

9.1、快排退化至最坏情况：

快速排序在以下两种情况下会退化至最坏情况O(N^2)：

每次分区都选择最大或最小元素作为基准：

  • 如果待排序的数组已经完全有序（升序或降序），并且每次都选择第一个或最后一个元素作为基准，那么每次分区都会产生一个空子数组和一个N-1长度的子数组。这导致递归深度达到N，每次分区操作的代价是O(N)，总时间复杂度为O(N^2)。
  • 例如，对[1, 2, 3, 4, 5]进行排序，如果每次都选第一个元素1作为基准，分区后得到[]和[2, 3, 4, 5]，递归继续处理[2, 3, 4, 5]，依此类推。

9.2、避免最坏情况的方法：

避免快速排序退化至最坏情况的核心思想是选择一个好的基准（pivot），使得每次分区都能将数组尽可能地分成大小相近的两个子数组。

  • 随机选择基准：

    • 在每次分区时，从待排序的子数组中随机选择一个元素作为基准。这使得最坏情况的发生概率变得非常小，即使输入数据是有序的，也能大概率避免退化。
    • 实现： 随机生成一个索引，然后将该索引处的元素与第一个元素（或最后一个元素）交换，再进行分区。

  • 三数取中法：

    • 从子数组的第一个、中间和最后一个元素中，选择它们的中位数作为基准。然后将这个中位数与第一个元素（或最后一个元素）交换，再进行分区。
    • 优点： 这种方法比随机选择更具确定性，并且在一定程度上能避免极端情况（如完全有序）。
    • 实现： 比较arr[low], arr[mid], arr[high]，将中位数放到arr[low]或arr[high]的位置。

  • 九数取中法或更多：

    在数据量非常大的情况下，可以从更多个位置（例如9个）取中位数作为基准，进一步提高基准选择的质量，但会增加选择基准本身的开销。

  • 结合插入排序：

    • 当子数组的长度小于某个阈值（例如10-20）时，不再递归调用快速排序，而是改用插入排序。因为对于小规模数组，插入排序的常数因子较小，性能可能优于快速排序。
    • 许多标准库的sort实现（如std::sort）都采用了这种混合排序策略。

总结： 快速排序的性能高度依赖于基准的选择。通过随机化或中位数选择基准，可以有效地降低遇到最坏情况的概率，使其在实践中成为一种非常高效的排序算法。

10、算法题：合并两个有序数组（就是写归并排序最后那个merge的过程） ​

问题描述： 给定两个已经排序的数组arr1和arr2，将它们合并成一个大的有序数组。

分析：

这个过程是归并排序的核心“合并”步骤。由于两个输入数组都已经有序，我们可以使用双指针法，从两个数组的开头开始比较元素，将较小的元素放入结果数组，并移动对应数组的指针。直到其中一个数组遍历完，再将另一个数组剩余的元素全部复制到结果数组中。

示例代码：

c++
#include <iostream>
#include <vector>
#include <algorithm>

// 合并两个有序数组
std::vector<int> merge_sorted_arrays(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    std::vector<int> result;
    result.reserve(arr1.size() + arr2.size()); // 预留空间，避免频繁扩容

    int i = 0; // 指向arr1的当前元素
    int j = 0; // 指向arr2的当前元素

    // 当两个数组都还有元素时，进行比较并合并
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            result.push_back(arr1[i]);
            i++;
        } else {
            result.push_back(arr2[j]);
            j++;
        }
    }

    // 将arr1中剩余的元素添加到结果数组
    while (i < arr1.size()) {
        result.push_back(arr1[i]);
        i++;
    }

    // 将arr2中剩余的元素添加到结果数组
    while (j < arr2.size()) {
        result.push_back(arr2[j]);
        j++;
    }

    return result;
}

int main() {
    std::vector<int> arr1 = {1, 3, 5, 7, 9};
    std::vector<int> arr2 = {2, 4, 6, 8, 10};

    std::vector<int> merged_arr = merge_sorted_arrays(arr1, arr2);

    std::cout << "Merged array: ";
    for (int x : merged_arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl; // 输出: 1 2 3 4 5 6 7 8 9 10

    std::vector<int> arr3 = {1, 2, 3};
    std::vector<int> arr4 = {4, 5, 6};
    std::vector<int> merged_arr2 = merge_sorted_arrays(arr3, arr4);
    std::cout << "Merged array 2: ";
    for (int x : merged_arr2) {
        std::cout << x << " ";
    }
    std::cout << std::endl; // 输出: 1 2 3 4 5 6

    std::vector<int> arr5 = {};
    std::vector<int> arr6 = {1, 2, 3};
    std::vector<int> merged_arr3 = merge_sorted_arrays(arr5, arr6);
    std::cout << "Merged array 3: ";
    for (int x : merged_arr3) {
        std::cout << x << " ";
    }
    std::cout << std::endl; // Expected: 1 2 3

    return 0;
}

时间复杂度： O(M + N)，其中M和N分别是两个输入数组的长度，因为每个元素只会被比较和复制一次。 空间复杂度： O(M + N)，需要额外的空间来存储合并后的结果数组。

11、unordered_map的底层数据结构是什么？ ​

std::unordered_map在C++标准库中通常是基于哈希表（Hash Table）实现的。

哈希表的特点：

  • 键值对存储： 存储键值对（key-value pairs）。
  • 无序性： 元素存储的顺序与键的插入顺序无关，也与键的大小无关。
  • 通过哈希函数映射： 使用哈希函数将键映射到哈希表中的桶（bucket）索引。
  • 冲突解决： 当不同的键通过哈希函数映射到同一个桶时，会发生哈希冲突。std::unordered_map通常使用链地址法来解决冲突，即每个桶存储一个链表（或std::list、std::vector），链表中包含所有哈希到该桶的键值对。

std::unordered_map基于哈希表的优势：

  1. 高效的平均时间复杂度： 在理想情况下（哈希函数均匀分布，冲突较少），查找、插入和删除操作的平均时间复杂度为O(1)。
  2. 快速访问： 适用于需要快速查找和插入/删除元素的场景，而不需要保持元素有序。

std::unordered_map的潜在问题：

  • 最坏时间复杂度： 如果哈希函数设计不当，导致大量哈希冲突，所有元素都集中在少数几个桶中，那么哈希表会退化为链表，查找、插入和删除操作的最坏时间复杂度将变为O(N)，其中N是元素数量。
  • 内存开销： 需要额外的内存来存储桶数组和链表节点。
  • 哈希函数： 对于自定义类型作为键，需要提供自定义的哈希函数（std::hash特化）和相等比较函数（std::equal_to特化）。

总结： std::unordered_map使用哈希表作为底层数据结构，通过哈希函数和冲突解决机制（通常是链地址法）实现键值对的快速存取，其平均时间复杂度为O(1)。

12、哈希碰撞有几种解决方式？各自有什么优缺点？ ​

哈希碰撞（Hash Collision）是指两个或多个不同的键经过哈希函数计算后，得到相同的哈希地址。

解决哈希碰撞的方法主要有以下几种：

链地址法

  • 原理： 将哈希到同一个桶的所有键值对存储在一个链表（或其他动态数据结构，如std::vector）中。哈希表的每个桶不再直接存储元素，而是存储一个指向链表头部的指针。

  • 优点：

    • 实现简单： 相对容易实现。

    • 处理冲突能力强： 理论上可以存储任意数量的元素，只要内存足够。

    • 删除操作简单： 只需要从链表中删除对应的节点。

    • 对装载因子不敏感： 即使装载因子（元素数量/桶数量）大于1，也能正常工作，只是性能会下降。

  • 缺点：

    • 空间开销： 需要额外的指针空间来维护链表。
    • 缓存不友好： 链表中的节点可能分散在内存中，导致缓存命中率低。
    • 性能波动： 如果链表过长，查找、插入和删除操作会退化为O(N)（N为链表长度）。

  • 应用： std::unordered_map和std::unordered_set通常采用此方法。

开放地址法

  • 原理： 当发生哈希冲突时，不是将元素存储在链表中，而是寻找哈希表中的下一个空闲位置来存储冲突的元素。探测下一个空闲位置的方法有多种：
    • 线性探测： 冲突后，依次检查H(key)+1, H(key)+2, H(key)+3, ...直到找到空闲位置。
    • 二次探测： 冲突后，依次检查H(key)+1^2, H(key)+2^2, H(key)+3^2, ...直到找到空闲位置。
    • 双重哈希： 使用第二个哈希函数来计算探测步长：H(key) + i * H2(key)。
  • 优点：
    • 缓存友好： 元素存储在连续的内存块中，有利于CPU缓存。
    • 无需额外指针： 节省了链表指针的空间开销。
  • 缺点：
    • 实现复杂： 删除操作相对复杂，通常采用“惰性删除”（标记为已删除，但不真正移除）。
    • 聚集问题： 线性探测容易导致元素聚集，使得后续查找和插入的探测次数增加。
    • 对装载因子敏感： 装载因子不能过高（通常建议小于0.7），否则性能会急剧下降。
    • 扩容开销大： 当哈希表需要扩容时，所有元素都需要重新哈希并插入到新的表中。
  • 应用： 某些语言的哈希表实现（如Python的字典）或特定场景下使用。

再哈希

  • 原理： 当哈希表的装载因子达到某个阈值时，创建一个更大的哈希表，并使用一个新的哈希函数将旧表中的所有元素重新插入到新表中。这通常与链地址法或开放地址法结合使用。
  • 优点： 维持哈希表的良好性能，避免因冲突过多导致的性能下降。
  • 缺点： 扩容时需要重新计算所有元素的哈希值并重新插入，这是一个O(N)的操作，开销较大。如果频繁扩容，会影响性能。
  • 应用： 几乎所有动态哈希表都会采用再哈希策略。

完美哈希

  • 原理： 针对一个静态的键集，设计一个哈希函数，使得所有键都不会发生冲突。这通常需要复杂的算法和预计算。
  • 优点： 查找效率为O(1)，没有冲突。
  • 缺点： 只能用于键集固定不变的场景，设计复杂。

总结： 链地址法和开放地址法是解决哈希碰撞的两种主要策略，各有优缺点。在实际应用中，通常会结合再哈希来动态调整哈希表的大小，以维持良好的性能。

13、普通哈希扩容时，如果哈希中元素很多那么扩容效率会很低，如何解决？（这里我答了渐进式哈希） ​

面试官对“渐进式哈希”的回答表示认可，这说明你提到了一个高级且有效的解决方案。当哈希表（无论是链地址法还是开放地址法）需要扩容时，通常需要创建一个更大的新表，并将旧表中的所有元素重新哈希并插入到新表中。如果元素数量非常多，这个过程会非常耗时，可能导致程序长时间停顿，这在实时性要求高的系统中是不可接受的。

渐进式哈希

  • 原理： 渐进式哈希的核心思想是将扩容操作分摊到多次普通的哈希表操作（如插入、删除、查找）中，而不是一次性完成。当需要扩容时，会创建一个新的、更大的哈希表，但不会立即将所有旧元素迁移过去。相反，在每次对哈希表进行操作时，除了完成当前操作外，还会将旧表中的少量元素迁移到新表。

  • 具体步骤：

    1. 触发扩容： 当哈希表的装载因子达到阈值时，决定进行扩容。
    2. 创建新表： 分配一个新的、更大的哈希表（通常是旧表容量的两倍）。
    3. 双表并存： 此时，哈希表中同时存在旧表和新表。所有新的插入操作都直接插入到新表中。
    4. 渐进式迁移： 在每次进行查找、插入、删除等操作时，除了完成当前操作外，还会从旧表中迁移k个元素（或k个桶）到新表。这个k可以是常数，也可以根据负载动态调整。
    5. 查找操作： 如果在旧表中找到元素，则返回；否则在新表中查找。
    6. 删除操作： 如果在旧表中找到元素，则在旧表中删除；如果在新表中找到，则在新表中删除。如果两个表都有，则两个都删除。
    7. 完成扩容： 当旧表中的所有元素都迁移到新表后，旧表被销毁，新表成为唯一的哈希表。

  • 优点：

    • 避免长时间停顿： 将O(N)的扩容操作分摊为多次O(1)（或接近O(1)）的小操作，避免了单次操作的性能尖峰，提高了系统的响应性和吞吐量。
    • 适用于实时系统： 特别适合对延迟敏感的系统，如游戏服务器、高并发网络服务等。

  • 缺点：

    • 实现复杂： 需要同时维护两个哈希表，并处理元素在两个表之间的迁移逻辑，增加了实现的复杂性。
    • 查找开销略增： 在迁移过程中，查找操作可能需要在两个表中都进行查找，略微增加了查找的平均时间。
    • 内存开销： 在迁移期间，需要同时维护两个哈希表，内存占用会暂时增加。

总结： 渐进式哈希是一种非常有效的解决哈希表扩容性能瓶颈的方法，它通过将扩容操作平摊化，确保了哈希表在任何时候都能提供稳定的性能，尤其适用于对响应时间有严格要求的场景。

14、渐进式哈希扩容的过程中，插入、删除、查找的过程是什么？（面试官说目前渐进式哈希扩容的解决方案不多，让我按自己的想法说就行） ​

既然面试官让你按自己的想法说，这表明他更看重你对原理的理解和逻辑推理能力。以下是基于渐进式哈希原理，对插入、删除、查找操作的详细描述：

假设我们有两个哈希表：old_table（旧表）和new_table（新表）。migrate_index是一个指针，指示old_table中下一个需要迁移的桶。

  1. 初始化状态： 只有old_table存在，new_table为空，migrate_index = 0。
  2. 触发扩容： 当old_table的装载因子超过阈值时，创建new_table，其容量通常是old_table的两倍。此时，old_table和new_table并存。

操作过程：

  • 插入：

    1. 执行迁移： 在执行插入操作之前，先从old_table的migrate_index处迁移k个桶（或k个元素）到new_table。更新migrate_index。
    2. 插入新元素： 将新的键值对直接插入到new_table中。
    3. 检查完成： 如果migrate_index已经遍历完old_table的所有桶，则销毁old_table，new_table成为唯一的哈希表，扩容完成。

  • 查找：

    1. 执行迁移： 在执行查找操作之前，先从old_table的migrate_index处迁移k个桶（或k个元素）到new_table。更新migrate_index。
    2. 查找元素：
      • 首先在new_table中查找目标键。如果找到，则返回。
      • 如果new_table中未找到，则在old_table中查找目标键。如果找到，则返回。
      • 如果两个表都未找到，则表示元素不存在。
    3. 检查完成： 如果migrate_index已经遍历完old_table的所有桶，则销毁old_table，new_table成为唯一的哈希表，扩容完成。

  • 删除：

    1. 执行迁移： 在执行删除操作之前，先从old_table的migrate_index处迁移k个桶（或k个元素）到new_table。更新migrate_index。
    2. 删除元素：
      • 首先在new_table中尝试删除目标键。如果删除成功，则完成操作。
      • 如果new_table中未找到，则在old_table中尝试删除目标键。如果删除成功，则完成操作。
      • 如果两个表都未找到，则表示元素不存在。
    3. 检查完成： 如果migrate_index已经遍历完old_table的所有桶，则销毁old_table，new_table成为唯一的哈希表，扩容完成。

关键点：

  • k的选取： 每次迁移的元素数量k需要权衡。k太小会导致迁移过程过长，k太大则会增加单次操作的开销。通常k是一个小常数，或者根据当前负载动态调整。
  • 线程安全： 在多线程环境下，所有对哈希表的操作（包括迁移过程）都需要进行适当的同步，以保证数据的一致性。

15、哈希冲突的链表法和开放定址法怎么进行删除操作 ​

15.1、链地址法 (Separate Chaining) 的删除操作：

  • 原理： 链地址法中，每个桶存储一个链表。删除操作就是从这个链表中移除对应的节点。
  • 步骤：
    1. 根据键计算哈希值，找到对应的桶。
    2. 遍历该桶中的链表，查找目标键。
    3. 如果找到目标键，将其从链表中移除（需要更新前一个节点的指针）。
    4. 释放被删除节点占用的内存。
  • 优点： 简单直接，不会引入复杂性。
  • 缺点： 如果链表很长，查找和删除的效率会降低。

示例：

cpp
// 假设哈希表结构大致如下
struct Node {
    KeyType key;
    ValueType value;
    Node* next;
};
std::vector<Node*> buckets; // 哈希表的桶，每个桶是一个链表头指针

void remove(KeyType target_key) {
    size_t bucket_idx = hash_func(target_key) % buckets.size();
    Node* current = buckets[bucket_idx];
    Node* prev = nullptr;

    while (current != nullptr && current->key != target_key) {
        prev = current;
        current = current->next;
    }

    if (current != nullptr) { // 找到目标键
        if (prev == nullptr) { // 目标是链表头节点
            buckets[bucket_idx] = current->next;
        } else {
            prev->next = current->next;
        }
        delete current; // 释放内存
    }
}

15.2、开放地址法的删除操作：

开放地址法在删除时比较复杂，因为直接移除元素可能会破坏后续查找的探测序列，导致无法找到其他元素。因此，通常采用惰性删除或标记删除的策略。

  • 原理： 不真正移除元素，而是将该位置标记为“已删除”（或“墓碑”，DELETED）。
  • 步骤：
    1. 根据键计算哈希值，并沿着探测序列查找目标键。
    2. 如果找到目标键，不直接清空该位置，而是将该位置标记为DELETED。
    3. 查找时： 遇到DELETED标记会继续沿着探测序列查找。
    4. 插入时： 遇到DELETED标记可以覆盖该位置，但需要注意更新探测序列。
  • 优点： 避免了破坏探测序列，保证了后续查找的正确性。
  • 缺点：
    • 空间浪费： 被标记为DELETED的位置仍然占用空间，并且在查找时需要跳过，增加了探测次数。
    • 性能下降： 随着DELETED标记的增多，哈希表的性能会逐渐下降，最终可能需要进行重新哈希（Rehashing）来清理这些标记。
    • 实现复杂： 插入和查找逻辑需要额外处理DELETED标记。

示例（线性探测）：

cpp
// 假设哈希表结构大致如下
enum EntryStatus { EMPTY, OCCUPIED, DELETED };
struct Entry {
    KeyType key;
    ValueType value;
    EntryStatus status = EMPTY;
};
std::vector<Entry> table; // 哈希表的桶

void remove(KeyType target_key) {
    size_t initial_idx = hash_func(target_key) % table.size();
    size_t current_idx = initial_idx;
    int probe_count = 0;

    while (table[current_idx].status != EMPTY && probe_count < table.size()) {
        if (table[current_idx].status == OCCUPIED && table[current_idx].key == target_key) {
            table[current_idx].status = DELETED; // 标记为已删除
            return;
        }
        current_idx = (current_idx + 1) % table.size(); // 线性探测
        probe_count++;
    }
}

// 查找时需要跳过DELETED标记
ValueType* find(KeyType target_key) {
    size_t initial_idx = hash_func(target_key) % table.size();
    size_t current_idx = initial_idx;
    int probe_count = 0;

    while (table[current_idx].status != EMPTY && probe_count < table.size()) {
        if (table[current_idx].status == OCCUPIED && table[current_idx].key == target_key) {
            return &table[current_idx].value;
        }
        current_idx = (current_idx + 1) % table.size();
        probe_count++;
    }
    return nullptr;
}

总结： 链地址法的删除相对简单，直接移除链表节点。开放地址法的删除则需要采用惰性删除策略，将位置标记为DELETED，以维护探测序列的完整性，但会带来额外的空间和性能开销，最终可能需要通过重新哈希来清理。

16、C++继承的内存布局 ​

C++继承的内存布局是理解C++对象模型和多态实现的关键。它涉及到基类和派生类成员在内存中的排列方式。

16.2、单一继承：

  • 无虚函数：

    • 派生类对象会包含基类子对象的所有成员变量，然后是派生类自己的成员变量。
    • 基类成员变量通常在派生类成员变量之前。
    • 内存布局是连续的。
    cpp
    class Base { int b; };
class Derived : public Base { int d; };
// sizeof(Derived) = sizeof(Base) + sizeof(int) = 4 + 4 = 8 (假设没有对齐填充)
// 内存布局: [Base::b | Derived::d]

  • 有虚函数：

    • 如果基类有虚函数，那么基类对象会包含一个虚表指针（vptr）。派生类对象也会继承这个vptr。
    • vptr通常是对象内存布局的第一个成员。
    • 如果派生类重写了虚函数，vptr会指向派生类的虚函数表。
    cpp
    class Base { virtual void f() {} int b; };
class Derived : public Base { virtual void f() {} int d; };
// sizeof(Derived) = sizeof(vptr) + sizeof(Base::b) + sizeof(Derived::d) = 8 + 4 + 4 = 16 (64位系统，vptr 8字节)
// 内存布局: [vptr | Base::b | Derived::d]

16.2、多重继承：

多重继承是指一个类继承自多个基类。这会使内存布局变得更复杂。

  • 无虚函数：

    • 派生类对象会包含所有基类子对象的成员变量，然后是派生类自己的成员变量。
    • 基类子对象的顺序通常按照继承列表的顺序排列。
    cpp
    class Base1 { int b1; };
class Base2 { int b2; };
class Derived : public Base1, public Base2 { int d; };
// sizeof(Derived) = sizeof(Base1) + sizeof(Base2) + sizeof(Derived::d) = 4 + 4 + 4 = 12
// 内存布局: [Base1::b1 | Base2::b2 | Derived::d]

  • 有虚函数：

    • 如果多个基类都有虚函数，那么派生类对象会包含多个虚表指针，每个带有虚函数的基类对应一个vptr。
    • 这些vptr通常会出现在对应的基类子对象的起始位置。
    • 当通过不同基类指针指向派生类对象时，this指针的值可能不同，需要编译器进行this指针调整（thunk）来确保正确访问派生类成员。
    cpp
    class Base1 { virtual void f1() {} int b1; };
class Base2 { virtual void f2() {} int b2; };
class Derived : public Base1, public Base2 { virtual void f1() {} virtual void f2() {} int d; };
// 内存布局: [vptr_Base1 | Base1::b1 | vptr_Base2 | Base2::b2 | Derived::d]
// sizeof(Derived) = 8 + 4 + 8 + 4 + 4 = 28 (64位系统)

16.3、虚继承 - 解决菱形继承问题：

虚继承用于解决多重继承中的菱形继承问题，即当一个类D同时继承自B1和B2，而B1和B2又都继承自同一个基类A时，D中会包含A的两个副本。虚继承确保A的子对象在D中只有一个副本。

  • 内存布局：
    • 虚继承的基类（A）的子对象通常会被放置在派生类对象内存布局的末尾，或者通过一个虚基类指针（vbptr）来间接访问。
    • 每个虚继承的派生类（B1, B2）会包含一个vbptr，指向一个虚基类表（vbtable），vbtable中存储了到虚基类子对象的偏移量。
    • 这种布局使得A的子对象在D中只存在一份，并且所有路径都能正确访问到它。
    cpp
    class A { int a; };
class B1 : virtual public A { int b1; };
class B2 : virtual public A { int b2; };
class C : public B1, public B2 { int c; };
// 内存布局可能大致为: [vbptr_B1 | B1::b1 | vbptr_B2 | B2::b2 | C::c | A::a]
// A::a被放置在最后，通过vbptr间接访问。

总结： C++的继承内存布局是编译器实现细节，但理解其基本原理有助于分析程序行为和优化。单一继承相对简单，多重继承引入了多个vptr和this指针调整，虚继承则通过vbptr和虚基类表来解决菱形继承问题。

17、C++的菱形继承 ​

17.1、什么是菱形继承？

菱形继承是多重继承中一个经典的问题。它发生在以下场景：

  • 有一个基类A。
  • 有两个派生类B1和B2，它们都直接继承自A。
  • 有一个最终派生类C，它同时继承自B1和B2。

在类图上，这会形成一个菱形结构：

      A
     / \
    B1  B2
     \ /
      C

问题所在： 如果没有特殊处理，C类对象中会包含A类的两个子对象副本：一个来自B1，另一个来自B2。这会导致以下问题：

  • 数据冗余： A类的成员变量在C对象中存在两份，浪费内存。
  • 二义性： 当C对象尝试访问A类的成员时，编译器不知道应该访问哪个A的副本，从而产生编译错误（二义性）。例如，C c; c.a_member; 会报错，因为a_member可以通过B1::a_member和B2::a_member两条路径访问。

示例：

cpp
#include <iostream>

class A {
public:
    int a_member;
    A() : a_member(1) { std::cout << "A constructor\n"; }
};

class B1 : public A {
public:
    int b1_member;
    B1() : b1_member(2) { std::cout << "B1 constructor\n"; }
};

class B2 : public A {
public:
    int b2_member;
    B2() : b2_member(3) { std::cout << "B2 constructor\n"; }
};

class C : public B1, public B2 {
public:
    int c_member;
    C() : c_member(4) { std::cout << "C constructor\n"; }
};

int main() {
    C c_obj;
    // c_obj.a_member = 10; // 编译错误：请求对成员 'a_member' 的访问不明确
    // 必须显式指定路径：
    c_obj.B1::a_member = 10;
    c_obj.B2::a_member = 20;
    std::cout << "B1's a_member: " << c_obj.B1::a_member << std::endl; // 10
    std::cout << "B2's a_member: " << c_obj.B2::a_member << std::endl; // 20
    // 可以看到，A的成员确实存在两份
    return 0;
}

17.2、如何解决菱形继承问题 - 虚继承：

C++通过虚继承来解决菱形继承问题。当一个类以virtual关键字继承自某个基类时，该基类被称为虚基类。虚继承确保在最终派生类中，虚基类的子对象只存在一个共享的副本。

  • 使用方法： 在中间派生类（B1和B2）继承A时，使用virtual关键字。

    cpp
    class A { /* ... */ };
class B1 : virtual public A { /* ... */ }; // 虚继承
class B2 : virtual public A { /* ... */ }; // 虚继承
class C : public B1, public B2 { /* ... */ };

  • 解决原理：

    • 虚继承后，A的子对象在C对象中只保留一份，并且这个唯一的A子对象由最底层的派生类C来构造和管理。
    • B1和B2不再直接包含A的子对象，而是通过一个虚基类指针（vbptr）或虚基类表（vbtable）来间接访问共享的A子对象。这个vbptr存储了到共享A子对象的偏移量。
    • 这样，C对象中的A子对象只有一个，消除了数据冗余和二义性。

示例（虚继承）：

cpp
#include <iostream>

class A {
public:
    int a_member;
    A() : a_member(1) { std::cout << "A constructor\n"; }
};

class B1 : virtual public A {
public:
    int b1_member;
    B1() : b1_member(2) { std::cout << "B1 constructor\n"; }
};

class B2 : virtual public A {
public:
    int b2_member;
    B2() : b2_member(3) { std::cout << "B2 constructor\n"; }
};

class C : public B1, public B2 {
public:
    int c_member;
    C() : c_member(4) { std::cout << "C constructor\n"; }
};

int main() {
    C c_obj;
    c_obj.a_member = 10; // 正确：不再有二义性，只有一个A::a_member
    std::cout << "C's a_member: " << c_obj.a_member << std::endl; // 10
    // 此时 sizeof(C) 会比非虚继承时大，因为引入了虚基类指针/表
    return 0;
}

虚继承的代价：

  • 性能开销： 引入了虚基类指针和虚基类表，增加了对象的大小。访问虚基类成员需要通过间接寻址，会略微增加访问时间。
  • 实现复杂性： 编译器需要更复杂的机制来管理虚继承的内存布局和构造顺序。

总结： 菱形继承是多重继承带来的一个问题，通过虚继承可以有效地解决数据冗余和二义性，但会引入一定的性能和空间开销。

18、C++虚继承时继承的内存布局和普通继承相比有什么变化（没答出来） ​

在普通继承（非虚继承）中，派生类会直接包含基类的子对象。如果存在多重继承和共同基类，会导致基类子对象的冗余副本。而虚继承的目的是解决这个问题，因此其内存布局与普通继承有显著不同。

普通继承的内存布局（以菱形继承为例）：

      A
     / \
    B1  B2
     \ /
      C
  • C对象中会包含B1的子对象和B2的子对象。
  • 由于B1和B2都直接包含A的子对象，所以C对象中会有两个A的子对象副本。
  • 内存布局大致为：[B1子对象 (包含A子对象) | B2子对象 (包含A子对象) | C自身成员]
    • [A::a_member | B1::b1_member | A::a_member | B2::b2_member | C::c_member]

虚继承的内存布局（解决菱形继承）：

当B1和B2虚继承A时：

cpp
class A { int a; };
class B1 : virtual public A { int b1; };
class B2 : virtual public A { int b2; };
class C : public B1, public B2 { int c; };

虚继承的内存布局变化主要体现在以下几点：

  1. 共享虚基类子对象： A的子对象在C对象中只存在一个共享的副本，而不是两个。

  2. 虚基类指针 (vbptr) 或虚基类表 (vbtable)：

    • 每个虚继承的派生类（如B1和B2）会引入一个虚基类指针（vbptr）。这个vbptr通常位于对象内存布局的开头（或紧随vptr之后）。
    • vbptr指向一个虚基类表（vbtable）。vbtable是一个整数数组，存储了从当前子对象（如B1子对象）的起始地址到共享虚基类子对象（A子对象）的偏移量。

  3. 虚基类子对象的位置：

    • 共享的虚基类子对象（A子对象）通常会被放置在最终派生类（C）对象内存布局的末尾。这样做是为了确保无论通过哪个路径（B1或B2）访问A的成员，都能通过固定的偏移量找到唯一的A子对象。

  4. 访问虚基类成员：

    • 访问虚基类A的成员时，不再是直接偏移，而是通过vbptr找到vbtable，再通过vbtable中的偏移量间接访问A的成员。这会引入一次额外的间接寻址，略微增加访问开销。

内存布局大致示意图：

cpp
C 对象内存布局:
+-------------------------------+
| vptr_B1 (如果B1有虚函数)        |
| B1::b1_member                 |
| vbptr_B1 (指向vbtable)         |
+-------------------------------+
| vptr_B2 (如果B2有虚函数)        |
| B2::b2_member                 |
| vbptr_B2 (指向vbtable)         |
+-------------------------------+
| C::c_member                   |
+-------------------------------+
| A::a_member (共享的虚基类子对象) |
+-------------------------------+

vbtable_B1:
+---------------------+
| 偏移量到 A 子对象     |
+---------------------+

vbtable_B2:
+---------------------+
| 偏移量到 A 子对象     |
+---------------------+

总结变化：

  • 普通继承： 简单地将基类子对象嵌入派生类，可能导致冗余。
  • 虚继承： 引入了vbptr和vbtable机制，将虚基类子对象放置在对象内存的固定位置（通常是末尾），并通过间接寻址来访问，从而确保了虚基类子对象的唯一性。这种机制增加了对象的大小和访问成员的开销，但解决了菱形继承的二义性问题。

19、C++的多态怎么实现的 ​

C++中的多态（Polymorphism）主要通过虚函数和虚函数表机制来实现运行时多态（动态多态）。

  1. 虚函数：
  • 在基类中声明为virtual的成员函数。当通过基类指针或引用调用虚函数时，实际执行哪个函数取决于指向或引用的对象的实际类型，而不是指针或引用的类型。
  1. 虚函数表（vtable）：
  • 定义： 每个包含虚函数的类（或继承了虚函数的类）都会有一个虚函数表。虚函数表是一个静态的、只读的函数指针数组，它存储了该类中所有虚函数的地址。
  • 内容： 虚函数表中的每个条目对应一个虚函数。如果派生类重写了基类的虚函数，那么该条目会指向派生类中重写的函数；如果派生类没有重写，则指向基类中的函数。
  • 生成时机： 虚函数表是在编译时由编译器为每个类生成的。
  1. 虚表指针（vptr）：
  • 定义： 每个包含虚函数的类的对象，都会在其实例的内存布局中包含一个虚表指针（vptr）。vptr是一个指向该对象所属类的虚函数表的指针。
  • 内容： vptr存储的是对应类的虚函数表的地址。
  • 初始化时机： vptr是在对象构造时由编译器自动初始化的。当构造一个派生类对象时，vptr会先指向基类的虚函数表，然后随着构造过程的进行，最终指向派生类的虚函数表。
  • 位置： vptr通常是对象内存布局中的第一个成员（或者在某些编译器实现中是第二个，如果第一个是基类的vptr）。

多态的实现过程：

  1. 编译时：
    • 编译器为每个含有虚函数的类生成一个虚函数表（vtable）。
    • 编译器在每个含有虚函数的类的对象中添加一个虚表指针（vptr）。
  2. 运行时：
    • 当通过基类指针或引用调用一个虚函数时，编译器会生成代码，通过以下步骤进行调用： a. 首先，通过基类指针（或引用）找到对象的内存地址。 b. 从对象的内存地址中，找到存储在对象开头的虚表指针（vptr）。 c. 通过vptr找到该对象所属类的虚函数表（vtable）。 d. 在虚函数表中，根据虚函数在类中的声明顺序（偏移量），找到对应虚函数的地址。 e. 调用该地址处的函数。

总结： C++通过虚函数、虚函数表和虚表指针的组合，实现了在运行时根据对象的实际类型来调用相应函数的能力，这就是动态多态。

20、讲一讲C++的虚函数 ​

  1. 虚函数 (Virtual Function) 的定义：

虚函数是C++中实现运行时多态（动态多态）的关键机制。它是在基类中声明的，允许在派生类中被重写（override），并通过基类指针或引用调用时，能够根据对象的实际类型而不是指针或引用的类型来执行相应的函数。

  1. 虚函数的特点：
  • 关键字 virtual： 在基类中声明函数时，使用virtual关键字。
    cpp
    class Base {
public:
    virtual void func() { /* Base implementation */ }
};
  • 重写 (Override)： 派生类可以重写基类的虚函数。C++11引入了override关键字，用于显式标记派生类函数是重写基类虚函数，有助于编译器检查错误。
    cpp
    class Derived : public Base {
public:
    void func() override { /* Derived implementation */ } // 显式使用override
};
  • 多态性： 只有通过基类指针或引用调用虚函数时，才能体现多态性。
    cpp
    Base* b = new Derived();
b->func(); // 调用 Derived::func()
delete b;
  • 虚函数表 (vtable) 和虚表指针 (vptr)： 虚函数的实现依赖于vtable和vptr机制（详见问题19）。
  • 纯虚函数： 如果一个虚函数在基类中被声明为= 0，则它成为纯虚函数。包含纯虚函数的类是抽象类，不能被实例化。派生类必须实现所有纯虚函数才能被实例化。
    cpp
    class AbstractBase {
public:
    virtual void pureVirtualFunc() = 0; // 纯虚函数
};
  1. 虚函数的作用：
  • 实现动态多态： 允许在程序运行时根据对象的实际类型来决定调用哪个函数版本，增强了程序的灵活性和可扩展性。
  • 设计模式： 是许多面向对象设计模式（如工厂模式、策略模式、模板方法模式）的基础。
  • 接口定义： 纯虚函数可以用来定义接口，强制派生类实现特定的行为。
  1. 虚函数的限制：
  • 不能是static函数： static函数不属于任何对象，没有this指针，无法实现多态。
  • 不能是friend函数： friend函数不是类的成员，无法声明为虚函数。
  • 构造函数不能是虚函数： 在对象构造时，vptr尚未完全初始化，无法进行虚函数调用。此外，虚函数机制依赖于vptr，而vptr是在构造函数中初始化的。
  • 析构函数可以是虚函数： 强烈建议将基类的析构函数声明为虚函数，以避免内存泄漏（详见问题21）。

总结： 虚函数是C++面向对象编程中实现多态的核心特性，它通过vtable和vptr机制，使得程序能够根据对象的实际类型在运行时选择正确的函数版本，极大地提高了代码的灵活性和可维护性。

21、构造函数能是虚函数吗？析构函数能是虚函数吗？ ​

  1. 构造函数能是虚函数吗？

不能。 C++标准明确规定，构造函数不能是虚函数。

原因：

  • 虚函数机制依赖于虚表指针 (vptr)： 虚函数机制的核心是虚函数表（vtable）和虚表指针（vptr）。vptr是在对象构造过程中初始化的，它指向当前正在构造的类的vtable。
  • 对象类型未确定： 在构造函数执行期间，对象的类型是逐步确定的。当基类构造函数执行时，对象的vptr指向基类的vtable；当派生类构造函数执行时，vptr才指向派生类的vtable。如果在构造函数中调用虚函数，其行为将是不确定的，因为对象的完整类型尚未形成。
  • 多态的意义： 虚函数是为了实现多态，即通过基类指针或引用调用派生类对象的函数。而构造函数是在创建对象时调用的，此时还没有“基类指针指向派生类对象”的概念，对象本身正在被构建。
  1. 析构函数能是虚函数吗？

能，并且强烈建议将基类的析构函数声明为虚函数。

原因：

  • 避免内存泄漏： 当通过基类指针delete一个派生类对象时，如果基类的析构函数不是虚函数，那么只会调用基类的析构函数，而不会调用派生类的析构函数。这会导致派生类中特有的资源（如动态分配的内存、文件句柄等）无法被释放，从而造成内存泄漏或其他资源泄漏。
  • 实现多态销毁： 将基类的析构函数声明为虚函数，可以确保在通过基类指针delete派生类对象时，能够正确地调用派生类的析构函数，然后依次调用基类的析构函数，从而完整地销毁对象及其所有资源。

示例：

cpp
#include <iostream>

class Base {
public:
    Base() { std::cout << "Base constructor\n"; }
    // 如果这里不是virtual，delete b_ptr只会调用Base的析构函数
    virtual ~Base() { std::cout << "Base destructor\n"; }
};

class Derived : public Base {
public:
    int* data;
    Derived() : data(new int[10]) { std::cout << "Derived constructor\n"; }
    ~Derived() override { // 显式使用override是好习惯
        std::cout << "Derived destructor\n";
        delete[] data; // 释放派生类特有的资源
    }
};

int main() {
    Base* b_ptr = new Derived(); // 基类指针指向派生类对象
    delete b_ptr; // 如果Base::~Base()不是virtual，Derived::~Derived()将不会被调用，导致内存泄漏
    return 0;
}

输出（Base::~Base()为virtual时）：

c++
Base constructor
Derived constructor
Derived destructor
Base destructor

输出（Base::~Base()不是virtual时）：

c++
Base constructor
Derived constructor
Base destructor
// Derived destructor 未被调用，data 内存泄漏

总结： 构造函数不能是虚函数，因为虚函数机制在对象构造时还未完全建立。析构函数可以是虚函数，并且为了保证通过基类指针正确销毁派生类对象（避免内存泄漏），基类的析构函数必须声明为虚函数。

22、讲讲share_ptr ​

std::shared_ptr是C++11引入的一种智能指针，它实现了共享所有权的语义。多个shared_ptr可以共同管理同一个动态分配的对象，只有当所有指向该对象的shared_ptr都失效时，该对象才会被销毁。

  1. shared_ptr的特点：
  • 引用计数 (Reference Counting)： shared_ptr通过维护一个引用计数器来跟踪有多少个shared_ptr实例指向同一个对象。每当一个新的shared_ptr指向该对象时，引用计数加1；每当一个shared_ptr失效（超出作用域或被重置）时，引用计数减1。
  • 自动内存管理： 当引用计数变为0时，shared_ptr会自动调用被管理对象的析构函数并释放其内存，从而避免了内存泄漏。
  • 共享所有权： 多个shared_ptr可以共享同一个对象的所有权。它们之间是平等的，没有主次之分。
  • 线程安全（引用计数本身）： shared_ptr的引用计数操作是原子性的，因此在多线程环境下，引用计数的增减是线程安全的。但被管理对象的访问和修改不是线程安全的，仍需要额外的同步机制（如互斥量）来保护。
  • 不能管理数组： shared_ptr默认不能直接管理动态数组（new T[]），因为它默认调用delete obj而不是delete[] obj。如果需要管理数组，需要提供自定义删除器。
  1. shared_ptr的创建：

  • std::make_shared (推荐)：

    cpp
    std::shared_ptr<int> p1 = std::make_shared<int>(100); // 创建并初始化一个int对象
std::shared_ptr<MyClass> p2 = std::make_shared<MyClass>(arg1, arg2); // 创建并初始化MyClass对象
    • 优点： std::make_shared只进行一次内存分配，同时为对象和控制块（包含引用计数等信息）分配内存，效率更高，且具有异常安全。

  • 直接构造：

    cpp
    std::shared_ptr<int> p3(new int(200)); // 不推荐，两次内存分配，可能存在异常安全问题
  1. shared_ptr的使用：
  • 解引用： *p访问对象，p->member访问成员。
  • 获取原始指针： p.get()返回原始指针，但不要直接delete这个原始指针。
  • 获取引用计数： p.use_count()返回当前引用计数。
  • 重置： p.reset()或p.reset(new_obj)可以重置shared_ptr。
  1. shared_ptr的控制块 (Control Block)： 每个shared_ptr实例都关联一个控制块，它存储了：
  • 强引用计数： 记录有多少个shared_ptr指向该对象。
  • 弱引用计数： 记录有多少个weak_ptr指向该对象。
  • 自定义删除器： 如果提供了自定义删除器，也存储在这里。
  • 分配器： 如果提供了自定义分配器，也存储在这里。
  1. shared_ptr的缺点：
  • 循环引用： 两个或多个shared_ptr互相引用，导致引用计数永远不为零，从而造成内存泄漏。这是shared_ptr最常见的问题，需要使用std::weak_ptr来解决（详见问题23）。
  • 性能开销： 维护引用计数和控制块会带来一定的内存和CPU开销，但通常可以接受。

总结： std::shared_ptr通过引用计数实现了共享所有权的自动内存管理，极大地简化了C++中的内存管理，是现代C++编程中管理动态内存的首选工具之一。但需要注意避免循环引用问题。

23、怎么避免share_ptr产生的循环引用问题 ​

std::shared_ptr的循环引用（Circular Reference）是其设计中一个常见的陷阱，它会导致内存泄漏。当两个或多个对象通过shared_ptr互相引用时，它们的引用计数永远不会降到零，即使它们已经不再被外部使用，也无法被销毁。

示例：循环引用

cpp
#include <iostream>
#include <memory>

class B;

class A {
public:
    std::shared_ptr<B> b_ptr;
    A() { std::cout << "A constructor\n"; }
    ~A() { std::cout << "A destructor\n"; }
    void setB(std::shared_ptr<B> b) { b_ptr = b; }
};

class B {
public:
    std::shared_ptr<A> a_ptr;
    B() { std::cout << "B constructor\n"; }
    ~B() { std::cout << "B destructor\n"; }
    void setA(std::shared_ptr<A> a) { a_ptr = a; }
};

int main() {
    {
        std::shared_ptr<A> pa = std::make_shared<A>();
        std::shared_ptr<B> pb = std::make_shared<B>();

        pa->setB(pb); // A持有B的shared_ptr
        pb->setA(pa); // B持有A的shared_ptr

        std::cout << "pa use_count: " << pa.use_count() << std::endl; // 2
        std::cout << "pb use_count: " << pb.use_count() << std::endl; // 2
    }
    // pa和pb超出作用域，引用计数减为1，而不是0
    // A和B的析构函数都不会被调用，导致内存泄漏
    std::cout << "End of main\n";
    return 0;
}

输出：

c++
A constructor
B constructor
pa use_count: 2
pb use_count: 2
End of main

可以看到，A和B的析构函数都没有被调用。

避免循环引用的方法：使用 std::weak_ptr

std::weak_ptr是一种不控制对象生命周期的智能指针。它指向一个由std::shared_ptr管理的对象，但不会增加对象的引用计数。weak_ptr可以看作是shared_ptr的一个“旁观者”或“观察者”。

解决原理： 当一个对象需要引用另一个对象，但又不希望拥有其所有权（即不希望影响其生命周期）时，就应该使用std::weak_ptr。在循环引用场景中，将其中一个shared_ptr改为weak_ptr即可打破循环。

修改后的示例：

cpp
#include <iostream>
#include <memory>

class B;

class A {
public:
    std::shared_ptr<B> b_ptr;
    A() { std::cout << "A constructor\n"; }
    ~A() { std::cout << "A destructor\n"; }
    void setB(std::shared_ptr<B> b) { b_ptr = b; }
};

class B {
public:
    std::weak_ptr<A> a_ptr; // 将shared_ptr改为weak_ptr
    B() { std::cout << "B constructor\n"; }
    ~B() { std::cout << "B destructor\n"; }
    void setA(std::weak_ptr<A> a) { a_ptr = a; }
};

int main() {
    {
        std::shared_ptr<A> pa = std::make_shared<A>();
        std::shared_ptr<B> pb = std::make_shared<B>();

        pa->setB(pb); // A持有B的shared_ptr，B的引用计数+1
        pb->setA(pa); // B持有A的weak_ptr，A的引用计数不变

        std::cout << "pa use_count: " << pa.use_count() << std::endl; // 1
        std::cout << "pb use_count: " << pb.use_count() << std::endl; // 2

        // 尝试通过weak_ptr访问A
        if (std::shared_ptr<A> s_pa = pb->a_ptr.lock()) { // lock()方法将weak_ptr提升为shared_ptr
            std::cout << "Accessing A from B: " << s_pa.use_count() << std::endl; // 2
        }
    }
    // pa和pb超出作用域，引用计数减为0，A和B的析构函数被调用
    std::cout << "End of main\n";
    return 0;
}

输出：

c++
A constructor
B constructor
pa use_count: 1
pb use_count: 2
Accessing A from B: 2
B destructor
A destructor
End of main

weak_ptr的使用注意事项：

  • weak_ptr不能直接访问所管理的对象，因为它不拥有对象。需要通过调用其lock()方法来获取一个shared_ptr。如果对象已经销毁，lock()会返回一个空的shared_ptr。
  • weak_ptr主要用于解决循环引用，或者作为观察者模式中的观察者，避免持有不必要的强引用。

总结： 避免shared_ptr循环引用的最佳实践是，在对象之间存在相互引用时，仔细分析它们之间的所有权关系。如果一个对象对另一个对象的引用不应该影响其生命周期，那么就应该使用std::weak_ptr来持有该引用，从而打破循环，确保内存能够被正确释放。