00 C++面经

C/C++八股

关键字

static

1.static的作用是什么

• 在函数体内 + 修饰局部变量：其访问权限在函数内，仅初始化一次，存储于静态存储区
• 在函数体外 + 修饰全局变量：将模块的全局变量限制在模块内部（仅供.c使用），不能跨文件共享
• 修饰函数：该函数仅可被本模块调用，不能作为接口暴露给其他模块

注意：static 与 extern不可同时修饰一个变量

2.static结合函数重入性的理解

可重入函数：函数可以被多个任务/线程同时调用而不会产生错误结果

• static会引入状态持久性和共享状态，这与可重入函数所需的无状态和独立性要求直接冲突

3.全局变量和局部变量分别变为静态时，两者的生存周期，作用域，链接属性有什么变化

特性	普通全局变量	静态全局变量	普通局部变量	静态局部变量
生存周期	程序运行期间	程序运行期间	函数调用期间	程序运行期间
作用域	文件作用域	文件作用域	函数/块作用域	函数/块作用域
链接属性	外部链接	内部链接	无链接	无链接

extern

1.extern关键字的作用是什么

• 声明一个在其他文件或作用域中定义的变量或函数，告诉编译器“这个符号在别处定义，不要在这里分配存储空间”

const

1.define和const区别，分别什么时候生效

• #define（宏定义）
  • 预处理阶段生效，由预处理器进行简单的文本替换，不占用内存
  • 无类型检查，可能导致意外错误（如 #define PI 3.14 替换后可能产生表达式问题）
  • 作用域：从定义处到文件末尾（或 #undef）
• const（常量）
  • 编译阶段生效，是类型安全的变量，占用内存（通常存储在只读数据段）
  • 编译器会检查类型，避免错误
  • 作用域：遵循变量作用域规则（如局部 const 只在函数内有效）

何时使用？

• 用 #define：需要全局替换、条件编译（如 #ifdef DEBUG）或定义无类型常量（如数组大小）
• 用 const：需要类型安全、调试时可查看符号、或涉及指针/引用时（如 const int* p）

2.char const* p有什么特点？地址变吗？

区分“指针常量“与”常量指针“：* (指针)和 const（常量） 谁在前先读谁 ；*象征着地址，const象征着内容；谁在前面谁就不允许改变

• char const* p属于常量指针，p指向的地址可以变，但是地址的值不能变

#define

1.define宏为什么要加括号？

• 避免运算符优先级导致的错误

#define SQUARE(x) x * x      // 错误写法
int a = SQUARE(1 + 2);       // 替换为 1 + 2 * 1 + 2 = 5（非预期）

#define SQUARE(x) (x) * (x)  // 正确写法
int a = SQUARE(1 + 2);       // 替换为 (1 + 2) * (1 + 2) = 9

union

1.结构体和联合体的区别？

特性	结构体（struct）	联合体（union）
内存布局	成员独立存储，占用总大小为各成员之和（对齐后）	成员共享内存，大小为最大成员的大小
访问方式	所有成员可同时访问	同一时间只能使用一个成员
用途	存储逻辑相关的多个数据（如坐标点 {x, y}）	节省内存，表示互斥数据（如类型转换）
示例	struct { int x; float y; };	union { int i; float f; };

2.和bitfield的区别：union是所有成员共用一块内存，而位段的每个成员是独立的，他是把一个结构体的内存分成多份

typedef

1.define和typedef的区别？

特性	#define	typedef
阶段	预处理阶段（文本替换）	编译阶段（类型别名）
类型安全	无类型检查，可能出错	有类型检查，更安全
作用域	文件作用域（可 #undef）	遵循变量作用域规则
复杂声明	需谨慎处理（如指针类型）	适合定义复杂类型（如函数指针）
示例	#define INT_P int*（易误用）	typedef int* INT_P;（明确类型）

volatile

1.volatile的作用是什么

• 作用：告诉编译器被修饰的变量是易变的（可能在程序看起来不修改它的情况下发生变化）

  • 运行期：不能使用通用寄存器进行缓存：每次访问都必须从内存/外设寄存器中读取/写入

  • 编译期：防止编译器对连续多条的读写语句进行合并优化

  • 但是这个关键字只防止编译优化，不处理对数据并发访问时的同步、互斥问题

