杭州信核 C++ 软件开发 一面 面经

1. 什么是指针？指针的本质是什么？

答案：

指针是一个变量，它存储的是另一个变量的内存地址。指针的本质是内存地址，通过地址可以直接访问和操作内存中的数据。

指针的特点：指针本身占用内存空间，在32位系统中占4字节，64位系统中占8字节。指针有类型，不同类型的指针决定了如何解释内存中的数据以及指针运算的步长。指针可以进行算术运算，如加减整数，移动到相邻的内存位置。

指针的用途：动态内存分配，使用new或malloc在堆上分配内存。函数参数传递，通过指针传递可以修改原始数据，避免大对象的拷贝。数组和字符串操作，数组名本质上是指向首元素的指针。实现复杂数据结构，如链表、树、图等需要指针连接节点。

指针的危险性：野指针，指向未知或已释放的内存，访问会导致程序崩溃。空指针解引用，访问空指针会导致段错误。内存泄漏，动态分配的内存未释放。缓冲区溢出，指针越界访问导致安全问题。

2. 什么是空指针和野指针？如何避免？

答案：

空指针（Null Pointer）：

空指针是不指向任何有效内存地址的指针，值为nullptr（C++11）或NULL（C++98）或0。空指针是一种安全的状态，表示指针当前不指向任何对象。解引用空指针会导致程序崩溃，但这是可预测和可检测的错误。

使用场景：初始化指针时，如果暂时不指向任何对象，应该初始化为nullptr。函数返回值，表示操作失败或未找到对象。判断指针是否有效，使用if(ptr != nullptr)检查。

野指针（Dangling Pointer）：

野指针是指向已经释放或无效内存的指针，这是最危险的指针类型。产生原因：指针指向的内存被释放后，指针未置空。指针指向局部变量，函数返回后局部变量被销毁。指针未初始化，包含随机值。

野指针的危险：访问野指针可能不会立即崩溃，而是读取到错误数据。可能破坏其他数据，导致难以调试的bug。可能被恶意利用，造成安全漏洞。

如何避免空指针和野指针：

指针初始化，声明指针时立即初始化为nullptr或有效地址。释放后置空，delete或free后立即将指针设为nullptr。使用智能指针，unique_ptr和shared_ptr自动管理内存，避免野指针。检查指针有效性，使用前检查指针是否为nullptr。避免返回局部变量地址，不要返回指向栈上对象的指针。使用引用代替指针，引用必须初始化且不能为空，更安全。

3. C++有哪几种智能指针？它们的区别是什么？

答案：

C++11引入了三种智能指针：unique_ptr、shared_ptr、weak_ptr，用于自动管理动态内存。

unique_ptr（独占所有权）：

同一时刻只能有一个unique_ptr指向某个对象，不能拷贝只能移动。当unique_ptr被销毁时，它所指向的对象也会被自动删除。性能开销最小，没有引用计数的开销。适用于明确对象只有一个所有者的场景，这是最推荐使用的智能指针。

shared_ptr（共享所有权）：

允许多个shared_ptr指向同一个对象，内部维护引用计数。每次拷贝引用计数加1，每次析构引用计数减1，当引用计数归零时删除对象。引用计数使用原子操作，保证线程安全但有性能开销。适用于对象需要被多个地方共享的场景。

注意事项：循环引用会导致内存泄漏，需要用weak_ptr打破循环。不要用同一个裸指针初始化多个shared_ptr，会导致重复释放。shared_ptr有两次内存分配的开销，一次是对象本身，一次是控制块。

weak_ptr（弱引用）：

不增加引用计数的智能指针，用于打破shared_ptr的循环引用。不能直接访问对象，需要先通过lock()转换为shared_ptr。可以检测对象是否还存在，expired()返回对象是否已被销毁。适用于观察者模式、缓存系统等需要弱引用的场景。

三者的对比：

所有权：unique_ptr独占，shared_ptr共享，weak_ptr不拥有。拷贝：unique_ptr不可拷贝只能移动，shared_ptr可拷贝，weak_ptr可拷贝。性能：unique_ptr最快，shared_ptr有引用计数开销，weak_ptr类似shared_ptr。

使用建议：

