牛客网C++社招开发高频算法题目整理

一、数据结构算法

常见问题：链表、排序、二叉树。

• 数组和链表区别和优缺点
• 快速排序
• 堆排序是怎么做的
• 冒泡排序
• 二分查找（复杂度）
• hash表数据很大。rehash的代价很高，怎么办
• 二叉树前序遍历非递归
• 链表反转
• 二叉树输出每一层最右边的节点
• 千万级数组如何求最大k个数？（用最小堆反之最大堆） 千万数据范围有限，0到1000，有很多重复的，按频率排序怎么处理？
• 计算二叉树层高。
• 给一个连续非空子数组，找它乘积最大的（动态规划）
• 排序算法. 哪些是稳定的，哪些不稳定的
• 树的深度和高度。一开始分别用了一个层序遍历和一个dfs，然后面试官问能否都在一个dfs里面呢，提示了一下在dfs是否可以传一个参数，然后解决了。
• 布隆过滤器介绍
• 为什么不用布隆过滤器
• .数据结构相关，图的种类，表示方法，图有哪些经典算法+描述算法
• 求最大的k个数字，解法：优先队列（堆）或者快速排序
• 一个大数问题，解法：转换为字符串解决，这题没写好，leetcode应该有很多类似的问题
• hash解决冲突 （ 开放定址法、链地址法、再哈希法、建立公共溢出区 ），四种方式详细的过程、思路
• 链地址法和再哈希法之间的关联和区别，两者分别适用场景，两者底层的数据结构，关联和区别
• 链表和数组的底层结构设计、关联、区别、应用场景
• 死锁的概念，进程调度算法怎么解决死锁

二、C/C++语言

常见问题：智能指针、多态、虚函数、stl原理。

• 智能指针实现原理
• 智能指针，里面的计数器何时会改变
• 智能指针和管理的对象分别在哪个区（智能指针本身在栈区，托管的资源在堆区，利用了栈对象超出生命周期后自动析构的特征，所以无需手动delete释放资源。
• 面向对象的特性：多态原理
• 介绍一下虚函数，虚函数怎么实现的
• 多态和继承在什么情况下使用
• 除了多态和继承还有什么面向对象方法
• C++内存分布。什么样的数据在栈区，什么样的在堆区
• C++内存管理（RAII啥的）
• C++从源程序到可执行程序的过程
• 一个对象=另一个对象会发生什么（赋值构造函数）
• 如果new了之后出了问题直接return。会导致内存泄漏。怎么办（智能指针，raii）
• c++11的智能指针有哪些。weak_ptr的使用场景。什么情况下会产生循环引用
• 多进程fork后不同进程会共享哪些资源
• 多线程里线程的同步方式有哪些
• size_of是在编译期还是在运行期确定
• 函数重载的机制。重载是在编译期还是在运行期确定
• 指针常量和常量指针
• vector的原理，怎么扩容
• 介绍一下const
• 引用和指针的区别
• Cpp新特性知道哪些
• 类型转换
• RAII基于什么实现的（生命周期、作用域、构造析构
• 手撕：Unique_ptr，控制权转移(移动语义）
• 手撕：类继承，堆栈上分别代码实现多态
• unique_ptr和shared_ptr区别
• 右值引用
• 函数参数可不可以传右值
• 参考c/c++堆栈实现自己的堆栈。要求：不能用stl容器。
• stl容器了解吗？底层如何实现：vector数组，map红黑树，红黑树的实现
• 完美转发介绍一下 去掉std::forward会怎样？
• 介绍一下unique_lock和lock_guard区别？
• C代码中引用C++代码有时候会报错为什么？
• 静态多态有什么？虚函数原理 虚表是什么时候建立的 为什么要把析构函数设置成虚函数？
• map为啥用红黑树不用avl树？（几乎所有面试都问了map和unordered_map区别）
• inline 失效场景
• C++ 中 struct 和 class 区别
• 如何防止一个头文件 include 多次
• lambda表达式的理解，它可以捕获哪些类型
• 友元friend介绍
• move函数
• 模版类的作用
• 模版和泛型的区别
• 内存管理：C++的new和malloc的区别
• new可以重载吗，可以改写new函数吗
• C++中的map和unordered_map的区别和使用场景
• 他们是线程安全的吗
• c++标准库里优先队列是怎么实现的？
• gcc编译的过程
• C++ Coroutine
• extern C有什么作用
• c++ memoryorder/elf文件格式/中断对于操作系统的作
• C++的符号表
• C++的单元测试

三、操作系统

5.1操作系统原理

• 线程和进程的区别、应用场景。
• 多线程中各种锁，读写锁，互斥锁
• 内存池
• 内存管理
• 内存写漏
• 如果频繁进行内存的分配释放会有什么问题吗？
• 如果频繁分配释放的内存很大（>128k）,怎么处理？
• 虚拟内存以及堆栈溢出相关的问题，堆栈溢出怎么处理等等。
• 分段和分页的区别
• 进程间通信原理和方式
• fork()读时共享写时拷贝
• 互斥锁+条件变量
• 如果非堆内存一直在增长，可能哪个区域的内存出了问题（Java）
• 堆和栈的区别。什么情况下会往堆里放
• fork函数返回值是怎么实现的
• 用户级线程和内核级线程的区别
• 线程池和线程开销
• 线程切换的到底是什么
• 线程同步共享怎么实现
• 互斥同步的方法
• 信号量和自旋锁的区别
• 查看磁盘、cpu 占用、内存占用命令
• linux虚拟地址空间结构/动态库地址无关代码
• top

四、gdb/gcc/g++

• 什么是GDB？它用于做什么？
• GDB的常用命令有哪些？
• 如何在GDB中设置断点？
• 如何在GDB中查看变量的值？
• 如何使用GDB进行程序调试时，定位内存泄漏问题？
• 请解释GCC和G++之间的区别。
• GCC和G++都可以编译C++代码吗？如果可以，有什么不同之处？
• GCC的常用编译选项有哪些？
• G++的常用编译选项有哪些？
• 如何在GCC/G++中指定特定版本的标准（如C++11或C++14）进行编译？
• 怎么debug，怎么看内存泄漏。
• gdb 使用 -> 多线程程序切换到某线程栈帧 -> 如何查看寄存器值
• 怎么分析C++的core文件
• GDB有哪些命令
• gcc和g++的区别
• Linux下程序有问题，如何调试？（答GDB打开，打上Breakpoint进行调试）

五、设计模式

• 什么是设计模式？为什么使用设计模式？
• 列举常见的设计模式分类，并简要描述每个分类中的几个具体设计模式。
• 解释单例模式的概念和用途，以及如何实现单例模式。
• 什么是工厂方法模式和抽象工厂模式？它们之间有何区别？
• 解释装饰器模式和适配器模式的概念，并举例说明它们的应用场景。
• 什么是观察者模式？如何实现观察者模式？
• 解释策略模式和状态模式之间的区别，以及在什么情况下使用它们。
• 什么是迭代器模式和组合模式？它们可以一起使用吗？
• 解释桥接模式和适配器模式之间的区别，并说明在哪种情况下选择使用桥接或适配器。
• 介绍责任链模式和命令模式的概念，并说明它们如何解耦发送者和接收者。
• 单例模式实现区别
• 策略模式实现

数据结构算法：实现方法和代码思路

1. 链表反转

问题描述： 反转一个单链表。

实现方法与代码思路：

链表反转可以通过迭代或递归两种方式实现。迭代法通常更推荐，因为它避免了递归带来的栈溢出风险。

迭代法：

核心思想是遍历链表，在遍历过程中，将当前节点的 next 指针指向其前一个节点。需要维护三个指针：prev（前一个节点，初始为 nullptr），curr（当前节点，初始为链表头），next_temp（临时保存 curr->next，防止链表断裂）。

// 伪代码
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next_temp = curr->next; // 保存下一个节点
        curr->next = prev;              // 反转当前节点的指针
        prev = curr;                    // 移动prev到当前节点
        curr = next_temp;               // 移动curr到下一个节点
    }
    return prev; // prev最终会指向新的头节点
}

递归法：

递归的思路是，如果链表为空或只有一个节点，则直接返回。否则，递归反转 head->next，然后将 head->next 的 next 指针指向 head，最后将 head->next 置为 nullptr，返回新的头节点。

// 伪代码
ListNode* reverseListRecursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

2. 快速排序

问题描述： 对一个数组进行排序。

实现方法与代码思路：

快速排序是一种高效的排序算法，采用分治策略。其核心是选择一个“基准”（pivot）元素，然后将数组分为两部分：小于基准的元素和大于基准的元素。然后对这两部分递归地进行快速排序。

核心步骤：

1. 选择基准： 可以选择数组的第一个、最后一个、中间或随机元素作为基准。选择一个好的基准对性能至关重要。
2. 分区（Partition）： 重新排列数组，使得所有小于基准的元素都位于基准之前，所有大于基准的元素都位于基准之后。在这个分区结束之后，该基准就处于最终的正确位置。
3. 递归排序： 递归地对小于基准的子数组和大于基准的子数组进行快速排序。

// 伪代码
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区索引，arr[pi] 现在在正确的位置上
        int pi = partition(arr, low, high);

        // 递归排序左右两部分
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);     // 小于基准的元素的索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加小于基准的元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

3. 堆排序

问题描述： 对一个数组进行排序。

实现方法与代码思路：

堆排序是一种基于比较的排序算法，利用了堆这种数据结构。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即父节点的键值总是大于或等于（或小于或等于）任何一个子节点的键值。堆排序通常使用最大堆（父节点大于子节点）来实现升序排序。

核心步骤：

1. 构建最大堆： 将待排序的数组构造成一个最大堆。从最后一个非叶子节点开始，自底向上进行堆化（heapify）操作。
2. 堆排序： 将堆顶元素（最大值）与堆的最后一个元素交换，然后将堆的大小减1，并对新的堆顶元素进行堆化操作，重复此过程直到堆的大小为1。

// 伪代码
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 逐个提取元素进行排序
    for (int i = n - 1; i > 0; i--) {
        // 将当前根节点（最大值）与末尾元素交换
        swap(&arr[0], &arr[i]);

        // 对剩余元素进行堆化
        heapify(arr, i, 0);
    }
}

