【C++ 八股文】（篇二）：类与数据抽象 STL 容器与算法

这一篇把两块高频考点放在一起：类与数据抽象（继承、组合、构造析构、成员初始化列表、虚函数限制）和STL 容器与算法（六大组件、allocator、vector/list/deque、map/set、迭代器失效）。

一、类和数据抽象

1. 什么是类的继承？

类与类之间的关系

面向对象里，类与类之间大致有三种关系：

继承的相关概念

所谓的继承就是一个类继承了另一个类的属性和方法。这个新的类包含了上一个类的属性和方法，被称为子类（派生类）；被继承的类称为父类（基类）。

class Base { public: void func() { /* ... */ } protected: int prot_; private: int priv_; }; // Derived 继承自 Base，is-A 关系 class Derived : public Base { public: void newFunc() { /* ... */ } };

继承的特点

1. 子类拥有父类的属性和方法；

2. 子类可以拥有父类没有的属性和方法；

3. 子类对象可以当做父类对象使用（即后文说的兼容性原则）。

继承中的访问控制

三种继承方式会改变基类成员在派生类中的可见性：

记忆方法：继承方式只会“降级”，不会“升级”；private成员无论怎么继承都不可直接访问。

继承中的构造和析构函数

• 构造顺序：基类构造函数 → 成员对象构造函数（按声明顺序）→ 派生类构造函数体；

• 析构顺序与构造顺序完全相反：派生类析构 → 成员对象析构 → 基类析构；

• 基类构造函数不会被继承，派生类需要在初始化列表里显式调用；

• 基类析构函数应声明为virtual，否则通过基类指针delete派生类对象时，派生类的析构函数不会被调用，造成资源泄漏。

class Base { public: Base() { std::cout << "Base()\n"; } virtual ~Base() { std::cout << "~Base()\n"; } // 多态基类必须有虚析构 }; class Derived : public Base { public: Derived() : Base() { std::cout << "Derived()\n"; } ~Derived() override { std::cout << "~Derived()\n"; } };

继承中的兼容性原则

兼容性原则（也叫向上转型、is-A 原则）指：

• 派生类对象可以赋值给基类对象（会发生对象切片，slicing）；

• 派生类对象的地址可以赋给指向基类的指针；

• 派生类对象可以初始化基类的引用。

Derived d; Base b = d; // 对象切片：只保留基类部分 Base* p = &d; // 合法，通过 p 只能访问基类接口 Base& r = d; // 合法 // 反方向不行：基类对象不能直接赋给派生类对象

有了兼容性原则，才能用基类指针/引用 + 虚函数实现运行期多态。

2. 什么是组合？

一个类里面的数据成员是另一个类的对象，即内嵌其他类的对象作为自己的成员，这就叫组合（composition）。

创建组合类的对象：首先要创建各个内嵌对象，难点在于构造函数的设计。创建对象时既要对基本类型的成员进行初始化，又要对内嵌对象进行初始化。

组合类对象的构造顺序：

1. 先调用内嵌对象的构造函数；

2. 顺序按内嵌对象成员在组合类中的定义顺序，与组合类构造函数初始化列表中的书写顺序无关；

3. 然后执行组合类构造函数的函数体；

4. 析构函数的调用顺序完全相反。

class Engine { public: Engine(int hp) { std::cout << "Engine(" << hp << ")\n"; } ~Engine() { std::cout << "~Engine()\n"; } }; class Car { public: // 初始化列表写成 engine_ 在后也没用，实际顺序看声明顺序 Car() : brand_("Benz"), engine_(200) { std::cout << "Car()\n"; } ~Car() { std::cout << "~Car()\n"; } private: std::string brand_; Engine engine_; // 先于 brand_？不，brand_ 先声明，所以 brand_ 先构造 };

输出顺序为：brand_→Engine(200)→Car()；析构时反过来。

总结：构造从内到外（先成员后自身）、从父到子；析构从外到内、从子到父。

3. 构造函数、析构函数可否抛出异常？

构造函数

C++ 只会析构已经完成的对象，对象只有在其构造函数执行完毕才算是完全构造妥当。在构造函数中发生异常，控制权转出构造函数之外。因此，在对象 b 的构造函数中发生异常，对象 b 的析构函数不会被调用，因此可能造成内存泄漏。

解决办法：

• 用智能指针（如std::unique_ptr，早期是auto_ptr）对象来取代裸指针类成员，便对构造函数做了强化，免除了抛出异常时发生资源泄漏的危机，也不再需要在析构函数中手动释放资源；

• 或者遵循RAII：资源交给成员对象的析构函数管理，而不是写在构造函数体里。

class Widget { public: Widget() : data_(new int[100]) { /* 若此处抛异常，data_ 会被自动释放 */ } private: std::unique_ptr<int[]> data_; // RAII：异常安全 };

析构函数

• 如果控制权基于异常的因素离开析构函数，而此时正有另一个异常处于作用状态，C++ 会调用terminate函数让程序结束；

• 如果异常从析构函数抛出，而且没有在当地进行捕捉，那个析构函数便是执行不全的。如果析构函数执行不全，就是没有完成它应该执行的每一件事情。

结论：析构函数应当默认声明为noexcept，绝不让异常逃出析构函数；必须在析构函数里做的清理动作要自己try/catch吞掉异常。

4. 类如何实现只能静态分配和只能动态分配？

先看建立类对象的两种方式：

• 静态建立：由编译器为对象在栈空间中分配内存，如A a;

• 动态建立：A* p = new A();，使用new运算符为对象在堆空间中分配内存。这个过程分两步：