• 详解：CPU读取数据时，会从指定地址处取值并搬运到CPU通用寄存器中处理，在不加volatile时，对于频繁的操作，编译器会将代码的汇编指令进行优化，例子如下：

// 比如要往某一地址送两指令： 
int *ip = 0x12345678; //设备地址 
*ip = 1; //第一个指令 
*ip = 2; //第二个指令
// 编译器可能优化为：
int *ip = 0x12345678; //设备地址 
*ip = 2; //第二个指令
// 造成第一条指令被忽略
volatile int *ip = 0x12345678; //设备地址 
*ip = 1; //第一个指令 
*ip = 2; //第二个指令

• 使用场合：寄存器、临界区访问的变量、中断函数访问的全局或static变量

• 与Cache的区别：

  • volatile是==对编译器==的约束，不会删掉从RAM读取到通用寄存器的指令，但无法控制从RAM到通用寄存器的具体行为（从RAM到寄存器要经过cache）。若两次被volatile修饰的读取指令过快，即使RAM中的值改变了，但由于读取过快没有更新cache，那么实际上搬运到通用寄存器的值来自于cache，此类情况下需要禁用cache。
  • 编译器优化是针对于ld命令的，从内存中读取数据到寄存器时不允许优化这一过程，而None cache保护的是对内存数据的访问（volatile无法控制ld命令执行后是否刷新cache）

2.const 和 volatile可以一起修饰一个变量吗

• 可以的，表达的语义是：我（应用层代码）不允许去写这个变量，但它的值随时可变
• 典型应用是硬件只读寄存器：代码不能写，但硬件可能会更新，比如状态寄存器

register

• 建议编译器将变量存储在CPU寄存器中，以加快访问速度（因为寄存器比内存访问快得多）
• 此关键字在C++17中被移除

inline

1.inline的作用是什么

• 此关键字会给编译器提个建议，将函数体的代码直接“复制粘贴”到每一个调用它的地方，从而完全避免了函数调用的开销。并不是用了inline就一定会被展开，取决于编译器
• 函数调用的流程，参数的入/出栈是比较耗时的

1.执行call指令，跳转到函数地址
2.压入返回地址、保存寄存器（现场保护）
3.在栈上为函数局部变量分配空间
4.执行函数体
5.清理栈空间、恢复寄存器
6.执行ret指令，跳回调用处

字符串

嵌入式笔试貌似经常让手撕字符串相关的（库）函数，而我却不记得C语言怎么用字符串了…现在总结一下

1.创建字符串

所有字符串都是以'\0'（结束符）结尾的，即使创建的时候没有添加，编译器会自动加上的，且占1个字节