// 堆化函数：维护堆的性质
void heapify(int arr[], int n, int i) {
    int largest = i;       // 初始化最大元素为根节点
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于目前最大节点
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大元素不是根节点
    if (largest != i) {
        swap(&arr[i], &arr[largest]);

        // 递归堆化受影响的子树
        heapify(arr, n, largest);
    }
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

4. 二分查找

问题描述： 在一个有序数组中查找特定元素的位置。

实现方法与代码思路：

二分查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。它的工作原理是，首先比较数组的中间元素与目标值。如果目标值等于中间元素，则查找成功。如果目标值小于中间元素，则在数组的左半部分继续查找。如果目标值大于中间元素，则在数组的右半部分继续查找。这个过程会重复进行，直到找到目标值或搜索范围为空。

核心步骤：

1. 初始化： 设置 low 为数组的起始索引，high 为数组的结束索引。
2. 循环查找： 当 low <= high 时，计算中间索引 mid = low + (high - low) / 2。
3. 比较：
   • 如果 arr[mid] == target，返回 mid。
   • 如果 arr[mid] < target，说明目标在右半部分，更新 low = mid + 1。
   • 如果 arr[mid] > target，说明目标在左半部分，更新 high = mid - 1。
4. 未找到： 如果循环结束仍未找到，返回 -1。

// 伪代码
int binarySearch(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // 避免溢出

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // 未找到
}

5. 千万级数组求最大k个数

问题描述： 从一个包含千万个元素的数组中找出最大的k个数。

实现方法与代码思路：

这是一个经典的问题，可以使用最小堆（Min-Heap）或快速选择（QuickSelect）算法来解决。

方法一：最小堆（Min-Heap）

核心思想： 维护一个大小为k的最小堆。遍历数组中的每个元素，如果当前元素大于堆顶元素，则将堆顶元素替换为当前元素，并重新调整堆。遍历结束后，堆中的k个元素就是数组中最大的k个数。

步骤：

1. 创建一个大小为k的最小堆。
2. 将数组的前k个元素插入堆中。
3. 从第k+1个元素开始遍历数组：
   • 如果当前元素大于堆顶元素（堆中最小的元素），则将堆顶元素弹出，并将当前元素插入堆中。
   • 否则，跳过当前元素。
4. 遍历结束后，堆中剩下的k个元素就是最大的k个数。

优点： 适用于数据量非常大，甚至无法一次性加载到内存中的情况（流式数据）。时间复杂度为 O(N log k)。

// 伪代码 (使用C++ STL的priority_queue)
#include <queue>
#include <vector>

std::vector<int> findKLargest(const std::vector<int>& nums, int k) {
    if (k <= 0 || k > nums.size()) {
        return {}; // 处理无效k值
    }

    // 创建一个最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 将前k个元素放入堆中
    for (int i = 0; i < k; ++i) {
        minHeap.push(nums[i]);
    }

    // 遍历剩余元素
    for (int i = k; i < nums.size(); ++i) {
        if (nums[i] > minHeap.top()) {
            minHeap.pop();
            minHeap.push(nums[i]);
        }
    }

    // 将堆中元素取出，即为最大的k个数
    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    // 结果是升序的，如果需要降序可以反转
    std::reverse(result.begin(), result.end());
    return result;
}

方法二：快速选择（QuickSelect）

核心思想： 快速选择是快速排序的一个变种，它不是对所有元素进行排序，而是只找到第k个最小（或最大）的元素。一旦找到第k个元素，那么所有比它大的元素都在它的右边（如果目标是找最大的k个），这些就是我们需要的。

步骤：

1. 随机选择一个基准元素。
2. 通过分区操作，将数组分为两部分：小于基准的元素和大于基准的元素。
3. 判断基准元素的位置 p：
   • 如果 p 正好是第 k 大元素的位置，则找到。
   • 如果 p 大于 k，则在左侧子数组中继续查找。
   • 如果 p 小于 k，则在右侧子数组中继续查找（注意调整 k 的值）。

优点： 平均时间复杂度为 O(N)，最坏情况为 O(N^2)（可以通过随机选择基准来避免）。

// 伪代码 (基于快速排序的分区思想)
// 找到数组中第k大的元素（0-indexed）
int quickSelect(std::vector<int>& nums, int low, int high, int k) {
    if (low == high) {
        return nums[low];
    }

    int pivotIndex = partition(nums, low, high); // 分区操作

    if (pivotIndex == k) {
        return nums[k];
    } else if (pivotIndex < k) {
        return quickSelect(nums, pivotIndex + 1, high, k);
    } else {
        return quickSelect(nums, low, pivotIndex - 1, k);
    }
}

// partition函数与快速排序中的相同
// int partition(std::vector<int>& nums, int low, int high) { ... }

// 找出最大的k个数，可以先找到第k大的元素，然后遍历数组找出所有大于等于它的元素
std::vector<int> findKLargestQuickSelect(std::vector<int>& nums, int k) {
    if (k <= 0 || k > nums.size()) {
        return {};
    }
    // 找到第 nums.size() - k 个最小的元素，即第k大的元素
    int kthLargestVal = quickSelect(nums, 0, nums.size() - 1, nums.size() - k);

    std::vector<int> result;
    for (int num : nums) {
        if (num >= kthLargestVal) {
            result.push_back(num);
        }
    }
    // 注意：这里可能包含重复的 kthLargestVal，且数量可能多于k个，需要进一步处理
    // 更精确的做法是，找到第k大元素后，重新遍历一次数组，收集所有大于等于它的元素，并确保数量为k
    // 或者直接在quickSelect结束后，取右侧的k个元素
    return result;
}

6. 动态规划：最大乘积子数组

问题描述： 给定一个整数数组 nums，找出数组中乘积最大的连续非空子数组（该子数组中至少包含一个数字）。

实现方法与代码思路：

动态规划（Dynamic Programming）是解决这类问题的有效方法。与求最大和子数组不同，乘积可能因为负数的存在而变得复杂：一个很小的负数乘以另一个负数可能变成一个很大的正数。

核心思想：

在遍历数组时，我们需要同时维护以当前元素结尾的最大乘积和最小乘积。因为下一个元素可能是负数，当前最小乘积乘以负数可能变成下一个最大乘积。

状态定义：

• max_so_far[i]：以 nums[i] 结尾的最大乘积。
• min_so_far[i]：以 nums[i] 结尾的最小乘积。

状态转移方程： 对于每个 nums[i]，其最大乘积可能是 nums[i] 本身，或者是 nums[i] 乘以 max_so_far[i-1]，或者是 nums[i] 乘以 min_so_far[i-1]。最小乘积同理。

max_so_far[i] = max(nums[i], nums[i] * max_so_far[i-1], nums[i] * min_so_far[i-1])min_so_far[i] = min(nums[i], nums[i] * max_so_far[i-1], nums[i] * min_so_far[i-1])

同时，需要一个全局变量 result 来记录整个过程中出现的最大乘积。

优化空间： 考虑到 max_so_far[i] 和 min_so_far[i] 只依赖于 i-1 的状态，我们可以将空间复杂度优化到 O(1)，只用两个变量 current_max 和 current_min 来代替数组。

// 伪代码
int maxProduct(const std::vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    int result = nums[0];
    int current_max = nums[0]; // 以当前元素结尾的最大乘积
    int current_min = nums[0]; // 以当前元素结尾的最小乘积

    for (size_t i = 1; i < nums.size(); ++i) {
        int num = nums[i];
        // 临时保存 current_max，因为计算 current_min 时会用到旧的 current_max
        int temp_max = current_max;

        current_max = std::max({num, num * temp_max, num * current_min});
        current_min = std::min({num, num * temp_max, num * current_min});

        result = std::max(result, current_max);
    }

    return result;
}

7. Hash表解决冲突

问题描述： Hash表在插入元素时，如果计算出的哈希值发生冲突（即不同的键映射到同一个地址），如何解决？

实现方法与代码思路：

哈希冲突是哈希表设计中不可避免的问题，主要有以下几种解决策略：

方法一：链地址法（Separate Chaining）

核心思想： 将所有哈希到同一个地址的元素存储在一个链表中。哈希表的每个“桶”不再直接存储元素，而是存储一个链表的头指针。当发生冲突时，新元素被添加到对应桶的链表末尾（或头部）。

优点： 实现简单，对装载因子不敏感，可以存储任意数量的元素。 缺点： 链表操作可能导致性能下降（缓存不友好），需要额外的空间存储链表指针。

// 伪代码
// 假设哈希表是一个vector of list
std::vector<std::list<std::pair<Key, Value>>> hashTable;
int tableSize; // 哈希表大小

// 插入操作
void insert(const Key& key, const Value& value) {
    int index = hashFunction(key) % tableSize;
    // 遍历链表，如果键已存在则更新值，否则添加到链表末尾
    for (auto& entry : hashTable[index]) {
        if (entry.first == key) {
            entry.second = value;
            return;
        }
    }
    hashTable[index].push_back({key, value});
}

// 查找操作
Value* find(const Key& key) {
    int index = hashFunction(key) % tableSize;
    for (auto& entry : hashTable[index]) {
        if (entry.first == key) {
            return &entry.second;
        }
    }
    return nullptr; // 未找到
}

方法二：开放定址法（Open Addressing）

核心思想： 当发生冲突时，不是将元素存储在链表中，而是在哈希表中寻找下一个可用的空槽位。这需要定义一个探测序列来决定下一个尝试的地址。

常见的探测序列：

• 线性探测（Linear Probing）： (hash(key) + i) % tableSize，其中 i 是探测次数。
• 二次探测（Quadratic Probing）： (hash(key) + i*i) % tableSize。
• 双重哈希（Double Hashing）： (hash1(key) + i * hash2(key)) % tableSize。

优点： 缓存友好，不需要额外的链表存储空间。 缺点： 容易发生“聚集”（clustering）现象，导致性能下降；删除操作复杂；对装载因子敏感，当表满时需要扩容。

// 伪代码 (线性探测)
std::vector<std::pair<Key, Value>> hashTable; // 存储实际元素
std::vector<bool> occupied; // 标记槽位是否被占用
int tableSize; // 哈希表大小

// 插入操作
void insert(const Key& key, const Value& value) {
    int index = hashFunction(key) % tableSize;
    int originalIndex = index;
    while (occupied[index]) {
        if (hashTable[index].first == key) { // 键已存在，更新值
            hashTable[index].second = value;
            return;
        }
        index = (index + 1) % tableSize; // 线性探测下一个槽位
        if (index == originalIndex) { // 表已满，或无法插入
            // 处理扩容或错误
            return;
        }
    }
    hashTable[index] = {key, value};
    occupied[index] = true;
}

// 查找操作
Value* find(const Key& key) {
    int index = hashFunction(key) % tableSize;
    int originalIndex = index;
    while (occupied[index]) {
        if (hashTable[index].first == key) {
            return &hashTable[index].second;
        }
        index = (index + 1) % tableSize;
        if (index == originalIndex) {
            return nullptr; // 遍历一圈未找到
        }
    }
    return nullptr; // 遇到空槽位，未找到
}

8. 链表和数组的区别和优缺点

问题描述： 比较链表和数组这两种基本数据结构的特点、优缺点以及适用场景。

实现方法与代码思路：

链表和数组是两种最基本、最常用的线性数据结构，它们在内存存储、访问方式、插入/删除效率等方面有显著差异。

数组 (Array)

• 存储方式： 在内存中是连续存储的。每个元素占用固定大小的内存空间。
• 访问方式： 支持随机访问，可以通过索引直接访问任意元素，时间复杂度为 O(1)。
• 插入/删除： 在数组中间插入或删除元素需要移动大量后续元素，时间复杂度为 O(N)。在数组末尾插入/删除（如果空间允许）通常是 O(1)。
• 空间利用： 空间利用率高，但需要预先分配固定大小的内存，可能导致空间浪费或不足。
• 缓存友好： 由于内存连续，CPU缓存命中率高，有利于提高访问速度。

链表 (Linked List)

• 存储方式： 在内存中是非连续存储的。每个节点包含数据和指向下一个（或前一个）节点的指针。
• 访问方式： 只能顺序访问，要访问某个元素必须从头节点开始遍历，时间复杂度为 O(N)。
• 插入/删除： 在链表中间插入或删除元素只需要修改少数几个指针，时间复杂度为 O(1)（前提是已经定位到插入/删除位置）。
• 空间利用： 空间利用率相对较低，因为每个节点需要额外的空间存储指针。但可以动态分配内存，按需增长。
• 缓存不友好： 由于内存不连续，CPU缓存命中率低，可能导致访问速度相对较慢。

优缺点总结：

特性	数组 (Array)	链表 (Linked List)
内存存储	连续	非连续
访问方式	随机访问 (O(1))	顺序访问 (O(N))
插入/删除	中间 O(N)，末尾 O(1)	中间 O(1) (已知位置)，查找 O(N)
空间利用	较高，但可能浪费或不足	较低 (额外指针空间)，但动态性强
缓存友好	高	低

适用场景：

• 数组：
  • 需要频繁随机访问元素，例如通过索引快速查找数据。
  • 数据量相对固定，或者可以预估最大数据量。
  • 对内存连续性有要求，例如某些算法或硬件交互。
• 链表：
  • 需要频繁在中间位置进行插入和删除操作，例如实现队列、栈、LRU缓存等。
  • 数据量不确定，需要动态增删。
  • 内存空间不连续，或者需要灵活的内存管理。

9. 树的深度和高度

问题描述： 解释二叉树的深度和高度的概念，并给出计算方法。

实现方法与代码思路：

在树形数据结构中，深度和高度是描述节点位置和树结构的重要概念，但它们的定义是相对的。

• 节点深度 (Depth of a Node)： 指从根节点到该节点的路径上的边的数量。根节点的深度为0。
• 节点高度 (Height of a Node)： 指从该节点到其最远叶子节点的路径上的边的数量。叶子节点的高度为0。
• 树的深度 (Depth of a Tree)： 等于树中所有节点的最大深度，即最深叶子节点的深度。
• 树的高度 (Height of a Tree)： 等于树中所有节点的最大高度，即根节点的高度。

计算方法：

计算节点深度：

通常通过从根节点开始进行遍历（如DFS或BFS），并传递一个深度参数来实现。根节点的深度为0，每向下遍历一层，深度加1。

// 伪代码：计算某个节点的深度 (假设已知根节点)
int getDepth(TreeNode* root, TreeNode* targetNode, int currentDepth) {
    if (root == nullptr) {
        return -1; // 未找到
    }
    if (root == targetNode) {
        return currentDepth;
    }
    int leftDepth = getDepth(root->left, targetNode, currentDepth + 1);
    if (leftDepth != -1) {
        return leftDepth;
    }
    int rightDepth = getDepth(root->right, targetNode, currentDepth + 1);
    return rightDepth;
}

计算节点高度 (以及树的高度)：

计算节点高度通常采用递归方式，从叶子节点向上计算。叶子节点的高度为0。对于非叶子节点，其高度等于其左右子节点高度的最大值加1。

// 伪代码：计算节点高度 (同时也是计算树的高度，如果传入根节点)
int getHeight(TreeNode* node) {
    if (node == nullptr) {
        return -1; // 空节点高度定义为-1，方便计算
    }
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    return std::max(leftHeight, rightHeight) + 1;
}

// 如果树的高度定义为节点数，则空树高度为0，单节点树高度为1
// 另一种定义：空树高度为0，单节点树高度为1，则叶子节点高度为1
// 此时：
int getHeightAlternative(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    int leftHeight = getHeightAlternative(node->left);
    int rightHeight = getHeightAlternative(node->right);
    return std::max(leftHeight, rightHeight) + 1;
}

面试中常问的“能否都在一个dfs里面呢”的提示：

这通常是指在一次DFS遍历中同时计算树的高度和最大深度。虽然深度是自顶向下传递的，高度是自底向上返回的，但可以通过在DFS函数中返回高度，并在函数参数中传递当前深度来实现。

// 伪代码：在一次DFS中同时计算最大深度和高度
// max_depth_val 用于存储全局最大深度
int calculateHeightAndMaxDepth(TreeNode* node, int current_depth, int& max_depth_val) {
    if (node == nullptr) {
        max_depth_val = std::max(max_depth_val, current_depth - 1); // 更新最大深度
        return -1; // 空节点高度为-1
    }

    // 递归计算左右子树的高度
    int left_height = calculateHeightAndMaxDepth(node->left, current_depth + 1, max_depth_val);
    int right_height = calculateHeightAndMaxDepth(node->right, current_depth + 1, max_depth_val);

    // 当前节点的高度
    return std::max(left_height, right_height) + 1;
}

// 调用示例：
// int max_depth = 0;
// int tree_height = calculateHeightAndMaxDepth(root, 0, max_depth);
// 此时 max_depth 就是树的最大深度，tree_height 就是树的高度

10. 布隆过滤器

问题描述： 介绍布隆过滤器（Bloom Filter）的概念、原理、优缺点和适用场景。

实现方法与代码思路：

布隆过滤器是一种空间效率很高的数据结构，用于判断一个元素是否可能在一个集合中。它的特点是，如果判断一个元素不在集合中，那么它一定不在；如果判断一个元素在集合中，那么它可能在，也可能不在（存在误判）。

核心原理：

1. 位数组 (Bit Array)： 一个由 m 个比特位组成的数组，所有位初始都为0。
2. 哈希函数 (Hash Functions)： k 个独立的哈希函数，每个函数将元素映射到位数组中的一个位置。

插入元素： 当插入一个元素时，使用 k 个哈希函数分别计算出 k 个哈希值，然后将位数组中对应这 k 个位置的比特位都设置为1。

查询元素： 当查询一个元素时，同样使用 k 个哈希函数计算出 k 个哈希值，然后检查位数组中对应这 k 个位置的比特位。如果所有这 k 个位置的比特位都为1，则认为该元素可能在集合中；如果有任何一个位置的比特位为0，则该元素一定不在集合中。

误判率 (False Positive Rate)： 布隆过滤器存在误判，即一个元素实际上不在集合中，但被判断为在集合中。误判率与位数组的大小 m、哈希函数的数量 k 以及插入的元素数量 n 有关。增加 m 或优化 k 可以降低误判率。

优缺点：

• 优点：
  • 空间效率高： 相比于哈希表或集合，占用内存极少。
  • 查询速度快： 插入和查询的时间复杂度都是 O(k)，与集合大小无关。
  • 保密性好： 不存储实际元素，只存储哈希值，对隐私数据友好。
• 缺点：
  • 存在误判： 无法避免假阳性（False Positive），即“可能在”的情况。
  • 不能删除元素： 一旦某个位被设置为1，就不能轻易地将其改回0，因为这可能会影响到其他元素的判断。如果需要删除功能，可以使用计数布隆过滤器（Counting Bloom Filter）。
  • 容量固定： 位数组大小固定，当插入元素过多时，误判率会急剧上升。

适用场景：

• 判断元素是否存在： 例如，网页爬虫判断URL是否已爬取，避免重复爬取。
• 缓存穿透： 解决缓存穿透问题，在查询数据库之前，先通过布隆过滤器判断请求的数据是否存在，如果不存在则直接返回，避免对数据库的无效查询。
• 垃圾邮件过滤： 快速判断一个邮件地址是否在黑名单中。
• 分布式系统： 快速同步数据状态，减少网络传输。

// 伪代码：布隆过滤器基本实现
#include <vector>
#include <string>
#include <functional>

class BloomFilter {
public:
    BloomFilter(int size, int numHashes) : bitArray(size, false), numHashes(numHashes) {}

    void add(const std::string& s) {
        for (int i = 0; i < numHashes; ++i) {
            size_t hashVal = hashFunction(s, i); // 不同的哈希函数
            bitArray[hashVal % bitArray.size()] = true;
        }
    }

    bool contains(const std::string& s) const {
        for (int i = 0; i < numHashes; ++i) {
            size_t hashVal = hashFunction(s, i);
            if (!bitArray[hashVal % bitArray.size()]) {
                return false; // 某个位为0，一定不在
            }
        }
        return true; // 所有位都为1，可能在
    }

private:
    std::vector<bool> bitArray;
    int numHashes;

    // 示例哈希函数（实际应用中需要更复杂的哈希函数组合）
    size_t hashFunction(const std::string& s, int seed) const {
        size_t hash = 0;
        for (char c : s) {
            hash = (hash * 31 + c) + seed; // 简单的哈希，结合种子
        }
        return hash;
    }
};

11. 图的种类，表示方法，图有哪些经典算法+描述算法

问题描述： 介绍图（Graph）的基本概念、常见的表示方法以及一些经典的图算法。

实现方法与代码思路：

图是一种非线性数据结构，由顶点（Vertex/Node）和边（Edge）组成，用于表示对象之间的关系。图可以分为多种类型，并有不同的表示方法和算法。

图的种类：

1. 有向图 (Directed Graph)： 边有方向，从一个顶点指向另一个顶点。例如，单向街道。
2. 无向图 (Undirected Graph)： 边没有方向，连接的两个顶点可以互相访问。例如，双向街道。
3. 带权图 (Weighted Graph)： 边上带有权重（或成本），表示从一个顶点到另一个顶点的“代价”或“距离”。例如，地图上的距离。
4. 无权图 (Unweighted Graph)： 边上没有权重，只表示连接关系。
5. 简单图 (Simple Graph)： 不包含自环（连接到自身的边）和多重边（两个顶点之间有多条边）的图。
6. 多重图 (Multigraph)： 允许顶点之间有多条边的图。
7. 完全图 (Complete Graph)： 图中任意两个不同的顶点之间都有一条边相连。
8. 稀疏图 (Sparse Graph)： 边的数量远小于可能的最大边数（V*(V-1)/2）的图。
9. 稠密图 (Dense Graph)： 边的数量接近可能的最大边数的图。
10. 连通图 (Connected Graph)： 在无向图中，任意两个顶点之间都存在路径。在有向图中，分为强连通（任意两点互相可达）和弱连通（忽略方向后连通）。
11. 树 (Tree)： 一种特殊的无向连通图，不包含环。
12. 森林 (Forest)： 多个不相交的树的集合。

图的表示方法：

1. 邻接矩阵 (Adjacency Matrix)：

   • 使用一个 V x V 的二维数组 adj[i][j] 来表示图。如果顶点 i 和 j 之间有边，则 adj[i][j] 为1（或权重），否则为0（或无穷大）。
   • 优点： 检查两个顶点之间是否存在边非常快 (O(1))；易于实现。
   • 缺点： 空间复杂度高 (O(V^2))，对于稀疏图会浪费大量空间；查找一个顶点的所有邻居需要遍历一行 (O(V))。

   // 伪代码：邻接矩阵
   const int MAX_VERTICES = 100;
   int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 0表示无边，1表示有边，或存储权重
   int numVertices;
   
   void initGraph(int V) {
       numVertices = V;
       for (int i = 0; i < V; ++i) {
           for (int j = 0; j < V; ++j) {
               adjMatrix[i][j] = 0; // 或 INFINITY
           }
       }
   }
   
   void addEdge(int u, int v, int weight = 1) {
       adjMatrix[u][v] = weight;
       // 如果是无向图，还需要 adjMatrix[v][u] = weight;
   }

2. 邻接表 (Adjacency List)：

   • 使用一个数组（或 vector）存储链表（或 vector）。数组的每个索引代表一个顶点，其对应的链表存储该顶点所有邻居的列表。
   • 优点： 空间复杂度低 (O(V + E))，对于稀疏图非常高效；查找一个顶点的所有邻居非常快 (O(degree(V)))。
   • 缺点： 检查两个顶点之间是否存在边需要遍历链表 (O(degree(V)))。

   // 伪代码：邻接表
   #include <vector>
   #include <list>
   
   std::vector<std::list<std::pair<int, int>>> adjList; // pair: {neighbor_vertex, weight}
   int numVertices;
   
   void initGraph(int V) {
       numVertices = V;
       adjList.resize(V);
   }
   
   void addEdge(int u, int v, int weight = 1) {
       adjList[u].push_back({v, weight});
       // 如果是无向图，还需要 adjList[v].push_back({u, weight});
   }

经典图算法：

1. 广度优先搜索 (BFS - Breadth-First Search)：

   • 描述： 从起始顶点开始，逐层地访问所有可达的顶点。它使用队列来管理待访问的顶点。
   • 应用： 查找最短路径（无权图），判断图是否连通，查找图中的所有连通分量，社交网络中查找一度好友等。
   • 思路：
     1. 创建一个队列并将起始顶点加入队列。
     2. 标记起始顶点为已访问。
     3. 当队列不为空时，取出队头顶点 u。
     4. 访问 u 的所有未访问邻居 v，将 v 加入队列并标记为已访问。

   // 伪代码
   #include <queue>
   #include <vector>
   
   void BFS(int startNode, int numVertices, const std::vector<std::list<int>>& adj) {
       std::vector<bool> visited(numVertices, false);
       std::queue<int> q;
   
       visited[startNode] = true;
       q.push(startNode);
   
       while (!q.empty()) {
           int u = q.front();
           q.pop();
           // 访问节点 u
           // std::cout << u << " ";
   
           for (int v : adj[u]) {
               if (!visited[v]) {
                   visited[v] = true;
                   q.push(v);
               }
           }
       }
   }

2. 深度优先搜索 (DFS - Depth-First Search)：

   • 描述： 从起始顶点开始，沿着一条路径尽可能深地访问顶点，直到不能再深入为止，然后回溯到上一个顶点，继续探索其他路径。它使用递归或栈来实现。
   • 应用： 判断图是否有环，拓扑排序，查找连通分量，解决迷宫问题等。
   • 思路：
     1. 从起始顶点 u 开始访问。
     2. 标记 u 为已访问。
     3. 递归地对 u 的所有未访问邻居 v 进行DFS。

   // 伪代码
   #include <vector>
   #include <list>
   
   void DFSUtil(int u, std::vector<bool>& visited, const std::vector<std::list<int>>& adj) {
       visited[u] = true;
       // 访问节点 u
       // std::cout << u << " ";
   
       for (int v : adj[u]) {
           if (!visited[v]) {
               DFSUtil(v, visited, adj);
           }
       }
   }
   
   void DFS(int startNode, int numVertices, const std::vector<std::list<int>>& adj) {
       std::vector<bool> visited(numVertices, false);
       DFSUtil(startNode, visited, adj);
   }

3. Dijkstra 算法 (Dijkstra's Algorithm)：

   • 描述： 用于在带非负权重的图中查找从单个源点到所有其他顶点的最短路径。它使用优先队列来高效地选择下一个要处理的顶点。
   • 应用： 导航系统中的最短路径，网络路由协议等。
   • 思路：
     1. 初始化所有顶点的距离为无穷大，源点距离为0。
     2. 使用优先队列存储 (距离, 顶点) 对，按距离从小到大排序。
     3. 从优先队列中取出距离最小的顶点 u。
     4. 对于 u 的每个邻居 v，如果通过 u 到 v 的路径更短，则更新 v 的距离并将其加入优先队列。

   // 伪代码
   #include <queue>
   #include <vector>
   #include <limits>
   
   const int INF = std::numeric_limits<int>::max();
   
   void dijkstra(int startNode, int numVertices, const std::vector<std::list<std::pair<int, int>>>& adj) {
       std::vector<int> dist(numVertices, INF);
       // 优先队列存储 {distance, vertex}，按distance升序排列
       std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
   
       dist[startNode] = 0;
       pq.push({0, startNode});
   
       while (!pq.empty()) {
           int d = pq.top().first;
           int u = pq.top().second;
           pq.pop();
   
           // 如果已经处理过，跳过
           if (d > dist[u]) {
               continue;
           }
   
           // 遍历所有邻居
           for (auto& edge : adj[u]) {
               int v = edge.first;
               int weight = edge.second;
   
               // 如果找到更短路径
               if (dist[u] + weight < dist[v]) {
                   dist[v] = dist[u] + weight;
                   pq.push({dist[v], v});
               }
           }
       }
       // dist 数组中存储了从 startNode 到所有其他节点的最短距离
   }

4. Prim 算法 (Prim's Algorithm) 和 Kruskal 算法 (Kruskal's Algorithm)：

   • 描述： 两种经典的最小生成树（Minimum Spanning Tree, MST）算法。MST 是连接图中所有顶点，且总边权和最小的树。
   • 应用： 城市规划、网络设计、电路板布线等。
   • Prim 算法思路： 从一个起始顶点开始，逐步添加边，每次选择连接已加入MST的顶点和未加入MST的顶点之间权值最小的边，直到所有顶点都被包含。
   • Kruskal 算法思路： 将所有边按权值从小到大排序，然后依次选择边，如果选择这条边不会形成环，则将其加入MST，直到MST包含 V-1 条边。

   // 伪代码：Prim 算法 (使用优先队列)
   #include <queue>
   #include <vector>
   #include <limits>
   
   const int INF = std::numeric_limits<int>::max();
   
   void primMST(int startNode, int numVertices, const std::vector<std::list<std::pair<int, int>>>& adj) {
       std::vector<int> key(numVertices, INF); // 存储连接到MST的最小权重
       std::vector<bool> inMST(numVertices, false); // 标记是否已在MST中
       std::vector<int> parent(numVertices, -1); // 存储MST中的父节点
   
       // 优先队列存储 {weight, vertex}，按weight升序排列
       std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
   
       key[startNode] = 0;
       pq.push({0, startNode});
   
       while (!pq.empty()) {
           int u = pq.top().second;
           pq.pop();
   
           if (inMST[u]) continue;
           inMST[u] = true;
   
           for (auto& edge : adj[u]) {
               int v = edge.first;
               int weight = edge.second;
   
               if (!inMST[v] && weight < key[v]) {
                   key[v] = weight;
                   parent[v] = u;
                   pq.push({key[v], v});
               }
           }
       }
       // parent 数组存储了MST的结构
   }
   
   // 伪代码：Kruskal 算法 (使用并查集)
   #include <algorithm>
   #include <vector>
   
   struct Edge {
       int u, v, weight;
       bool operator<(const Edge& other) const {
           return weight < other.weight;
       }
   };
   
   // 并查集 (Union-Find) 结构
   std::vector<int> parent; // 存储父节点
   std::vector<int> ranks;  // 存储树的高度或大小
   
   void makeSet(int n) {
       parent.resize(n);
       ranks.resize(n, 0);
       for (int i = 0; i < n; ++i) {
           parent[i] = i;
       }
   }
   
   int findSet(int i) {
       if (parent[i] == i) {
           return i;
       }
       return parent[i] = findSet(parent[i]); // 路径压缩
   }
   
   void unionSets(int i, int j) {
       int root_i = findSet(i);
       int root_j = findSet(j);
       if (root_i != root_j) {
           // 按秩合并
           if (ranks[root_i] < ranks[root_j]) {
               std::swap(root_i, root_j);
           }
           parent[root_j] = root_i;
           if (ranks[root_i] == ranks[root_j]) {
               ranks[root_i]++;
           }
       }
   }
   
   void kruskalMST(int numVertices, std::vector<Edge>& edges) {
       std::sort(edges.begin(), edges.end()); // 按权重排序
       makeSet(numVertices);
   
       std::vector<Edge> resultMST;
       int mstWeight = 0;
   
       for (const auto& edge : edges) {
           if (findSet(edge.u) != findSet(edge.v)) {
               resultMST.push_back(edge);
               mstWeight += edge.weight;
               unionSets(edge.u, edge.v);
           }
       }
       // resultMST 存储了MST的边
   }

12. 排序算法的稳定性

问题描述： 解释排序算法的稳定性概念，并列举哪些常见排序算法是稳定的，哪些是不稳定的。

实现方法与代码思路：

排序算法的稳定性：

稳定性是指，如果数组中有两个或多个元素的值相等，并且在排序前它们有特定的相对顺序，那么在排序后，这些相等元素的相对顺序保持不变，则称该排序算法是稳定的。如果相等元素的相对顺序可能发生改变，则称该排序算法是不稳定的。

举例说明：

假设有一个数组 [(5, A), (2, B), (5, C)]，其中数字是排序的键，字母是附加信息。如果排序后得到 [(2, B), (5, A), (5, C)]，那么这个排序算法是稳定的，因为两个 5 的相对顺序 A 在 C 之前保持不变。如果得到 [(2, B), (5, C), (5, A)]，那么这个排序算法就是不稳定的。

常见排序算法的稳定性：

排序算法	稳定性	备注
冒泡排序	稳定	只有相邻元素交换，相等元素不会改变相对顺序。
插入排序	稳定	只有当前元素与前面元素比较，相等元素不会改变相对顺序。
归并排序	稳定	合并过程中，如果左右子数组的元素相等，优先取左边元素，保持相对顺序。
计数排序	稳定	通过统计频率和从后向前遍历，可以保持稳定性。
基数排序	稳定	依赖于子排序算法的稳定性，通常使用计数排序作为子排序，因此是稳定的。

排序算法	稳定性	备注
选择排序	不稳定	每次选择最小（或最大）元素与当前位置元素交换，可能改变相等元素的相对顺序。
快速排序	不稳定	分区过程中，基准元素的放置可能改变相等元素的相对顺序。
堆排序	不稳定	堆的调整过程可能改变相等元素的相对顺序。
希尔排序	不稳定	跨距离交换元素，可能改变相等元素的相对顺序。

为什么关注稳定性？

在某些应用场景中，稳定性非常重要。例如，当数据记录包含多个字段，并且需要根据一个字段排序，然后在此基础上再根据另一个字段排序时，如果第一次排序的算法不稳定，可能会破坏之前排序的相对顺序，导致最终结果不符合预期。例如，先按姓名排序，再按年龄排序，如果姓名相同，希望保持原有的年龄顺序，就需要稳定的排序算法。

13. 二叉树前序遍历非递归

问题描述： 实现二叉树的前序遍历（根-左-右），但不能使用递归，而要使用迭代方式。

实现方法与代码思路：

二叉树的非递归遍历通常需要借助栈（Stack）来实现。前序遍历的顺序是“根-左-右”。

核心思路：

1. 创建一个栈，并将根节点压入栈中。
2. 当栈不为空时，执行以下操作：
   • 弹出栈顶节点 node。
   • 访问 node（即处理根节点）。
   • 先将 node 的右子节点压入栈中（如果存在）。
   • 再将 node 的左子节点压入栈中（如果存在）。
   • （注意：先压右子节点再压左子节点，是为了保证弹出时先处理左子节点，符合“左-右”的顺序）

// 伪代码
#include <stack>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    std::stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();

        result.push_back(node->val); // 访问根节点

        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
    return result;
}

14. 二叉树输出每一层最右边的节点

问题描述： 给定一棵二叉树，输出每一层最右边的节点的值。

实现方法与代码思路：

这个问题可以通过广度优先搜索（BFS）或深度优先搜索（DFS）来解决。

方法一：广度优先搜索 (BFS)

核心思想： BFS 逐层遍历二叉树。在遍历每一层时，最后一个被访问的节点就是该层最右边的节点。

步骤：

1. 使用一个队列进行BFS。
2. 将根节点加入队列。
3. 当队列不为空时，处理当前层的所有节点：
   • 获取当前层的节点数量 level_size。
   • 循环 level_size 次，每次从队列中取出一个节点。
   • 如果这是当前层的最后一个节点（即循环的第 level_size 次），则其值就是该层最右边的节点值，将其添加到结果列表中。
   • 将当前节点的左子节点和右子节点（如果存在）加入队列。

// 伪代码
#include <queue>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> rightSideViewBFS(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int level_size = q.size();
        for (int i = 0; i < level_size; ++i) {
            TreeNode* node = q.front();
            q.pop();

            // 如果是当前层的最后一个节点，则它是最右边的节点
            if (i == level_size - 1) {
                result.push_back(node->val);
            }

            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
    }
    return result;
}