  1. 执行operator new()函数，在堆中搜索一块内存并进行分配；

  2. 调用类构造函数构造对象。

只能静态分配（对象只能建在栈上）

只有使用new运算符，对象才会被建立在堆上，因此只要限制new运算符就可以实现类对象只能建立在栈上：把new、delete运算符重载为private。

class StackOnly { public: StackOnly() {} ~StackOnly() {} private: static void* operator new(size_t); // 禁止 new static void operator delete(void*); // 禁止 delete };

只能动态分配（对象只能建在堆上）

把构造、析构函数设为protected，再用子类来动态创建（也可以配合一个静态工厂函数返回new出来的对象）。

class HeapOnly { public: static HeapOnly* create() { return new HeapOnly(); } void destroy() { delete this; } protected: HeapOnly() {} ~HeapOnly() {} };

因为构造/析构是protected，外部无法在栈上直接定义对象，也无法delete，只能通过create()/destroy()走堆。

5. 何时需要成员初始化列表？过程是什么？

必须使用初始化列表的四种场景

1. 初始化一个引用成员变量时；

2. 初始化一个const成员变量时；

3. 当调用一个基类的构造函数，而该构造函数拥有一组参数时；

4. 当调用一个成员类的构造函数，而它拥有一组参数时。

class Demo { public: // 引用、const、基类带参构造、成员类带参构造，都只能写在初始化列表 Demo(int& r, int v) : ref_(r), kConst_(v), base_(v), member_(v) {} private: int& ref_; const int kConst_; Base base_; Member member_; };

初始化列表的执行过程

编译器会一一操作初始化列表，以适当顺序在构造函数之内安插初始化操作，并且在任何显式的用户代码之前执行。

关键点：列表中项目的顺序是由类中的成员声明顺序决定的，不是初始化列表中的排列顺序决定的。

class Bad { public: Bad(int v) : b_(v), a_(b_) {} // 危险：实际先初始化 a_，此时 b_ 还未初始化 private: int a_; int b_; };

实践建议：初始化列表顺序永远与成员声明顺序保持一致，并开启-Wreorder告警。

6. 程序员定义的析构函数被扩展的过程？

编译器会在程序员写的析构函数前后补充动作，扩展后的执行顺序为：

1. 析构函数函数体被执行；

2. 如果 class 拥有成员类对象，而后者拥有析构函数，那么它们会以其声明顺序的相反顺序被调用；

3. 如果对象有一个vptr，现在被重新定义（指回基类/当前类的虚表）；

4. 如果有任何直接的上层非虚基类拥有析构函数，则它们会以声明顺序相反的顺序被调用；

5. 如果任何虚基类拥有析构函数，则调用它们。

7. 构造函数的执行算法？

在派生类构造函数中，编译器按以下顺序安插动作：

1. 所有的虚基类及上一层基类的构造函数调用；

2. 对象的vptr 被初始化；

3. 如果有成员初始化列表，将在构造函数体内扩展开来，这必须在 vptr 被设定之后才做；

4. 执行程序员所提供的代码。

注意第 3 点：成员初始化列表的展开在 vptr 设定之后，这也是为什么在构造函数里调用虚函数不会呈现多态（此时对象还属于当前正在构造的类）。

8. 构造函数的扩展过程？

1. 记录在成员初始化列表中的数据成员初始化操作会被放在构造函数的函数体内，并与成员的声明顺序为顺序；

2. 如果一个成员并没有出现在成员初始化列表中，但它有一个默认构造函数，那么默认构造函数必须被调用；

3. 如果 class 有虚表，那么它必须被设定初值；

4. 所有上一层的基类构造函数必须被调用；

5. 所有虚基类的构造函数必须被调用。

9. 哪些函数不能是虚函数？

补充两个常被追问的：

• 析构函数可以是虚函数，而且多态基类的析构函数应该是虚函数；

• static成员函数不能是虚函数，但可以是纯虚函数的“替代”写法吗？不行；不过类可以声明纯虚析构函数（仍需提供定义）。

二、STL 容器和算法

具体图解见加餐篇：第十三章～第十七章的图解 STL 源码。

1. C++ 的 STL 介绍

六大组件

STL 一共提供六大组件：容器、算法、迭代器、仿函数、配接器、配置器。彼此可以组合套用：

容器通过配置器取得数据存储空间，算法通过迭代器存取容器内容，仿函数可以协助算法完成不同的策略变化，配接器可以应用于容器、仿函数和迭代器。

扩展：内存管理 allocator

SGI 设计了双层级配置器：

• 第一级配置器直接使用malloc()和free()完成内存的分配和回收；

• 第二级配置器则根据需求量的大小选择不同的策略执行。

第二级配置器的策略：

1. 如果需求块大小大于 128 bytes，则直接转而调用第一级配置器，使用malloc()分配内存；

2. 如果需求块大小小于 128 bytes，第二级配置器中维护了16 个自由链表，负责 16 种小型区块的次配置能力：