// 方式1：字符数组
char str1[20] = "Hello, World!";
// 方式2：不指定长度
char str2[] = "Hello, World!";
// 方式3：逐个字符初始化
char str3[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
// 方式4：字符指针
char *str4 = "Hello, World!";  // 字符串常量，不可修改

2.常见库函数

#include <stdio.h>
// 计算字符串的长度(不计算'\0')
size_t strlen(const char *str); 
// 字符串复制(和memcpy很像，从第0个字节开始对dest覆盖，但此函数遇到'\0'自动停止)
char *strcpy(char *dest, const char *src);
char *strncpy(char *dest, const char *src, size_t n);
// 字符串拼接
char *strcat(char *dest, const char *src);
char *strncat(char *dest, const char *src, size_t n);
// 字符串转数字
int atoi(const char *str);
double atof(const char *str);
long atol(const char *str);
// 按位比较大小（返回0表示完全相等，不相等的话返回第一个不相等的字符的ASCII码差值）
int strcmp(const char *str1, const char *str2);

以char*为返回值的，char*其实是个指向dest的指针，之所以搞成这样是历史遗留问题

面试问题

1.char s[]={'a','b','c'}和char *s="abc"有什么区别

特性	char s[] = {'a', 'b', 'c'};	char *s = "abc";
类型	字符数组	指针（指向字符串字面量）
内存区域	栈/.data（取决于是局部还是全局变量）	s存在栈，而”abc”存在.rodata
结尾是否有 '\0'	无	自动添加
能否修改内容	能	不能
sizeof结果	数组大小（3）	指针大小（4或8）
strlen结果	崩溃	3

内存管理

嵌入式笔试貌似经常让手撕内存相关的（库）函数，而我却基本忘完了…现在总结一下

// 分配指定字节数的未初始化内存
void* malloc(size_t size);
// 分配指定数量和大小的内存，并初始化为0
void* calloc(size_t num, size_t size);
// 调整已分配内存块的大小(可能原地操作，也可能换个位置操作)
void* realloc(void* ptr, size_t new_size);
// 释放之前分配的内存
void free(void* ptr);
// 从源内存复制n个字节到目标内存（返回值是dest）
void* memcpy(void* dest, const void* src, size_t n);
// 安全内存复制，能处理src和dest重叠情况
void* memmove(void* dest, const void* src, size_t n);
// 将内存块的前n个字节设置为指定值
void* memset(void* ptr, int value, size_t n);
// 比较两个内存区域的前n个字节
int memcmp(const void* ptr1, const void* ptr2, size_t n);

内存对齐

• 目的：为了提升性能。CPU访问内存（比如ld汇编指令）不是以字节为单位，而是以字为单位（通常是4/8字节），字的大小就是所谓的对齐边界
  • 大多数现代CPU（如x86, ARM）对对齐的内存访问做了优化。例如，一个4字节的int变量存储在4的倍数地址上，CPU可以通过一个内存读写操作来完成访问。
  • 如果数据未对齐（例如一个int变量起始地址在0x0003），CPU可能需要执行两次内存访问（一次取0x0000-0x0003，一次取0x0004-0x0007），然后拼接出所需的数据，这大大降低了效率。

结构体内存对齐

结构体对齐是编译器为了实现内存对齐采用的一种策略，他的规则如下：

• 成员自身对齐：结构体中的每个成员变量，其地址必须是它自身大小（或编译器默认对齐值，取较小者）的整数倍

  • char（1字节）： 地址可以是任何值（1的倍数）

  • short（2字节）： 地址必须是2的倍数（0x0, 0x2, 0x4…）

  • int（4字节）： 地址必须是4的倍数（0x0, 0x4, 0x8…）

  • double（8字节）： 地址必须是8的倍数（0x0, 0x8, 0x10…）

  • 指针：在32位系统上是4字节对齐，在64位系统上是8字节对齐

• 结构体整体对齐：

  • 整个结构体的大小，必须是所有成员中最大对齐值（或编译器默认对齐值，取较小者）的整数倍

• 编译器默认对齐值：

  • 编译器通常有一个默认的对齐字节数（如8字节），可以通过预编译指令 #pragma pack(n)来修改

举点例子：

struct Example1 {
    char a;   // 1字节，地址: 0
    int b;    // 4字节，地址必须是4的倍数，不能是1 -> 填充3字节 -> 地址: 4
    short c;  // 2字节，地址: 8 (4+4=8, 是2的倍数)
}; // 总大小目前是 12 字节

Offset: 0   1   2   3   4   5   6   7   8   9   10  11
        |a | . | . | . |b |b |b |b |c |c | . | . |
    
    
// 使用#pragma pack(4)强制改变编译器的默认对齐值
#pragma pack(push, 4) // 保存当前对齐值，并设置为4
struct Example4 {
    char a;     // 1字节 -> 地址: 0
    double d;   // 8字节，但编译器对齐要求现在是4 -> 地址是4的倍数即可 -> 填充3字节 -> 地址: 4
    int b;      // 4字节 -> 地址: 12 (4+8=12, 是4的倍数)
}; // 目前大小: 0-15 -> 16字节
   // 整体对齐: 必须是min(4, max(1,8,4))=4的倍数 -> 16是4的倍数 -> 总大小: 16
#pragma pack(pop) // 恢复之前的对齐值

//如果修改编译器默认对齐值得话，就会占用24字节

类的内存分布

一个类的内存包含2部分：

• 成员变量
• 虚函数指针（如果有虚函数的话），占4字节(32位)或8字节(64位)

当有虚函数的时候，类的内存对齐会将每个成员变量填充至8字节

位段

• 定义：位段（bit filed）是结构体中的特殊成员，它把一个结构体的内存拆成多份，用于 按位分配内存，节省空间

struct {
    unsigned int flag1 : 1;  // 占1位
    unsigned int flag2 : 3;  // 占3位
    unsigned int padding : 4; // 占4位（对齐用）
} bitfield;

• 用途：

  • 硬件编程（如操作寄存器特定位）

  • 网络协议（如IP头部的标志位）

大小端

在计算机体系结构中，大小端描述的是多字节数据在内存中的存储顺序：

• 大端：高字节存储在低地址，低字节存储在高地址
• 小端：低字节存储在低地址，高字节存储在高地址

---

面试问题

1.类实例的内存大小有哪些影响原因

• 非静态成员变量：这是最主要的影响因素。所有非静态成员变量的类型和大小直接相加是基础
• 内存对齐：为了CPU高效访问内存，编译器会在成员之间插入填充字节（Padding），确保每个成员都从其自身大小整数倍的地址开始。这会导致总大小可能大于所有成员大小之和
• 虚函数：如果类有虚函数，编译器会为该类自动生成一个虚函数表指针。这个指针通常占用一个机器字长（如32位系统4字节，64位系统8字节）
• 继承：派生类会包含其所有基类的非静态成员（可能还包括基类的vptr）
• 空类：一个完全没有成员的空类，其大小通常为1字节。这是为了确保每个实例在内存中都有唯一的地址

2.成员对象的顺序会对实例的内存有影响吗

• 有影响，主要是通过内存对齐影响

3.成员函数的大小会对实例的内存有影响吗

• 不会，成员函数都存在.text段，并且所有实例共享

4.虚函数和static函数对实例的内存有影响吗

• static函数不会，虚函数会，因为它会让编译器给这个类添加一个新的成员变量（虚函数表指针），这会增大一个指针大小的开销，但是虚函数本身在.text段，无影响

5.栈内是保存什么的？malloc出来的地址在栈还是堆？

• 栈保存局部变量、函数传入的参数、函数调用返回地址以及一些CPU寄存器
• malloc分配的内存在堆区，但是它返回的指针变量本身是在栈上

6.全局变量和静态变量保存在哪里

• 看是否初始化，在.data或者.bss

7.C语言函数里面如何定义多个名字相同的变量？变量作用域？

• 不能直接定义同名变量，因为C语言在同一作用域内不允许变量重名
• 但可以通过作用域嵌套（块作用域）实现“同名”变量

8.C的函数的入参是存放在哪里？所有入参都是栈吗？

• 以RISCV为例，函数调用的入口参数放在a0~`a7`寄存器，放不下的放到栈里面

10.malloc的底层原理

malloc是C库的一个函数，它的核心任务是：在用户态的堆空间中，高效地管理一块巨大的虚拟内存（由内核提供），从中分割出小块满足申请需求，并处理释放和复用

它的底层实现依赖于C标准库（glibc），不直接操作物理内存，而是通过系统调用管理进程虚拟地址空间，整个过程分为2步：

• C库的内存管理器：它向内核“批发”大块内存（heap），然后自己设计算法（基于free list）来管理（分割、合并、分配、回收）这些内存，回应程序的 malloc/free请求。目标是速度快、碎片少
• 操作系统内核：负责“批发”和“映射”。它通过 brk和 mmap系统调用，为进程分配和映射虚拟内存页。目标是安全、隔离

11.realloc的底层原理

realloc的根本目的是改变一块已分配内存的大小。它的核心在于会根据新旧内存块的大小和位置，选择最高效的策略来完成调整，其行为可以概括为以下三种情况：

• 原地扩大：如果当前内存块后面的相邻空间是空闲的且足够大，可以直接扩展当前块，无需移动数据。这是最理想、最高效的情况
• 原地缩小：直接缩小当前块的大小，多余的部分会被释放并交还给内存管理器，放入空闲链表以供后续分配。也无需移动数据
• 异地重新分配：如果无法原地扩大，realloc会执行“分配新空间 -> 拷贝旧数据 -> 释放旧空间”的完整流程。这是开销最大的情况

12.malloc和realloc的本质区别是什么

• malloc的核心是开辟一块新内存，而realloc的核心是调整一块已分配的内存，不一定会分配新的内存

13.memcpy和memmove的区别是什么

智能指针

1.用过智能指针吗？一般用在什么地方？

2.用智能指针时需要注意什么？

STL

1.对STL有了解吗？用过哪些

2.vector和list有哪些区别

3.list是单链表还是双链表

4.用过STL的函数吗？std::sort是哪个排序

5.vector和list的sort是一样的吗

6.map和set都是有序的吗

7.unordered-map和map的底层实现是什么

8.STL是不是线程安全的？

面向对象

1.C++的多态是怎么实现的

多态通常是使用父类指针指向子类对象/引用时触发，核心是虚函数 + 虚函数表

• 每个包含虚函数的类，编译器会生成一个虚函数表，本质上是个函数指针数组
  • 虚函数本身放在.text，但是虚函数表放在.rodata
• 编译器给每个对象生成一个虚表指针（vptr），指向所属类的 vtable
• 当调用虚函数时，通过对象里的 vptr → 找到 vtable → 调用函数指针 → 跳转到 .text 段执行

2.C语言如何面向对象中成员函数的那种效果

• 结构体 + 函数指针

typedef struct Point {
    int x, y;
    void (*set)(struct Point* self, int x, int y);
    void (*print)(struct Point* self);
} Point;

void Point_set(Point* self, int x, int y) {
    self->x = x;
    self->y = y;
}
void Point_print(Point* self) {
    printf("(%d, %d)\n", self->x, self->y);
}
int main() {
    Point p = {0, 0, Point_set, Point_print}; // 初始化时绑定函数
    p.set(&p, 10, 20);   // 调用方式像成员函数
    p.print(&p);         // 输出 (10, 20)
}

3.如果用C语言实现C++的成员变量的权限要怎么实现

• 隐藏实现（不透明指针）：只在 .c 文件里定义结构体完整内容，在 .h 文件里只声明 struct

// api.h
typedef struct OpaqueType OpaqueType;   // 只声明，不定义
OpaqueType* create();
void destroy(OpaqueType* obj);
void do_something(OpaqueType* obj);
// api.c
struct OpaqueType {
    int secret;
    char name[20];
};
OpaqueType* create() {
    return malloc(sizeof(OpaqueType));
}
void destroy(OpaqueType* obj) {
    free(obj);
}
void do_something(OpaqueType* obj) {
    obj->secret = 42;
}

在 api.h 中，外部用户只能拿到 OpaqueType*，不能直接访问 struct 里的 secret 和 name，这就是不透明指针

指针

1.指针函数和函数指针有什么区别

2.什么情况下会用到函数指针

3.当struct数组的指针+1时，实际增加了多少字节

4.如何使用指针去操作内存？

5.使用指针如何避免越界访问？

C++11杂项

1.右值引用是什么

2.std::async()的原理知道吗？是用什么实现的？（协程）知道异步执行的原理吗

数据结构

元素按顺序排列，只有一个前驱和一个后继（首尾元素除外）

线性结构

1.数组

• 介绍：在内存中分配一段连续的存储空间，用于存储相同类型的数据元素。通过索引（下标）可以随机访问任何元素
• 优点：随机访问速度快（时间复杂度 O(1)）
• 缺点：大小固定（静态数组），插入和删除元素效率低（可能需要移动大量元素，时间复杂度 O(n)）
• 使用场景：
  • 需要频繁通过索引查询数据。例如，存如传感器校准值、PID参数、字体点阵、正弦波表等
  • 处理固定大小的集合例如，存储图片的像素矩阵
  • 作为其他复杂数据结构的基础（如堆、哈希表）

2.链表

• 介绍：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在内存中是非连续的
• 优点：大小动态可变，插入和删除效率高（只需修改指针，时间复杂度 O(1)，但查找位置需要 O(n)）
• 缺点：无法随机访问，查找效率低（时间复杂度 O(n)）；需要额外的空间存储指针
• 变体：
  • 单向链表：节点只指向下一个节点
  • 双向链表：节点指向前一个和后一个节点，支持反向遍历
  • 循环链表：尾节点指向头节点，形成环
• 使用场景：
  • 需要频繁插入和删除，但较少随机访问的场景。例如：实现栈、队列、双向队列
  • 浏览器的“前进”、“后退”功能（双向链表）
  • 操作系统的进程调度队列
  • LRU（最近最少使用）缓存淘汰算法（结合哈希表）

3.栈

• 介绍：一种后进先出的线性结构。只能在一端（栈顶）进行插入（压栈）和删除（弹栈）操作
• 特点：访问受限，操作简单高效
• 使用场景：
  • 函数调用栈：硬件自动使用栈来保存返回地址、局部变量、函数参数。这是栈最根本的应用
  • 上下文切换：RTOS在进行任务调度时，将当前任务的上下文（寄存器值等）压入其专属的任务栈中
  • 表达式求值：检查括号匹配、将中缀表达式转换为后缀表达式
  • 撤销/重做功能：将操作压栈，撤销时弹栈
  • 浏览器的历史记录（点击后退按钮）

4.队列

• 介绍：一种先进先出的线性结构。在一端（队尾）插入，在另一端（队头）删除
• 特点：访问受限，操作简单高效
• 变体：
  • 双端队列：两端都可以进行插入和删除
  • 优先队列：出队顺序按优先级而非入队顺序，通常用堆实现
• 使用场景：
  • 需要按顺序处理的场景。例如：消息队列、任务队列（如打印机作业排队）
  • 广度优先搜索（BFS）算法，多线程的阻塞队列

非线性结构

元素之间不存在简单的顺序关系，一个元素可能有多个前驱或后继

1.树：一种分层级的非线性结构，由节点和边组成。每个节点有零个或多个子节点

• 二叉树：每个节点最多有两个子节点（左、右）

• 满二叉树：只有度为0的结点和度为2的结点，并且度为0的结点在同一层上。深度为k的满二叉树有2^k-1个节点

• 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置
  • 特性：因为没有空位，所以可以用数组存储（按层序遍历的顺序）

关系	计算公式	例子（i=2）
父节点	parent(i) = (i - 1) / 2	(2-1)/2 = 0
左孩子	left_child(i) = 2*i + 1	2 * 2+1 = 5
右孩子	right_child(i) = 2*i + 2	2 * 2+2 = 6

• 二叉搜索树（BST）：每个节点有数值，是个有序树：左子树所有节点的值 < 根节点的值 < 右子树所有节点的值；左右子树都是二叉搜索树

  • 特性：利用中序遍历得到的数组，是升序的
  • 使用场景：动态数据集合的快速查找、插入、删除（平均 O(log n)）。用于实现集合、映射（字典）

• 平衡二叉搜索树（AVL树/红黑树）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

  

  • 红黑树：在每次插入节点后，通过旋转或重新着色来主动调整树结构，是其始终保持平衡的结构，用于解决BST退化成链表的问题，保证在最坏的情况下增删改查的性能为O(logn)

  • AVL树：当插入或删除一个节点后，可能会使得某个节点的平衡因子的绝对值大于1，这时就需要通过旋转来调整树的结构，使其重新平衡

  • 使用场景：在需要保证最坏情况下性能的场景，如数据库索引、Java中的 TreeMap、TreeSet

• 堆：一种特殊的完全二叉树，父节点的值总是大于等于（大顶堆）或小于等于（小顶堆）子节点的值

  • 使用场景：
    • 用于实现​​STL的优先队列​​(priority_queue)
    • 在RTOS中，任务调度器通常使用​​优先队列​​来决定下一个运行的最高优先级就绪任务

2.图

• 存储方式：主要有2种

  • 邻接矩阵：一个二维矩阵
  • 邻接表：还是个二维数组，每一行代表一个独立的节点，后边的每一列代表与该节点直接相连的节点

其他数据结构

1.哈希表：通过哈希函数将键映射到数组中的一个位置来访问记录，以实现 O(1) 时间复杂度的平均查找速度。

• 优点：查找、插入、删除速度极快（平均情况下）
• 缺点：哈希冲突；遍历顺序不确定；最坏情况下性能退化到 O(n)
• 使用场景：需要快速查找、插入、删除的场景。例如：
  • 实现字典、集合（如Python的 dict，Java的 HashMap）
  • 缓存（如Memcached、Redis）
  • 快速去重

2.跳表：在有序链表的基础上添加了多级索引，以提高查找效率。可以视为一种“以空间换时间”的算法

• 特点：实现相对简单，效率与平衡树媲美（查找、插入、删除平均 O(log n)）
• 使用场景：
  • Redis中的有序集合（Sorted Set）实现

面试问题

1.哈希表的实现原理

• 哈希表的核心思想是 “基于键的快速随机访问”，它通过一个函数将键（Key）直接映射到一个存储位置，从而在平均情况下实现O(1)时间复杂度的插入、删除和查找。它的核心包括3个部分：
  • 哈希函数：接收一个键（Key）作为输入，经过计算，输出一个整数（哈希值）
  • 哈希桶：这是一个数组，大小通常为质数（为了取模时更均匀），每个元素是一个存储位置
  • 冲突解决：不同的 key 可能被哈希函数映射到同一个地址，这叫哈希冲突。解决冲突是哈希表的关键

2.平衡二叉树的实现原理

• 有多种实现方式，常见的有红黑树和AVL树，通过每次插入新节点之后调整树的结构来使其一直保持近似平衡，主要是为了解决退化成链表的问题

3.你之前用过哪些数据结构

算法

递归

递归的三要素：

• 1.确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型
• 2.确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，编译器也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出
• 3.确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程

最简单的递归例子：

void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
}

