小米C++开发，校招二面

公众号：阿Q技术站

来源：https://www.nowcoder.com/feed/main/detail/e584c8b5d5e74f1faf8e8b9cc033dae2

1、智能指针用过没有，说一下？

std::shared_ptr：
- 原理：std::shared_ptr是基于引用计数的智能指针，用于管理动态分配的对象。它维护一个引用计数，当计数为零时，释放对象的内存。
- 使用场景：适用于多个智能指针需要共享同一块内存的情况。例如，在多个对象之间共享某个资源或数据。
```
std::shared_ptr<int> sharedInt = std::make_shared<int>(42);
std::shared_ptr<int> anotherSharedInt = sharedInt; // 共享同一块内存
```
std::unique_ptr：
- 原理：std::unique_ptr是独占式智能指针，意味着它独占拥有所管理的对象，当其生命周期结束时，对象会被自动销毁。
- 使用场景：适用于不需要多个指针共享同一块内存的情况，即单一所有权。通常用于资源管理，例如动态分配的对象或文件句柄。
```
std::unique_ptr<int> uniqueInt = std::make_unique<int>(42);
// uniqueInt 的所有权是唯一的
```
std::weak_ptr：
- 原理：std::weak_ptr是一种弱引用指针，它不增加引用计数。它通常用于协助std::shared_ptr，以避免循环引用问题。
- 使用场景：适用于协助解决std::shared_ptr的循环引用问题，其中多个shared_ptr互相引用，导致内存泄漏。
```
std::shared_ptr<int> sharedInt = std::make_shared<int>(42);
std::weak_ptr<int> weakInt = sharedInt;
```
std::auto_ptr（已废弃）：
- 原理：std::auto_ptr是C++98标准引入的智能指针，用于独占地管理对象。但由于其存在潜在的问题，已在C++11中被废弃。
- 使用场景：在C++98标准中，可用于独占性地管理动态分配的对象。不推荐在现代C++中使用。
```
std::auto_ptr<int> autoInt(new int(42)); // 已废弃
```

2、析构函数设置成虚函数的原因？

将析构函数设置为虚函数的主要原因是为了确保在使用基类指针或引用指向派生类对象时，能够正确地调用到派生类的析构函数，从而避免内存泄漏和资源泄漏的问题。

在面向对象的编程中，通常会使用基类指针或引用来管理派生类对象，这种情况下，如果基类的析构函数不是虚函数，那么当删除基类指针指向的派生类对象时，只会调用基类的析构函数，而不会调用派生类的析构函数，导致派生类中的资源得不到释放，造成内存泄漏。

通过将基类的析构函数设置为虚函数，可以在删除基类指针指向的对象时，根据对象的实际类型来调用相应的析构函数，确保派生类的析构函数被正确地调用，从而释放对象占用的资源，避免内存泄漏问题。

3、vector的扩容机制？

初始容量：当创建一个空的 std::vector 对象时，它的初始容量为 0。
添加元素：当向 std::vector 中添加元素时，如果当前元素数量小于容量（即 size() < capacity()），则直接在已分配的内存空间中添加元素；如果当前元素数量等于容量，则需要进行扩容。
扩容：扩容操作会申请一块新的内存空间，一般是当前容量的两倍，并将原有的元素复制到新的内存空间中，然后释放原有的内存空间。这个过程可能会导致迭代器、引用和指针失效。
内存分配器：std::vector 使用的内存分配器是 std::allocator，它是一个模板类，可以根据需要进行自定义。
控制扩容策略：可以使用 reserve() 方法预先分配一定大小的内存空间，以减少扩容操作的次数。也可以使用 shrink_to_fit() 方法要求释放多余的内存空间。

4、既然你知道vector扩容会把之前的内容复制一份放到新空间，那么如何节省这一部分开销？

预分配足够的空间：在向 std::vector 中添加大量元素之前，可以使用 reserve() 方法预先分配足够的内存空间，避免多次扩容。这样可以减少扩容操作的次数，提高性能。
使用适当的容量增长策略：std::vector 的容量增长策略是当前容量的两倍，这在大多数情况下是合理的。但是如果知道要添加的元素数量可以估算出一个比较精确的值，可以使用 reserve() 方法一次性分配足够的内存空间，避免多次扩容。
避免不必要的拷贝：在进行元素的插入、删除等操作时，尽量使用移动语义（move semantics）而不是拷贝操作，避免不必要的拷贝构造和析构操作，提高性能。
使用 emplace_back() 函数：emplace_back() 函数可以直接在 std::vector 的末尾构造元素，避免了拷贝构造的开销。如果可以直接构造元素而不是先创建临时对象再拷贝到容器中，可以提高性能。