默认使用unique_ptr，只在确实需要共享所有权时使用shared_ptr。避免使用裸指针管理动态内存。注意shared_ptr的循环引用问题，必要时使用weak_ptr。不要混用智能指针和裸指针管理同一对象。

4. vector的底层实现是怎样的？有哪些重要属性？

答案：

vector是动态数组，底层使用连续的内存空间存储元素。

底层实现：

使用三个指针管理内存：start指向数组的起始位置，finish指向最后一个元素的下一个位置，end_of_storage指向分配内存的末尾。实际存储的元素在start到finish之间，finish到end_of_storage是预留的空间。

内存布局：元素在内存中连续存储，支持随机访问，时间复杂度O(1)。插入和删除可能需要移动元素，时间复杂度O(n)。尾部插入删除效率高，如果有预留空间则是O(1)。

重要属性和方法：

size()：返回当前元素个数，等于finish - start。capacity()：返回当前分配的容量，等于end_of_storage - start。empty()：判断是否为空，等价于size() == 0。max_size()：返回理论上的最大元素个数。

reserve(n)：预留至少n个元素的空间，不改变size，只改变capacity。resize(n)：改变元素个数为n，如果n大于当前size则填充默认值，如果n小于当前size则删除多余元素。shrink_to_fit()：释放多余的容量，使capacity等于size。

push_back()：在尾部添加元素，可能触发扩容。pop_back()：删除尾部元素，不会缩小容量。insert()：在指定位置插入元素，需要移动后续元素。erase()：删除指定位置或范围的元素，需要移动后续元素。

5. vector的size和capacity有什么区别？

答案：

size和capacity是vector的两个重要概念，经常被混淆。

size（大小）：

表示vector中当前实际存储的元素个数。通过size()方法获取。每次push_back、insert、erase等操作都会改变size。size可以为0，表示空vector。

capacity（容量）：

表示vector当前分配的内存可以容纳的元素个数。通过capacity()方法获取。capacity总是大于或等于size。capacity不会因为删除元素而减小，除非显式调用shrink_to_fit()。

两者的关系：

size <= capacity始终成立。当size < capacity时，有预留空间，push_back不需要重新分配内存。当size == capacity时，没有预留空间，push_back会触发扩容。

为什么需要capacity：

避免频繁的内存分配，内存分配是昂贵的操作。预留空间可以提高性能，尤其是频繁插入元素时。通过reserve()预分配空间，可以避免多次扩容。

实际应用：

如果知道大概需要多少元素，使用reserve()预分配空间。频繁插入删除时，capacity可能远大于size，造成内存浪费，可以用shrink_to_fit()释放多余空间。size()是O(1)操作，capacity()也是O(1)操作。

6. vector的扩容机制是怎样的？

答案：

vector的扩容机制是为了在动态增长时平衡性能和内存使用。

扩容的触发条件：

当size等于capacity时，再次push_back或insert会触发扩容。扩容时需要重新分配更大的内存空间。

扩容的过程：

分配新的更大的内存空间，通常是当前容量的1.5倍或2倍（不同实现可能不同）。将原有元素拷贝或移动到新空间。释放原有的内存空间。更新start、finish、end_of_storage指针。

扩容倍数的选择：

GCC的实现通常是2倍扩容。MSVC的实现通常是1.5倍扩容。2倍扩容增长更快，但可能浪费更多内存。1.5倍扩容更节省内存，但可能需要更多次扩容。

扩容的性能分析：

单次扩容的时间复杂度是O(n)，需要拷贝所有元素。但均摊时间复杂度是O(1)，因为扩容次数是对数级别的。n次push_back操作的总时间复杂度是O(n)。

扩容的代价：

内存分配和释放的开销。元素的拷贝或移动开销。可能导致迭代器、指针、引用失效。可能导致内存碎片。

7. 如何避免vector的多次扩容？

答案：

频繁扩容会影响性能，可以通过以下方法避免：

使用reserve()预分配空间：

如果知道大概需要多少元素，提前调用reserve(n)预分配空间。reserve()只改变capacity，不改变size，不会构造元素。预分配后，在容量范围内的push_back不会触发扩容。

使用resize()预设大小：

