C++ 八股知识整理（一）：语法、面向对象、内存与 STL

C++ 语法基础

const 关键字

作用：修饰变量、函数、指针或成员函数，表示只读语义或不修改对象状态。

（1）修饰变量：

修饰常量，常量不能被改变；编译器可能进行常量折叠或替换。
可以用 const_cast 去除指针或引用的底层 const，但只有原对象本身不是 const 时才允许修改；若原对象本身为 const，修改属于未定义行为。

（2）修饰指针/引用

常量指针（底层 const）指向的常量不可改变

const int* p;
int const* p;

指针常量（顶层 const）指针不可改变

int * const p;

常量引用，只读常量的引用

const int a = 10;
const int &b = a;

（3）修饰成员函数（放在末尾）：表示保证不修改对象状态

const 对象只能调用 const 方法

const 函数中如果想调用其他方法，调用的方法必须是 const 的

class A {
public:
    int func() const { // 表示保证不修改对象状态
        // 编译错误，不能修改成员变量的值
        m_value = 10;
        return m_value;
    }
private:
    int m_value;
};

static 关键字

static 可以修饰变量、函数以及类的静态成员，不能直接"修饰类"。

（1）static 修饰变量

static 全局变量
- 将变量的作用域限定在当前文件中
- 在程序启动时被初始化（执行main函数前执行全局初始化函数）
- 生命周期和程序一样长
static 局部变量
- 函数返回后不会销毁，下次调用函数时继续使用（只初始化一次），直到程序结束才销毁。
- 作用域仅限本函数，生命周期和程序一样长

（2）static 修饰函数

将函数的作用域限定在当前文件中，使得其他文件无法访问该函数，以避免命名冲突和代码重复定义

（3）static 修饰类成员变量和成员函数（不属于对象，属于类）

static 成员变量
- 类外初始化（const static 类内初始化）
- 多个对象共享变量
static 成员函数
- 没有 this 指针，因此静态成员函数不能声明为 const。
- 不能访问非 static 成员/函数

volatile 关键字

作用：修饰变量，表示该变量可能被编译器无法感知的外部因素修改，例如硬件寄存器或信号处理流程。编译器会避免把相关访问优化成寄存器缓存。注意：volatile 不是线程同步工具，不能保证原子性、内存顺序或数据竞争安全；线程间同步应使用 std::atomic、互斥锁等机制。

mutable 关键字

用于修饰类的成员变量，表示该成员变量即使在一个 const 成员函数中也可以被修改。

explicit 关键字

explicit 通常用于构造函数的声明中，用于防止隐式转换，提高代码安全性

extern 关键字

extern 用于指示变量或函数的定义在另一个源文件中，并在当前源文件中声明，说明该符号具有外部链接（external linkage）属性。

编译完所有源文件后，链接器会将 extern 的所有引用（extern 声明在其他文件中会建立一个对该符号的引用）解析为在编译的源文件中找到的一个定义。

作用：

声明变量但不定义
常量全局变量的外部链接（const 全局变量默认内部链接）

extern “C” 的作用

如果不用 extern "C"，由于 C++ 和 C 语言在编译和链接时使用的命名规则不同，这会导致 C++ 代码无法调用 C 语言编写的函数或变量（链接时找不到符号）。

extern "C" {
    // C 语言函数或变量的声明
}
// 会采用 C 语言的链接规则，即符号的名称和调用约定与 C 语言相同

（1）C 和 C++ 函数命名规则不同（name mangling）

对于 C++ 语言，由于需要支持重载，编译器会对函数名进行名称修饰（name mangling），通常会把函数名、命名空间、类作用域和参数类型等编码进符号名。函数重载本身通常不依赖返回值类型区分。

命名规则在不同 OS、不同编译器都可能不同

C++ 声明和定义

声明是指告诉编译器某个符号的存在，在程序变量表中记录类型和名字，而定义则是指为该符号分配内存空间或实现其代码逻辑。

（1）变量

凡是没有带extern的声明同时也都是定义

（2）函数

带有{}是定义，否则是声明

define 和 inline 区别

（1）define

定义宏，可以定义常量/函数，直接替换，没有类型检查，预处理时替换

#define SQUARE_SUM(x, y) ((x) * (x) + (y) * (y))
// 写宏函数一定要注意：参数和函数体应当用括号包围，避免因运算优先级导致的错误。

（2）inline

inline 不保证实际展开，是否消除函数调用开销由编译器优化器决定；递归、复杂控制流等场景通常由编译器自行判断。语言层面上，inline 还允许函数定义出现在多个翻译单元中。
有类型检查，可以调试

除了inline，其他方法声明内联函数