回溯

回溯是通过递归来实现的，其本质是穷举所有可能，最多再加一些剪枝操作，所以性能一般很差。回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出K个数的集合
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等

回溯法一般都可以抽象成树形结构（N叉树），它解决的问题一般是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度

回溯算法模板：

• 回溯函数模板返回值以及参数
  • 一般返回值是void
  • 参数里一般都有for循环用的startIndex
• 回溯函数终止条件
  • 一般是到达叶子节点
• 回溯搜索的遍历过程（for循环嵌递归）
  • for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

图论

图论中的算法题一般包含以下几部分：

• 遍历类问题
  • 连通性检测
  • 路径存在性检测
• 最短路径问题
• 拓扑排序问题
• 并查集

深度优先搜索

定义：往一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向，它其实是一种回溯

DFS用于各种数据结构中，比如：

• 二叉树的前/中/后序遍历
• 图论问题（邻接矩阵/邻接表）中找所有满足条件的路径

代码框架：

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

// x：目前遍历的节点
// n：终点
void dfs (const vector<vector<int>>& grid, int x, int n){
    // 当前遍历的节点x 到达节点n 
    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
        if (grid[x][i] == 1) { // 找到 x链接的节点
            path.push_back(i); // 遍历到的节点加入到路径中来
            dfs(grid, i, n); // 进入下一层递归
            path.pop_back(); // 回溯，撤销本节点
        }
    }
}