5、vector的capacity和resize说说？

capacity() 函数：返回当前向量的容量，即向量可以容纳的元素个数，而不是当前实际存储的元素个数。向量的容量是动态调整的，当添加元素时，如果当前容量不足，会自动扩容。
resize() 函数：用于改变向量的大小，可以增加或减少向量中的元素个数。具体使用方式如下：
- 如果新的大小小于当前大小，则会删除末尾多余的元素，即截断向量。
- 如果新的大小大于当前大小，则会在末尾添加足够数量的默认构造的元素，使向量的大小达到新的大小。

std::vector<int> vec = {1, 2, 3, 4, 5};vec.resize(3); // 缩减大小，vec = {1, 2, 3}
vec.resize(5); // 扩展大小，vec = {1, 2, 3, 0, 0}

6、map和unordered_map的区别？

底层实现：
- std::map 基于红黑树（Red-Black Tree）实现，保证了元素的有序性，插入、删除和查找操作的时间复杂度都是 O(log n)。
- std::unordered_map 基于哈希表（Hash Table）实现，元素的存储顺序不固定，插入、删除和查找操作的平均时间复杂度是 O(1)，最坏情况下是 O(n)。
有序性：
- std::map 中的元素是按照键的大小顺序进行存储的，因此遍历时可以按照键的顺序访问元素。
- std::unordered_map 中的元素存储顺序与插入顺序无关，因此遍历时不能保证元素的顺序。
查找性能：
- std::map 在有序性的基础上提供了快速的查找操作，适用于需要按照键的顺序访问元素的场景。
- std::unordered_map 在无序性的基础上提供了更快的查找操作，适用于不需要保持元素顺序的场景。
内存占用：
- std::map 在存储元素时需要额外的空间来维护红黑树结构，因此占用的内存通常比较大。
- std::unordered_map 在存储元素时只需要考虑哈希表的大小，通常情况下比 std::map 占用的内存更少。
元素比较：
- std::map 使用键类型的比较函数或者默认的 < 操作符来比较元素的大小。
- std::unordered_map 使用键类型的哈希函数和相等比较函数来确定元素的位置。

7、对于已知大小的数据，用map和unordered_map哪一个更省内存？

对于已知大小的数据，使用 std::array 或 std::vector 都比 std::map 和 std::unordered_map 更省内存。这是因为 std::map 和 std::unordered_map 都需要额外的内存来存储键和值之间的关联关系，而 std::array 和 std::vector 只需要存储元素本身。

std::map 和 std::unordered_map 的话，一般情况下 std::unordered_map 更省内存。因为 std::unordered_map 使用哈希表实现，不需要维护元素的顺序，也不需要存储额外的红黑树节点信息。而 std::map 使用红黑树实现，需要存储额外的节点信息来维护元素的有序性。

但是在实际使用中，这个差别可能并不明显，而且在一些特殊情况下，std::map 可能比 std::unordered_map 更省内存。例如，如果 std::unordered_map 中的哈希表负载因子较高，可能会导致内存占用增加；而 std::map 的内存占用是固定的，与元素数量无关。所以在选择容器时，还是要根据具体的场景和需求来进行选择。

8、说一说queue，deque，priority_queue？

queue：
- queue 是一个先进先出（FIFO）的容器，类似于现实生活中的排队。
- 底层一般使用 deque 或 list 实现。
- 只能从队尾插入元素，从队头移除元素。
deque：
- deque 是双端队列（Double-Ended Queue）的缩写，支持在两端高效地插入和删除元素。
- 可以像 vector 一样随机访问元素，但在两端插入和删除元素的操作比 vector 更高效。
- deque 内部是由多个分段（chunk）组成的，每个分段可以存储多个元素，这样可以减少元素移动的次数，提高性能。
priority_queue：
- priority_queue 是一个优先级队列，元素按照一定的优先级顺序排列，而不是按照插入顺序。
- 通常使用 vector 或 deque 作为底层容器，同时还需要指定一个比较函数来确定元素的优先级顺序。
- 默认情况下，priority_queue 是大顶堆，即优先级最高的元素在队首。可以通过自定义比较函数来实现小顶堆。

