面试真题 | 禾赛C++

面试开始

1. 自我介绍
   • 请简要介绍自己，包括教育背景、工作经验、技能特长等。

STL容器相关问题

2. STL有哪些容器？

   • 请列举并简要描述STL（标准模板库）中的容器类型。

3. 详细讲一下deque（双端队列）

   • 请详细描述deque的特性和用法，包括其底层实现、插入和删除操作的时间复杂度等。

4. 详细讲一下vector（动态数组）

   • 请详细描述vector的特性和用法，包括其内存管理、容量控制、迭代器失效等方面。

2. STL有哪些容器？

STL（标准模板库）中的容器可分为以下几大类：

（1）顺序容器

• vector：动态数组，支持快速随机访问，尾部插入/删除高效（O(1)），中间操作较慢（O(n)）。 • deque：双端队列，支持头尾高效插入/删除（O(1)），随机访问性能接近vector，但内存不连续。 • list：双向链表，任意位置插入/删除高效（O(1)），但不支持随机访问。 • string：类似vector<char>，专为字符串操作优化。

（2）关联容器（有序/无序）

• 有序关联容器（基于红黑树）： • set/multiset：唯一键/允许重复键的集合，自动排序。 • map/multimap：键值对映射，键唯一/允许重复。 • 无序关联容器（基于哈希表，C++11引入）： • unordered_set/unordered_multiset • unordered_map/unordered_multimap

（3）容器适配器

• stack：后进先出（LIFO），默认基于deque实现。 • queue：先进先出（FIFO），默认基于deque实现。 • priority_queue：优先级队列，默认基于vector实现堆结构。

3. 详细讲一下deque（双端队列）

特性与底层实现

1. 双端操作： • 支持push_front()和push_back()，头尾插入/删除时间复杂度为O(1)。
2. 底层结构： • 由多个固定大小的缓冲区（通常为512或1024字节）组成，通过指针链表连接，形成逻辑上的连续空间。 • 使用中央控制器（map）管理缓冲区指针，实现动态扩容。
3. 时间复杂度： • 随机访问：O(1)（通过计算偏移定位缓冲区）。 • 中间插入/删除：O(n)（需移动元素）。

1. 特性与底层实现

（1）双端操作特性
• 高效头尾操作：支持push_front()和push_back()，头尾插入/删除的时间复杂度为O(1)。
• 与vector对比：vector头部插入需移动所有元素（O(n)），而deque通过分段存储实现直接操作。

（2）底层结构
• 分段连续空间：
• deque由多个固定大小的缓冲区（如512或1024字节）组成，每个缓冲区存储一段连续数据。
• 逻辑连续：通过**中控器（map数组）**管理缓冲区指针，形成逻辑上的连续空间。map是一个二级指针数组，每个元素指向一个缓冲区。
• 动态扩容：
• 头部或尾部空间不足时，分配新缓冲区并更新map数组。
• 若map数组容量不足，会重新分配更大的map空间并拷贝旧指针。

（3）时间复杂度
• 随机访问：O(1)
• 通过计算元素在map中的位置和缓冲区内的偏移实现（例如：元素位置 = (索引 / 缓冲区大小)定位map指针，再取余定位缓冲区内位置）。
• 中间操作：O(n)
• 插入/删除需移动元素，效率低于头尾操作。

2. 迭代器设计与失效问题

（1）迭代器结构
• deque迭代器包含4个指针：
• cur：指向当前元素。
• first和last：标记当前缓冲区的起始和结束地址。
• node：指向map数组中对应的缓冲区指针（二级指针）。
• 跨缓冲区跳转：
• 当迭代器到达缓冲区边缘时，调用set_node()切换到相邻缓冲区。

（2）迭代器失效规则
• 插入操作：
• 头尾插入不导致扩容：仅影响当前缓冲区的迭代器。
• 插入导致map扩容：所有迭代器失效。
• 删除操作：
• 删除头尾元素：仅被删除元素的迭代器失效。
• 删除中间元素：所有指向被删除元素之后的迭代器失效。