   • 有小于 128 bytes 的需求块时，首先查看所需需求块大小所对应的链表中是否有空闲空间，有则直接返回；

   • 没有则向内存池中申请所需大小的内存空间，申请成功则将其加入到自由链表中；

   • 如果内存池中没有空间，则使用malloc()从堆中申请，且申请到的大小是需求量的二倍（或二倍 + n 附加量），一倍放在自由空间中，一倍（或一倍 + n）放入内存池中；

3. 如果malloc()也失败，则会遍历自由空间链表，四处寻找“尚有未用区块，且区块够大”的 freelist，找到一块就挖出一块交出；

4. 如果还是没有，仍交由malloc()处理，因为malloc()有 out-of-memory 处理机制，或许有机会释放其他的内存拿来用；可以就成功，不行就报bad_alloc异常。

STL 中序列式容器的实现

vector

• 是动态空间，随着元素的加入，内部机制会自行扩充空间以容纳新元素；

• vector维护的是一个连续的线性空间，普通指针就可以满足要求作为vector的迭代器（RandomAccessIterator）；

• 数据结构其实就是三个迭代器构成：一个指向目前使用空间头的iterator，一个指向目前使用空间尾的iterator，一个指向目前可用空间尾的iterator；

• 当有新元素插入时：容量够用则直接插入；容量不够则容量扩充至两倍，两倍容量不足就扩张至足够大的容量；

• 扩充过程不是在原空间后面追加容量，而是重新申请一块连续空间 → 拷贝原有数据 → 释放原有空间。所以每次扩充后，原有的迭代器会失效。

std::vector<int> v; v.push_back(1); // size=1, capacity 可能是 1 v.push_back(2); // 触发扩容，capacity 通常翻倍

list

• 与vector相比，list的好处是每次插入或删除一个元素，就配置或释放一个空间，而且原有的迭代器也不会失效；

• STLlist是一个双向链表，普通指针不能满足list迭代器的需求，因为list的存储空间是不连续的；

• list的迭代器必须具备前移和后退功能，所以提供的是BidirectionalIterator；

• 数据结构中只要一个指向 node 节点的指针就可以了。

deque

• vector是单向开口的连续线性空间，deque则是双向开口的连续线性空间：支持从头尾两端进行元素的插入和删除；

• 相比vector的扩充方式，deque更贴切地实现了动态空间的概念。deque没有容量的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并连接起来；

• 为了维护“整体连续”的假象并提供随机存取接口（也提供RandomAccessIterator），避开了“重新配置、复制、释放”的轮回，代价是迭代器结构复杂。所以除非必要，应尽可能使用vector而不是deque。

deque 如何维护整体连续的假象：

• 采用一块所谓的map 作为主控，这里的 map 实际上是一块大小连续的空间，其中每一个元素（称为节点 node）都指向另一段连续线性空间（称为缓冲区），缓冲区才是deque的真正存储空间主体；

• SGI STL 允许指定缓冲区大小，默认 0 表示使用 512 bytes 缓冲区；

• 当 map 满载时，选用一块更大的空间来作为 map，重新调整配置；

• deque另一个关键是iterator 设计，其迭代器有四部分：cur指向缓冲区现行元素，first指向缓冲区头，last指向缓冲区尾（有时会包含备用空间），node指向管控中心；

• 总结：deque数据结构中包含指向第一个节点的iterator start、指向最后一个节点的iterator finish、一块连续空间作为主控 map，还需要记住 map 的大小，以备判断何时配置更大的 map。

stack

• 是一种先进后出的数据结构，只有一个出口；允许从最顶端新增元素、移除最顶端元素、取得最顶端元素；

• deque是双向开口的数据结构，所以使用deque作为底部结构并封闭其头端开口，就形成了一个stack。

queue

• 是一种先进先出的数据结构，有两个出口；允许从最底端加入元素、取得最顶端元素、从最底端新增元素、从最顶端移除元素；

• deque是双向开口的数据结构，若以deque为底部结构并封闭其底端的出口和头端的入口，就形成了一个queue（其实list也可以实现queue）。

heap

• 堆并不属于 STL 容器组件，它是个幕后英雄，扮演priority_queue的助手；

• priority_queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高（数值最高）的元素开始取；大根堆（binary max heap）正具有这样的性质，适合作为priority_queue的底层机制；

• 大根堆是一个满足每个节点的键值都大于或等于其子节点键值的二叉树。具体实现是一个vector（一块连续空间），通过维护某种顺序来实现这个二叉树；

• 插入：新元素放在最下一层为叶节点，即填补在由左至右的第一个空格（插入在底层vector的end()），然后执行上溯程序：将新节点与父节点比较，如果键值比父节点大就父子对换位置，如此一直上溯，直到不需要对换或直到根节点为止；

• 取出：最大值在根节点，取走根节点后，割舍最下层最右边的节点，并将其值重新安插至最大堆；最末节点放入根节点后，进行下溯程序：将空间节点和其较大的子节点对调，并持续下溯，直到叶节点为止。

priority_queue

底层是一个vector，使用 heap 形成的算法（插入、获取 heap 中元素的算法）维护这个vector，以达到“允许用户以任何次序将任何元素插入容器内，但取出时一定是从优先权最高的元素开始取”的目的。

slist

STLlist是一个双向链表，slist是一个单向链表。

2. vector 使用注意点及其原因

使用注意点

1. 注意插入和删除元素后迭代器失效的问题；

2. 清空vector数据时，如果保存的数据项是指针类型，需要逐项delete，否则会造成内存泄漏。

std::vector<int*> vp; // ... push 若干 new 出来的对象 for (int* p : vp) delete p; // 必须逐项释放 vp.clear(); // C++11 之后更推荐： std::vector<std::unique_ptr<int>> vup; // 自动管理，无需手动 delete

频繁调用 push_back() 的影响

向vector的尾部添加元素，很有可能引起整个对象存储空间的重新分配：重新分配更大的内存，再将原数据拷贝到新空间中，再释放原有内存。这个过程是耗时耗力的，频繁对vector调用push_back()会导致性能的下降。

C++11 之后，vector容器中添加了新的方法emplace_back()：

• 和push_back()一样都是在容器末尾添加一个新的元素进去；

• 不同的是emplace_back()在效率上相比push_back()有了一定的提升；

• 原理上的改进包括内存优化和运行效率两方面：