方法二：深度优先搜索 (DFS)

核心思想： DFS 遍历二叉树，优先遍历右子树。在遍历过程中，维护一个记录当前层数的变量。对于每一层，只记录第一次访问到的节点（因为优先遍历右子树，所以第一次访问到的就是最右边的节点）。

步骤：

1. 定义一个递归函数 dfs(node, level, result)。
2. 在函数中，如果 node 为空，则返回。
3. 如果 level 等于 result.size()（表示第一次访问到这一层），则将 node->val 添加到 result 中。
4. 递归调用 dfs(node->right, level + 1, result)。
5. 递归调用 dfs(node->left, level + 1, result)。

// 伪代码
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void dfsRightSideView(TreeNode* node, int level, std::vector<int>& result) {
    if (node == nullptr) {
        return;
    }

    // 如果当前层是第一次访问，则该节点是最右边的节点
    if (level == result.size()) {
        result.push_back(node->val);
    }

    // 优先遍历右子树
    dfsRightSideView(node->right, level + 1, result);
    dfsRightSideView(node->left, level + 1, result);
}

std::vector<int> rightSideViewDFS(TreeNode* root) {
    std::vector<int> result;
    dfsRightSideView(root, 0, result);
    return result;
}

15. Hash表rehash的代价和处理

问题描述： 当哈希表中的数据量很大，达到一定阈值时，需要进行rehash（扩容），rehash的代价很高，如何处理？

实现方法与代码思路：

当哈希表中的元素数量达到一定程度（通常是装载因子 Load Factor 超过某个阈值，例如0.7或0.75）时，为了保持哈希表的性能（减少冲突，提高查找效率），需要进行扩容，这个过程称为rehash。Rehash的代价确实很高，因为它涉及到创建一个更大的新哈希表，并将旧表中所有元素重新计算哈希值并插入到新表中。

Rehash的代价：

• 时间复杂度： O(N)，其中N是哈希表中元素的数量。因为每个元素都需要重新哈希和插入。
• 空间复杂度： 临时需要 O(N) 的额外空间来存储新旧两个哈希表。
• 阻塞： 在单线程环境中，rehash过程会阻塞所有对哈希表的读写操作，导致服务暂停或响应延迟。

处理Rehash高代价的方法：

主要策略是避免一次性完成所有rehash操作，而是将其分散到多次操作中，或者采用更智能的扩容机制。

1. 渐进式Rehash (Incremental Rehashing)：

   • 核心思想： 不一次性完成所有元素的迁移，而是将rehash过程分解为多个小步骤，每次只迁移少量元素。在rehash期间，哈希表会同时维护新旧两个表。
   • 实现：
     1. 当需要rehash时，创建一个新的、更大的哈希表，但此时不立即迁移所有旧表中的元素。
     2. 在每次对哈希表进行插入、删除或查找操作时，除了执行正常的操作外，还从旧表中迁移一小部分元素到新表。
     3. 当所有旧表中的元素都迁移到新表后，旧表就可以被销毁了。
   • 优点： 避免了长时间的阻塞，将rehash的开销分摊到多次操作中，对用户体验影响小。
   • 缺点： 实现复杂度增加；在rehash期间，查询可能需要同时查询新旧两个表，稍微增加查询时间。
   • 应用： Redis的哈希表就是采用渐进式rehash。

   // 伪代码：渐进式Rehash概念
   class IncrementalHashTable {
   private:
       HashTable* oldTable; // 旧表
       HashTable* newTable; // 新表
       int rehashIndex;     // 记录rehash进度
       bool rehashing;      // 是否正在rehash
   
   public:
       void insert(Key k, Value v) {
           if (rehashing) {
               // 同时插入新旧表
               newTable->insert(k, v);
               oldTable->insert(k, v);
               // 每次操作迁移少量元素
               migrateOneStep();
           } else {
               oldTable->insert(k, v);
               if (oldTable->loadFactor() > THRESHOLD) {
                   startRehash();
               }
           }
       }
   
       Value* find(Key k) {
           if (rehashing) {
               Value* val = newTable->find(k);
               if (val != nullptr) return val;
               val = oldTable->find(k);
               // 每次操作迁移少量元素
               migrateOneStep();
               return val;
           } else {
               return oldTable->find(k);
           }
       }
   
   private:
       void startRehash() {
           rehashing = true;
           newTable = new HashTable(oldTable->size() * 2); // 新表通常是旧表两倍大小
           rehashIndex = 0;
       }
   
       void migrateOneStep() {
           // 迁移 oldTable[rehashIndex] 桶中的所有元素到 newTable
           // ...
           rehashIndex++;
           if (rehashIndex >= oldTable->size()) {
               // 迁移完成
               delete oldTable;
               oldTable = newTable;
               newTable = nullptr;
               rehashing = false;
           }
       }
   };

2. 写时复制 (Copy-on-Write, COW)：

   • 核心思想： 在rehash期间，不立即复制整个哈希表。当需要修改哈希表时，才复制被修改的部分。这通常用于多线程或多进程环境。
   • 实现： 当触发rehash时，创建一个新的哈希表，但旧表仍然存在并可读。所有新的写操作都写入新表。旧表中的数据只有在被修改时才会被复制到新表。读操作可以同时在新旧表上进行。
   • 优点： 读操作不会被阻塞；减少了初始的复制开销。
   • 缺点： 实现复杂；需要额外的机制来同步新旧表的数据。

3. 预分配和懒惰扩容：

   • 核心思想： 在创建哈希表时，预先分配一个较大的初始容量，以减少早期扩容的频率。当需要扩容时，可以采用懒惰策略，即只在真正需要时才进行扩容，或者在系统负载较低时进行。
   • 优点： 减少了rehash的次数；可以在非高峰期进行扩容。
   • 缺点： 可能浪费一些内存空间。

4. 分片 (Sharding) 或分布式哈希表 (Distributed Hash Table, DHT)：

   • 核心思想： 将一个大的哈希表分成多个小的哈希表，分布在不同的服务器或节点上。当需要扩容时，可以只扩容其中一部分，或者增加新的节点来分担负载。
   • 优点： 极大地提高了可伸缩性，避免了单点rehash的瓶颈。
   • 缺点： 增加了系统架构的复杂性，需要考虑数据一致性、网络延迟等问题。

在实际应用中，通常会结合多种策略来优化哈希表的rehash性能，例如在Redis中，就结合了渐进式rehash和惰性删除等机制。

16. 链地址法和再哈希法之间的关联和区别，两者分别适用场景，两者底层的数据结构，关联和区别

问题描述： 详细比较哈希冲突解决策略中的链地址法和再哈希法，包括它们的关联、区别、底层数据结构以及各自的适用场景。

实现方法与代码思路：

链地址法（Separate Chaining）和开放定址法（Open Addressing，其中再哈希法是其一种探测序列）是解决哈希冲突的两种主要策略。它们在处理冲突、内存布局和性能特性上存在显著差异。

1. 链地址法 (Separate Chaining)

• 核心思想： 当多个键哈希到同一个槽位时，将这些键值对存储在该槽位关联的一个链表（或其他动态数据结构，如红黑树）中。哈希表的每个槽位存储的是一个指向链表头部的指针。
• 底层数据结构： 哈希表本身是一个数组（或 vector），数组的每个元素是一个链表（std::list 或 std::forward_list），也可以是其他数据结构如红黑树（例如 std::unordered_map 在某些实现中当链表过长时会转换为红黑树）。
• 冲突处理： 简单地将新元素添加到链表的末尾或头部。
• 优点：
  • 实现相对简单。
  • 对装载因子不敏感： 即使装载因子大于1，哈希表也能正常工作（尽管性能会下降）。
  • 删除操作简单： 直接从链表中删除节点即可。
  • 可以存储任意数量的元素： 链表可以动态增长。
  • 不易发生聚集： 冲突的元素只影响到对应的链表，不会影响到其他槽位。
• 缺点：
  • 空间开销： 每个节点需要额外的指针空间。
  • 缓存不友好： 链表节点在内存中可能不连续，导致CPU缓存命中率低，遍历链表时性能可能下降。
  • 需要动态内存分配： 频繁的 new/delete 操作可能带来性能开销和内存碎片。
• 适用场景：
  • 对内存使用不是极其敏感，但需要高效的插入和删除操作。
  • 元素数量可能动态变化，且装载因子可能较高。
  • 例如，std::unordered_map 和 std::unordered_set 的默认实现通常采用链地址法。

2. 开放定址法 (Open Addressing)

• 核心思想： 当发生哈希冲突时，不使用额外的链表，而是在哈希表（一个大的数组）中寻找下一个可用的空槽位来存储冲突的元素。这需要一个“探测序列”来决定下一个尝试的地址。
• 底层数据结构： 一个单一的数组（或 vector），直接存储键值对。通常还需要一个辅助数组或特殊值来标记槽位的状态（空、已占用、已删除）。
• 冲突处理： 按照探测序列查找下一个空槽位。
• 常见的探测序列：
  • 线性探测 (Linear Probing)： (hash(key) + i) % tableSize
  • 二次探测 (Quadratic Probing)： (hash(key) + i*i) % tableSize
  • 双重哈希 (Double Hashing)： (hash1(key) + i * hash2(key)) % tableSize (再哈希法就是双重哈希的一种)
• 优点：
  • 缓存友好： 元素存储在连续内存中，CPU缓存命中率高。
  • 空间效率高： 不需要额外的指针空间。
  • 避免动态内存分配： 减少了 new/delete 的开销。
• 缺点：
  • 容易发生聚集 (Clustering)： 线性探测容易形成“块”，导致后续冲突的元素需要更长的探测序列。
  • 删除操作复杂： 简单地删除元素会破坏查找链，需要使用“惰性删除”或特殊标记。
  • 对装载因子敏感： 当装载因子接近1时，性能会急剧下降，必须进行rehash。
  • 容量固定： 必须预先确定最大容量，或者在达到阈值时进行rehash。
• 适用场景：
  • 对内存使用非常敏感，追求极致空间效率。
  • 元素数量相对固定，或者可以接受频繁rehash的开销。
  • 对缓存命中率有较高要求。
  • 例如，某些嵌入式系统、高性能缓存、或需要避免动态内存分配的场景。

再哈希法 (Double Hashing) 作为开放定址法的一种：

再哈希法是开放定址法中一种更高级的探测序列策略。它使用两个哈希函数 hash1(key) 和 hash2(key)。当 hash1(key) 发生冲突时，探测序列由 (hash1(key) + i * hash2(key)) % tableSize 决定。hash2(key) 必须保证不返回0，且与 tableSize 互质，以确保能探测到所有槽位。

• 关联： 再哈希法是开放定址法的一种具体实现，旨在解决线性探测和二次探测可能导致的聚集问题。
• 区别： 与线性探测和二次探测相比，再哈希法生成的探测序列更加随机，可以有效减少聚集现象，从而提高哈希表的性能。

总结表格：

特性	链地址法 (Separate Chaining)	开放定址法 (Open Addressing)
冲突处理	链表 (或红黑树)	探测序列 (线性、二次、再哈希等)
底层结构	数组 + 链表/红黑树	单一数组
空间开销	额外指针空间	无额外指针空间
缓存友好性	较低	较高
删除操作	简单	复杂 (需惰性删除)
装载因子敏感	不敏感 (可 > 1)	敏感 (需 < 1)
聚集问题	无	有 (线性探测最严重，再哈希法改善)
动态内存分配	频繁	较少 (主要在rehash时)

在选择哈希冲突解决策略时，需要根据具体的应用场景和需求（如内存限制、性能要求、数据量大小、插入/删除频率等）进行权衡。

17. 死锁的概念，进程调度算法怎么解决死锁

问题描述： 解释死锁（Deadlock）的概念，并探讨进程调度算法如何解决死锁问题。

实现方法与代码思路：

死锁 (Deadlock) 概念：

死锁是指在多任务操作系统中，多个进程（或线程）在竞争资源时，因互相等待对方释放资源而造成的一种僵局，若无外力作用，这些进程将永远无法推进。通俗地说，就是“你等我，我等你，大家谁也动不了”。

死锁产生的四个必要条件 (Coffman 条件)：

1. 互斥条件 (Mutual Exclusion)： 至少有一个资源是不能共享的，即一次只能被一个进程占用。如果另一个进程请求该资源，则必须等待，直到该资源被释放。
2. 持有并等待条件 (Hold and Wait)： 一个进程已经持有了至少一个资源，但又请求新的资源，而新的资源被其他进程占用，此时该进程在等待新资源的同时，不释放已持有的资源。
3. 不可剥夺条件 (No Preemption)： 资源只能由持有它的进程自愿释放，不能被其他进程强制剥夺。
4. 循环等待条件 (Circular Wait)： 存在一个进程集合 {P0, P1, ..., Pn}，使得 P0 正在等待 P1 持有的资源，P1 正在等待 P2 持有的资源，...，Pn 正在等待 P0 持有的资源，形成一个环路。

解决死锁的策略：

解决死锁的方法主要有四种：死锁预防、死锁避免、死锁检测和死锁恢复。

1. 死锁预防 (Deadlock Prevention)：

通过破坏死锁产生的四个必要条件中的一个或多个来防止死锁的发生。这是最严格的方法，但可能导致资源利用率低下或系统并发性降低。

• 破坏互斥条件： 很少可行，因为有些资源本质上就是互斥的（如打印机）。
• 破坏持有并等待条件：
  • 一次性请求所有资源： 进程在开始执行前，一次性请求所有它需要的资源。如果不能全部获得，则不持有任何资源并等待。缺点是资源利用率低，可能导致饥饿。
  • 请求新资源时释放已持有资源： 进程在请求新资源时，必须释放所有已持有的资源。缺点是实现复杂，可能导致数据不一致。
• 破坏不可剥夺条件：
  • 如果一个进程请求的资源被拒绝，它必须释放所有已持有的资源。或者，当一个进程请求的资源被另一个进程持有，并且该进程正在等待其他资源时，可以强制剥夺其已持有的资源。缺点是实现复杂，可能导致回滚和开销。
• 破坏循环等待条件：
  • 资源有序分配法： 对所有资源进行编号，进程只能按资源编号递增的顺序请求资源。例如，进程 P1 已经持有资源 Rj，现在要请求资源 Ri，则必须满足 i > j。这可以打破循环等待。

2. 死锁避免 (Deadlock Avoidance)：