3. 应用场景与性能对比

（1）适用场景
• 频繁头尾操作：如滑动窗口算法、队列/栈的默认实现。
• 随机访问需求：优于list，但弱于vector（因分段存储需额外计算）。

（2）与vector对比

特性dequevector

头插效率	O(1)	O(n)
内存连续性	逻辑连续，物理分散	完全连续
扩容开销	仅扩展map或新增缓冲区	整体拷贝，开销大

面试官可能的追问与答案

追问1：deque的缓冲区大小是固定的吗？如何决定？
• 答案：缓冲区大小通常由编译器决定（如GCC默认为512字节），但会根据元素类型调整。例如，存储int时可能为512/4=128元素/缓冲区。

追问2：deque的push_front()如何实现O(1)复杂度？
• 答案：在map数组头部预留空间，插入时直接使用空缓冲区；若无空间，扩展map数组并添加新缓冲区。

追问3：deque的迭代器为何需要四个指针？
• 答案：cur定位当前元素，first和last标记缓冲区边界，node维护与map数组的关联，确保跨缓冲区跳转时能快速定位。

总结

deque通过分段存储和中控器管理，在头尾操作和随机访问间取得了平衡。其底层设计复杂但高效，适合两端操作频繁且需随机访问的场景，但需注意迭代器失效规则和性能局限性。

迭代器失效

• 插入操作：若导致扩容（如头/尾部缓冲区不足），所有迭代器失效。 • 删除操作： • 删除头部/尾部元素：仅被删除元素的迭代器失效。 • 删除中间元素：所有指向被删除元素之后的迭代器失效。

应用场景

• 实现栈（stack）和队列（queue）的默认底层容器。 • 需要频繁在头尾增删数据的场景（如滑动窗口算法）。

4. 详细讲一下vector（动态数组）

特性与内存管理

1. 动态扩容： • 初始容量为0，插入元素时按2倍或编译器特定策略扩容。 • 扩容过程：分配新内存 → 拷贝旧元素 → 释放旧内存（时间复杂度O(n)）。
2. 内存连续性： • 元素在内存中连续存储，支持快速随机访问（O(1)）。
3. 容量控制： • size()：当前元素数量。 • capacity()：当前总容量。 • reserve(n)：预分配容量，避免多次扩容。

迭代器失效

• 插入操作： • 若引发扩容，所有迭代器失效（包括begin()和end()）。 • 未扩容时，插入点之后的迭代器失效。 • 删除操作： • erase()删除元素后，被删除元素之后的迭代器失效。

优化技巧

• 预分配内存：使用reserve()减少扩容次数。 • 避免中间插入：大量中间操作时优先考虑list或deque。 • 移动语义：对自定义类型实现移动构造函数，减少拷贝开销。

1. 动态扩容与内存管理

1. 扩容策略
   • 指数增长机制：当vector容量不足时，新容量通常为旧容量的 1.5倍或2倍（具体实现依赖编译器，如GCC默认2倍，MSVC默认1.5倍）。这种设计通过分摊时间复杂度（均摊O(1)）减少频繁扩容的开销。
   • 扩容过程：
   ◦ 分配新内存（如初始容量为0时首次插入分配1个元素空间）。
   ◦ 将旧元素拷贝或移动到新内存（若元素类型支持移动语义，可减少拷贝成本）。
   ◦ 释放旧内存，更新_Myfirst、_Mylast、_Myend指针（底层实现的三元组）。

2. 内存连续性优势
   • 随机访问O(1)：连续存储允许直接通过指针偏移访问元素，与元素数量无关。
   • 缓存友好性：连续内存布局提升CPU缓存命中率，性能显著优于链表（如访问1000个元素时，vector耗时0.02ms，list耗时15ms）。

3. 容量控制接口
   • reserve(n)：预分配至少容纳n个元素的内存，避免多次扩容（如插入100万元素时，预分配可减少约20次扩容）。
   • shrink_to_fit()：释放未使用的内存（非强制，依赖编译器实现）。