  • 内存优化主要体现在使用了就地构造（直接在容器内构造对象，不用拷贝一个复制品再使用）+强制类型转换的方法来实现；

  • 运行效率方面，由于省去了拷贝构造过程，因此也有一定的提升。

std::vector<std::string> v; v.push_back(std::string("hello")); // 构造临时对象 + 移动/拷贝 v.emplace_back("hello"); // 就地构造，省一次临时对象

合理做法：提前reserve()预估容量，减少扩容次数。

3. map 和 set 有什么区别，分别又是怎么实现的？

map和set都是 C++ 的关联容器，其底层实现都是红黑树（RB-Tree）。

由于map和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的map和set的操作行为，都只是转调 RB-tree 的操作行为。

map 和 set 的区别：

(1) 存储内容不同

• map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；

• set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

(2) 迭代器的可修改性不同

• set的迭代器是const的，不允许修改元素的值；

• map允许修改 value，但不允许修改 key。

原因：map和set是根据关键字排序来保证其有序性的。如果允许修改 key，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡——如此一来严重破坏了map和set的结构，导致 iterator 失效，不知道应该指向改变前还是改变后的位置。所以 STL 中将set的迭代器设置成const；而map的迭代器则不允许修改 key 值，允许修改 value 值。

(3) 下标操作

• map支持下标操作，set不支持；

• map可以用 key 做下标，map的下标运算符[]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中；

• 因此下标运算符[]在map应用中需要慎用：