在系统运行时动态地检查资源分配状态，以确保系统永远不会进入不安全状态。最著名的算法是 银行家算法 (Banker's Algorithm)。

• 银行家算法：

  • 核心思想： 银行家（操作系统）在分配资源之前，会检查此次分配是否会导致系统进入不安全状态。如果会导致不安全状态，则拒绝分配。它需要预先知道每个进程对资源的最大需求量。
  • 安全状态： 如果系统能够找到一个执行序列，使得所有进程都能顺利完成，则称系统处于安全状态。否则，处于不安全状态。
  • 优点： 比死锁预防更灵活，资源利用率更高。
  • 缺点： 需要预知进程的最大资源需求，实现复杂，运行时开销大。

  // 伪代码：银行家算法核心思想 (简化)
  // Available: 向量，表示每种类型可用资源的数量
  // Max: 矩阵，表示每个进程对每种类型资源的最大需求
  // Allocation: 矩阵，表示每个进程当前已分配的每种类型资源
  // Need: 矩阵，表示每个进程还需要每种类型资源的数量 (Max - Allocation)
  
  bool isSafe(int numProcesses, int numResources, ... /* 上述矩阵和向量 */) {
      // 1. 初始化 Work = Available, Finish[i] = false for all i
      // 2. 找到一个 i，使得 Finish[i] == false 且 Need[i] <= Work
      // 3. 如果找到，Work = Work + Allocation[i], Finish[i] = true, goto 2
      // 4. 如果没找到，检查所有 Finish[i] 是否都为 true
      //    如果都为 true，则安全；否则不安全。
      return true; // 简化，实际实现复杂
  }
  
  bool requestResource(int processId, ... /* 请求资源向量 */) {
      // 1. 检查请求是否合法 (Request <= Need)
      // 2. 检查是否有足够资源 (Request <= Available)
      // 3. 尝试分配 (临时更新 Available, Allocation, Need)
      // 4. 调用 isSafe() 检查是否安全
      // 5. 如果安全，则确认分配；否则回滚分配并拒绝请求。
      return true; // 简化，实际实现复杂
  }

3. 死锁检测 (Deadlock Detection)：

允许系统进入死锁状态，然后通过算法检测死锁是否发生，并提供信息以便进行恢复。

• 资源分配图： 可以用资源分配图来表示进程和资源之间的关系。如果图中存在环，且每个环中的资源都是互斥的，则可能存在死锁。
• 检测算法： 类似于银行家算法的安全状态检测，但不需要预知最大需求，而是基于当前分配情况。
• 优点： 资源利用率高，因为不限制资源请求。
• 缺点： 检测算法本身有开销；一旦检测到死锁，需要进行恢复，恢复的代价可能很高。

4. 死锁恢复 (Deadlock Recovery)：

一旦检测到死锁，需要采取措施解除死锁，使系统恢复正常运行。

• 终止进程：
  • 终止所有死锁进程。
  • 一次终止一个死锁进程，直到死锁解除。选择终止的进程通常基于优先级、已运行时间、已占用资源数量等。
• 剥夺资源：
  • 从一个或多个死锁进程中抢占资源，并将这些资源分配给其他死锁进程，直到死锁解除。被剥夺资源的进程可能需要回滚到之前的状态。

在实际系统中，通常会根据系统的特性和对死锁的容忍度，选择合适的死锁处理策略。例如，数据库系统可能更倾向于死锁检测和恢复，而实时系统可能更倾向于死锁预防或避免。

C/C++语言：实现方法和代码思路

1. 智能指针

问题描述： 解释C++智能指针的实现原理、计数器何时改变、智能指针和管理的对象分别在哪个区，以及weak_ptr的使用场景和循环引用问题。

实现方法与代码思路：

智能指针是C++11引入的重要特性，旨在解决传统C++中手动内存管理（new和delete）带来的内存泄漏和野指针问题。它们通过RAII（Resource Acquisition Is Initialization）机制，在对象生命周期结束时自动释放所管理的资源。

1.1 智能指针实现原理

智能指针本质上是封装了原始指针的类模板，并在其析构函数中自动调用 delete 来释放所指向的对象。它们通过重载 * 和 -> 运算符，使其行为类似于原始指针。

• std::unique_ptr： 独占所有权。一个 unique_ptr 只能指向一个对象，且不能被复制，只能被移动。当 unique_ptr 对象被销毁时，它所指向的对象也会被自动释放。

  • 实现思路： 内部包含一个原始指针。拷贝构造函数和赋值运算符被禁用（或标记为 delete），只提供移动构造函数和移动赋值运算符。析构函数中调用 delete。

  // 伪代码：UniquePtr 简化实现
  template<typename T>
  class UniquePtr {
  public:
      explicit UniquePtr(T* ptr = nullptr) : _ptr(ptr) {}
      ~UniquePtr() { delete _ptr; }
  
      // 禁用拷贝构造和拷贝赋值
      UniquePtr(const UniquePtr&) = delete;
      UniquePtr& operator=(const UniquePtr&) = delete;
  
      // 移动构造和移动赋值
      UniquePtr(UniquePtr&& other) noexcept : _ptr(other._ptr) {
          other._ptr = nullptr;
      }
      UniquePtr& operator=(UniquePtr&& other) noexcept {
          if (this != &other) {
              delete _ptr; // 释放当前资源
              _ptr = other._ptr;
              other._ptr = nullptr;
          }
          return *this;
      }
  
      T* operator->() const { return _ptr; }
      T& operator*() const { return *_ptr; }
      T* get() const { return _ptr; }
      explicit operator bool() const { return _ptr != nullptr; }
  
  private:
      T* _ptr;
  };

• std::shared_ptr： 共享所有权。多个 shared_ptr 可以指向同一个对象，通过引用计数（Reference Count）来管理对象的生命周期。当最后一个 shared_ptr 被销毁时，对象才会被释放。

  • 实现思路： 内部包含一个原始指针和一个指向控制块（Control Block）的指针。控制块通常包含引用计数、弱引用计数以及自定义删除器等信息。每次拷贝 shared_ptr，引用计数加1；每次 shared_ptr 被销毁，引用计数减1。当引用计数为0时，释放对象。

  // 伪代码：SharedPtr 简化实现 (不包含弱引用计数和自定义删除器)
  template<typename T>
  class SharedPtr {
  public:
      explicit SharedPtr(T* ptr = nullptr) : _ptr(ptr), _refCount(new int(1)) {}
  
      // 拷贝构造
      SharedPtr(const SharedPtr& other) : _ptr(other._ptr), _refCount(other._refCount) {
          (*_refCount)++;
      }
  
      // 拷贝赋值
      SharedPtr& operator=(const SharedPtr& other) {
          if (this != &other) {
              release(); // 释放当前资源
              _ptr = other._ptr;
              _refCount = other._refCount;
              (*_refCount)++;
          }
          return *this;
      }
  
      ~SharedPtr() { release(); }
  
      T* operator->() const { return _ptr; }
      T& operator*() const { return *_ptr; }
      int use_count() const { return (_refCount ? *_refCount : 0); }
  
  private:
      T* _ptr;
      int* _refCount;
  
      void release() {
          if (_refCount) {
              (*_refCount)--;
              if (*_refCount == 0) {
                  delete _ptr;
                  delete _refCount;
                  _ptr = nullptr;
                  _refCount = nullptr;
              }
          }
      }
  };

• std::weak_ptr： 弱引用。它不拥有所指向的对象，因此不会增加对象的引用计数。主要用于解决 shared_ptr 的循环引用问题。

  • 实现思路： 内部包含一个原始指针和一个指向控制块的指针。它只观察 shared_ptr 所管理的对象，但不影响其生命周期。可以通过 lock() 方法尝试获取一个 shared_ptr，如果对象已被释放，则 lock() 返回空的 shared_ptr。

1.2 智能指针和管理的对象分别在哪个区

• 智能指针本身： 智能指针对象（如 std::unique_ptr<T> p; 或 std::shared_ptr<T> p;）通常声明在栈上。当它们超出作用域时，其析构函数会自动调用。
• 智能指针管理的对象： 智能指针通常管理的是在堆上分配的对象。例如，std::make_unique<MyClass>() 或 std::make_shared<MyClass>() 会在堆上分配 MyClass 对象。
• shared_ptr 的控制块： shared_ptr 的引用计数和弱引用计数等信息存储在堆上的一个单独的“控制块”中。这个控制块通常与对象本身一起通过 std::make_shared 一次性分配，或者在 shared_ptr 从原始指针构造时单独分配。

1.3 weak_ptr 的使用场景和循环引用问题

循环引用问题：

当两个或多个 shared_ptr 相互引用，形成一个环时，就会发生循环引用。在这种情况下，即使外部已经没有 shared_ptr 指向这些对象，它们的引用计数也永远不会变为0，导致内存泄漏。

示例：

class B;

class A {
public:
    std::shared_ptr<B> b_ptr;
    ~A() { std::cout << 


A destructor called


 << "A destructor called" << std::endl; }
};

class B {
public:
    std::shared_ptr<A> a_ptr;
    ~B() { std::cout << "B destructor called" << std::endl; }
};

// main函数中
// { // 作用域开始
//     std::shared_ptr<A> pa(new A());
//     std::shared_ptr<B> pb(new B());
//     pa->b_ptr = pb;
//     pb->a_ptr = pa;
// } // 作用域结束，pa和pb的引用计数不会变为0，导致内存泄漏

在这个例子中，pa 持有 pb 的 shared_ptr，pb 也持有 pa 的 shared_ptr。当它们超出作用域时，pa 和 pb 的引用计数都为1，因此它们的析构函数都不会被调用，导致内存泄漏。

weak_ptr 的使用场景：

weak_ptr 不增加对象的引用计数，因此可以打破 shared_ptr 之间的循环引用。当 shared_ptr 形成循环引用时，将其中一个 shared_ptr 改为 weak_ptr 即可。

解决循环引用：

class B;

class A {
public:
    std::shared_ptr<B> b_ptr;
    ~A() { std::cout << "A destructor called" << std::endl; }
};

class B {
public:
    std::weak_ptr<A> a_ptr; // 将其中一个改为 weak_ptr
    ~B() { std::cout << "B destructor called" << std::endl; }
};

// main函数中
// { // 作用域开始
//     std::shared_ptr<A> pa(new A());
//     std::shared_ptr<B> pb(new B());
//     pa->b_ptr = pb;
//     pb->a_ptr = pa; // 这里是 weak_ptr 赋值
// } // 作用域结束，A和B的析构函数都会被调用

在这个修改后的例子中，pb->a_ptr 是一个 weak_ptr，它不增加 A 对象的引用计数。当 pa 超出作用域时，A 对象的引用计数变为0，A 被销毁。A 销毁后，pb 持有的 shared_ptr<B> 的引用计数也变为0，B 被销毁。这样就避免了内存泄漏。

weak_ptr 的其他使用场景：

• 观察者模式： 观察者持有被观察者的 weak_ptr，避免被观察者被观察者自身持有而无法释放。
• 缓存： 缓存中存储对象的 weak_ptr，当对象在其他地方不再被引用时，缓存中的 weak_ptr 会失效，从而自动从缓存中移除。

2. 多态、虚函数与虚表

问题描述： 解释C++中多态的原理、虚函数的实现机制、虚表何时建立，以及为什么析构函数要设置为虚函数。

实现方法与代码思路：

2.1 多态 (Polymorphism)

多态是面向对象编程的三大特性之一（封装、继承、多态）。它允许我们使用一个基类指针或引用来操作派生类对象，从而实现“一个接口，多种形态”的效果。

• 静态多态 (编译时多态)： 通过函数重载和运算符重载实现。在编译时根据函数签名（函数名、参数列表）确定调用哪个函数。
• 动态多态 (运行时多态)： 通过虚函数（virtual 关键字）和基类指针/引用实现。在运行时根据实际指向的对象类型来决定调用哪个函数。

2.2 虚函数 (Virtual Function) 实现机制

虚函数是实现C++动态多态的关键。当一个类中声明了虚函数，并且通过基类指针或引用调用该虚函数时，会根据实际指向的派生类对象来调用相应的函数。

实现原理：

1. 虚函数表 (Virtual Table, vtable)： 编译器为每个包含虚函数的类生成一个虚函数表。这个表是一个函数指针数组，其中存储了该类中所有虚函数的地址。
2. 虚函数表指针 (Virtual Table Pointer, vptr)： 每个包含虚函数的类的对象都会在其实例的内存布局中包含一个虚函数表指针（vptr）。这个 vptr 指向该对象所属类的虚函数表。

调用过程：

当通过基类指针或引用调用虚函数时，编译器会生成代码，通过 vptr 找到对应的 vtable，然后根据虚函数在 vtable 中的偏移量找到实际要调用的函数地址，最后执行该函数。

// 伪代码：虚函数实现示意
class Base {
public:
    virtual void func1() { /* Base implementation */ }
    virtual void func2() { /* Base implementation */ }
    // ...
};

class Derived : public Base {
public:
    void func1() override { /* Derived implementation */ } // 覆盖基类的虚函数
    // ...
};

// 内存布局示意 (简化)
// Base对象:
// | vptr |
// | data members |

// Derived对象:
// | vptr |
// | Base data members |
// | Derived data members |

// vtable for Base:
// | &Base::func1 |
// | &Base::func2 |

// vtable for Derived:
// | &Derived::func1 |
// | &Base::func2   | // 如果Derived没有覆盖func2，则指向Base的实现

2.3 虚表何时建立

虚函数表（vtable）是在编译时由编译器生成的。它是一个静态的、只读的数据结构，存储在程序的只读数据段（.rodata 或 .rdata）中。

而虚函数表指针（vptr）是在运行时，当对象被创建时，由构造函数进行初始化。构造函数会将对象的 vptr 指向其所属类的 vtable。

2.4 为什么要把析构函数设置成虚函数？

当通过基类指针 delete 一个派生类对象时，如果基类的析构函数不是虚函数，那么只会调用基类的析构函数，而不会调用派生类的析构函数。这会导致派生类中动态分配的资源无法被正确释放，从而造成内存泄漏。

将基类的析构函数声明为 virtual，可以确保在通过基类指针 delete 派生类对象时，能够正确地调用到派生类的析构函数，然后依次调用基类的析构函数，从而完整地释放所有资源。

class Base {
public:
    Base() { std::cout << "Base constructor" << std::endl; }
    // 如果没有 virtual，delete pBase 只会调用 Base::~Base()
    virtual ~Base() { std::cout << "Base destructor" << std::endl; }
};

class Derived : public Base {
public:
    int* data;
    Derived() : data(new int[10]) { std::cout << "Derived constructor" << std::endl; }
    ~Derived() {
        delete[] data;
        std::cout << "Derived destructor" << std::endl;
    }
};

// main函数中
// Base* pBase = new Derived();
// delete pBase; // 如果Base的析构函数不是虚函数，只会调用Base::~Base()，导致Derived::data内存泄漏

总结： 只有当一个类可能被用作基类，并且通过基类指针或引用来删除派生类对象时，才需要将基类的析构函数声明为虚函数。如果一个类不作为基类使用，或者不通过基类指针/引用删除对象，则没有必要将其析构函数声明为虚函数，因为这会增加对象的大小（多一个 vptr）和一些运行时开销。

3. map 和 unordered_map 的区别和使用场景

问题描述： 比较C++标准库中的 std::map 和 std::unordered_map，解释它们的底层实现、性能特点、线程安全性以及各自的适用场景。

实现方法与代码思路：

std::map 和 std::unordered_map 都是C++标准库提供的关联容器，用于存储键值对。它们的主要区别在于底层实现和性能特性。

3.1 std::map

• 底层实现： 通常基于红黑树 (Red-Black Tree) 实现。红黑树是一种自平衡二叉查找树，它能保证在最坏情况下的查找、插入和删除操作的时间复杂度为 O(log N)。
• 特点：
  • 有序性： 元素按照键的严格弱序排列（默认升序）。这意味着遍历 map 时，元素是按键有序的。
  • 查找、插入、删除： 平均和最坏时间复杂度都是 O(log N)。
  • 内存占用： 每个节点需要存储键、值、颜色信息以及左右子节点和父节点的指针，因此内存开销相对较大。
  • 缓存友好性： 由于节点在内存中可能不连续，缓存命中率相对较低。
• 线程安全性： std::map 本身不是线程安全的。在多线程环境下对 map 进行读写操作需要加锁保护。
• 适用场景：
  • 需要保持键的有序性，例如需要按键范围查找或遍历。
  • 对性能的稳定性有较高要求，即使在最坏情况下也能保证 O(log N) 的性能。
  • 内存不是极其敏感的场景。

3.2 std::unordered_map

• 底层实现： 通常基于哈希表 (Hash Table) 实现。它使用哈希函数将键映射到桶（bucket）中，并通过链地址法（或开放定址法）解决哈希冲突。
• 特点：
  • 无序性： 元素存储的顺序与键的哈希值有关，不保证任何特定顺序。
  • 查找、插入、删除： 平均时间复杂度为 O(1)。最坏情况下（所有键哈希到同一个桶，或哈希冲突严重）可能退化到 O(N)。
  • 内存占用： 除了存储键值对，还需要存储哈希桶的数组和链表指针。当哈希冲突较多时，链表会变长，内存开销也会增加。
  • 缓存友好性： 相比 map，由于哈希桶中的元素可能在内存中连续，或者在同一个缓存行中，因此在某些情况下缓存命中率可能更高。
• 线程安全性： std::unordered_map 本身也不是线程安全的。在多线程环境下对 unordered_map 进行读写操作需要加锁保护。
• 适用场景：
  • 不需要保持键的有序性，只关心快速查找、插入和删除。
  • 对平均性能有较高要求，可以接受偶尔的最坏情况性能下降。
  • 键的哈希函数设计合理，能够均匀分布。
  • 例如，实现字典、计数器、快速查找表等。

3.3 总结表格：

特性	std::map	std::unordered_map
底层实现	红黑树 (Red-Black Tree)	哈希表 (Hash Table)
有序性	键有序	键无序
查找/插入/删除	O(log N) (平均和最坏)	O(1) (平均)，O(N) (最坏)
内存占用	相对较大 (节点额外信息)	相对较小 (但哈希冲突多时可能增加)
缓存友好性	较低	较高 (取决于哈希函数和冲突解决策略)
线程安全	否	否
适用场景	需要有序遍历、范围查找；对性能稳定性要求高	需要快速查找、插入、删除；对平均性能要求高

关于线程安全：

无论是 std::map 还是 std::unordered_map，它们都不是线程安全的。这意味着在多线程环境下，如果多个线程同时对同一个容器进行修改（插入、删除、修改元素），或者一个线程修改而另一个线程读取，都可能导致数据竞争和未定义行为。为了在多线程中使用这些容器，需要使用互斥锁（std::mutex）或其他同步机制来保护对容器的访问。

4. size_of 和 strlen 的区别

问题描述： 解释C++中 sizeof 运算符和 strlen 函数的区别。

实现方法与代码思路：

sizeof 是一个运算符，而 strlen 是一个函数。它们用于不同的目的，并且在编译时和运行时执行。

4.1 sizeof 运算符

• 定义： sizeof 是C++中的一个运算符，用于获取类型或变量在内存中所占的字节数。
• 执行时机： 通常在编译时计算。这意味着编译器在编译代码时就会确定 sizeof 的结果，而不是在程序运行时。
• 操作对象： 可以是类型（如 sizeof(int)）或变量（如 sizeof(arr)）。
• 对数组： 对于数组，sizeof 返回整个数组所占的字节数（数组长度 * 元素大小）。
• 对指针： 对于指针，sizeof 返回指针本身所占的字节数（通常是4或8字节，取决于系统架构），而不是指针所指向的数据的大小。
• 对字符串字面量： 对于字符串字面量（如 `

"hello"），sizeof返回字符串的长度加上终止符\0` 的大小。

// 伪代码
int arr[10];
std::cout << sizeof(arr); // 输出 40 (假设int占4字节)

int* ptr = arr;
std::cout << sizeof(ptr); // 输出 4 或 8 (指针大小)

char str_literal[] = "hello";
std::cout << sizeof(str_literal); // 输出 6 (h,e,l,l,o,\0)

char* p_str = "world";
std::cout << sizeof(p_str); // 输出 4 或 8 (指针大小)

4.2 strlen 函数

• 定义： strlen 是C标准库 <cstring>（C++中是 <string.h>）中的一个函数，用于计算以空字符 \0 结尾的字符串的长度（不包括 \0）。
• 执行时机： 在运行时计算。
• 操作对象： 接受一个 char* 类型的参数，即一个指向C风格字符串的指针。
• 工作原理： 从给定的内存地址开始，逐字节地向后查找，直到遇到第一个空字符 \0 为止，返回期间遍历的字节数。
• 注意事项： 如果传入的指针没有以 \0 结尾，strlen 会继续向后查找，可能导致访问非法内存，引发程序崩溃。

// 伪代码
#include <cstring> // 或 <string.h>
#include <iostream>

char str_arr[] = "hello";
std::cout << strlen(str_arr); // 输出 5

char* p_str = "world";
std::cout << strlen(p_str); // 输出 5

char no_null_str[5] = {'a', 'b', 'c', 'd', 'e'};
// std::cout << strlen(no_null_str); // 危险！可能导致崩溃

4.3 区别总结：

特性	sizeof	strlen
类型	运算符	函数
执行时机	编译时 (大部分情况)	运行时
功能	计算类型或变量在内存中占用的字节数	计算C风格字符串的实际长度 (不含\0)
参数	类型或变量	char* (指向C风格字符串的指针)
对数组	返回整个数组的大小	无法直接用于数组名，需要传入指向字符串的指针
对指针	返回指针变量本身的大小	返回指针所指向的字符串的长度
是否包含\0	包含 (对于字符串字面量和字符数组)	不包含

5. 函数重载的机制和确定时机

问题描述： 解释C++中函数重载的机制，以及重载是在编译期还是在运行期确定。

实现方法与代码思路：

5.1 函数重载 (Function Overloading)

函数重载是指在同一个作用域内，可以定义多个名称相同但参数列表（参数类型、参数个数、参数顺序）不同的函数。编译器会根据调用时提供的参数类型和数量来选择匹配的函数。

示例：

void print(int i) {
    std::cout << "Printing int: " << i << std::endl;
}

void print(double d) {
    std::cout << "Printing double: " << d << std::endl;
}

void print(std::string s) {
    std::cout << "Printing string: " << s << std::endl;
}

// main函数中
// print(10);       // 调用 print(int)
// print(3.14);     // 调用 print(double)
// print("hello");  // 调用 print(std::string)

5.2 重载的确定时机：编译期

函数重载是在编译期确定的。这个过程被称为函数签名匹配或重载决议 (Overload Resolution)。

机制：

1. 名称修饰 (Name Mangling/Decoration)： 编译器在编译时，会将重载函数的名称进行修饰（或称“名称改编”），将函数的参数类型、返回类型、所属类等信息编码到函数名中，生成一个独一无二的内部名称。例如，print(int) 可能被修饰为 _Z5printi，print(double) 可能被修饰为 _Z5printd。
2. 链接： 在链接阶段，链接器会根据这些修饰后的名称来查找对应的函数定义。
3. 调用匹配： 当程序调用一个重载函数时，编译器会根据调用时提供的实参类型，在所有同名重载函数中查找最佳匹配的函数签名。如果找到唯一最佳匹配，则生成调用该函数的代码；如果没有找到匹配，或者找到多个同样好的匹配（二义性），则会产生编译错误。

总结： 编译器在编译阶段就已经确定了具体调用哪个重载函数，因此函数重载是静态多态（编译时多态）的一种体现。

6. 指针常量和常量指针

问题描述： 解释C++中指针常量和常量指针的区别。

实现方法与代码思路：

指针常量和常量指针是C++中关于 const 关键字修饰指针的两种不同方式，它们在语义和使用上有着本质的区别。

6.1 常量指针 (Pointer to Constant)

• 定义： 指针指向的内容是常量，即不能通过该指针修改其指向的值。但是，指针本身可以被修改，使其指向另一个地址。
• 语法： const type* pointer_name; 或 type const* pointer_name;
• 读法： 从右往左读，* 表示指针，const 修饰 type，表示指向 type 类型的常量。

示例：

int value = 10;
int another_value = 20;

const int* ptr_to_const = &value; // 常量指针

// *ptr_to_const = 15; // 错误：不能通过ptr_to_const修改value的值

ptr_to_const = &another_value; // 正确：可以修改ptr_to_const指向另一个地址

6.2 指针常量 (Constant Pointer)

• 定义： 指针本身是常量，即指针一旦初始化后，就不能再指向其他地址。但是，可以通过该指针修改其指向的值（如果指向的值不是常量）。
• 语法： type* const pointer_name;
• 读法： 从右往左读，const 修饰 pointer_name，表示 pointer_name 是一个常量指针。

示例：

int value = 10;
int another_value = 20;

int* const const_ptr = &value; // 指针常量

*const_ptr = 15; // 正确：可以通过const_ptr修改value的值

// const_ptr = &another_value; // 错误：不能修改const_ptr指向另一个地址

6.3 总结表格：

特性	常量指针 (const type* ptr;)	指针常量 (type* const ptr;)
const 修饰	指针指向的内容 (值)	指针本身 (地址)
能否修改指向的值	否	是 (如果指向的不是常量)
能否修改指向的地址	是	否
读法	指向常量的指针	常量指针

6.4 既是常量指针又是指针常量：

可以同时使用 const 修饰指针指向的内容和指针本身。

• 语法： const type* const pointer_name;
• 定义： 指针指向的内容是常量，且指针本身也是常量。既不能通过该指针修改其指向的值，也不能修改指针使其指向其他地址。

示例：

int value = 10;
const int* const const_ptr_to_const = &value; // 既是常量指针又是指针常量

// *const_ptr_to_const = 15; // 错误
// const_ptr_to_const = &another_value; // 错误

理解这两种 const 修饰指针的方式对于编写安全、健壮的C++代码至关重要。

7. vector 的原理和扩容机制

问题描述： 解释C++标准库容器 std::vector 的底层原理和扩容机制。

实现方法与代码思路：

std::vector 是C++标准库中最常用的动态数组，它提供了一种连续存储元素的方式，并且可以根据需要自动调整大小。它的底层原理和扩容机制是理解其性能特性的关键。

7.1 vector 的底层原理

std::vector 的底层实现是一个连续的内存块（通常是动态分配的数组）。这意味着 vector 中的所有元素都存储在内存中的相邻位置。这种连续存储的特性使得 vector 具有以下优点：

• 随机访问： 可以通过索引（[] 运算符或 at() 方法）在 O(1) 时间内访问任何元素，类似于普通数组。
• 缓存友好： 由于元素连续存储，CPU缓存可以更有效地预取数据，提高访问速度。

vector 内部通常维护三个指针（或一个指针和两个大小/容量变量）：

1. _start (或 _begin)： 指向内存块的起始位置。
2. _finish (或 _end)： 指向当前已存储元素的末尾的下一个位置（即 size()）。
3. _end_of_storage (或 _capacity_end)： 指向内存块的末尾的下一个位置（即 capacity()）。

• size()： 当前 vector 中实际存储的元素数量，即 _finish - _start。
• capacity()： vector 当前已分配的内存块可以容纳的元素总数，即 _end_of_storage - _start。

7.2 vector 的扩容机制

当 vector 中已存储的元素数量（size）达到其当前分配的内存容量（capacity）时，如果尝试插入新元素，vector 就必须进行扩容。

扩容步骤：

1. 分配新内存： vector 会分配一块新的、更大的内存空间。通常，新容量是旧容量的1.5倍或2倍（具体策略取决于编译器实现）。这种倍增策略是为了分摊扩容的开销，使得均摊时间复杂度为 O(1)。
2. 复制/移动元素： 将旧内存块中的所有元素复制（或移动）到新的内存块中。对于非POD（Plain Old Data）类型，会调用元素的拷贝构造函数（或移动构造函数）。
3. 释放旧内存： 释放旧的内存块。
4. 更新指针： 更新 _start、_finish 和 _end_of_storage 指针以指向新的内存块。

扩容的代价：

扩容是一个代价较高的操作，因为它涉及到：

• 内存分配： 操作系统调用，可能耗时。
• 元素复制/移动： 如果元素数量很多，复制/移动操作会消耗大量时间。对于复杂对象，还会涉及构造和析构。
• 迭代器失效： 扩容后，所有指向 vector 内部元素的迭代器、指针和引用都会失效，因为元素被移动到了新的内存地址。

为什么采用倍增策略扩容？

如果每次只扩容一个元素所需的空间，那么每次插入都会导致扩容，总时间复杂度将是 O(N^2)。采用倍增策略（例如每次扩容为原来的两倍），虽然单次扩容的代价很高，但这些高代价的操作发生的频率较低。通过均摊分析 (Amortized Analysis)，可以证明 vector 在末尾插入元素的均摊时间复杂度为 O(1)。

优化建议：

• 预留空间： 如果能预估 vector 将要存储的元素数量，可以使用 reserve() 方法预先分配足够的内存空间，从而避免多次扩容，提高性能。
• emplace_back vs push_back： 对于复杂对象，emplace_back 可以直接在 vector 内部构造对象，避免一次额外的拷贝或移动。
• shrink_to_fit()： 如果 vector 的容量远大于实际元素数量，并且不再需要额外的容量，可以使用 shrink_to_fit() 来释放多余的内存，但这个操作不保证一定会减少容量。

8. const 关键字

问题描述： 解释C++中 const 关键字的用法和作用。

实现方法与代码思路：

const 关键字在C++中用于声明常量，表示一个值在初始化后不能被修改。它在不同上下文中的使用方式和含义有所不同，但核心思想都是“只读”或“不可变”。

8.1 修饰变量

• 修饰普通变量： 声明一个常量，其值在初始化后不能被改变。

  const int MAX_VALUE = 100; // MAX_VALUE 是一个常量
  // MAX_VALUE = 200; // 错误：不能修改常量

• 修饰引用： 声明一个常量引用，不能通过该引用修改其引用的对象。但原对象本身如果不是常量，仍然可以通过其他方式修改。

  int a = 10;
  const int& ref_a = a; // ref_a 是一个常量引用
  // ref_a = 20; // 错误：不能通过ref_a修改a
  a = 30; // 正确：a本身不是常量，可以通过a修改

8.2 修饰指针

这在“指针常量和常量指针”部分已详细解释，这里简要回顾：

• 常量指针 (Pointer to Constant)： const type* ptr; 或 type const* ptr;
  • 指针指向的内容是常量，不能通过该指针修改值。
  • 指针本身可以修改，指向其他地址。
• 指针常量 (Constant Pointer)： type* const ptr;
  • 指针本身是常量，一旦初始化不能指向其他地址。
  • 可以通过该指针修改其指向的值（如果指向的不是常量）。
• 既是常量指针又是指针常量： const type* const ptr;
  • 指针指向的内容是常量，且指针本身也是常量。

8.3 修饰函数参数

• 值传递： void func(const int i)
  • 传入的参数 i 在函数内部不能被修改。这主要用于表明函数不会修改传入的值，提高代码可读性。
• 指针传递： void func(const int* ptr)
  • 不能通过 ptr 修改其指向的值。这表示函数不会修改指针所指向的数据。
• 引用传递： void func(const int& ref)
  • 不能通过 ref 修改其引用的对象。这表示函数不会修改引用所绑定的数据。

使用 const 修饰函数参数的优点：

• 安全性： 防止函数意外修改传入的参数。
• 清晰性： 明确告知函数的使用者，该参数在函数内部是只读的。
• 效率： 对于类类型，如果函数参数是 const T&，可以避免不必要的拷贝，同时保证不修改原对象。

8.4 修饰成员函数

• 语法： return_type function_name(parameters) const;
• 作用： 声明一个常量成员函数。常量成员函数不能修改对象的任何非静态成员变量（mutable 关键字修饰的除外），也不能调用该类的非 const 成员函数。
• 目的： 保证当通过 const 对象或 const 引用调用成员函数时，对象的内部状态不会被改变。

class MyClass {
public:
    int value;
    void setValue(int v) { value = v; } // 非const成员函数
    int getValue() const { return value; } // const成员函数
    // void modifyValue() const { value = 10; } // 错误：不能修改非mutable成员
    // void callNonConst() const { setValue(5); } // 错误：不能调用非const成员函数
};

// main函数中
// const MyClass obj;
// obj.getValue(); // 正确：可以调用const成员函数
// obj.setValue(10); // 错误：不能调用非const成员函数

8.5 const 和 mutable

mutable 关键字用于修饰类的非静态成员变量。被 mutable 修饰的成员变量即使在 const 成员函数中也可以被修改。

示例：

class MyClass {
public:
    int value;
    mutable int cache_value; // 即使在const函数中也可以修改

    void doSomething() const {
        // value = 10; // 错误
        cache_value = 20; // 正确：mutable成员可以在const函数中修改
    }
};

8.6 const 和宏定义 (#define) 的区别

• const： 是C++语言的关键字，有类型检查，遵循作用域规则，可以用于修饰变量、函数参数、成员函数等。
• #define： 是预处理器指令，在编译前进行简单的文本替换，没有类型检查，不遵循作用域规则，可能导致一些意想不到的问题。

总结： const 关键字是C++中实现类型安全和代码健壮性的重要工具，它允许程序员明确地表达变量、指针、引用和函数行为的“只读”特性，从而帮助编译器进行更多的检查，减少潜在的错误。在现代C++编程中，应优先使用 const 而不是宏定义来定义常量。

9. 引用和指针的区别

问题描述： 解释C++中引用（Reference）和指针（Pointer）的区别。

实现方法与代码思路：

引用和指针都是C++中用于间接访问对象的机制，但它们在概念、语法和使用上存在显著差异。

9.1 概念和语法

• 指针 (Pointer)：

  • 概念： 指针是一个变量，其值为另一个变量的内存地址。它“指向”内存中的某个位置。
  • 语法： type* pointer_name;
  • 空值： 可以为 nullptr（或 NULL），表示不指向任何对象。
  • 可变性： 指针本身可以被重新赋值，使其指向不同的对象。
  • 间接访问： 需要使用解引用运算符 * 来访问其指向的值。
  • 算术运算： 可以进行指针算术运算（如 ptr++），使其指向相邻的内存位置。

  int x = 10;
  int* ptr = &x; // ptr指向x的地址
  std::cout << *ptr; // 访问x的值
  ptr++; // ptr指向下一个int的地址

• 引用 (Reference)：

  • 概念： 引用是已存在变量的别名。一旦引用被初始化，它就永远绑定到该变量，不能再引用其他变量。引用本身不是一个独立的对象，它不占用额外的内存（通常，编译器会优化掉引用本身的存储，但在某些情况下，如作为类成员，可能需要存储）。
  • 语法： type& reference_name = existing_variable;
  • 空值： 引用不能为 nullptr，必须在声明时初始化，并且必须引用一个有效的对象。
  • 可变性： 引用一旦绑定，就不能改变其绑定的对象。
  • 间接访问： 无需使用解引用运算符，直接使用引用名即可访问其绑定的值，就像直接使用变量名一样。
  • 算术运算： 不能进行引用算术运算。

  int x = 10;
  int& ref = x; // ref是x的别名
  std::cout << ref; // 访问x的值
  ref = 20; // 修改ref就是修改x
  // int y = 30;
  // ref = y; // 错误！这不是重新绑定，而是将y的值赋给x

9.2 区别总结：

特性	指针 (Pointer)	引用 (Reference)
本质	变量，存储地址	别名，不是独立对象
空值	可以为 nullptr	不能为 nullptr，必须引用有效对象
初始化	可以先声明后初始化	必须在声明时初始化
重新绑定	可以重新指向其他对象	一旦绑定，不能改变绑定对象
解引用	需要 * 运算符	不需要，直接使用
算术运算	可以进行指针算术运算	不能进行算术运算
内存占用	占用内存 (存储地址)	通常不占用额外内存 (编译器优化)，但作为类成员可能占用
安全性	存在野指针、空指针风险	相对更安全，没有空引用或野引用

9.3 适用场景：

• 指针：
  • 需要表示“没有对象”的情况（如返回 nullptr）。
  • 需要在函数内部改变指针所指向的地址（如链表操作）。
  • 需要进行指针算术运算（如遍历数组）。
  • 处理动态内存分配（new/delete）。
• 引用：
  • 作为函数参数，避免大对象的拷贝，同时保证不改变原对象（const&）。
  • 作为函数返回值，允许函数返回一个左值，可以被赋值。
  • 实现运算符重载。
  • 作为类成员，实现与另一个对象的强绑定关系。

总结： 引用可以看作是“受限的指针”，它提供了指针的便利性（间接访问），同时消除了指针的一些危险性（空指针、野指针、随意改变指向）。在C++中，如果不需要指针的灵活性（如可变性、空值），通常优先使用引用，因为它更安全、更简洁。

10. C++内存分布

问题描述： 解释C++程序在运行时内存的分布情况，以及不同类型的数据存储在哪个区域。

实现方法与代码思路：

C++程序在运行时，内存通常被划分为几个不同的区域，每个区域有其特定的用途和生命周期。理解内存分布对于避免内存错误（如内存泄漏、栈溢出、野指针）和优化程序性能至关重要。

10.1 内存区域划分

典型的C++程序内存分布通常包括以下几个区域：

1. 代码区 (Text Segment / Code Segment)：

   • 存储内容： 存放CPU执行的机器指令（编译后的可执行代码）。
   • 特性： 只读，共享。只读是为了防止程序意外修改自身代码；共享是为了多进程可以共享同一份代码。
   • 生命周期： 程序的整个运行期间。

2. 数据区 (Data Segment)：

   • 存储内容： 存放已初始化的全局变量、静态变量和常量（字符串字面量通常也在此区域，但有时会单独划分为常量区）。
   • 特性： 可读写。
   • 生命周期： 程序的整个运行期间。

3. BSS区 (Block Started by Symbol Segment)：

   • 存储内容： 存放未初始化的全局变量和静态变量。在程序加载时，系统会自动将这些变量初始化为0。
   • 特性： 可读写。
   • 生命周期： 程序的整个运行期间。
   • 注意： BSS区不占用可执行文件的大小，只在运行时占用内存。

4. 堆区 (Heap Segment)：

   • 存储内容： 存放程序运行时动态分配的内存。通过 new、malloc、calloc 等函数分配的内存都位于堆区。
   • 特性： 可读写，由程序员手动管理（分配和释放）。
   • 生命周期： 从分配开始到程序员手动释放或程序结束。
   • 特点： 空间大，但分配和释放效率相对较低，容易产生内存碎片，需要注意内存泄漏。

5. 栈区 (Stack Segment)：

   • 存储内容： 存放局部变量（非静态）、函数参数、函数返回地址等。由编译器自动分配和释放。
   • 特性： 可读写，自动管理。
   • 生命周期： 随着函数的调用而创建，随着函数的返回而销毁。
   • 特点： 空间小（通常只有几MB），分配和释放效率高，不会产生内存碎片。但如果递归调用过深或局部变量过大，可能导致栈溢出 (Stack Overflow)。

10.2 示例：不同类型数据在内存中的位置

#include <iostream>

// 1. 全局变量 (未初始化，在BSS区)
int g_uninitialized_var;

// 2. 全局变量 (已初始化，在数据区)
int g_initialized_var = 10;

// 3. 静态变量 (无论是否初始化，都在数据区或BSS区)
static int s_static_var_uninitialized;
static int s_static_var_initialized = 20;

// 4. 字符串字面量 (通常在数据区或单独的常量区，只读)
const char* g_str_literal = "Hello World";

void func(int param_a) {
    // 5. 局部变量 (在栈区)
    int local_var = 30;

    // 6. 局部静态变量 (在数据区或BSS区)
    static int local_static_var = 40;

    // 7. 动态分配的内存 (在堆区)
    int* heap_var = new int(50);

    std::cout << "Address of g_uninitialized_var: " << &g_uninitialized_var << std::endl;
    std::cout << "Address of g_initialized_var: " << &g_initialized_var << std::endl;
    std::cout << "Address of s_static_var_uninitialized: " << &s_static_var_uninitialized << std::endl;
    std::cout << "Address of s_static_var_initialized: " << &s_static_var_initialized << std::endl;
    std::cout << "Address of g_str_literal: " << (void*)g_str_literal << std::endl;
    std::cout << "Address of local_var: " << &local_var << std::endl;
    std::cout << "Address of local_static_var: " << &local_static_var << std::endl;
    std::cout << "Address of heap_var (pointer itself): " << &heap_var << std::endl;
    std::cout << "Address of *heap_var (dynamically allocated): " << heap_var << std::endl;

    delete heap_var; // 释放堆内存
}

int main() {
    func(1);
    return 0;
}

运行上述代码，你会发现不同类型的变量地址通常落在不同的内存区域，并且地址的范围会有明显的区分。

10.3 内存管理和常见问题

• 栈溢出 (Stack Overflow)： 当栈区空间不足时发生，通常是由于无限递归或局部变量过大导致。
• 内存泄漏 (Memory Leak)： 在堆区分配的内存没有被及时释放，导致程序可用的内存越来越少。
• 野指针 (Dangling Pointer)： 指针指向的内存已经被释放，但指针本身没有被置空，继续使用会导致未定义行为。
• 重复释放 (Double Free)： 多次释放同一块内存，导致程序崩溃或数据损坏。
• 内存越界 (Buffer Overflow/Underflow)： 访问数组或缓冲区时超出了其合法范围。

理解C++内存分布是编写高效、稳定程序的基石，也是面试中常考的知识点。

11. C++内存管理 (RAII)

问题描述： 解释C++中的内存管理，特别是RAII（Resource Acquisition Is Initialization）机制。

实现方法与代码思路：

C++的内存管理主要涉及堆内存的分配和释放。传统的C风格内存管理（malloc/free）容易出错，而C++引入了 new/delete 运算符，并在此基础上发展出了RAII（Resource Acquisition Is Initialization）这一核心原则，极大地提高了内存管理的安全性。

11.1 传统C风格内存管理 (malloc/free)

• 分配： void* malloc(size_t size)：从堆上分配指定大小的字节，返回 void* 指针。需要手动进行类型转换。
• 释放： void free(void* ptr)：释放 malloc 分配的内存。
• 问题：
  • 手动管理： 容易忘记 free，导致内存泄漏。
  • 类型不安全： 返回 void*，需要强制类型转换，容易出错。
  • 没有构造/析构： malloc 只分配内存，不调用对象的构造函数；free 只释放内存，不调用析构函数。对于类对象，这会导致资源管理不当。

11.2 C++的 new/delete 运算符

• 分配： new Type 或 new Type[N]：
  • 在堆上分配 Type 类型（或 N 个 Type 类型）的内存。
  • 自动调用构造函数来初始化对象。
  • 返回指向新分配对象的类型安全指针。
• 释放： delete ptr 或 delete[] ptr：
  • 自动调用析构函数来清理对象资源。
  • 释放对象占用的内存。
• 优点：
  • 类型安全： 返回正确类型的指针，无需强制转换。
  • 自动调用构造/析构函数： 保证对象的正确初始化和清理。
• 问题： 仍然需要手动配对 new 和 delete，容易忘记 delete 导致内存泄漏，或者重复 delete 导致程序崩溃。

11.3 RAII (Resource Acquisition Is Initialization)

RAII 是C++中一种重要的编程范式，它将资源的生命周期与对象的生命周期绑定。资源在对象构造时获取，在对象析构时自动释放。

• 核心思想： 将资源（如内存、文件句柄、互斥锁、网络连接等）封装在一个类中。当这个类的对象被创建时，资源被获取；当这个对象超出作用域被销毁时（无论是正常退出、异常抛出还是其他原因），其析构函数会自动被调用，从而自动释放资源。
• 优点：
  • 自动资源管理： 极大地减少了内存泄漏和其他资源泄漏的风险。
  • 异常安全： 即使在发生异常时，也能保证资源被正确释放。
  • 代码简洁： 程序员无需手动编写资源释放代码。
• 实现基础： 依赖于C++的栈语义和析构函数自动调用机制。

RAII 的典型应用：

1. 智能指针 (Smart Pointers)：

   • std::unique_ptr：独占所有权，当 unique_ptr 对象销毁时，其管理的内存自动释放。
   • std::shared_ptr：共享所有权，通过引用计数，当最后一个 shared_ptr 对象销毁时，其管理的内存自动释放。
   • std::weak_ptr：配合 shared_ptr 解决循环引用。

2. 文件流： std::fstream、std::ifstream、std::ofstream

   • 文件在对象构造时打开，在对象析构时自动关闭。

   #include <fstream>
   
   void processFile(const std::string& filename) {
       std::ifstream file(filename); // 构造时打开文件
       if (file.is_open()) {
           // 读取文件内容
       }
       // file 对象超出作用域时，析构函数自动关闭文件
   }

3. 互斥锁： std::lock_guard、std::unique_lock

   • 在构造时锁定互斥量，在析构时自动解锁，确保锁的正确释放，即使在异常情况下。

   #include <mutex>
   
   std::mutex mtx;
   
   void criticalSection() {
       std::lock_guard<std::mutex> lock(mtx); // 构造时加锁
       // 临界区代码
       // lock 对象超出作用域时，析构函数自动解锁
   }

总结： RAII 是C++中管理资源的核心思想。通过将资源封装在具有自动管理生命周期的对象中，可以极大地简化资源管理，提高程序的健壮性和安全性。在现代C++编程中，应尽可能地利用RAII来管理所有类型的资源，避免手动管理带来的风险。

12. C++从源程序到可执行程序的过程

问题描述： 详细解释C++源程序从编写到最终生成可执行程序的整个编译链接过程。

实现方法与代码思路：

C++源程序要经过一系列的阶段才能最终生成可执行程序。这个过程通常包括预处理、编译、汇编和链接四个主要阶段。

12.1 预处理 (Preprocessing)

• 输入： .cpp、.cxx、.cc 等C++源文件。
• 工具： 预处理器（cpp，C PreProcessor）。
• 作用： 处理源代码中以 # 开头的预处理指令。
• 主要任务：
  • 宏替换： 将 #define 定义的宏展开。
  • 文件包含： 将 #include 包含的头文件内容插入到当前文件中。
  • 条件编译： 处理 #if、#ifdef、#ifndef、#else、#elif、#endif 等指令，根据条件选择性地编译代码块。
  • 行控制： 处理 #line 指令，改变当前行号和文件名。
  • 删除注释： 删除所有注释（// 和 /* */）。
• 输出： 经过预处理的 .i 文件（或 .ii 文件），它是一个纯C++代码文件，不包含任何宏、#include 指令或注释。

12.2 编译 (Compilation)

• 输入： 预处理后的 .i 文件。
• 工具： 编译器（g++ 或 clang++ 的编译阶段）。
• 作用： 将C++源代码翻译成汇编代码。
• 主要任务：
  • 词法分析： 将源代码分解成一系列的词素（tokens）。
  • 语法分析： 根据语言的语法规则，将词素组织成抽象语法树（AST）。
  • 语义分析： 检查程序的语义是否合法，例如类型检查、变量声明等。
  • 中间代码生成： 将AST转换为中间代码（如三地址码）。
  • 代码优化： 对中间代码进行优化，提高程序执行效率。
  • 目标代码生成： 将优化后的中间代码转换为目标机器的汇编代码。
• 输出： 汇编代码文件（.s 文件）。

12.3 汇编 (Assembly)

• 输入： 汇编代码文件（.s 文件）。
• 工具： 汇编器（as）。
• 作用： 将汇编代码翻译成机器语言指令，生成目标文件。
• 主要任务： 将汇编指令转换为二进制的机器码，并生成符号表（记录函数和变量的地址信息）和重定位信息（用于链接）。
• 输出： 目标文件（.o 或 .obj 文件），它是机器码，但还不能直接执行，因为它可能包含对其他文件或库中定义的函数和变量的引用。

12.4 链接 (Linking)

• 输入： 一个或多个目标文件（.o）以及所需的库文件（静态库 .a / .lib 或动态库 .so / .dll）。
• 工具： 链接器（ld）。
• 作用： 将所有目标文件和库文件组合在一起，解决符号引用，生成最终的可执行程序。
• 主要任务：
  • 符号解析： 查找所有未定义的符号（如函数调用、全局变量引用），并在其他目标文件或库中找到它们的定义。
  • 地址重定位： 根据符号的实际地址，修正代码中所有对这些符号的引用。
  • 库链接： 将程序所需的库代码合并进来。
    • 静态链接： 将库中所有被用到的代码直接复制到可执行文件中。优点是可执行文件独立，运行时不需要依赖库；缺点是文件较大，更新库需要重新编译链接。
    • 动态链接： 在可执行文件中只保留对库的引用，实际的库代码在程序运行时才加载。优点是文件较小，节省内存，方便库的更新；缺点是运行时需要依赖库文件。
• 输出： 可执行文件（在Linux上通常没有扩展名，在Windows上是 .exe）。

12.5 整个过程示意图：

源文件 (.cpp) --(预处理)--> 预处理文件 (.i) --(编译)--> 汇编文件 (.s) --(汇编)--> 目标文件 (.o) --(链接)--> 可执行文件

总结： 了解C++程序的编译链接过程有助于理解程序的工作原理，解决编译和链接错误，以及进行性能优化。每个阶段都有其特定的任务和输出，共同协作将人类可读的源代码转换为机器可执行的指令。

13. C++ 和 C 的区别

问题描述： 解释C++和C语言之间的主要区别。

实现方法与代码思路：

C和C++都是由贝尔实验室开发的编程语言，C++是在C语言的基础上发展而来的，因此C++兼容C语言的大部分特性。然而，C++引入了许多新的概念和特性，使其成为一门独立的、更强大的语言。

13.1 核心区别：面向对象编程 (OOP)

• C语言： 是一门面向过程的语言。它强调通过函数来处理数据，程序结构围绕着函数展开。C语言没有类、对象、继承、多态等面向对象的概念。
• C++语言： 是一门面向对象的语言（同时兼容面向过程）。它引入了类（Class）的概念，允许程序员通过封装、继承和多态来组织和设计程序，更好地模拟现实世界。

13.2 主要区别点：

1. 面向对象特性：

   • C++支持： 类、对象、封装（public/private/protected）、继承、多态（虚函数、抽象类）、构造函数、析构函数等。
   • C不支持： C语言没有这些概念，通常通过结构体（struct）和函数指针来模拟一些面向对象的行为，但远不如C++原生支持的强大和方便。

2. 内存管理：

   • C： 主要使用 malloc() 和 free() 进行动态内存分配和释放。这些是库函数，不调用构造函数和析构函数。
   • C++： 引入了 new 和 delete 运算符。它们不仅分配/释放内存，还会自动调用对象的构造函数和析构函数，从而更好地管理对象生命周期。C++也兼容 malloc/free。

3. 类型检查：

   • C： 类型检查相对宽松，例如 void* 可以隐式转换为其他指针类型。
   • C++： 类型检查更严格，void* 不能隐式转换为其他指针类型，需要显式转换。这有助于减少类型相关的错误。

4. 引用 (Reference)：

   • C++支持： 引入了引用，作为变量的别名，提供了比指针更安全、更简洁的间接访问方式。
   • C不支持： C语言没有引用的概念。

5. 函数重载 (Function Overloading) 和运算符重载 (Operator Overloading)：

   • C++支持： 允许在同一作用域内定义同名但参数列表不同的函数（函数重载），以及为自定义类型重定义运算符的行为（运算符重载）。
   • C不支持： C语言不允许函数重载，也没有运算符重载。

6. 默认参数 (Default Arguments)：

   • C++支持： 函数参数可以设置默认值，调用时可以省略这些参数。
   • C不支持： C语言没有默认参数。

7. 模板 (Templates)：

   • C++支持： 引入了函数模板和类模板，实现了泛型编程，可以编写独立于具体数据类型的代码。
   • C不支持： C语言没有模板。

8. 异常处理 (Exception Handling)：

   • C++支持： 提供了 try-catch-throw 机制，用于处理程序运行时可能发生的异常，使错误处理更加结构化。
   • C不支持： C语言通常通过返回错误码或设置全局变量来处理错误。

9. 标准库：

   • C： 主要依赖于C标准库（如 stdio.h、stdlib.h、string.h 等）。
   • C++： 除了兼容C标准库外，还拥有更丰富、更强大的C++标准库（STL - Standard Template Library），包括容器（vector、list、map 等）、算法（sort、find 等）、迭代器、函数对象等。

10. const 关键字：

    • C： const 主要用于声明只读变量。
    • C++： const 的用法更加丰富和严格，可以修饰变量、指针、引用、函数参数、成员函数等，提供了更强的类型安全和语义表达能力。

11. 命名空间 (Namespace)：

    • C++支持： 提供了命名空间机制，用于解决大型项目中命名冲突的问题。
    • C不支持： C语言没有命名空间。

13.3 总结表格：

特性	C语言	C++语言
编程范式	面向过程	面向对象、面向过程、泛型编程
内存管理	malloc/free (手动，无构造/析构)	new/delete (自动调用构造/析构)，兼容malloc/free
类型检查	相对宽松	严格
引用	不支持	支持
函数/运算符重载	不支持	支持
默认参数	不支持	支持
模板	不支持	支持
异常处理	不支持 (通过错误码)	支持 (try-catch-throw)
标准库	C标准库	C标准库 + STL (更丰富)
const	声明只读变量	更丰富、严格的用法
命名空间	不支持	支持

总结： C++在C语言的基础上，通过引入面向对象、泛型编程等特性，以及更强大的标准库和更严格的类型检查，使其成为一门功能更强大、表达能力更丰富、更安全的编程语言。C++可以看作是C的超集，但其编程思想和最佳实践与C有很大不同。

14. extern C 的作用

问题描述： 解释C++中 extern "C" 的作用。

实现方法与代码思路：

`extern

"C"是C++语言中的一个链接指示符（linkage specifier），它的主要作用是**指示编译器以C语言的链接约定来处理被extern "C"` 修饰的函数和变量**。

14.1 为什么需要 extern "C"？

C++支持函数重载，为了实现这一特性，编译器在编译C++代码时会对函数名进行名称修饰（Name Mangling）。名称修饰会将函数的参数类型、返回类型、所属类等信息编码到函数名中，生成一个独一无二的内部名称。例如，C++中的 void func(int) 和 void func(double) 经过名称修饰后会变成不同的符号，从而允许它们共存。

然而，C语言不支持函数重载，因此C编译器在编译函数时不会进行名称修饰，它会直接使用函数名作为符号。这就导致了一个问题：

• C++代码调用C函数： 如果C++代码直接调用一个C语言编写的函数，C++编译器会尝试对C函数名进行名称修饰，但链接器在C库中找不到这个修饰后的名称，从而导致链接错误（undefined reference）。
• C函数调用C++函数： 如果C语言代码调用一个C++函数，C编译器会直接使用函数名，但C++编译器生成的函数名是经过修饰的，C代码无法找到正确的函数。

extern "C" 就是为了解决这种C++和C语言混合编程时的链接兼容性问题。

14.2 extern "C" 的作用

当C++编译器遇到 extern "C" 时，它会告诉自己：

• 对于被修饰的函数： 不要对这个函数名进行名称修饰，而是按照C语言的约定来生成符号名。
• 对于被修饰的变量： 按照C语言的约定来处理这个变量的符号名。

这样，C++编译器生成的符号名就与C编译器生成的符号名一致，从而使得C++代码可以正确地链接到C库中的函数和变量，反之亦然。

14.3 使用场景和示例

场景一：在C++代码中调用C函数

假设有一个C语言头文件 c_func.h 和实现文件 c_func.c：

// c_func.h
#ifndef C_FUNC_H
#define C_FUNC_H

void c_function(int a, int b);

#endif

// c_func.c
#include <stdio.h>
#include "c_func.h"

void c_function(int a, int b) {
    printf("C function called with %d and %d\n", a, b);
}

在C++代码中调用 c_function：

// cpp_main.cpp
#include <iostream>

// 告诉C++编译器，c_function 是一个C语言函数，不要对其进行名称修饰
extern "C" {
    void c_function(int a, int b);
}

int main() {
    c_function(10, 20); // 正确调用C函数
    return 0;
}

场景二：在C++中定义函数，供C代码调用

假设C代码需要调用一个C++中实现的函数：

// cpp_lib.cpp
#include <iostream>

// 告诉C++编译器，这个函数要按照C语言的链接约定来生成符号名
extern "C" void cpp_function_for_c(int x) {
    std::cout << "C++ function called from C with: " << x << std::endl;
}

// cpp_lib.h (供C代码包含)
#ifndef CPP_LIB_H
#define CPP_LIB_H

#ifdef __cplusplus // 只有在C++编译器下才使用 extern "C"
extern "C" {
#endif

void cpp_function_for_c(int x);

#ifdef __cplusplus
}
#endif

#endif

// c_main.c
#include "cpp_lib.h"

int main() {
    cpp_function_for_c(50); // 正确调用C++函数
    return 0;
}

14.4 总结：

extern "C" 是C++为了兼容C语言而提供的一种机制，它确保了C++编译器在处理特定代码块时，使用C语言的链接约定，从而避免了名称修饰带来的链接问题。这对于C++和C语言混合编程至关重要。

15. C++ 中的 struct 和 class 区别

问题描述： 解释C++中 struct 和 class 的区别。

实现方法与代码思路：

在C++中，struct 和 class 都可以用于定义类类型。它们在功能上几乎是完全相同的，都可以包含成员变量、成员函数、构造函数、析构函数、继承、多态等。然而，它们之间存在两个细微但重要的默认行为上的区别。

15.1 默认访问权限 (Default Access Specifier)

• struct： 默认的成员访问权限是 public。
• class： 默认的成员访问权限是 private。

示例：

struct MyStruct {
    int data1; // 默认 public
    void func1() {} // 默认 public
};

class MyClass {
    int data2; // 默认 private
    void func2() {} // 默认 private
};

// main函数中
// MyStruct s;
// s.data1 = 10; // 正确
// s.func1(); // 正确

// MyClass c;
// c.data2 = 20; // 错误：data2 是 private
// c.func2(); // 错误：func2 是 private

15.2 默认继承权限 (Default Inheritance Specifier)

• struct： 默认的继承权限是 public。
• class： 默认的继承权限是 private。

示例：

struct BaseStruct {};
struct DerivedStruct : BaseStruct {}; // 默认 public 继承

class BaseClass {};
class DerivedClass : BaseClass {}; // 默认 private 继承

// 如果要显式指定继承权限，则 struct 和 class 行为一致
// struct DerivedStruct : public BaseStruct {};
// class DerivedClass : public BaseClass {};

15.3 历史和惯例

• 历史原因： struct 是从C语言继承而来的关键字，在C语言中 struct 只能包含数据成员。C++为了兼容C语言，并扩展了 struct 的功能，使其也能包含成员函数等。为了保持与C语言的兼容性，struct 默认成员访问权限被设置为 public。
• 编程惯例：
  • 通常，当定义一个主要用于聚合数据（Plain Old Data, POD）的类型时，倾向于使用 struct，因为其默认 public 访问权限更符合数据结构的直观使用。
  • 当定义一个具有封装性、包含行为和状态的完整对象时，倾向于使用 class，因为其默认 private 访问权限更符合面向对象设计的封装原则。

15.4 总结表格：

特性	struct	class
默认成员访问权限	public	private
默认继承权限	public	private
功能	完全相同 (都可以定义类、成员、继承、多态等)	完全相同
惯例	用于数据聚合，POD类型	用于封装行为和状态的完整对象

结论： struct 和 class 在C++中几乎是等价的，它们之间的唯一区别在于默认的成员访问权限和默认的继承权限。在实际编程中，选择使用 struct 还是 class 更多是基于编程风格和语义上的清晰度。

16. 如何防止一个头文件 include 多次

问题描述： 解释在C++中如何防止同一个头文件被多次包含，以及为什么需要这样做。

实现方法与代码思路：

在C++编程中，一个头文件（.h 或 .hpp 文件）被多次包含到一个编译单元（.cpp 文件）中是一个常见的问题。这可能导致以下问题：

• 重复定义错误： 如果头文件中定义了变量、函数（非内联）、类等，多次包含会导致这些实体被重复定义，从而引发编译错误（redefinition）。
• 编译时间增加： 编译器需要重复处理同一个头文件的内容，增加了编译时间。
• 逻辑错误： 某些情况下，重复包含可能导致意想不到的逻辑错误。

为了解决这个问题，C++提供了两种主要的机制来防止头文件被多次包含：头文件卫士 (Include Guards) 和 #pragma once。

16.1 头文件卫士 (Include Guards)

• 原理： 使用预处理器宏来检查头文件是否已经被包含过。如果已经被包含，则跳过整个头文件的内容。

• 语法：

  #ifndef HEADER_FILE_NAME_H // 如果没有定义 HEADER_FILE_NAME_H
  #define HEADER_FILE_NAME_H // 则定义 HEADER_FILE_NAME_H
  
  // 头文件内容
  // 变量声明、函数声明、类定义等
  
  #endif // 结束 ifndef

• 命名约定： 宏的名称通常是头文件名的全大写形式，并将 . 替换为 _，并在末尾添加 _H 或 _HPP 等后缀，以确保唯一性。例如，my_header.h 对应的宏可以是 MY_HEADER_H。

• 优点：

  • 可移植性强： 几乎所有C++编译器都支持，是标准C++的一部分。
  • 明确： 宏的定义和检查逻辑清晰可见。

• 缺点：

  • 可能存在宏名冲突： 如果不同头文件使用了相同的宏名，可能会导致问题（尽管这种情况很少见，因为通常会使用唯一命名约定）。
  • 需要手动添加： 每个头文件都需要手动添加这些宏。

16.2 #pragma once

• 原理： 这是一个编译器特定的预处理指令。当编译器遇到 #pragma once 时，它会检查当前文件是否已经被包含过。如果已经被包含，则跳过该文件的后续内容。

• 语法：

  #pragma once
  
  // 头文件内容
  // 变量声明、函数声明、类定义等

• 优点：

  • 简洁： 只需要一行代码，比头文件卫士更简洁。
  • 效率高： 编译器可以直接通过文件名或文件路径来判断是否已经包含，通常比宏检查更快。
  • 避免宏名冲突： 不依赖于宏名，因此不会有宏名冲突的问题。

• 缺点：

  • 非标准： 尽管被大多数主流编译器（如GCC、Clang、MSVC）支持，但它不是C++标准的一部分。在极少数情况下，可能存在不兼容性。

16.3 总结和选择

特性	头文件卫士 (#ifndef/#define/#endif)	#pragma once
标准	C++标准的一部分	编译器特定扩展 (非标准)
可移植性	强	较强 (主流编译器支持)
语法	多行宏定义和条件编译	单行指令
效率	相对较低 (需要宏查找)	较高 (编译器直接判断)
宏名冲突	可能存在 (需要唯一命名)	不存在

选择建议：

• 在追求最大可移植性的项目中，或者当项目需要支持非常老旧的编译器时，应优先使用头文件卫士。
• 在现代C++项目中，或者当项目主要使用主流编译器时，#pragma once 是一个更简洁、更高效的选择。许多现代IDE和代码生成工具也默认使用 #pragma once。

在实际开发中，两种方法可以混合使用，或者根据团队的编码规范进行选择。但无论选择哪种，都应该确保每个头文件都包含防止多次包含的机制。

17. lambda 表达式的理解和捕获类型

问题描述： 解释C++11引入的 lambda 表达式，包括其理解、语法以及捕获（capture）机制。

实现方法与代码思路：

lambda 表达式是C++11引入的一个重要特性，它允许在代码中定义匿名函数对象（或称闭包），从而使得函数式编程风格在C++中更加方便。lambda 表达式通常用于需要短小、一次性使用的函数对象，例如作为算法的谓词或回调函数。

17.1 lambda 表达式的理解

lambda 表达式本质上是一个可调用对象，它可以在定义它的作用域内捕获（访问）外部变量。它提供了一种简洁的方式来定义局部函数，而无需单独定义一个具名函数或函数对象类。

基本语法：

[capture_list](parameters) -> return_type { function_body }

• [capture_list] (捕获列表)： 定义了 lambda 表达式可以访问其外部作用域中的哪些变量，以及如何访问（按值或按引用）。
• (parameters) (参数列表)： 与普通函数的参数列表相同。如果 lambda 不接受任何参数，可以省略 ()。
• -> return_type (返回类型)： 可选。如果 lambda 的函数体只包含一个 return 语句，或者没有 return 语句（void 返回类型），编译器可以自动推断返回类型。否则，需要显式指定。
• { function_body } (函数体)： lambda 表达式的实际代码。

示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    int factor = 10;

    // 简单的lambda表达式，按值捕获factor
    auto multiply = [factor](int x) -> int {
        return x * factor;
    };

    std::cout << multiply(5) << std::endl; // 输出 50

    // 在算法中使用lambda
    std::for_each(nums.begin(), nums.end(), [factor](int n) {
        std::cout << n * factor << " ";
    });
    std::cout << std::endl; // 输出 10 20 30 40 50

    return 0;
}

17.2 捕获类型 (Capture Types)

捕获列表决定了 lambda 表达式如何访问其定义作用域中的非静态局部变量。主要有以下几种捕获方式：

1. 值捕获 (Capture by Value)：[var]

   • 将外部变量 var 的值复制一份到 lambda 内部。lambda 内部使用的是 var 的副本，对副本的修改不会影响外部的 var。
   • 默认情况下，值捕获的变量在 lambda 内部是 const 的，不能被修改。如果需要修改，需要将 lambda 声明为 mutable。

   int x = 10;
   auto lambda_val = [x]() { std::cout << x << std::endl; }; // x 的副本
   // auto lambda_val_mutable = [x]() mutable { x = 20; std::cout << x << std::endl; }; // 修改副本

2. 引用捕获 (Capture by Reference)：[&var]

   • 将外部变量 var 的引用传递到 lambda 内部。lambda 内部直接访问外部的 var，对 var 的修改会影响外部的 var。

   int y = 10;
   auto lambda_ref = [&y]() { y = 20; std::cout << y << std::endl; }; // 直接修改外部 y
   lambda_ref(); // 输出 20
   std::cout << y << std::endl; // 输出 20

3. 隐式捕获 (Implicit Capture)：[=] 或 [&]

   • [=] (按值隐式捕获所有外部变量)： lambda 表达式中使用的所有外部非静态局部变量都将按值捕获。
   • [&] (按引用隐式捕获所有外部变量)： lambda 表达式中使用的所有外部非静态局部变量都将按引用捕获。

   int a = 1, b = 2;
   auto lambda_all_val = [=]() { std::cout << a << " " << b << std::endl; };
   auto lambda_all_ref = [&]() { a = 10; b = 20; };

4. 混合捕获： 可以混合使用值捕获和引用捕获。

   int c = 1, d = 2;
   auto lambda_mix = [c, &d]() { // c 按值捕获，d 按引用捕获
       // c = 10; // 错误，c 是 const 副本
       d = 20; // 正确，d 是引用
   };

5. C++14 广义捕获 (Generalized Capture)：[var = expression]

   • 允许在捕获列表中初始化新的变量，这些变量的值来自表达式。这对于捕获只移动类型（move-only types）或创建新的成员变量非常有用。

   // C++14
   std::unique_ptr<int> ptr(new int(10));
   auto lambda_move = [p = std::move(ptr)]() { // 移动捕获 unique_ptr
       std::cout << *p << std::endl;
   };

17.3 mutable 关键字

默认情况下，值捕获的变量在 lambda 内部是 const 的。如果需要修改值捕获的变量，可以在参数列表后添加 mutable 关键字。

int counter = 0;
auto incrementer = [counter]() mutable {
    counter++; // 修改的是副本
    std::cout << "Inside lambda: " << counter << std::endl;
};

incrementer(); // 输出 Inside lambda: 1
incrementer(); // 输出 Inside lambda: 2
std::cout << "Outside lambda: " << counter << std::endl; // 输出 Outside lambda: 0

总结： lambda 表达式是C++11中一个非常强大的特性，它简化了函数对象的创建，并提供了灵活的变量捕获机制，使得C++在函数式编程方面更加便利。理解其语法和捕获规则对于编写现代C++代码至关重要。

18. move 函数和右值引用

问题描述： 解释C++11引入的 std::move 函数和右值引用（Rvalue Reference）的概念，以及它们在C++中的作用。

实现方法与代码思路：

C++11引入了右值引用和移动语义（Move Semantics），旨在解决传统C++中不必要的深拷贝问题，从而提高程序的性能。std::move 是实现移动语义的关键工具。

18.1 右值引用 (Rvalue Reference)

• 概念： 右值引用是一种新的引用类型，用 && 声明。它只能绑定到右值（rvalue）。
  • 右值： 临时对象、字面量、函数返回值等，它们在表达式结束后就不再存在，或者不能被取地址。
  • 左值： 具有名称、可以取地址的表达式，例如变量。
• 语法： Type&& rvalue_ref = rvalue_expression;

示例：

int x = 10; // x 是左值
int& lref = x; // 左值引用绑定到左值

// int&& rref = x; // 错误：右值引用不能绑定到左值

int&& rref = 10; // 正确：右值引用绑定到右值字面量
int&& rref2 = x + 5; // 正确：x + 5 的结果是临时对象（右值）

// 函数返回右值
int create_rvalue() { return 100; }
int&& rref3 = create_rvalue(); // 正确：右值引用绑定到函数返回值

18.2 移动语义 (Move Semantics)

移动语义的核心思想是，对于那些即将被销毁的临时对象（右值），我们不需要进行昂贵的深拷贝，而是可以直接“窃取”它们的资源（如堆内存），将其所有权转移给新的对象。这避免了资源的重复分配和释放，提高了效率。

移动语义通过移动构造函数和移动赋值运算符来实现。

• 移动构造函数： ClassName(ClassName&& other);
• 移动赋值运算符： ClassName& operator=(ClassName&& other);

示例：

class MyString {
public:
    char* data;
    size_t length;

    // 构造函数
    MyString(const char* s = "") {
        length = std::strlen(s);
        data = new char[length + 1];
        std::strcpy(data, s);
        std::cout << "Constructor: " << data << std::endl;
    }

    // 析构函数
    ~MyString() {
        delete[] data;
        std::cout << "Destructor: " << (data ? data : "(null)") << std::endl;
    }

    // 拷贝构造函数 (深拷贝)
    MyString(const MyString& other) {
        length = other.length;
        data = new char[length + 1];
        std::strcpy(data, other.data);
        std::cout << "Copy Constructor: " << data << std::endl;
    }

    // 移动构造函数 (浅拷贝 + 置空源对象)
    MyString(MyString&& other) noexcept {
        data = other.data;
        length = other.length;
        other.data = nullptr; // 将源对象置空，防止二次释放
        other.length = 0;
        std::cout << "Move Constructor: " << (data ? data : "(null)") << std::endl;
    }

    // 拷贝赋值运算符
    MyString& operator=(const MyString& other) {
        if (this != &other) {
            delete[] data;
            length = other.length;
            data = new char[length + 1];
            std::strcpy(data, other.data);
        }
        std::cout << "Copy Assignment: " << data << std::endl;
        return *this;
    }

    // 移动赋值运算符
    MyString& operator=(MyString&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;
            length = other.length;
            other.data = nullptr;
            other.length = 0;
        }
        std::cout << "Move Assignment: " << (data ? data : "(null)") << std::endl;
        return *this;
    }
};

// MyString create_string() { return MyString("temporary"); }

// int main() {
//     MyString s1 = create_string(); // 这里会调用移动构造函数，而不是拷贝构造函数
//     MyString s2;
//     s2 = MyString("another temporary"); // 这里会调用移动赋值运算符
//     return 0;
// }

18.3 std::move 函数

• 概念： std::move 是C++标准库 <utility> 中的一个函数模板。它的作用是将一个左值强制转换为右值引用。它本身不进行任何数据移动，只是改变了表达式的类型。
• 作用： 告诉编译器，某个左值对象可以被“移动”了，即它的资源可以被窃取，因为它在之后不会再被使用了。
• 语法： std::move(lvalue_expression)

示例：

// int main() {
//     MyString s3("original");
//     MyString s4 = std::move(s3); // 调用移动构造函数，s3 的资源被转移给 s4
//     // 此时 s3 处于有效但未指定状态，不应再使用其内容
//     // std::cout << s3.data; // 危险！
//     std::cout << "s4: " << s4.data << std::endl;
//     return 0;
// }

18.4 std::move 和右值引用的关系

• std::move 是一个类型转换工具，它将左值转换为右值引用，从而使得编译器能够选择调用移动构造函数或移动赋值运算符。
• 右值引用是类型，它是移动语义的基础。移动构造函数和移动赋值运算符的参数类型就是右值引用。

18.5 函数参数可不可以传右值？

可以。 C++11引入右值引用后，函数参数可以接受右值引用，从而实现移动语义。

• 通过值传递： void func(MyString s)
  • 如果传入左值，会调用拷贝构造函数。
  • 如果传入右值，会调用移动构造函数（如果定义了）。
• 通过左值引用传递： void func(MyString& s)
  • 只能接受左值。
• 通过 const 左值引用传递： void func(const MyString& s)
  • 可以接受左值和右值，但不能修改 s。
  • 会调用拷贝构造函数（如果需要临时对象）。
• 通过右值引用传递： void func(MyString&& s)
  • 只能接受右值。
  • 通常用于实现移动语义，表示函数会“消耗”传入的右值。

示例：

void process_string(MyString&& s) { // 接受右值引用
    std::cout << "Processing (moved): " << s.data << std::endl;
    // s 的资源可以被安全地窃取或修改，因为它是右值
}

// int main() {
//     MyString original_str("hello");
//     // process_string(original_str); // 错误：不能将左值绑定到右值引用
//     process_string(std::move(original_str)); // 正确：将左值转换为右值引用
//     process_string(MyString("world")); // 正确：传入临时对象（右值）
//     return 0;
// }

总结： std::move 和右值引用是C++11中实现移动语义的关键，它们使得C++程序在处理临时对象和资源管理时更加高效，避免了不必要的深拷贝。理解这些概念对于编写高性能的现代C++代码至关重要。

19. STL 容器了解吗？底层如何实现：vector 数组，map 红黑树，红黑树的实现

问题描述： 解释C++标准模板库（STL）中常见容器的底层实现，特别是 vector、map 和红黑树。

实现方法与代码思路：

C++标准模板库（STL）提供了一系列高效、通用的数据结构和算法。容器是STL的核心组成部分，它们是用于存储和组织数据的类模板。理解其底层实现对于高效使用STL和解决实际问题至关重要。

19.1 std::vector：动态数组

• 底层实现： std::vector 的底层是一个连续的动态数组。它在内存中分配一块连续的存储空间来存放元素。当存储空间不足时，vector 会自动进行扩容（通常是当前容量的1.5倍或2倍），分配新的更大的内存块，并将旧内存中的元素复制（或移动）到新内存中，然后释放旧内存。
• 特点：
  • 随机访问： 支持通过索引 [] 或 at() 进行 O(1) 时间复杂度的随机访问。
  • 尾部插入/删除： 在末尾添加或删除元素通常是 O(1) 的均摊时间复杂度。
  • 中间插入/删除： 在中间插入或删除元素需要移动后续所有元素，时间复杂度为 O(N)。
  • 缓存友好： 连续存储有利于CPU缓存。
• 扩容： 扩容操作会重新分配内存，导致所有迭代器、指针和引用失效。

19.2 std::map：红黑树

• 底层实现： std::map 的底层通常是红黑树 (Red-Black Tree)。红黑树是一种自平衡的二叉查找树（Binary Search Tree, BST），它在插入和删除节点时通过一系列的旋转和颜色调整来保持树的平衡，从而保证了查找、插入和删除操作的最坏时间复杂度为 O(log N)。
• 特点：
  • 有序性： 元素按照键的严格弱序排列，因此遍历 map 时元素是有序的。
  • 查找、插入、删除： 平均和最坏时间复杂度都是 O(log N)。
  • 节点结构： 每个节点通常包含键、值、颜色（红或黑）、父节点指针、左子节点指针和右子节点指针。
  • 内存占用： 相对于 vector，每个节点需要额外的指针和颜色信息，内存开销较大。
  • 缓存不友好： 节点在内存中可能不连续，缓存命中率相对较低。

19.3 红黑树的实现

红黑树是一种复杂的自平衡二叉查找树，它满足以下五个性质：

1. 节点颜色： 每个节点要么是红色，要么是黑色。
2. 根节点： 根节点是黑色的。
3. 叶子节点： 每个叶子节点（NIL节点，通常是表示空节点的特殊黑色节点）是黑色的。
4. 红色节点规则： 如果一个节点是红色的，则它的两个子节点都是黑色的（即不能有两个连续的红色节点）。
5. 黑色高度： 从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

这些性质保证了红黑树的高度近似于 log N，从而保证了操作的对数时间复杂度。

红黑树的插入和删除操作：

当插入或删除一个节点时，可能会破坏红黑树的性质。为了恢复平衡，红黑树会进行以下两种操作：

1. 重新着色 (Recoloring)： 改变节点的颜色。
2. 旋转 (Rotation)： 改变树的结构，包括左旋和右旋。

这些操作是复杂的，通常需要考虑多种情况。以下是其核心思想的伪代码，实际实现会更复杂：

// 伪代码：红黑树节点结构
enum Color { RED, BLACK };

struct RBNode {
    int key;
    Color color;
    RBNode *parent;
    RBNode *left;
    RBNode *right;

    RBNode(int k) : key(k), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};

class RedBlackTree {
private:
    RBNode* root;
    RBNode* NIL; // 哨兵节点，代表空节点，颜色为黑色

    void leftRotate(RBNode* x) {
        // 左旋操作：将 x 的右子节点 y 提升为 x 的父节点，x 成为 y 的左子节点
        // ... 调整指针和父子关系
    }

    void rightRotate(RBNode* y) {
        // 右旋操作：将 y 的左子节点 x 提升为 y 的父节点，y 成为 x 的右子节点
        // ... 调整指针和父子关系
    }

    void insertFixup(RBNode* z) {
        // 插入后修复红黑树性质
        // 循环直到 z 的父节点是黑色，或者 z 是根节点
        // 根据 z、z 的父节点、z 的祖父节点和 z 的叔叔节点的颜色和位置，进行重新着色和旋转
        // ...
    }

    void deleteFixup(RBNode* x) {
        // 删除后修复红黑树性质
        // ...
    }

public:
    RedBlackTree() {
        NIL = new RBNode(0); // 哨兵节点，通常不存储实际数据
        NIL->color = BLACK;
        NIL->left = NIL;
        NIL->right = NIL;
        root = NIL;
    }

    void insert(int key) {
        RBNode* z = new RBNode(key);
        z->left = NIL;
        z->right = NIL;

        RBNode* y = NIL;
        RBNode* x = root;

        while (x != NIL) {
            y = x;
            if (z->key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        z->parent = y;

        if (y == NIL) {
            root = z;
        } else if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }

        insertFixup(z);
    }

    // ... 其他操作如查找、删除
};

总结： vector 和 map 是STL中最常用的两种容器，分别代表了连续存储和基于树的有序存储。vector 适用于需要随机访问和尾部快速增删的场景，而 map 适用于需要保持元素有序性和高效查找、插入、删除的场景。红黑树作为 map 的底层实现，通过复杂的自平衡机制保证了其性能的稳定性。

20. gcc 编译的过程

问题描述： 详细解释 gcc（或 g++）编译器将C/C++源文件编译成可执行文件的整个过程。

实现方法与代码思路：

gcc (GNU Compiler Collection) 是一个功能强大的编译器套件，支持C、C++、Objective-C、Fortran、Ada、Go等多种编程语言。当我们将C或C++源文件交给 gcc 或 g++ 编译时，它会经历四个主要阶段：预处理、编译、汇编和链接。这与前面“C++从源程序到可执行程序的过程”中描述的通用编译链接过程是一致的，这里将结合 gcc 的具体命令来进一步说明。

20.1 预处理 (Preprocessing)

• 作用： 处理源代码中的预处理指令（#include、#define、条件编译等），删除注释。
• 命令： gcc -E source_file.c -o output_file.i
  • -E：指示 gcc 只进行预处理。
  • source_file.c：输入源文件。
  • -o output_file.i：指定输出文件名为 output_file.i。
• 输出： .i 文件，是纯C/C++代码，不含预处理指令和注释。

20.2 编译 (Compilation)

• 作用： 将预处理后的C/C++代码翻译成汇编代码。
• 命令： gcc -S input_file.i -o output_file.s
  • -S：指示 gcc 只进行编译，生成汇编代码。
  • input_file.i：输入预处理文件。
  • -o output_file.s：指定输出文件名为 output_file.s。
• 输出： .s 文件，是汇编代码。

20.3 汇编 (Assembly)

• 作用： 将汇编代码翻译成机器码，生成目标文件。
• 命令： gcc -c input_file.s -o output_file.o
  • -c：指示 gcc 只进行汇编，生成目标文件。
  • input_file.s：输入汇编文件。
  • -o output_file.o：指定输出文件名为 output_file.o。
• 输出： .o 文件，是机器码，但尚未链接。

20.4 链接 (Linking)

• 作用： 将一个或多个目标文件以及所需的库文件组合成最终的可执行文件。
• 命令： gcc input_file.o -o executable_file
  • input_file.o：输入目标文件。
  • -o executable_file：指定输出可执行文件名为 executable_file。
• 输出： 可执行文件。

20.5 常用 gcc/g++ 编译选项

• -o <file>：指定输出文件名。
• -I <dir>：添加头文件搜索路径。
• -L <dir>：添加库文件搜索路径。
• -l <libname>：链接指定的库文件（例如 -lm 链接数学库，-lpthread 链接POSIX线程库）。
• -Wall：开启所有常用警告。
• -Wextra：开启额外警告。
• -g：生成调试信息，方便使用GDB等调试器。
• -O<level>：优化代码，<level> 可以是0、1、2、3、s、fast等，级别越高优化越激进。
• -std=<standard>：指定C++标准版本，例如 -std=c++11、-std=c++14、-std=c++17、-std=c++20。
• -D <macro>：定义宏。
• -U <macro>：取消定义宏。
• -shared：生成共享库（.so）。
• -static：静态链接。
• -fPIC：生成位置无关代码（用于共享库）。

20.6 完整编译示例：

假设有一个 main.cpp 和 my_lib.cpp，其中 my_lib.cpp 实现了 my_function 函数。

// my_lib.h
#ifndef MY_LIB_H
#define MY_LIB_H

void my_function();

#endif

// my_lib.cpp
#include <iostream>
#include "my_lib.h"

void my_function() {
    std::cout << "Hello from my_function!" << std::endl;
}

// main.cpp
#include <iostream>
#include "my_lib.h"

int main() {
    std::cout << "Hello from main!" << std::endl;
    my_function();
    return 0;
}

分步编译：

1. 编译 my_lib.cpp：g++ -c my_lib.cpp -o my_lib.o
2. 编译 main.cpp：g++ -c main.cpp -o main.o
3. 链接：g++ my_lib.o main.o -o my_program

一步编译：

g++ main.cpp my_lib.cpp -o my_program

gcc/g++ 会自动按顺序执行预处理、编译、汇编和链接。

总结： gcc/g++ 的编译过程是一个多阶段的复杂过程，每个阶段都有其特定的任务。理解这些阶段以及常用的编译选项，对于C/C++开发者来说是基本功，有助于更好地控制编译过程，解决问题，并优化程序性能。

21. C++ 中的 map 和 unordered_map 的区别和使用场景

问题描述： 比较C++标准库中的 std::map 和 std::unordered_map，解释它们的底层实现、性能特点、线程安全性以及各自的适用场景。

实现方法与代码思路：

这部分内容已在前面“C/C++语言”的“3. map 和 unordered_map 的区别和使用场景”中详细阐述，此处不再重复。请参考该部分内容。

22. c++ 标准库里优先队列是怎么实现的？

问题描述： 解释C++标准库中 std::priority_queue 的底层实现原理。

实现方法与代码思路：

std::priority_queue 是C++标准库中一个容器适配器（Container Adapter），它提供了一种优先级队列的功能。优先级队列是一种抽象数据类型，它允许你以任意顺序插入元素，但总是能够快速地访问（并移除）具有最高（或最低）优先级的元素。

22.1 底层实现：堆 (Heap)

std::priority_queue 的底层通常是使用堆 (Heap) 来实现的。具体来说，它默认使用最大堆 (Max-Heap)，这意味着优先级最高的元素（即最大元素）总是位于堆的顶部。如果需要最小堆（优先级最低的元素在顶部），可以通过提供自定义的比较器来实现。

• 堆的特性：
  • 近似完全二叉树： 堆通常用数组（或 std::vector）来表示，通过数组索引来模拟二叉树的父子关系。例如，对于索引为 i 的节点，其左子节点为 2*i + 1，右子节点为 2*i + 2，父节点为 (i - 1) / 2。
  • 堆序性： 对于最大堆，每个父节点的值都大于或等于其子节点的值。对于最小堆，每个父节点的值都小于或等于其子节点的值。

22.2 std::priority_queue 的模板参数

std::priority_queue 有三个模板参数：

template<typename T, typename Container = std::vector<T>, typename Compare = std::less<T>>
class priority_queue;

• T：存储的元素类型。
• Container：底层容器类型，默认为 std::vector<T>。也可以是 std::deque<T>，但不能是 std::list<T>（因为堆操作需要随机访问）。
• Compare：比较函数对象，用于定义元素的优先级。默认为 std::less<T>，这意味着 (a < b) 为真时 a 的优先级低于 b，因此 priority_queue 会将最大元素放在顶部（最大堆）。如果想实现最小堆，可以使用 std::greater<T>。

22.3 核心操作和时间复杂度

std::priority_queue 的主要操作包括：

• push(const T& val)： 插入元素。将元素添加到底层容器的末尾，然后通过“上浮”（heapify-up）操作维护堆的性质。时间复杂度为 O(log N)。
• pop()： 移除最高优先级元素。移除堆顶元素，将底层容器的最后一个元素放到堆顶，然后通过“下沉”（heapify-down）操作维护堆的性质。时间复杂度为 O(log N)。
• top()： 获取最高优先级元素。直接返回堆顶元素。时间复杂度为 O(1)。
• empty()： 检查队列是否为空。时间复杂度为 O(1)。
• size()： 返回队列中元素的数量。时间复杂度为 O(1)。

22.4 堆的“上浮”和“下沉”操作

• 上浮 (Heapify-up / Sift-up)： 当一个新元素被添加到堆的末尾时，它可能比其父节点大（最大堆），从而破坏堆的性质。上浮操作就是将这个新元素与其父节点比较，如果新元素更大，则交换它们，然后继续向上比较，直到新元素找到正确的位置或到达堆顶。
• 下沉 (Heapify-down / Sift-down)： 当堆顶元素被移除，或者一个元素被替换到堆顶时，它可能比其子节点小（最大堆），从而破坏堆的性质。下沉操作就是将这个元素与其较大的子节点比较，如果子节点更大，则交换它们，然后继续向下比较，直到元素找到正确的位置或到达叶子节点。

22.5 示例：使用 std::priority_queue

#include <iostream>
#include <queue> // 包含 priority_queue
#include <vector>
#include <functional> // 包含 std::greater

int main() {
    // 默认：最大堆
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);
    max_pq.push(5);

    std::cout << "Max-Heap elements (top to bottom): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " "; // 30 20 10 5
        max_pq.pop();
    }
    std::cout << std::endl;

    // 最小堆：通过提供 std::greater<int> 作为比较器
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);
    min_pq.push(5);

    std::cout << "Min-Heap elements (top to bottom): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " "; // 5 10 20 30
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