定义在类内部
模板函数：模板定义通常放在头文件中，实例化后是否实际内联仍由编译器决定。
使用 __attribute__((always_inline))：在支持 GNU 扩展的编译器（如 GCC）中，可以使用 __attribute__ 尝试强制内联。
使用 #pragma 指令：在支持特定编译器指令的编译器中，可以使用 #pragma 指示编译器内联函数。
使用编译器特定的内联关键字：某些编译器可能有自己的内联关键字，比如在MSVC中可以使用__forceinline。
使用 constexpr 关键字：constexpr 表示函数可用于常量求值，不等价于一定被内联展开。

define 和 typedef 区别

（1）define：同上

（2）typedef：是一种类型定义关键字，用于为现有类型创建新的名称（别名），编译阶段处理

（3）区别：

作用域：define（没有），typedef（受到命名空间、类限制）
define 不支持模板，typedef 支持：

// 使用 typedef 定义模板类型别名
template <typename T>
struct MyContainer {
    typedef std::vector<T> Type;
};

// 使用 using 定义模板类型别名（C++11 及以后）
template <typename T>
struct MyContainer {
    using Type = std::vector<T>;
}

指针操作不同：

typedef int * ptr;
#define PTR int *

const ptr p = &a; // int * const p
const PTR q = &b; // const int * q

字节对齐

字节对齐是内存分配的一种策略，如果不对数据存储进行适当的对齐，可能会导致存取效率降低

（1）自然边界对齐：基本类型的自身大小

（2）结构体对齐：

结构体本身的总大小也会根据其最大对齐边界的成员进行对齐（比如结构体成员包含的最长类型为int类型，那么整个结构体要按照4的倍数对齐），以便在数组中正确对齐

空 struct / class 内存为 1，为了区别空结构体/类

（3）联合体union对齐

联合体的大小等于其最大大小的成员，因为联合体的所有成员共享相同的内存空间。

（4）通过编译器指令修改对齐规则

例如 #pragma pack

（5）指定对齐属性

在 C++11 及更高版本中，可以使用 alignas 关键字为数据结构或变量指定对齐要求。这个命令是对某个类型或者对象生效的。例如，alignas(16) int x; 将确保 x 的地址是 16 的倍数。

class 和 struct 的区别

C 语言 struct 和 C++ struct 的区别：

C 中没有方法（函数）
C 中没有 private 和 protected 权限
不可以继承

C++中 class 和 struct 的区别

默认权限/继承不同（private / public）
在模板参数列表中可以写 class 或 typename，不能写 struct。这不是 class 与 struct 类型定义能力的区别。

template <class T>
struct  Person {
public:
    T age;
};

// 错误
template <struct T>
struct  Person {
public:
    T age;
};

使用 struct 多用于 POD（Plain Old Data），用于兼容旧的函数保持数据结构不变（例如 memcpy）

sizeof 运算符

作用：编译期间，计算一个类型/对象的所占用的内存大小（字节数）

常考：

sizeof(指针)：大小永远是固定的，取决于处理器位数，32位就是 4 字节，64位就是 8 字节
- 此外数组作为函数参数时会退化为指针，大小要按指针的计算
- 如果数组作为引用传递则不会退化，该是多大就多大，因为引用避免拷贝的同时传递的是相同的地址
sizeof(结构体)：内存对齐
sizeof(字符串数组)：算上末尾的 ‘\0’

sizeof 和 strlen

strlen：C 标准库中的函数，用于计算 C 风格字符串（以空字符 ‘\0’ 结尾的字符数组）的长度，即不包括结尾的空字符的字符个数。

sizeof：见上

C++ 类型转换

（1）static_cast

编译时期转换
基本类型的转换
指针类型之间的转换
- 上行转换：安全
- 下行转换（基类→派生类）：可能不安全
引用类型转换：同指针

（2）dynamic_cast

主要应用于父子类层次结构中的安全类型转换

解决下行转换不安全的问题
- 如果转换失败，dynamic_cast 将返回空指针（对于指针类型）或抛出异常（对于引用类型）
用于多态类型检查
- dynamic_cast 只有在基类存在虚函数(虚函数表)的情况下才有可能将基类指针转化为子类

（3）const_cast

当需要修改 const 对象时，可以使用 const_cast 来删除 const 属性。

（4）reinterpret_cast

用于在不同类型之间进行低级别的转换，仅仅是重新解释底层比特（也就是对指针所指针的那片比特位换个类型做解释），而不进行任何类型检查。

int a = 42;
int* int_ptr = &a;
char* char_ptr = reinterpret_cast<char*>(int_ptr); // 将int指针转换为char指针

指针和引用的区别