广度优先搜索

定义：先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程

代码框架：

// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || 
                nexty < 0 || nexty >= grid[0].size()) 
                continue;  // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

什么时候需要使用visited矩阵

• 主要看走回头路的话会不会有影响，有影响的话就需要使用，DFS和BFS都可能使用到
• 有环图必须用，不然出不去了

什么时候用BFS/DFS

问题是否需要找所有解/路径？ → 是 → 用DFS（回溯）
  ↓否
问题是否需要最短路径/最小步数？ → 是 → 用BFS
  ↓否  
问题是连通性检测/拓扑排序？ → 是 → 两者都可，DFS更简洁
  ↓否
问题是层级遍历/最近邻？ → 是 → 用BFS
  ↓否
问题是多源扩散？ → 是 → 用BFS
  ↓否
用DFS（默认选择）

拓扑排序

定义：针对有向无环图，输出满足其依赖关系的顶点线性序列

具体步骤就2步:

1. 找到入度为0 的节点，加入结果集
2. 将该节点从图中移除

循环以上两步，直到 所有节点都在图中被移除了，结果集的顺序，就是我们想要的拓扑排序的顺序

贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。贪心没有状态推导，而是从局部直接选最优的

动态规划

相比于贪心，动态规划中每一个状态一定是由上一个状态推导出来的