总结： std::priority_queue 是一个基于堆实现的容器适配器，提供了高效的优先级队列功能。其底层使用 std::vector 来存储元素，并通过堆的“上浮”和“下沉”操作来维护优先级顺序，从而保证了插入和删除操作的对数时间复杂度。

23. C++ Coroutine

问题描述： 解释C++20引入的协程（Coroutine）的概念、作用和基本用法。

实现方法与代码思路：

C++20引入了协程（Coroutine）作为一项重要的语言特性，它提供了一种新的、更高效的并发编程模型，用于编写异步、非阻塞的代码。协程是一种用户态的轻量级线程，它允许函数在执行过程中暂停（suspend）并在稍后从暂停点恢复（resume），而无需阻塞整个线程。

23.1 协程的概念

• 可暂停函数： 协程是一种可以暂停执行并在稍后恢复执行的函数。与传统函数不同，传统函数一旦开始执行，就会一直运行直到返回或抛出异常。
• 非抢占式调度： 协程的调度是协作式的，即协程主动放弃CPU控制权（通过 co_await 或 co_yield），而不是被操作系统抢占。这使得协程的上下文切换开销远小于线程。
• 用户态： 协程在用户空间实现，不需要操作系统的调度支持，因此创建和销毁的开销非常小。
• 状态机： 编译器会将协程转换为一个状态机，每次暂停和恢复都对应状态机的状态切换。