区别：

指针是一个变量，它保存了另一个变量的内存地址；引用是另一个变量的别名，与原变量共享内存地址。
指针(除指针常量)可以被重新赋值，指向不同的变量；引用在初始化后不能更改，始终指向同一个变量。
指针可以为 nullptr，表示不指向任何变量；引用必须绑定到一个变量，不能为 nullptr。
使用指针需要对其进行解引用以获取或修改其指向的变量的值；引用可以直接使用，无需解引用。
指针有多级，引用没有
指针和引用的自增(++）和自减含义不同，指针是指针运算, 而引用是代表所指向的对象对象执行++或–

联系：

很多实现中引用可按类似指针的方式实现，但语言层面引用不是指针常量。

指针传递、值传递和引用传递

值传递：形参的修改不会影响到实参
引用传递：是将实参的引用传递给形参。在这种情况下，函数内对形参的修改会影响到实参。
指针传递：是将实参的地址传递给形参（实际上也是值传递，传递的是指针）。在这种情况下，函数内对形参的修改会影响到实参。

智能指针

智能指针通过 RAII 管理动态资源，避免手动 new / delete 带来的泄漏和异常安全问题。

std::unique_ptr：独占所有权，不能拷贝，可以移动，适合表达唯一资源拥有者。
std::shared_ptr：共享所有权，通过引用计数管理对象生命周期；最后一个 shared_ptr 析构时释放对象。
std::weak_ptr：不增加引用计数，常用于打破 shared_ptr 循环引用。

C++ 面向对象

C++ 面向对象三大特性

（1）封装性

将属性和方法封装在类中，隐藏类的内部实现细节，仅暴露必要的接口给外部。

通过封装，可以控制类成员的访问级别，限制对类内部数据的直接访问，确保数据的完整性和安全性

（2）继承性

继承是一个类（派生类，Derived Class）从另一个类（基类，Base Class）那里获得其属性和方法的过程

减少重复代码，提高代码复用性和可维护性
单一、多重、菱形(虚继承)

（3）多态性

同一个函数或者操作在不同的对象上有不同的表现形式

静态多态：在程序在编译期就确定了对象类型和调用的函数地址（函数模板、重载）
- 静态多态的对象类型和函数是在编译时确定的，因此不会产生额外的性能开销。同时静态多态也不需要为每个类创建虚表，因此在空间上也不会像动态多态那样产生额外的消耗
动态多态（基于虚表进行动态绑定：虚函数、纯虚函数）
- 必须通过基类的指针或者引用调用虚函数，被调用的函数是虚函数，且必须完成对基类虚函数的重写
- 动态多态发生在运行时，通常在运行时需要一个指针间接寻址，因此会有额外的性能开销

重载、重写、隐藏

（1）重载（Overloading）

重载是指相同作用域(比如命名空间或者同一个类)内拥有相同的方法名，但具有不同的参数类型和/或参数数量的方法。重载允许根据所提供的参数不同来调用不同的函数

（2）重写（Overriding）

重写是指在派生类中重新定义基类中的方法。当派生类需要改变基类方法的功能时，就需要用到重写。

基类被重写函数需要使用virtual修饰

（3）隐藏（Hiding）

派生类的函数屏蔽了与其同名的基类函数，只要同名函数，不管参数列表是否相同，基类函数都会被隐藏

类对象构造和析构顺序

（1）类构造顺序：基类初始化（优先虚继承）→ 成员变量初始化（按照声明顺序）→ 构造函数

（2）析构顺序和构造相反

委托构造函数

这种构造函数可以委托其他构造函数来帮它完成一些对象成员的初始化操作

被委托的构造函数在委托构造函数的初始化列表里被调用，而不是在委托构造函数的函数体里被调用。
委托构造函数的初始值列表中，只允许出现被委托的构造函数，而不能直接给成员变量进行初始化。

class student {
public:
	int age = 18;
	int weight = 120;
	student(int give_age):student(give_age,180)//委托构造函数
	{
		std::cout << "委托老兄办点事！" << std::endl;
	}
	student(int give_age,int give_weight):age(give_age),weight(give_weight)
	{
		std::cout << "我被委托做一些事情！" << std::endl;
	}
};

int main() {
	const student stu = student(20);
	std::cout << stu.age << std::endl << stu.weight << std::endl;
	return 0;
}

// "我被委托做一些事情！"
// "委托老兄办点事！"
// 20 180

析构函数中是否可以抛出异常

不建议在析构函数中抛出异常。现代 C++ 中析构函数通常默认是 noexcept，析构期间抛出异常可能导致 std::terminate；如果正在栈展开时再次抛异常，风险更高。

如果抛出异常的解决方法：

（1）调用 abort()

DBConn::~DBConn()
{
    try
    {
	    db.close();
    }
    catch(...)
    {
        abort(); // 强制结束程序
    }
}

（2）吞下异常

DBConn::~DBConn()
{
    try{ db.close();}
    catch(...)
    {
        //制作运转记录，记下对close的调用失败！
    }
}

（3）把调用close的责任从DBConn析构函数手上移到DBConn客户手中

如果一定要处理，只能在除析构函数以外的函数中处理

浅拷贝和深拷贝

（1）浅拷贝

仅复制对象的基本类型成员和指针成员的值，而不复制指针所指向的内存。可能导致两者共享资源，造成内存泄漏、意外修改资源

默认拷贝构造函数

（2）深拷贝

在浅拷贝基础上，还复制指针所指向的内存

需要显式实现拷贝构造和赋值拷贝构造

类中this指针

this是一个指向当前对象的指针，python中为self

this 实际上是成员函数的一个形参，在调用成员函数时将对象的地址作为实参传递给 this（隐式）
常量成员函数（const member function）中，this 指针的类型是指向常量对象的常量指针（const pointer to const object）（这就是为什么static和const不能同时修饰类函数），因此不能用来修改成员变量的值
static 函数没有this指针，因为其属于类而非某个对象，不能访问非static 成员

C++虚函数表

虚函数表（Virtual Table，V-Table）中保存类的虚函数地址，用于支持运行期的动态派发。它能在基类指针或引用调用虚函数时，找到实际对象对应的函数实现。

一个对象在内存中一般由成员变量（非静态）、虚函数表指针(vptr)构成
虚函数表指针指向一个数组，数组的元素就是各个虚函数的地址，通过函数的索引，我们就能直接访问对应的虚函数

纯虚函数

**定义：**纯虚函数是在基类中声明为 = 0 的虚函数，作用类似定义接口；派生类通常需要实现它，否则派生类也会成为抽象类。纯虚函数也可以在类外提供定义，但类仍然是抽象类。

包含纯虚函数的类称为抽象类（Abstract Class），抽象类无法实例化。

class Shape {
   public:
      // 纯虚函数
      virtual void draw() = 0;
};

构造函数和析构函数能不能是虚函数

（1）构造函数不能是虚函数

虚函数的主要作用是实现多态，即派生类重写基类函数，但每个类都有自己的构造函数，不需要被重写
构造/析构期间调用虚函数不会动态派发到更派生类版本，而是按照当前正在构造或析构的类型解析。因此构造函数不应依赖虚调用实现多态行为。

（2）析构函数可以是虚函数

当使用基类指针或引用指向派生类时，如果基类的析构函数没有设置成虚函数，则在 delete 基类时无法调用派生类的析构，可能造成内存泄漏。只有将基类析构函数设置成 virtual，才会正确调用派生类析构函数。
析构函数为什么默认不是虚函数？（零成本抽象）声明虚函数会产生 vptr 和 vtable，造成额外的内存开销，如果我们不希望该类为基类，则不需要设置虚函数。

一个函数不能既是模板函数又是虚函数

因为C++的编译与链接模型是"分离"的
一个 function template最后到底会被实例化为多少个函数，要等整个程序(所有的编译单元)全部被编译完成才知道
同时，virtual function的实现大多利用了一个"虚函数表"，虚函数表的内存布局需要在这个类编译完成的时候就被完全确定
综上就会导致编译时无法确定需要调用哪个特定的模板实例

C++ 空类的大小

为1，C++标准要求每个对象都必须具有独一无二的内存地址

如果一个空类做基类，则基类不占用空间（空基类优化）

虚基类

解决菱形继承的问题，当派生类从多个基类派生，而这些基类又有共同基类，则在访问此共同基类中的成员时，将产生冗余，并有可能因冗余带来不一致性。

C++11 新特性

nullptr 和 NULL

由于C++中引入了函数重载和模板，而NULL实际上只是整数的0，不能代表指针类型，故引入nullptr，避免了二义性，更加安全

类型萃取(type_traits)

type_traits是一种编译时技术，用于在编译期间获取和操作类型的信息，用于泛型编程以及在编译时做出决策

template <typename T>
typename std::enable_if<std::is_integral<T>::value, T>::type
foo(T t) {
    std::cout << "foo() called with an integral type: " << t << std::endl;
    return t;
}

template <typename T>
typename std::enable_if<std::is_floating_point<T>::value, T>::type
foo(T t) {
    std::cout << "foo() called with a floating point type: " << t << std::endl;
    return t;
}

int main() {
    foo(42); // Output: foo() called with an integral type: 42
    foo(3.14); // Output: foo() called with a floating point type: 3.14
}

使用 std::enable_if 和类型萃取来选择不同的函数实现

智能指针

见前文的 RAII 和智能指针小节。C++11 将 std::unique_ptr、std::shared_ptr、std::weak_ptr 纳入标准库，推荐优先使用智能指针表达资源所有权，减少裸指针负责释放资源的场景。

Lambda 表达式

https://zhuanlan.zhihu.com/p/384314474

lambda 表达式可以让代码更简洁；它定义了一个匿名函数对象，并且可以捕获一定范围内的变量。

lambda 表达式的构成：


  [captures]<tparams>(params)lambda-specifiers{body;};

captures 捕获列表，lambda可以把上下文变量以值或引用的方式捕获，在body中直接使用。
- [] 什么也不捕获
- [=] 按值的方式捕获所有变量 [&] 按引用的方式捕获所有变量注意[=, =a]是错误的，[=, &a]正确的
- [this] 在成员函数中，也可以直接捕获this指针，其实在成员函数中，[=]和[&]也会捕获this指针。
tparams 模板参数列表：C++20 引入，让 lambda 可以像模板函数一样被调用。
params 参数列表：C++14 之后允许使用 auto 作为参数类型。
lambda-specifiers 说明符：常见的是 mutable，允许修改按值捕获进来的副本；异常说明和尾置返回类型也可以出现在 lambda 声明中。
trailing-return-type 返回值类型：一般可以省略，由编译器推导。
body 函数体：函数的具体逻辑。

编译器会将 lambda 表达式翻译成一个类，并重载 operator()，如果 captures 是按值传递的（不含任何引用传递），自动加上 const，如果要修改，应该在说明符位置加上 mutable。

左值引用、右值引用、move、完美转发

左值引用通常绑定到有名字、可取地址的对象；右值引用用于绑定临时对象，配合移动构造、移动赋值转移资源所有权。std::move 本身不移动对象，只是把表达式转换为右值引用；完美转发通常使用万能引用和 std::forward 保留实参的值类别。

C++ 内存管理

C++ 内存分区

常见的进程内存区域包括代码区、全局/静态区、堆区和栈区。局部自动变量通常位于栈上，动态分配对象通常位于堆上，全局变量和静态变量位于全局/静态存储区。具体布局会受操作系统、编译器和 ABI 影响。

C++ RAII

资源获取即初始化（Resource Acquisition Is Initialization，简称 RAII）是一种 C++ 编程技术，它将在使用前获取（分配的堆内存、执行线程、打开的套接字、打开的文件、锁定的互斥量、磁盘空间、数据库连接等有限资源）的资源的生命周期与某个对象的生命周期绑定在一起。

利用栈上局部变量的自动析构来保证资源一定会被释放

C++ malloc/free 底层原理

在 Linux 中，若通过 malloc() 请求一大块内存，C 运行库将创建一个匿名内存映射，而不使用堆内存。“大块"意味着比阈值 MMAP_THRESHOLD 还大，缺省为 128KB，可通过 mallopt() 调整。

mm_struct 结构是对整个用户空间（进程空间）的描述：

struct mm_struct {
	unsigned long start_brk, brk, start_stack;
};
// 其中 start_brk 和 brk 分别是堆的起始和终止地址，我们使用 malloc 动态分配的内存就在这之间。
// start_stack是进程栈的起始地址，栈的大小是在编译时期确定的，在运行时不能改变。

实际中系统分配较大的堆空间，进程通过 malloc() 库函数在堆上进行空间动态分配，堆如果不够用，malloc 可以进行系统调用（brk 和 sbrk 系统调用），增大 brk 的值。

malloc 实现方案：

为避免频繁进行用户态和内核态之间的切换，malloc采用的是内存池的实现方式（先申请一大块内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块即可）

new / delete 和 malloc / free 的区别

（1）申请内存的位置

new：自由存储区；malloc：堆。通常实现上都来自堆，但概念层次不同。

ps：自由存储区是一个抽象概念，一般为堆，也可以是其他区域，主要看operator new的实现

指定内存地址分配：placement new：new (place_address) type，实际上调用了一个特殊的、不可重定义的 placement operator new。

（2）申请时是否需要指定大小

new：no；malloc：yes

（3）内存分配失败的返回值

new：bad_alloc；malloc：NULL

（4）是否调用构造和析构

new：yes；malloc：no

（5）new/delete 底层可以调用malloc和free

void * operator new (size_t size)
{
    if(void * mem = malloc(size))
        return mem;
    else
        throw bad_alloc();
}
void operator delete(void *mem) noexcept
{
    free(mem);
}

（6）是否可以重载

new：yes；malloc：no

（7）是否可以重新分配内存

new：no；malloc：通过realloc （先判断当前的指针所指内存是否有足够的连续空间，如果有，原地扩大可分配的内存地址，并且返回原来的地址指针；如果空间不够，先按照新指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来的内存区域。）

C++ 内存泄漏

（1）定义：申请了动态内存，却没有释放

（2）检测：

手动检测
工具：
- Valgrind valgrind --leak-check=yes your_program
- AddressSanitizer

（3）如何避免

RAII / 智能指针
异常安全：在C++中，如果程序抛出异常，需要确保在异常处理过程中正确释放已分配的内存。使用try-catch块来捕获异常并在适当的位置释放内存

野指针和悬空指针

（1）野指针：未被初始化指针

值不确定，可能指向任何地方，造成数据损坏

（2）空悬指针：指向已经被释放（如删除、回收）的内存的指针

C++ 常见内存错误

（1）间接引用坏指针

int val;
scanf("%d", &val);
// 坏指针：
scanf("%d", val) // 如果val地址可RW，那么原先的内容就会被覆盖

（2）读没有初始化的内存

例如堆内存里面的变量默认没有初始化

（3）栈缓冲区溢出

void bufoverflow()
{
    char buf[64];
    // gets 已被废弃，这里仅用于说明栈缓冲区溢出风险。
    gets(buf);
    return;
}

（4）误解指针运算

while (*p && *p != val)
        p += sizeof(int); /* Should be p++ */

（5）引用不存在的变量

int *stackref ()
{
    int val;

    return &val;
}

（6）内存泄漏

Coredump

在程序发生某些错误而导致进程异常退出时，Linux 内核会根据进程当时的内存信息，生成一个 coredump 文件

core dump 文件的路径是由 /proc/sys/kernel/core_pattern 定义的

C++ STL

STL

Standard Template Library，标准模板库，STL 包含 6 大部件：容器、迭代器、算法、仿函数、容器适配器和空间配置器。

容器：容纳一组元素的对象，提供各种数据结构
迭代器：提供访问容器元素的方法。从实现角度看，迭代器通常是重载了 operator*、operator->、operator++ 等操作的类模板。
算法：包括查找算法、排序算法等等
仿函数：一个行为类似函数的对象，调用它就像调用函数一样，重载了 operator() 的类或者类模板
容器适配器：用来修饰容器等，比如queue和stack，底层借助了deque
空间配置器：负责空间配置和管理，是一个实现了动态空间配置，空间管理，空间释放的类模板

容器种类

（1）序列容器

array(固定大小数组), vector, list, forward-list(单链表), deque

（2）关联容器

set, multiset, map, multimap

（3）无序容器

unordered_map, unordered_set, unordered_multiset, unordered_multimap

vector

（1）概述

支持动态扩容的连续线性空间，支持快速随机访问，尾部增删元素

（2）底层原理

底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部

当插入N个元素时，推导出扩容次数为log2(N)，每次扩充引起的元素拷贝次数为：2^0 + 2^1 + 2^2, …, 2^lgN。相加得：2 * 2^lgN - 1 约为 2N次，共拷贝了N次最后一个元素，所以总的操作大概为3N。

（3）扩容机制

当空间不够容纳新元素（如 vec.push_back(val)）时，vector 会申请一片更大的连续空间，移动或拷贝原有元素，然后释放原空间。扩容倍率是实现细节，常见实现可能采用约 1.5 倍或 2 倍增长。只要触发重新分配，指向原 vector 存储区的迭代器、指针和引用都会失效。

（4）size和capacity

size指容器的元素个数
capacity指容器分配存储空间中能够容纳的元素个数

（5）reserve和resize

**reserve的作用是更改vector的容量（capacity），size没有变，使vector至少可以容纳n个元素，**如果n大于vector当前的容量，reserve会对vector进行扩容。其他情况下都不会重新分配vector的存储空间，可以减少多次开辟、释放空间的问题
resize是改变容器的大小，且创建对象，改变了capacity和size，分配内存且调用构造函数创建对象

（6）vector元素可以是引用吗

不能，vector中的元素有两个要求：可以赋值和拷贝，引用必须初始化，但是vector开辟内存时无法初始化

（7）vector迭代器失效的情况

vector扩容造成内存重新分配，迭代器全部失效
erase删除元素，导致迭代器失效，erase返回下一个有效iter

// 删除指定元素
int main() {
    vector<int> nums{1, 2, 3, 4};

    for (auto iter = nums.begin(); iter != nums.end();) {
        if (*iter == 3) {
            iter = nums.erase(iter);
        } else {
            ++iter;
        }
    }

    for (auto i : nums) {
        cout << i << endl;
    }
    return 0;
}

（8）vector开辟内存在哪，能创建10万个元素吗

动态扩容通常发生在堆上，系统必须有足够的可用内存来存储这些元素。

（9）vector作为函数返回值

返回 vector 时通常不必过度担心拷贝成本：RVO/NRVO 可以进行复制消除，C++11 以后还可以利用移动语义降低返回成本。

如果希望复用已有对象或避免重新构造，也可以改成通过引用参数输出，例如 void fun(Base& x)。

（10）emplace_back和push_back

相同：都支持左值和右值的传入，左值调用构造函数创建匿名对象，右值调用移动构造函数
不同：emplace_back 还支持另一种调用方式，原地构造，传入的参数可以是vector类型的构造函数的参数，直接原地构造

emplace_back(10, "test") // 可以只调用一次构造函数
push_back(MyClass(10, "test")) // 会先构造临时对象，再移动或拷贝到容器中；具体是否被优化由编译器和标准版本决定。

（11）一个vector内存很大但实际我只用了很小一部分怎么解决

// 利用swap释放内存
    vector<int> nums{1, 2, 3, 3, 4};
    nums.reserve(10);
    vector<int>(nums).swap(nums);
    // nums_swap.reserve(5);

    cout << "nums capacity" << nums.capacity() << endl; // 5
    cout << "nums size" << nums.size() << endl; // 5

（12）删除元素

// erase 和 clear只改变size
    vector<int> nums{1, 2, 3, 3, 4};
    nums.reserve(10);

    nums.erase(nums.begin(), nums.begin() + 1);
    for(auto i : nums) cout << i << " ";

    cout << "nums capacity" << nums.capacity() << endl; // 10
    cout << "nums size" << nums.size() << endl; // 4

    nums.clear();
    for(auto i : nums) cout << i << " ";

    cout << "nums capacity" << nums.capacity() << endl; // 10
    cout << "nums size" << nums.size() << endl; // 0

（13）为什么扩容成倍增长，而不是固定数字？

如果是以固定数扩容的话，通过数学方法可以算出来平摊下来的push_back时间是O(n)，而以倍数增长的扩容方式push_back的时间复杂度是O(1)

理想的分配方案是在第N次扩容时如果能复用之前N-1次释放的空间就太好了，2倍扩容必定大于前面的总和，过大会造成内存浪费，1.5倍扩容可以重用之前释放的内存

deque

deque 是一种双端开口的序列容器，逻辑上支持随机访问，但底层通常由多段连续缓冲区组成，并不要求整体内存连续。

（1）底层原理

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

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现"整体连续"的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

（2）map数组满了怎么办

类似vector扩容

（3）deque的iter

deque 的迭代器通常包含几个关键指针：cur 指向当前元素，first 指向当前缓冲区头部，last 指向当前缓冲区尾部，node 指向主控 map 中的节点。容器本身还会记录指向首尾节点的迭代器（常见实现中称为 start 和 finish）以及主控 map 的大小。

list

list 是一个双向链表，每次插入或删除一个元素就配置或释放一个空间，而且原有的迭代器也不会失效

stack

使用 deque 作为底部结构并封闭其头端开口，就形成了一个 stack

queue

若以 deque 为底部结构并封闭其底端的出口，和头端的入口就形成了一个 queue。(其实 list 也可以实现 deque)

map & set

（1）为何关联容器的插入删除效率一般比用其他序列容器高？

底层实现都是红黑树。对于关联容器来说，存储的只是节点。插入删除只是节点指针的换来换去，不需要做内存拷贝和内存移动

（2）multiset 重复数据是怎么实现的

set的返回值型别是由pair组织起来的两个值，pair第一个元素返回新元素的位置，或返回现存的同值元素的位置，pair第二个元素表示插入是否成功，如果插入失败，就只返回重复元素的位置

multiset中所有拥有位置提示参数的插入函数的返回值型别是相同的。这样就确保了至少有了一个通用型的插入函数，在各种容器中有共通接口

（3）insert后iter会不会失效

不会，只是节点指针的改变，每个节点的内存没有改变。iterator就是指向每个节点内存的指针，所以插入之后，该指针是不会变的

（4）为何map和set不能像vector一样有个reserve函数来预分配数据

map和set会存储节点的信息，例如结构体之类的，无法提前分配

（5）map使用[]越界了发生什么

会自动插入一个你搜索的key和默认的value。如果value为内置类型，其值将被初始化为0;如果value为自定义数据结构且用户定义了默认值则初始化为默认值，否则初始化为0

迭代器和指针的区别

迭代器不一定是裸指针，通常可以是类模板对象。它通过重载 operator*、operator->、operator++、operator-- 等操作，提供类似指针的访问方式。

算法

（1）sort和stable_sort

stable_sort (first, last)和sort() 函数功能相似，不同之处在于该函数不会改变它们的相对位置

stable_sort() 函数是基于归并排序实现的
sort() 只由标准规定复杂度要求，常见实现多采用内省排序（introsort），不能简单等同于快速排序。

STL 容器是线程安全的吗

不是，

加锁实现线程安全
固定 vector 大小只能避免扩容导致的迭代器/引用失效，并不等于线程安全，更不等于 lock-free；并发读写元素仍需同步。

vector<int> nums;
nums.resize(10); // 不是reserve

优先队列

priority_queue是C++标准库中的一个容器适配器（container adapter），用于实现优先队列（priority queue）的数据结构。优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序，每次取出的元素都是优先级最高的。它的底层实现通常使用堆（heap）数据结构。

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

Citation

Citation: When reposting or citing content from this article, please credit the original author and source.

Cited as:

Zachary WEI. (Oct 2024). C++ 八股知识整理（一）：语法、面向对象、内存与 STL. https://zachary-ww.github.io/zh/posts/cpp-bagu-knowledge/

@article{zachary2024-cpp-bagu-knowledge,
  title   = "{C++ 八股知识整理（一）：语法、面向对象、内存与 STL}",
  author  = "Zachary WEI",
  journal = "zachary-ww.github.io",
  year    = "2024",
  month   = "Oct",
  url     = "https://zachary-ww.github.io/zh/posts/cpp-bagu-knowledge/"
}

C++ 语法基础#

const 关键字#

static 关键字#

volatile 关键字#

mutable 关键字#

explicit 关键字#

extern 关键字#

extern “C” 的作用#

C++ 声明和定义#

define 和 inline 区别#

除了inline，其他方法声明内联函数#

define 和 typedef 区别#

字节对齐#

class 和 struct 的区别#

sizeof 运算符#

sizeof 和 strlen#

C++ 类型转换#

指针和引用的区别#

指针传递、值传递和引用传递#

智能指针#

C++ 面向对象#

C++ 面向对象三大特性#

重载、重写、隐藏#

类对象构造和析构顺序#

委托构造函数#

析构函数中是否可以抛出异常#

浅拷贝和深拷贝#

类中this指针#

C++虚函数表#

纯虚函数#

构造函数和析构函数能不能是虚函数#

一个函数不能既是模板函数又是虚函数#

C++ 空类的大小#

虚基类#

C++11 新特性#

nullptr 和 NULL#

类型萃取(type_traits)#

智能指针#

Lambda 表达式#

左值引用、右值引用、move、完美转发#

C++ 内存管理#

C++ 内存分区#

C++ RAII#

C++ malloc/free 底层原理#

new / delete 和 malloc / free 的区别#

C++ 内存泄漏#

野指针和悬空指针#

C++ 常见内存错误#

Coredump#

C++ STL#

STL#

容器种类#

vector#

deque#

list#

stack#

queue#

map & set#

迭代器和指针的区别#

算法#

STL 容器是线程安全的吗#

优先队列#

Citation#

C++ 语法基础

const 关键字

static 关键字

volatile 关键字

mutable 关键字

explicit 关键字

extern 关键字

extern “C” 的作用

C++ 声明和定义

define 和 inline 区别

除了inline，其他方法声明内联函数

define 和 typedef 区别

字节对齐

class 和 struct 的区别

sizeof 运算符

sizeof 和 strlen

C++ 类型转换

指针和引用的区别

指针传递、值传递和引用传递

智能指针

C++ 面向对象

C++ 面向对象三大特性

重载、重写、隐藏

类对象构造和析构顺序

委托构造函数

析构函数中是否可以抛出异常

浅拷贝和深拷贝

类中this指针

C++虚函数表

纯虚函数

构造函数和析构函数能不能是虚函数

一个函数不能既是模板函数又是虚函数

C++ 空类的大小

虚基类

C++11 新特性

nullptr 和 NULL

类型萃取(type_traits)

智能指针

Lambda 表达式

左值引用、右值引用、move、完美转发

C++ 内存管理

C++ 内存分区

C++ RAII

C++ malloc/free 底层原理

new / delete 和 malloc / free 的区别

C++ 内存泄漏

野指针和悬空指针

C++ 常见内存错误

Coredump

C++ STL

STL

容器种类

vector

deque

list

stack

queue

map & set

迭代器和指针的区别

算法

STL 容器是线程安全的吗

优先队列

Citation