  • const map不能用；

  • 只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用；

  • mapped_type类型没有默认值时也不应该使用；

  • 如果find能解决需求，尽可能用find。

std::map<std::string, int> m; if (m.find("key") != m.end()) { /* 存在 */ } // 推荐：不插入 int v = m["key"]; // 慎用：不存在会插入 {key, 0}

4. STL 迭代器删除元素

这个主要考察的是迭代器失效的问题。

序列容器vector、deque

• 使用erase(iterator)后，后边的每个元素的迭代器都会失效；

• 但后边每个元素都会往前移动一个位置，而erase会返回下一个有效的迭代器。

for (auto it = v.begin(); it != v.end(); ) { if (cond(*it)) it = v.erase(it); // 用返回值接住 else ++it; }

关联容器map、set

• 使用erase(iterator)后，当前元素的迭代器失效；

• 但其结构是红黑树，删除当前元素不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

for (auto it = m.begin(); it != m.end(); ) { if (cond(*it)) m.erase(it++); // C++11 起 erase 也返回下一个迭代器 else ++it; }

list

使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的 iterator，因此上面两种正确的方法都可以使用。

5. 迭代器的作用，有指针为何还要迭代器？

迭代器

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素，而又不需暴露该对象的内部表示。

或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由 iterator 提供的方法）访问聚合对象中的各个元素。

由于Iterator模式的以上特性——与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如 STL 的list、vector、stack等容器类及ostream_iterator等扩展 iterator。

迭代器和指针的区别

• 迭代器不是指针，是类模板，表现得像指针。它只是模拟了指针的一些功能，通过重载了指针的一些操作符->、*、++、--等；

• 迭代器封装了指针，是一个“可遍历 STL 容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升（lift），提供了比指针更高级的行为，相当于一种智能指针；它可以根据不同类型的数据结构来实现不同的++、--等操作；

• 迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用*取值后的值，而不能直接输出其自身。

std::vector<int> v{1, 2, 3}; for (auto it = v.begin(); it != v.end(); ++it) std::cout << *it << " "; // 必须解引用，不能直接 cout << it

迭代器产生原因

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构，而达到循环遍历集合的效果。

6. resize 和 reserve 的区别

resize()

改变当前容器内含有元素的数量（size()）。

std::vector<int> v; v.resize(10); // size 变为 10，新增 10 个元素，值默认为 0

• 例如vector v; v.resize(len);，v的 size 变为len；

• 如果原来v的 size 小于len，那么容器新增(len - size)个元素，元素的值默认为 0；

• 当v.push_back(3);之后，3 被放在了v的末尾，即下标为len，此时容器 size 为len + 1。

reserve()

改变当前容器的最大容量（capacity），它不会生成元素，只是确定这个容器允许放入多少对象。

std::vector<int> v; v.reserve(100); // capacity >= 100，size 仍为 0

• 如果reserve(len)的值大于当前的capacity()，那么会重新分配一块能存len个对象的空间；

• 然后把之前v.size()个对象通过copy constructor复制过来，并销毁之前的内存。

三.面试速记表