23.2 协程的作用

协程主要用于简化异步编程，解决传统回调函数或 future/promise 模式中可能出现的“回调地狱”（Callback Hell）问题，使异步代码看起来像同步代码一样直观。

• 简化异步代码： 将复杂的异步操作序列扁平化，避免多层嵌套的回调。
• 提高并发效率： 相比线程，协程的上下文切换开销小，可以创建大量的协程来处理并发任务。
• 构建生成器和流： 通过 co_yield 可以方便地实现生成器（Generator），按需生成序列。

23.3 协程的基本用法和关键字

C++20协程引入了三个新的关键字：

1. co_await： 用于暂停协程的执行，等待某个异步操作完成。当异步操作完成后，协程会从 co_await 的位置恢复执行。
2. co_yield： 用于生成器协程，暂停协程的执行并返回一个值。当下次需要值时，协程会从 co_yield 的位置恢复执行。
3. co_return： 用于结束协程的执行并返回一个值（或不返回值）。

协程的类型：

• 生成器 (Generator)： 使用 co_yield，用于按需生成序列。例如，一个斐波那契数列生成器。
• 异步任务 (Asynchronous Task)： 使用 co_await 和 co_return，用于执行异步操作并返回结果。例如，网络请求。

实现协程需要以下组件：

• Promise 类型： 协程的“承诺”对象，用于管理协程的状态、返回值和异常。每个协程都有一个关联的 Promise 对象。
• Coroutine Handle： 用于操作协程的句柄，可以用来恢复（resume）协程或销毁（destroy）协程。
• Awaitable 类型： 可以被 co_await 的对象。它定义了协程如何暂停和恢复。
• Awaiter 类型： Awaitable 类型的辅助类型，定义了 await_ready、await_suspend 和 await_resume 三个成员函数。