2. 迭代器失效的深层分析

• 插入操作：
• 触发扩容：所有迭代器、指针、引用均失效（因内存地址变更）。
• 未扩容：仅插入点之后的迭代器失效（元素后移导致逻辑位置变化）。
• 删除操作：
• erase()：被删除元素之后的迭代器失效（元素前移，但内存地址未变，逻辑位置需重新计算）。
• 安全操作建议：
• 插入/删除后重新获取迭代器（如erase()返回新迭代器）。
• 优先使用索引或back()/front()接口操作尾部/头部元素。

3. 性能优化技巧

1. 预分配与容量规划
   • 已知元素数量时，优先使用reserve()（如读取文件前预分配足够空间）。
   • 避免反复扩容（如频繁push_back()时，未预分配的vector插入1000个元素需10次扩容，预分配后仅1次）。

2. 操作位置选择
   • 尾部操作：push_back()/emplace_back()时间复杂度为均摊O(1)。
   • 中间操作：插入/删除需移动元素，时间复杂度O(n)（如删除第3个元素需移动后续n-3个元素）。

3. 高效构造与移动语义
   • 使用emplace_back()替代push_back()：直接构造元素，避免临时对象拷贝（如emplace_back("text", 5)直接调用构造函数）。
   • 为自定义类型实现移动构造函数：减少深拷贝开销（如vector<Matrix>中移动大矩阵对象）。

4. 与其他容器的对比

特性vectorlistdeque

随机访问	O(1)（连续内存）	不支持（需遍历）	O(1)（分段连续）
尾部插入	均摊O(1)	O(1)	O(1)
中间插入	O(n)（元素移动）	O(1)（链表节点操作）	O(n)（元素移动）
内存连续性	完全连续	不连续	逻辑连续，物理分段

5. 面试官可能的追问与答案

追问1：为什么vector选择1.5倍而非2倍扩容？
• 答案：1.5倍扩容（黄金分割比例）允许复用之前释放的内存块（如扩容到9后，可复用之前释放的6和3的空间），而2倍扩容会导致旧内存块永远无法复用，造成内存碎片。

追问2：emplace_back()和push_back()有何本质区别？
• 答案：emplace_back()通过完美转发直接调用构造函数，避免临时对象的构造和拷贝；push_back()需先构造临时对象，再拷贝或移动到容器中。

追问3：如何避免vector扩容时的性能抖动？
• 答案：

1. 预分配足够容量（reserve()）。
2. 使用noexcept移动构造函数减少元素迁移开销。
3. 优先存储轻量对象（如指针而非大型结构体）。

总结

vector通过动态扩容、连续内存布局和高效接口，成为C++中最通用的容器。其核心优化方向包括：预分配内存减少扩容、避免中间操作、利用移动语义降低拷贝开销。理解其底层机制（如1.5倍扩容的数学原理）和迭代器失效规则，是写出高性能代码的关键。

面试官可能的追问与答案

追问1：deque如何实现高效的头部插入？与vector有何区别？

• 答案：deque的底层由多个缓冲区组成，头部插入只需在第一个缓冲区未满时直接操作，无需移动其他元素。而vector头部插入需移动所有元素（O(n)）。

追问2：vector的resize()和reserve()有何区别？

• 答案： • reserve(n)：仅预分配容量，不改变元素数量。 • resize(n)：调整元素数量，若n > size()则填充默认值；若n < size()则删除多余元素。

追问3：如何避免vector迭代器失效？

• 答案： • 插入/删除后重新获取迭代器（如使用erase()返回的新迭代器）。 • 使用索引替代迭代器（如for (int i=0; i<v.size(); i++)）。

总结

• STL容器选择原则：根据操作频率（头/尾/随机访问）和内存需求选择，例如： • 频繁随机访问 → vector。 • 频繁头尾操作 → deque。 • 频繁中间插入 → list。 • 性能关键点：理解底层实现（如deque的分段数组、vector的动态扩容）是优化代码的基础。