动态规划写题步骤：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

查找

排序

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	是否稳定	适用场景
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模数据、教学示例
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	交换次数少、小规模数据
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模、基本有序的数据
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定	大规模数据、内存排序
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	外部排序（磁盘数据）、链表排序
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	大规模数据、内存受限场景
希尔排序	O(n log n)	O(n²)	O(n log n)	O(1)	不稳定	中等规模数据、改进的插入排序
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定	非负整数、范围较小的数据
桶排序	O(n + k)	O(n²)	O(n)	O(n + k)	稳定	均匀分布的数据
基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	稳定	整数或字符串排序

1.选择排序：多次遍历数据，每次都找到最小元素然后把他放到无序数据的左边(直接用swap)

void select_sort(vector<int>& nums)
{
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i)
    {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (nums[j] < nums[min_idx])
                min_idx = j;
        }
        swap(nums[i], nums[min_idx]);
    }
}

2.冒泡排序：不断把较大的元素移到右边，通过交换 arr[sortedIndex] 右侧的逆序对完成排序

void bubble_sort(vector<int> &nums)
{
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n - i - 1; ++j)
        {
            if (nums[j] > nums[j+1])
                swap(nums[j], nums[j+1]);
        }
    }
}

3.插入排序：将未排序部分的元素逐个插入到已排序部分的正确位置，类似于整理扑克牌