示例：简单的生成器协程 (C++20)

实现一个简单的斐波那契数列生成器：

#include <iostream>
#include <coroutine>
#include <optional>

// 1. 定义 Promise 类型
template<typename T>
struct GeneratorPromise {
    T value_;
    std::suspend_always yield_value(T value) {
        value_ = value;
        return {};
    }
    std::suspend_always initial_suspend() { return {}; }
    std::suspend_always final_suspend() noexcept { return {}; }
    GeneratorPromise* get_return_object() { return this; }
    void return_void() {}
    void unhandled_exception() { std::terminate(); }
};

// 2. 定义 Generator 类型 (作为协程的返回类型)
template<typename T>
struct Generator {
    using promise_type = GeneratorPromise<T>;
    std::coroutine_handle<promise_type> handle_;

    Generator(GeneratorPromise<T>* promise) : handle_(std::coroutine_handle<promise_type>::from_promise(*promise)) {}
    ~Generator() { if (handle_) handle_.destroy(); }

    // 迭代器接口 (简化)
    struct iterator {
        std::coroutine_handle<promise_type> handle_;
        bool operator!=(const iterator& other) const { return handle_ != other.handle_; }
        iterator& operator++() { handle_.resume(); return *this; }
        T operator*() const { return handle_.promise().value_; }
    };