9、说一说list？

双向链表：std::list 内部实现为双向链表，每个节点包含指向前一个节点和后一个节点的指针，因此可以高效地在任意位置插入和删除元素。
无需移动元素：由于链表的特性，插入和删除操作不需要移动其他元素，只需要调整节点的指针，因此在插入和删除操作频繁的场景下，std::list 比 std::vector 更高效。
不支持随机访问：由于链表不具备随机访问的特性，无法像 std::vector 那样通过下标快速访问元素，只能通过迭代器逐个访问元素。
高效的插入和删除：在链表中，插入和删除操作的时间复杂度为 O(1)，而在 std::vector 中，插入和删除操作的时间复杂度为 O(n)，因为需要移动元素。
内存分配：每个元素在链表中都是独立分配内存的，因此在频繁插入和删除大量元素时，可能会导致内存碎片问题。
迭代器失效：由于插入和删除操作可能会导致链表结构的改变，因此在插入和删除操作后，之前获取的迭代器可能会失效，需要重新获取。

10、模板底层了解过吗？

模板实例化：模板本身并不是一个真正的函数或类，而是一个模板的描述。当我们在代码中使用模板时，编译器会根据模板的描述生成具体的函数或类的实例，这个过程称为模板实例化。例如，当我们使用 std::vector<int> 时，编译器会根据 std::vector 的模板描述生成一个 std::vector<int> 的具体实现。
模板实参推导：在使用模板时，有时候我们并不需要显式地指定模板参数，编译器可以根据函数参数或表达式的类型推导出模板参数的类型，这个过程称为模板实参推导。例如，对于一个模板函数 template<typename T> void foo(T t)，我们可以调用 foo(42)，编译器会推导出 T 的类型为 int。
模板函数的链接：模板函数的实现通常放在头文件中，因为编译器需要在每个使用该模板的地方生成相应的实例。这意味着模板函数的定义会被包含在每个使用的源文件中，因此需要注意模板函数的链接问题，以避免多重定义错误。
模板的特化和偏特化：模板可以根据特定的模板参数进行特化，即提供针对特定类型或值的特殊实现。特化分为全特化和偏特化两种。全特化是指对所有模板参数进行特化，而偏特化是指对部分模板参数进行特化。

11、手撕题目：给了一幅图，求最大的岛屿面积

问题描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

思路

创建一个函数 dfs，用于深度优先搜索岛屿面积。函数参数包括当前位置 (i, j)，以及当前岛屿的面积。
在 dfs 函数中，首先判断当前位置是否越界或者当前位置的值是否为 0，如果是则返回 0。
如果当前位置的值为 1，则将当前位置的值置为 0，表示已经访问过。然后分别向当前位置的上、下、左、右四个方向继续进行深度优先搜索，将结果相加，即为当前岛屿的面积。
在遍历整个二维矩阵的过程中，每当遇到值为 1 的位置，即岛屿的起始位置，就调用 dfs 函数计算当前岛屿的面积，并与之前的最大岛屿面积进行比较，更新最大岛屿面积。
最后返回最大岛屿面积。

参考代码

C++

#include <vector>
#include <iostream>
using namespace std;class Solution {
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int maxArea = 0;  // 最大岛屿面积int m = grid.size();  // 矩阵的行数int n = grid[0].size();  // 矩阵的列数// 遍历整个二维矩阵for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1) {int area = dfs(grid, i, j);  // 以当前格子为起点进行DFS，统计岛屿面积maxArea = max(maxArea, area);  // 更新最大岛屿面积}}}return maxArea;}private:// 深度优先搜索int dfs(vector<vector<int>>& grid, int i, int j) {// 越界或者当前格子为水（值为0），返回面积为0if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {return 0;}// 将当前格子标记为0，防止重复访问grid[i][j] = 0;// 统计当前格子的面积，并继续向四个方向搜索return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);}
};int main() {vector<vector<int>> grid = {{1, 1, 0, 0, 0},{1, 1, 0, 0, 0},{0, 0, 0, 1, 1},{0, 0, 0, 1, 1}};Solution s;cout << s.maxAreaOfIsland(grid) << endl;  // 输出最大岛屿面积为 4return 0;
}