算法思路：

(1)初始状态：数组的第一个元素视为已排序部分，其余部分视为未排序

(2)遍历未排序部分：从第二个元素开始，逐个取出元素

(3)插入到正确位置：

• 将该元素与已排序部分的元素从后向前比较
• 如果当前元素比已排序部分的某个元素小，则将该元素后移一位
• 直到找到合适的位置，插入当前元素

(4)重复执行，直到所有元素都被插入到正确位置

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {       // 从第二个元素开始
        int key = arr[i];               // 当前待插入元素
        int j = i - 1;                  // 已排序部分的最后一个元素索引

        // 从后向前比较，找到合适的插入位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];        // 比 key 大的元素后移
            j--;
        }
        arr[j + 1] = key;              // 插入 key 到正确位置
    }
}

4.快速排序：

• 首先选择一个基准元素pivot（最左/最右/随机…）对数据进行分区（partition），不断调整元素位置使得左侧的数据都小于这个基准元素、右侧的数据都大于这个基准元素
• 然后对左侧和右侧的数组递归进行快速排序

代码思路：

• 指针 i：记录“已处理的≤pivot部分”的最后一个位置
• 指针 j：从左到右扫描数组，检查每个元素是否应该放到左边

// 分区函数，返回基准的最终位置
int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right];  // 选择最后一个元素作为基准的初始值
    int i = left - 1;        // i最后会指向左边部分的末尾,这里只是初始化一下
    
	//`j`从左到右扫描，如果 `nums[j] <= pivot`，就交换 `nums[++i]`和 `nums[j]`
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // 将小于基准的元素移到左边
        }
    }
    swap(arr[i + 1], arr[right]);   // 将基准放到正确的位置
    return i + 1;
}