    iterator begin() { handle_.resume(); return iterator{handle_}; }
    iterator end() { return iterator{nullptr}; }
};

// 3. 协程函数
Generator<int> fibonacci_generator() {
    int a = 0, b = 1;
    while (true) {
        co_yield a;
        int next = a + b;
        a = b;
        b = next;
    }
}

// int main() {
//     auto gen = fibonacci_generator();
//     int count = 0;
//     for (int val : gen) {
//         std::cout << val << " ";
//         if (++count > 10) break;
//     }
//     std::cout << std::endl;
//     return 0;
// }

总结： C++协程是一个相对复杂的特性，它为异步编程和生成器模式提供了强大的支持。虽然其底层机制需要深入理解，但一旦掌握，可以极大地提高代码的可读性和效率，尤其是在处理I/O密集型任务时。协程是现代C++并发编程的重要发展方向。

24. C++ 的符号表

问题描述： 解释C++中符号表（Symbol Table）的概念、作用以及它在编译链接过程中的角色。

实现方法与代码思路：

在C++程序的编译和链接过程中，符号表是一个至关重要的概念。它在不同的阶段扮演着不同的角色，但核心作用都是记录程序中各种符号（如变量名、函数名、类名等）的信息，并将其映射到对应的内存地址或定义。

24.1 符号 (Symbol) 的概念

在编程语言中，符号是对程序中各种实体的抽象表示。例如：

• 变量名： int x; 中的 x
• 函数名： void func(); 中的 func
• 类名： class MyClass; 中的 MyClass
• 枚举名、结构体名、联合体名
• 标签名

编译器和链接器需要知道这些符号的类型、作用域、存储位置等信息，才能正确地生成机器码和连接不同的代码模块。

24.2 符号表的作用

符号表是编译器和链接器用于管理和查找这些符号的数据结构。它主要有以下作用：

1. 编译阶段：

   • 语法和语义检查： 编译器在进行语法分析和语义分析时，会使用符号表来查找符号的定义、检查类型匹配、作用域规则等。例如，当遇到一个变量使用时，编译器会在符号表中查找其声明，以确定其类型和是否已定义。
   • 生成中间代码： 符号表中的信息用于生成正确的中间代码。
   • 名称修饰 (Name Mangling)： 对于C++，符号表会记录经过名称修饰后的函数和变量名，以便在链接时能够找到正确的定义。

2. 链接阶段：

   • 符号解析 (Symbol Resolution)： 链接器的主要任务之一就是解决符号引用。当一个目标文件引用了另一个目标文件或库中定义的符号时，链接器会在所有输入的目标文件和库的符号表中查找这些符号的定义，并将其关联起来。
   • 地址重定位 (Relocation)： 链接器根据符号在最终可执行文件中的实际地址，修正所有对这些符号的引用。

24.3 符号表的存储和形式

符号表在不同的阶段和工具中可能以不同的形式存在：

• 编译器内部： 在编译过程中，编译器会维护一个内部的符号表，用于记录当前编译单元中的所有符号信息。这个符号表是临时的，通常在编译完成后就会被丢弃。
• 目标文件 (.o 文件)： 编译完成后，编译器会将编译单元中定义的全局符号（函数、全局变量、静态变量等）以及引用的外部符号信息存储在目标文件的符号表节 (Symbol Table Section) 中。这个符号表是二进制格式的，可以通过 nm 或 objdump 等工具查看。
• 可执行文件/共享库 (.exe / .so / .dll)： 链接完成后，最终的可执行文件或共享库中也会包含一个符号表，用于运行时动态链接（对于共享库）或调试信息。

24.4 符号的类型

在符号表中，符号通常会有一个类型，表示其是定义还是引用，以及其可见性：

• T (Text Segment)： 函数或已初始化的全局变量，定义在代码段。
• D (Data Segment)： 已初始化的全局变量，定义在数据段。
• B (BSS Segment)： 未初始化的全局变量，定义在BSS段。
• U (Undefined)： 未定义的符号，表示该符号在当前文件中被引用，但定义在其他文件或库中。
• W (Weak Symbol)： 弱符号，通常用于库中，允许其他定义覆盖它。
• A (Absolute)： 绝对符号，其值在链接时不会改变。

示例：使用 nm 命令查看目标文件符号表

假设有一个 test.cpp 文件：

// test.cpp
int global_var = 10;
extern int external_var;

void my_function() {
    static int static_var = 20;
    int local_var = 30;
    external_var = local_var;
}

int main() {
    my_function();
    return 0;
}

编译 test.cpp 生成目标文件：g++ -c test.cpp -o test.o

然后使用 nm 命令查看 test.o 的符号表：nm test.o

你可能会看到类似以下的输出（具体输出可能因编译器和系统而异）：

0000000000000000 B _ZN12_GLOBAL__N_110static_varE // local_var (static) in BSS
0000000000000000 D global_var                  // global_var in Data
0000000000000000 T _Z11my_functionv            // my_function in Text
                 U external_var                // external_var is Undefined
0000000000000000 T main                        // main in Text

其中，_ZN12_GLOBAL__N_110static_varE 和 _Z11my_functionv 是经过名称修饰后的C++符号名。

总结： 符号表是C++编译链接过程中的核心数据结构，它记录了程序中所有符号的信息，并为编译器和链接器提供了进行语法检查、语义分析、符号解析和地址重定位所需的基础。理解符号表有助于深入理解C++程序的构建过程和解决相关的编译链接问题。

25. C++ 的单元测试

问题描述： 解释C++中单元测试的概念、重要性以及常用的单元测试框架和基本用法。

实现方法与代码思路：

单元测试（Unit Testing）是软件测试中的一种，它对程序中的最小可测试单元（通常是函数、方法或类）进行验证，以确保它们按预期工作。在C++开发中，单元测试是保证代码质量、提高开发效率和减少bug的重要实践。

25.1 单元测试的概念和重要性

• 概念： 单元测试是对软件的最小功能模块进行验证。这些模块通常是独立的函数、方法或类。测试的目的是确保每个单元在隔离的环境下都能正确执行其功能。
• 重要性：
  • 早期发现bug： 在开发早期就能发现并修复bug，降低修复成本。
  • 提高代码质量： 促使开发者编写模块化、可测试的代码，提高代码的可维护性和可读性。
  • 回归测试： 每次修改代码后，可以快速运行所有单元测试，确保修改没有引入新的bug或破坏现有功能。
  • 文档： 单元测试本身可以作为代码的活文档，展示代码的预期行为和使用方式。
  • 重构信心： 在进行代码重构时，单元测试提供了一层安全网，确保重构不会破坏原有功能。

25.2 常用的C++单元测试框架

C++有许多优秀的单元测试框架，其中最常用和流行的包括：

1. Google Test (GTest)：

   • 特点： 由Google开发，功能强大，支持丰富的断言、测试夹具（Test Fixtures）、参数化测试、死亡测试等。语法简洁，易于上手。
   • 适用性： 广泛应用于各种规模的C++项目。

2. Catch2：

   • 特点： 轻量级，只需要一个头文件即可使用。语法更接近自然语言，支持BDD（Behavior-Driven Development）风格的测试。编译速度快。
   • 适用性： 适合小型项目或对编译速度有要求的项目。

3. Boost.Test：

   • 特点： Boost库的一部分，功能全面，支持多种测试组织方式和报告格式。但配置和使用可能相对复杂。
   • 适用性： 适合已经使用Boost库的项目。

25.3 Google Test (GTest) 基本用法

这里以Google Test为例，介绍其基本用法。

安装：

通常需要从GitHub下载源码并编译安装，或者通过包管理器安装。

基本结构：

GTest 的测试由测试套件 (Test Suite) 和测试用例 (Test Case) 组成。

• 测试套件： 使用 TEST_F 或 TEST 宏定义，通常对应一个类或一个模块。
• 测试用例： 在测试套件内部，使用 TEST_F 或 TEST 宏定义具体的测试点。

断言 (Assertions)：

GTest 提供了丰富的断言宏来检查测试结果。如果断言失败，测试用例就会失败。

• ASSERT_EQ(expected, actual);：检查两个值是否相等，失败时立即终止当前测试用例。
• EXPECT_EQ(expected, actual);：检查两个值是否相等，失败时继续执行当前测试用例。
• ASSERT_TRUE(condition); / EXPECT_TRUE(condition);：检查条件是否为真。
• ASSERT_FALSE(condition); / EXPECT_FALSE(condition);：检查条件是否为假。
• ASSERT_NE(val1, val2); / EXPECT_NE(val1, val2);：检查两个值是否不相等。
• ASSERT_LT(val1, val2); / EXPECT_LT(val1, val2);：检查 val1 < val2。
• ASSERT_LE(val1, val2); / EXPECT_LE(val1, val2);：检查 val1 <= val2。
• ASSERT_GT(val1, val2); / EXPECT_GT(val1, val2);：检查 val1 > val2。
• ASSERT_GE(val1, val2); / EXPECT_GE(val1, val2);：检查 val1 >= val2。

示例：

假设我们有一个简单的加法函数 add.h 和 add.cpp：

// add.h
#ifndef ADD_H
#define ADD_H

int add(int a, int b);

#endif

// add.cpp
#include "add.h"

int add(int a, int b) {
    return a + b;
}

编写测试文件 add_test.cpp：

// add_test.cpp
#include "gtest/gtest.h"
#include "add.h" // 包含被测试的头文件

// 定义一个测试套件名为 "AddFunctionTest"
TEST(AddFunctionTest, HandlesPositiveInput) {
    // 测试用例1：处理正数输入
    EXPECT_EQ(5, add(2, 3));
    EXPECT_EQ(10, add(5, 5));
}

TEST(AddFunctionTest, HandlesNegativeInput) {
    // 测试用例2：处理负数输入
    EXPECT_EQ(-5, add(-2, -3));
    EXPECT_EQ(0, add(-5, 5));
}

TEST(AddFunctionTest, HandlesZeroInput) {
    // 测试用例3：处理零输入
    EXPECT_EQ(3, add(3, 0));
    EXPECT_EQ(-2, add(0, -2));
}

// main 函数，运行所有测试
int main(int argc, char **argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

编译和运行：

假设GTest库已经安装在系统路径中，或者你知道其头文件和库文件的位置。

# 编译测试代码和被测试代码
g++ -std=c++11 add.cpp add_test.cpp -o add_test -I/path/to/googletest/include -L/path/to/googletest/lib -lgtest -lgtest_main -pthread

# 运行测试
./add_test

测试夹具 (Test Fixtures)：

当多个测试用例需要共享相同的设置（setup）和清理（teardown）代码时，可以使用测试夹具。通过继承 ::testing::Test 类并定义 SetUp() 和 TearDown() 方法来实现。

// 假设有一个 Calculator 类
class Calculator {
public:
    int add(int a, int b) { return a + b; }
    int subtract(int a, int b) { return a - b; }
};

// 定义测试夹具
class CalculatorTest : public ::testing::Test {
protected:
    // SetUp() 在每个测试用例运行前调用
    void SetUp() override {
        calc = new Calculator();
    }

    // TearDown() 在每个测试用例运行后调用
    void TearDown() override {
        delete calc;
        calc = nullptr;
    }

    Calculator* calc; // 在测试用例中共享的成员
};

// 使用 TEST_F 宏来使用测试夹具
TEST_F(CalculatorTest, AddPositiveNumbers) {
    EXPECT_EQ(5, calc->add(2, 3));
}

TEST_F(CalculatorTest, SubtractNumbers) {
    EXPECT_EQ(1, calc->subtract(3, 2));
}

总结： 单元测试是现代C++开发中不可或缺的一部分。通过使用像Google Test这样的测试框架，开发者可以有效地验证代码的正确性，提高软件质量，并为未来的维护和重构提供信心。养成编写单元测试的习惯是成为一名优秀C++开发者的重要一步。