resize(n)会改变size为n，如果n大于当前size会构造新元素。resize()后可以直接通过下标访问元素，不需要push_back。适合知道确切元素个数的场景。

使用emplace_back代替push_back：

emplace_back直接在容器中构造元素，避免临时对象的创建和移动。虽然不能避免扩容，但可以减少元素构造的开销。

批量插入：

使用insert()的范围版本一次插入多个元素，vector可以一次性分配足够的空间。比多次push_back效率更高。

选择合适的初始容量：

构造vector时可以指定初始大小或容量。根据实际需求选择合理的初始值。

实际建议：

性能关键的代码中，尽量使用reserve()预分配。如果无法预知大小，可以根据经验值预分配一个合理的容量。监控vector的扩容次数，优化预分配策略。

8. 什么是迭代器失效？什么情况下会发生？

答案：

迭代器失效是指迭代器指向的元素被删除或容器结构改变，导致迭代器不再有效，使用失效的迭代器会导致未定义行为。

vector的迭代器失效情况：

插入元素：如果插入导致扩容，所有迭代器都会失效，因为元素被移动到新内存。如果插入不导致扩容，插入点及之后的迭代器失效，因为元素被移动。

删除元素：被删除元素及之后的迭代器失效，因为后续元素前移。erase()返回下一个有效的迭代器，应该使用返回值更新迭代器。

赋值操作：operator=会使所有迭代器失效。

clear()：清空容器，所有迭代器失效。

其他容器的迭代器失效：

list：插入和删除只影响被操作的元素，其他迭代器不失效。deque：插入删除首尾元素，只有首尾迭代器失效；中间插入删除，所有迭代器失效。map/set：插入不影响其他迭代器，删除只影响被删除元素的迭代器。

如何避免迭代器失效：

删除元素时使用erase()的返回值更新迭代器。避免在遍历时修改容器，或者使用索引而不是迭代器。插入前使用reserve()预分配空间，避免扩容导致的失效。使用容器的成员函数而不是算法，如vector的erase而不是std::remove。

正确的删除方式：

错误方式：在循环中erase后继续使用原迭代器。正确方式：使用erase的返回值更新迭代器，或者使用erase-remove惯用法。

9. 二叉树的节点数如何计算？中序遍历的顺序是什么？

答案：

二叉树节点数的计算：

递归方法：节点数等于1（当前节点）加上左子树节点数加上右子树节点数。递归终止条件：空节点的节点数为0。时间复杂度O(n)，需要遍历所有节点。空间复杂度O(h)，h是树的高度，递归调用栈的深度。

层序遍历方法：使用队列进行层序遍历，统计遍历的节点个数。时间复杂度O(n)，空间复杂度O(w)，w是树的最大宽度。

特殊二叉树的节点数：

满二叉树：深度为h的满二叉树节点数为2^h - 1。完全二叉树：可以通过最后一层的节点数计算总节点数。

中序遍历的顺序：

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。对于二叉搜索树，中序遍历的结果是有序序列。

递归实现：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。非递归实现：使用栈模拟递归过程，先将左子树的所有节点入栈，然后依次出栈访问并处理右子树。

中序遍历的应用：

二叉搜索树的排序：中序遍历BST得到有序序列。验证BST：检查中序遍历是否严格递增。查找第k小的元素：中序遍历到第k个节点。

其他遍历方式：

前序遍历：根节点 -> 左子树 -> 右子树，用于复制树结构。后序遍历：左子树 -> 右子树 -> 根节点，用于删除树或计算表达式。层序遍历：按层从上到下、从左到右遍历，使用队列实现。

10. 进程和线程的区别是什么？

答案：

进程是资源分配的基本单位，线程是CPU调度的基本单位。

资源占用：

进程拥有独立的地址空间，包括代码段、数据段、堆、栈。线程共享进程的地址空间，但每个线程有独立的栈和寄存器。进程间资源隔离，线程间资源共享。

创建和切换开销：

进程创建需要分配独立的地址空间，开销大。线程创建只需要分配栈空间，开销小。进程切换需要切换页表和地址空间，开销大。线程切换只需要切换栈和寄存器，开销小。

通信方式：

进程间通信需要IPC机制