// 快速排序主函数
void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);  // 获取基准位置
        quickSort(arr, left, pivotIndex - 1);         // 递归排序左半部分
        quickSort(arr, pivotIndex + 1, right);        // 递归排序右半部分
    }
}

5.归并排序

归并排序是一种分治法排序算法，核心思想是将数组分成两半，分别排序后再合并。它的时间复杂度稳定为 O(n log n)，是稳定排序（相等元素的相对顺序不会改变），但需要 O(n) 的额外空间

归并排序分为两个主要阶段：

1.分（Divide）：递归地将数组分成两半，直到每个子数组只有一个元素（此时天然有序）

原始数组：[38, 27, 43, 3, 9, 82, 10]
第一次分割：左 [38, 27, 43, 3] | 右 [9, 82, 10]
第二次分割：
  左 [38, 27] | 右 [43, 3]
  左 [9, 82] | 右 [10]
第三次分割：
  左 [38] | 右 [27]
  左 [43] | 右 [3]
  左 [9] | 右 [82]
  左 [10]

2.治（Merge）：将两个有序子数组合并成一个更大的有序数组

1. 合并 [38] 和 [27] → [27, 38]
2. 合并 [43] 和 [3] → [3, 43]
3. 合并 [27, 38] 和 [3, 43] → [3, 27, 38, 43]
4. 合并 [9] 和 [82] → [9, 82]
5. 合并 [9, 82] 和 [10] → [9, 10, 82]
6. 最终合并 [3, 27, 38, 43] 和 [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

void merge(vector<int> &nums, int left, int mid, int right)
{
    vector<int> temp(right - left + 1);
    int k = 0;
    int i = left;
    int j = mid + 1;
    while (i < mid && j < right)
    {
        if (nums[i] < nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    }
    while (i < mid)
        temp[k++] = nums[i++];
    while (j < right)
        temp[k++] = nums[j++];


    for(int n = 0;n<temp.size();++n)
    {
        nums[left + n] = temp[n];
    }
}

void merge_sort(vector<int> &nums, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    merge_sort(nums, left, mid);
    merge_sort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}