面向对象编程相关问题

5. 讲一下继承和多态
   • 请解释继承和多态的概念，并给出具体的C++代码示例。
   • 描述继承和多态在面向对象编程中的作用和优势。

1. 继承（Inheritance）

概念
继承是面向对象编程的核心机制，允许子类（派生类）基于父类（基类）扩展功能，共享父类的属性和方法，同时新增或修改特性。其核心是代码复用和层次化设计。
• 代码复用：子类继承父类的公共成员，避免重复编写代码。
• 扩展性：子类可添加新成员或重写父类方法，实现功能扩展。

C++代码示例

#include <iostream>
using namespace std;

// 基类：动物
class Animal {
protected:
    string name;
public:
    Animal(const string& n) : name(n) {}
    void eat() { cout << name << " is eating." << endl; }
};

// 派生类：狗
class Dog : public Animal {
public:
    Dog(const string& n) : Animal(n) {} // 显式调用基类构造函数
    void bark() { cout << name << " says Woof!" << endl; } // 扩展新方法
};

int main() {
    Dog dog("Rex");
    dog.eat();  // 继承自Animal
    dog.bark(); // 子类新增方法
    return 0;
}

作用与优势
• 共性抽取：将公共属性和方法抽象到基类（如Animal的name和eat()），减少冗余代码。
• 层次化设计：通过派生类（如Dog、Cat）构建类层次结构，增强代码可读性和维护性。

2. 多态（Polymorphism）

概念
多态允许不同类型的对象对同一消息（方法调用）产生不同响应，核心是动态绑定（运行时确定调用的方法）。
• 编译时多态：通过函数重载和模板实现。
• 运行时多态：通过虚函数（virtual）和继承实现，是面向对象的关键特性。

C++代码示例

#include <iostream>
using namespace std;

// 基类：形状（抽象类）
class Shape {
public:
    virtual void draw() = 0; // 纯虚函数，强制派生类实现
};

class Circle : public Shape {
public:
    void draw() override { cout << "Drawing a circle." << endl; } // 重写虚函数
};

class Square : public Shape {
public:
    void draw() override { cout << "Drawing a square." << endl; }
};

int main() {
    Shape* shapes[] = { new Circle(), new Square() };
    for (auto shape : shapes) {
        shape->draw(); // 动态绑定：根据对象类型调用不同方法
    }
    return 0;
}

作用与优势
• 接口统一：通过基类指针或引用操作不同派生类对象，简化代码逻辑（如遍历Shape数组调用draw()）。
• 扩展灵活：新增派生类（如Triangle）无需修改现有代码，只需实现虚函数。

3. 继承与多态的结合应用

场景示例
在GUI开发中，基类Widget定义虚方法render()，派生类Button、TextBox重写该方法实现不同渲染逻辑。通过多态，所有控件可通过统一的Widget*指针管理。

优势
• 解耦合：业务逻辑与具体实现分离（如Shape无需关心Circle或Square的细节）。
• 可维护性：修改派生类不影响基类和其他派生类。

4. 常见问题与注意事项

1. 虚函数与动态绑定
   • 必须使用virtual关键字声明虚函数，否则无法实现多态。
   • 派生类重写虚函数时建议添加override关键字，提高代码可读性并避免错误。

2. 对象切片（Slicing）
   • 将派生类对象赋值给基类对象时，会丢失派生类特有成员。应使用指针或引用传递对象。

3. 构造与析构顺序
   • 构造顺序：基类 → 派生类；析构顺序：派生类 → 基类。
   • 基类析构函数应声明为虚函数，确保正确释放派生类资源。

总结

继承与多态是面向对象编程的基石：
• 通过代码复用和层次化设计提升开发效率； • 通过动态绑定和接口统一增强系统灵活性和扩展性。 结合使用二者（如虚函数重写）可构建高度模块化、易维护的软件架构。