由于考研失利,最近在准备春招,想要找一份游戏客户端开发的岗位,便想要将 C++ 常见的面试题整理出来。题目来自牛客网的 C++ 面试题库,答案结合了牛客网给出的参考答案、new bing 给出的回答以及个人的理解和思考。

C++ 和 C 中 struct 的区别,以及 C++ 中 struct 和 class 的区别

C++ 和 C 中 struct 的区别

  • C 中 struct 只能定义成员变量,不能定义成员函数,而 C++ 中 struct 可以定义成员函数,甚至构造函数,析构函数,友元等。
  • C 中 struct 内的成员变量不可以直接初始化,而 C++ 中可以。
  • C 中使用结构体需要加上 struct 关键字,或者使用 typedef 对结构体取别名后再直接使用其别名,而 C++ 使用结构体则可以直接忽略 struct 关键字。

C++ 中 struct 和 class 的区别

  • class 的成员默认是 private 的,而 struct 的成员默认是 public 的。
  • class 继承默认是 private 继承,而 struct 继承默认是 public 继承。

static 关键字的作用

  • static 可以修饰全局变量和函数,使它们只在本文件内可见,隐藏于其他文件。
  • static 可以修饰局部变量,使它们具有静态存储期,只初始化一次,且在函数调用结束后不销毁。
  • static 可以修饰类的成员变量和成员函数,使它们属于类而不属于对象,可以直接通过类名访问,且只有一份内存空间。

什么是野指针,怎么产生,如何避免

什么是野指针

野指针是指指向不可用内存的指针,可能会导致内存泄漏和程序崩溃。

野指针如何产生

  • 指针定义时未被初始化,指向随机的内存地址。
  • 使用 delete 释放内存空间后指针未被置空,指向已释放的内存地址。
  • 数组越界,指向非法的内存地址。

野指针如何避免

  • 指针定义时尽量初始化,或者赋值为 nullptr。
  • 使用 delete 释放内存空间后要将指针及时置空,或者使用智能指针。
  • 指针操作时注意边界检查,避免越界。

C 和 C++ 的区别

  • C 是一种面向过程的语言,而 C++ 是一种面向对象的语言,支持类和对象的概念。
  • C++ 包含了 C 的大部分语法,同时增加了一些新的特性,如继承、多态、模板、异常处理等。
  • C 使用 malloc 和 free 函数进行内存的动态分配和释放,C++ 则使用 new 和 delete 运算符。
  • C 只有局部和全局两个作用域,而 C++ 中有局部、全局、类、命名空间。

使用 const 和 define 定义常量的区别

  • const 定义的常量是变量,带有数据类型,而 define 定义的常量是预处理器替换的文本,不带数据类型。
  • const 定义的常量在编译运行时起作用,可以进行调试,而 define 定义的常量在预处理阶段起作用,不能进行调试。
  • const 定义的常量可以进行作用域限制,而 define 定义的常量没有作用域的概念。
  • const 定义的常量可以进行类型检查,而 define 定义的常量不能进行类型检查。

extern 的作用,extern 变量在内存的哪个数据段,为什么要 extern C

extern 的作用

extern 是 C 语言的关键字,用来引用不在同一个文件的变量或函数。

extern 变量存储在在内存的哪个数据段

extern 修饰一个变量,表明该变量是一个外部变量,也就是全局变量,因此存储在内存的静态存储区(全局区),也就是说它的生命周期是整个程序的运行周期。

为什么要 extern C

extern C 的作用是用来在 C++ 程序中调用 C 的函数,由于 C++ 支持函数重载,因此 C++ 的函数名会经过编译器的修饰,而 C 的函数名不会,因此需要用 extern C 来告诉编译器按照 C 的方式来处理函数名。

const 关键字的用法

  • 用来修饰指针变量,防止修改指针指向的内容或地址。
  • 用来修饰变量,使得该变量的值在初始化后不能被修改。
  • 用来修饰类的成员函数,使得函数不能修改类的成员变量。

各类型的 sizeof() 是多少,指针的 sizeof() 是多少,sizeof() 实现原理

各类型的 sizeof() 值

不同环境下各类型的 sizeof() 可能不同,这取决于机器和编译器,以下为 MSVC 32 bit 环境下各类型大小。

type size
bool 1B
char 1B
int 4B
float 4B
double 8B

指针的 sizeof() 值

由于指针存储的实质上是地址,因此它的大小取决于机器位数,在 32 位环境下为 4B,在 64 位环境下为 8B.

sizeof() 实现原理

sizeof() 是在编译期间,通过查找符号表,判断类型,然后根据基础类型来取值。对于基本数据类型,sizeof() 直接返回它们的固定大小;对于复合类型,如结构体类型,sizeof() 会考虑它们的内部结构和对齐方式,并返回它们的总大小。

C 语言的 volatile 有什么用,可以和 const 同时使用吗

volatile 的作用

C 语言的 volatile 是一个修饰符,用来告诉编译器不要对 volatile 修饰的变量进行优化,而是每次都从内存中读取它的值。这是因为 volatile 变量可能会被外部因素改变,比如中断、硬件设备或者多线程。

可以和 const 同时使用吗

const 是另一个修饰符,用来声明一个只读变量。

volatile 和 const 可以同时使用,表示一个只读的但可能会被外部因素改变的变量。

C++ 引用的概念

  • 引用是 C++ 相对于 C 语言的一个扩充。C++ 引用的概念是指一个变量的别名,也就是说,它是某个已存在变量的另一个名字,通过这个名字和原本的名字都可以找到其指定的数据。
  • 引用必须初始化,且初始化后不能改变其所绑定的对象。
  • 引用的本质是指针,底层实现还是指针。

指针和引用的区别

  • 指针是一个变量,存储的是一个地址,指向内存的一个存储单元;引用是原变量的一个别名,与其引用的变量实质上是同一个东西。
  • 指针可以不初始化,也可以为空;引用必须初始化,且不能为空。
  • 指针可以改变指向;引用不能改变指向。
  • 指针可以有多级;引用只能有一级。
  • 指针作为函数参数传递时传递的是指针变量的值,而引用作为参数传递的是实参本身。

内联函数的作用

  • 由于函数调用过程需要进行参数传递、上下文保存与恢复等操作,因此会引入时间与空间上的额外开销。通过编译器预处理,在调用内联函数的地方将内联函数内的语句复制到调用函数处,也就是直接展开代码执行,从而提高了效率,减少了不必要的开销。
  • 内联函数相比宏定义函数来说,有参数类型检查,执行更加安全。
  • 声明内联函数使用关键字 inline,但该关键字并不是一个强制要求,只是对编译器的一个建议,当内联函数体包含循环或递归等复杂结构时,编译器将不接受该建议,而将该函数当作普通函数对待。

简述 C++ 的内存管理

  • 代码区:存放程序的可执行指令,通常是只读的,可以被多个进程共享。
  • 数据区:存放程序的全局变量和静态变量,分为初始化和未初始化两部分。初始化部分包含了程序赋予初始值的变量,未初始化部分包含了程序没有赋予初始值的变量。
  • :存放程序动态分配的内存,由程序员控制其生命周期。堆是一个向上增长的数据结构,可以根据需要扩展或收缩。使用 new 和 delete 操作符分配和释放堆上的内存时,需要注意避免内存泄漏或野指针等问题。
  • :存放程序的局部变量和函数调用的参数和返回地址。栈是一个向下增长的数据结构,具有后进先出(LIFO)的特性。栈上的内存由编译器自动分配和释放,不需要程序员干预。栈上的内存空间通常有限,因此不适合存放大量或复杂的数据。

堆空间和栈空间的区别

  • 堆空间是由程序员动态分配和释放的,栈空间是由编译器自动分配和释放的。
  • 堆空间的大小可以根据需要扩展或收缩,栈空间的大小通常有限。
  • 堆空间的访问速度比栈空间慢,堆空间也容易产生内存碎片或内存泄漏等问题。
  • 堆空间的地址增长方向是向上的,也就是沿着内存地址增加的方向,而栈空间是向下的,也就是沿着内存地址减小的方向增长。

什么是内存泄漏,如何避免,如何检测

什么是内存泄漏

内存泄漏是指程序中已动态分配的堆内存由于某种原因未能正确释放,造成系统资源的浪费,导致程序运行速度减慢甚至系统崩溃等严重后果。

如何避免

  • 养成良好的编码习惯,动态分配内存后及时释放。
  • 使用智能指针来避免内存泄漏。

如何检测

检测内存泄漏有多种方法,其中一种是使用 Visual Studio 的 CRT 库,它可以在调试时输出内存泄漏的报告,包括泄露的内存块和调用栈。

另一种方法时使用 Visual Leak Detector 这个开源工具,它可以在调试时检测和报告内存泄露。

简述 C++ 的内存对齐

什么是内存对齐

内存对齐是指一个数据类型所定义的所有变量的内存地址都是某个数的倍数(通常为 4 或 8)。

内存对齐的原因

  • 平台原因:不是所有的硬件平台都能访问任意地址上的任意数据,某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。
  • 性能原因:因为 CPU 一次读取地字节数是固定的,如果一个变量跨越了多个字节,就需要多次读取,因此为了提高 CPU 访问内存的效率,数据结构应该尽可能在自然边界上对齐。

内存对齐的规则

内存对齐的规则是根据数据类型和编译器设置来确定的,一般有以下几点:

  • 结构体的第一个成员从 0 开始计算偏移量。
  • 第二个和之后的成员要放在该成员的大小与对齐模数比取较小值的整数倍上。
  • 结构体或类本身也要按照其最大属性大小与对齐模数比取较小值进行对齐。
  • 如果使用了 C++11 提供的关键字 alignas 和 alignof,可以指定或查询某个类型或变量的对齐方式。

简述 malloc() 的实现原理

malloc() 是一个用于动态内存分配的函数,它返回一个指向至少 size 字节的连续内存区域的指针。

malloc() 的实现原理是维护一个内存空闲链表,当申请内存时,搜索内存空闲链表,找到适配的空闲内存空间,如果没有搜索到,那么就调用 sbrk() 推进 brk 指针来申请内存空间。然后将空间分割为两个内存块,一个变成分配块,一个变成新的空闲块。调用 free() 时,将用户释放的内存块连接到空闲链表上。

简述 new 的实现原理,new 和 malloc() 的区别是什么

new 的实现原理

  • 对于基本数据类型,new 运算符直接调用 operator new() 函数, 在 operator new() 函数内会调用 malloc() 函数。
  • 对于复杂数据类型,new 运算符先调用 operator new() 函数分配内存空间,然后在分配的内存空间上调用用构造函数。

new 和 malloc() 的区别

  • new 是运算符,而 malloc() 是函数。

  • new 不仅分配内存,还调用构造函数;malloc() 只分配内存,不调用构造函数。

  • new 返回指定类型的指针;malloc() 返回 void* 类型的指针。

  • new 可以重载;malloc() 不能重载。

  • new 申请分配空间失败会抛出异常;而 malloc() 会返回 NULL.

简述 delete 和 free() 的区别

  • delete 是运算符,而 free() 是函数。
  • delete 用于释放 new 分配的空间,free() 用于释放 malloc() 分配的空间。
  • delete 会调用对象的析构函数,free() 只释放内存。
  • delete 可以重载,free() 不能重载。

简述一下什么是面向对象

面向对象的三大特征:封装、继承和多态。面向对象思想是基于面向过程思想的,要说面向对象思想,首先说说面向过程思想。

面向过程是一种以过程为中心的编程思想,主要是使用函数实现面向过程的思想。面向过程是把解决问题的步骤分析出来,然后用函数把这些步骤实现,在一步一步的具体步骤中再按顺序调用函数。面向过程是一种最为实际的思考方式,也是一种基础的方法。

面向对象的思想是把要解决的问题分解成各个对象,每个对象都有自己的属性和行为。面向对象的编程是以对象为中心,通过调用对象的方法来实现功能。面向对象的编程有三大特征:封装、继承和多态。封装是把数据和操作数据的方法封装在一起,提高安全性和复用性;继承是子类可以继承父类的属性和方法,实现代码的重用;多态是不同的子类可以有不同的行为,提高程序的灵活性。

简述一下 C++ 的重载和重写

C++ 的重载和重写是两个不同的概念。

  • 重载是指在同一类中定义多个同名的函数,但是参数列表不同。重载可以实现编译时的多态性,即根据参数的类型和个数来选择合适的函数调用。重载是多个函数或者同一个类中方法之间的关系,是平行关系。

  • 重写是指在子类中重新定义父类中的虚函数,即函数名和参数都一样。重写可以实现运行时的多态性,即根据对象的实际类型来选择合适的函数调用。重写是父类与子类之间的关系,是垂直关系。

简述一下面向对象的三大特征

面向对象的三大特征是:封装、继承、多态。

  • 封装是指将数据和行为组合成一个整体,对外部隐藏内部的实现细节,只提供必要的接口。封装可以保护数据的安全性,降低代码的复杂度,提高代码的可维护性。C++ 通过 private、protected、public 关键字来控制成员变量和成员函数的访问权限。

  • 继承是指子类可以继承父类的属性和方法,并且可以添加或修改自己特有的属性和方法。继承可以提高代码的复用性;提高代码的拓展性;同时也是多态的前提。

  • 多态是指不同类型的对象对同一消息可以做出不同的响应。多态可以分为编译时多态和运行时多态。编译时多态是指通过重载实现的多态,即在同一个类中定义了相同名称但不同参数的方法,根据调用时传递的参数不同而执行不同的方法。运行时多态是指通过重写实现的多态,即在子类中重新定义了父类中已有的方法,根据调用时使用的对象不同而执行不同的方法。多态可以实现接口的统一,增加程序的灵活性和可扩展性。

简述一下浅拷贝和深拷贝

  • 浅拷贝又称为值拷贝,将源对象的值拷贝到目标对象中,如果对象中有某个成员是指针类型数据,并且是在堆区创建,则使用浅拷贝仅仅拷贝的是这个指针变量的值,也就是在目标对象中该指针类型数据和源对象中的该成员指向的是同一块堆空间。这样会带来一个问题,就是在析构函数中释放该堆区数据,会被释放多次。默认的拷贝构造函数和默认的赋值运算符重载函数都是浅拷贝。

  • 深拷贝在拷贝的时候先开辟出和源对象大小一样的空间,然后将源对象里的内容拷贝到目标对象中去,这样指针成员就指向了不同的内存位置。并且里面的内容是一样的,这样不但达到了拷贝的目的,还不会出现问题,两个对象先后去调用析构函数,分别释放自己指针成员所指向的内存。即为每次增加一个指针,便申请一块新的内存,并让这个指针指向新的内存,深拷贝情况下,不会出现重复释放同一块内存的错误。

简述一下 C++ 的多态

C++ 的多态是指相同的对象收到不同的消息或不同的对象收到相同的消息时产生不同的实现动作。C++ 支持两种多态:编译时多态(静态多态)和运行时多态(动态多态)。

编译时多态是编译器在编译期间完成的,编译器会根据实参类型来选择调用合适的函数,如果有合适的函数就调用,没有的话就会发出警告或者报错。静态多态有函数重载、运算符重载、泛型编程等。

运行时多态是通过虚函数和继承来实现的,它是在运行阶段根据对象的类型来动态地确定函数调用的版本。虚函数允许子类重新定义成员函数,而子类重新定义父类的做法称为覆盖 (Override),或者称为重写。

简述一下虚函数的实现原理

编译器处理虚函数时,给每个对象添加一个隐藏的成员。隐藏的成员是一个指针类型的数据,指向的是函数地址数组,这个数组被称为虚函数表(virtual function table,vtbl)。虚函数表中存储的是类中的虚函数的地址。如果派生类重写了基类中的虚函数,则派生类对象的虚函数表中保存的是派生类的虚函数地址;如果派生类没有重写基类中的虚函数,则派生类对象的虚函数表中保存的是父类的虚函数地址。

因为虚函数需要虚函数表来实现动态绑定,而虚函数表会占用额外的内存空间,并且可能影响到编译器的优化,因此使用虚函数时,在内存和执行速度方面会有一定的开销。

什么是纯虚函数,有什么作用

纯虚函数是一种特殊的虚函数,它在基类中没有函数体,只有函数声明,并且用 <虚函数声明> = 0 来标识。纯虚函数的作用是为了实现一个接口,起到一个规范的作用,规范继承这个类的程序员必须实现这个函数。如果一个类中有纯虚函数,那么这个类就是一个抽象类,不能被实例化,只能被继承。

虚析构函数有什么作用

虚析构函数是为了避免内存泄漏,而且是当子类中有指针成员变量时才使用得到。虚析构函数使得在释放指向子类对象的基类指针时,可以调用子类的析构函数来实现释放子类堆内存的目的,从而防止内存泄漏。如果基类的析构函数是虚函数,那么派生类的析构函数不论是否用 virtual 关键字声明,都自动成为虚析构函数。

重载、重写、隐藏有什么区别

  • 重载是指同一作用域中,函数名相同但参数列表不同的函数。
  • 重写是指派生类中重新定义了与基类中同名、同参数列表、同返回值类型的虚函数。
  • 隐藏是指不同作用域中定义的同名函数构成隐藏。如派生类中定义了与基类中同名的函数,无论参数列表是否相同,基类函数都会被隐藏。

什么情况会调用拷贝构造,什么时候会调用赋值操作

  • 拷贝构造函数是用一个已经存在的对象来初始化另一个新创建的对象。拷贝构造函数有三种情况会被调用:
    • 当用类的一个对象去初始化类的另一个对象时,如 Data data1; Data data2 = data1;.
    • 函数的形参是类的非引用对象,进行参数传递时。
  • 赋值操作符是将一个已经存在的对象赋给另一个已经存在的对象。只有当两个对象初始化之后,通过 = 运算符进行赋值的时候,如 Data data1; Data data2; data2 = data1;.

虚函数可以是内联函数吗

  • 虚函数可以是内联函数,但是当虚函数表现多态性的时候不能内联。因为内联是在编译期建议编译器内联,而虚函数的多态性在运行期,编译器无法知道运行期调用哪个函数。
  • inline virtual 唯一可以内联的时候是:编译器知道所调用的对象是哪个类,这只有在编译器具有实际对象而不是对象的指针或引用时才会发生。

简述虚函数与纯虚函数的区别

  • 虚函数可以有定义,也可以没有定义;纯虚函数一定没有定义,只是声明了接口。
  • 虚函数可以被子类重写(override),也可以不被重写;纯虚函数必须被子类实现。
  • 虚函数的声明形式是 virtual void func(); 纯虚函数的声明形式是 virtual void func() = 0;
  • 含有纯虚函数的类叫做抽象类,不能实例化,派生类必须实现父类所有的纯虚函数才可以实例化,否则也是抽象类;而含有虚函数的类则无此限制。

简述 C++ 的四种类型转换

  • static_cast:明确指出类型转换,没有动态类型检查,上行转换(派生类到基类)安全,下行转换(基类到派生类)不安全。
  • dynamic_cast:用于有条件的转换,动态类型检查,运行时检查类型安全(转换失败返回 NULL),只能用于多态类型的指针或引用。
  • const_cast:用于改变运算对象的底层 const 属性,不能改变其顶层 const 属性。
  • reinterpret_cast:用于无关类型之间的转换,如整型和指针,不同类型的指针等。

STL 中有哪些常见的容器

STL 中的容器是用来管理某类对象的数据结构,可以分为顺序容器和关联容器两大类。

顺序容器是指元素位置取决于插入顺序的容器,有 vector、deque、list、forward_list、string、array .

  • vector:可变大小数组。支持快速随机访问。在尾部之外的位置增删元素可能很慢。
  • deque:双端队列。支持快速随机访问。在头尾位置增删元素速度很快。
  • list:双向链表。只支持双向顺序访问。在任何位置增删元素都能在常数时间完成。不支持随机存取。
  • forward_list:单向链表。只支持单向顺序访问。在链表的任何位置增删元素都能在常数时间内完成,由于没有了 size 操作以及简化了增删元素的链表节点操作,速度相比双向链表更快。不支持随机存取。
  • string:字符串。与 vector 相似的容器,但专门用于保存字符。随机访问快。在尾部增删元素快。
  • array:定长数组。支持快速随机访问。不能添加和删除元素。

关联容器是指元素位置取决于排序准则或键值的容器,有 map、set、multimap、multiset、unordered_map、unordered_set、unordered_multimap、unordered_multiset.

  • map:关联数组。保存键值对。
  • set:关键字即值,即只保存关键字的容器。
  • multimap:关键字可重复出现的 map.
  • multiset:关键字可重复出现的 set.
  • unordered_map:用哈希函数组织的 map.
  • unordered_set:用哈希函数组织的 set.
  • unordered_multimap:用哈希函数组织的 map;关键字可重复出现。
  • unordered_multiset:用哈希函数组织的 set;关键字可重复出现。

除了这些基本的容器,STL 还提供了一些容器适配器,如 stack、queue 和 priority_queue,它们是对其他容器进行封装和修改而得到的特殊用途的数据结构。

vector 和 list 有什么区别,分别适用于什么场景

vector 和 list 的区别主要有以下几点:

  • vector 底层是数组,list 底层是双向链表。
  • vector 支持随机访问,list 不支持。
  • vector 中的数据存储在连续的内存空间,而 list 中的元素在内存中的存放不是连续的。
  • vector 在中间增删元素会导致内存拷贝,list 不会。

一般来说,如果需要频繁的随机访问和查询,可以使用 vector;如果需要频繁的插入删除操作,可以使用 list。

简述 vector 的实现原理

vector 是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问。

由于具有连续的存储空间,所以在插入和删除操作方面,效率较低。 当 vector 的大小和容量相等(size == capacity),如果再向其添加元素,那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步:

  1. 完全弃用现有的内存空间,重新申请更大的内存空间。
  2. 将旧内存空间中的数据,按原有顺序移动到新的内存空间中。
  3. 最后将旧的内存空间释放。 vector 扩容是非常耗时的。为了降低再次分配内存空间时的成本,每次扩容时 vector 都会申请比用户需求量更多的内存空间(这也就是 vector 容量的由来,即 capacity >= size),以便后期使用。

不同的编译器在扩容时所采用的扩容因子可能不同,比如 MSVC 的扩容因子为 1.5,即每次扩容时容量变为原来的 1.5 倍。

迭代器失效的原因是什么,有哪些情况

STL 中某些容器调用了某些成员方法后会导致迭代器失效。

顺序容器迭代器失效:如 vector,由于容器内的元素是连续存储的,对容器执行元素插入操作后,如果导致容器扩容,那么所有的迭代器都将失效;如果没有扩容,那么插入位置之后的迭代器都会失效。而删除元素不会导致扩容,因此只有删除位置之后的迭代器会失效。

关联式容器迭代器失效:对于关联容器,如 map、 set,删除当前的迭代器,仅仅会使当前的迭代器失效,这是因为 map 之类的容器,使用了红黑树来实现,插入、删除一个节点不会对其他点造成影响。

简述 deque 的实现原理

deque 由一段一段的定量的连续空间构成,每段空间称为一个缓冲区。这些缓冲区通过一个 map 数组作为主控来进行管理,map 数组中存储了指向每个缓冲区的指针。deque 最大的工作就是维护这些分段连续的内存空间逻辑上的整体性,并提供随机存取的接口,避开了重新配置空间,复制,释放的轮回,代价就是复杂的迭代器架构。

简述 set 的实现原理

set 底层使用红黑树实现,一种高效的平衡二叉搜索树。

  • set 的插入操作是先在红黑树中找到合适的位置,然后创建一个新节点,并将其颜色设为红色。如果新节点的父节点也是红色,那么就需要进行旋转和变色操作来恢复平衡。
  • set 的删除操作是先在红黑树中找到要删除的节点,然后用其后继或前驱替换它,并释放原来的节点。如果被删除或替换的节点是黑色,那么就需要进行旋转和变色操作来恢复平衡。
  • set 的查找操作是沿着二叉搜索树的路径向下查找,直到找到目标元素或者为空为止。由于红黑树保证了高度平衡,所以查找操作的时间复杂度为 O(log n)。

简述 map 的实现原理,各操作的时间复杂度是多少

  • map 是一种模板类,它的模板参数是键值对的类型和比较函数。比较函数用来定义键值对之间的大小关系,从而确定键值对在红黑树中的位置。
  • map 的底层数据结构也是红黑树,它与 set 的红黑树相同,只是每个节点存储的不是单个元素,而是一个 pair 对象,包含一个 key 和一个 value。
  • map 的插入操作是先在红黑树中找到合适的位置,然后创建一个新节点,并将其颜色设为红色。如果新节点的父节点也是红色,那么就需要进行旋转和变色操作来恢复平衡。
  • map 的删除操作是先在红黑树中找到要删除的节点,然后用其后继或前驱替换它,并释放原来的节点。如果被删除或替换的节点是黑色,那么就需要进行旋转和变色操作来恢复平衡。
  • map 的查找操作是沿着二叉搜索树的路径向下查找,直到找到目标键值对或者为空为止。

由于红黑树保证了高度平衡,因此各操作的时间复杂度均为 O(log n)。

简述红黑树的特性,为什么要有红黑树

红黑树的特性

  • 每个节点只能是红色或者黑色。
  • 根节点必须是黑色。
  • 每个叶子节点(NIL 或 NULL)都是黑色。
  • 如果一个节点是红色,那么它的两个子节点都是黑色。
  • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

为什么要有红黑树

虽然平衡二叉树解决了二叉搜索树退化为近似链表的缺点,能够把查找时间控制在 O(log n),但却不是最佳的。因为平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个要求实在过于苛刻,导致每次进行插入/删除节点的时候,几乎都会破坏平衡树的这一规则,进而导致需要通过左旋和右旋来进行调整,使之再次成为一颗符合要求的平衡树。

显然,在那些插入、删除频率较高的场景中,平衡树需要频繁进行调整,这会使得平衡树的性能大打折扣,为了解决这个问题,就诞生了红黑树。

简述 unordered_map 的实现原理

unordered_map 是一种无序的关联容器,它存储了键值对的集合,其中每个键都是唯一的。

unordered_map 的实现原理是基于哈希表,通过把关键码值映射到哈希表中一个位置来访问记录。

unordered_map 中的元素没有按照它们的键值或映射值的任何顺序排序,而是根据它们的散列值组织成桶以允许通过它们的键值直接快速访问单个元素(具有常数平均时间复杂度)。

当两个元素具有相同的散列值时,会发生哈希冲突。为了解决这个问题,unordered_map 采用了链地址法,即每个桶中存储一个链表,链表中存放所有散列值相同的元素。

简述哈希冲突的原因、影响因素和解决办法

原因

哈希是通过对数据进行再压缩,提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的,而数据可能比较多,导致经过哈希函数处理后仍然有不同的数据对应相同的值,这时候就产生了哈希冲突。

影响因素

装填因子(装填因子 = 数据总数 / 哈希表长)、哈希函数、处理冲突的方法 。

解决办法

  • 开放地址法:当发生冲突时,寻找一个新的空闲的哈希地址,如线性探测法、平方探测法等。

  • 链式地址法:将所有哈希地址相同的数据链接在同一链表中。C++ 的无序容器使用的就是这种方法。

  • 再哈希法:当发生冲突时,使用另一个哈希函数计算新的哈希地址。

  • 建立公共溢出区:将所有发生冲突的数据存储在一个单独的区域中。

简述 map 和 unordered_map 的区别

map 基于红黑树实现,该结构具有自动排序的功能,因此 map 内部的所有元素都是有序的,红黑树的每一个节点都代表着 map 的一个元素。因此,对于 map 进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行这样的操作,故红黑树的效率决定了 map 的效率,其增删查改时间复杂度为 O(log n).

而 unordered_map 内部实现了一个哈希表,因此其元素的排列顺序是杂乱的,无序的。且增删查改时间复杂度为 O(1).

C++ 智能指针和指针的区别是什么

如果在程序中使用 new 关键字从堆(自由存储区)分配内存,等到不需要时,应使用 delete 将其释放。如果未能及时释放,该部分内存在程序运行期间将无法被释放,造成内存泄漏。

为了更方便地进行动态内存分配,C++11 新增了三种智能指针:unique_ptr、shared_ptr 和 weak_ptr.

智能指针实际上是对普通指针的封装,区别是它负责自动释放所指的对象,这样的一层封装机制的目的是为了使得智能指针可以方便地管理一个对象的生命期。指针是一种数据类型,用于保存内存地址;而智能指针是类模板。

weak_ptr 如何解决 shared_ptr 的循环引用问题

weak_ptr 是为了配合 shared_ptr 而引入的一种智能指针,它指向一个由 shared_ptr 管理的对象而不影响所指对象的生命周期,也就是将一个 weak_ptr 绑定到一个 shared_ptr 不会改变 shared_ptr 的引用计数。

循环引用是指两个或多个 shared_ptr 相互引用,导致它们的引用计数永远不为零,从而无法释放内存。weak_ptr 不会增加 shared_ptr 的引用计数,只是提供了对其所指对象的弱引用,不会影响内存的回收。

shared_ptr 如何得知与它共享对象的指针被释放

share_ptr 底层是采用引用计数的方式实现的。简单的理解,智能指针在申请堆内存空间的同时,会为其配备一个整型值(初始值为 1),每当有新对象使用此堆内存时,该整型值加 1;反之,每当使用此堆内存的对象被释放时,该整型值减 1。当堆空间对应的整型值为 0 时,即表明不再有对象使用它,该堆空间就会被释放掉。仅当最后一个指针过期时,才调用 delete.

智能指针有没有内存泄漏的情况

智能指针有内存泄露的情况。如果智能指针之间存在循环引用,就可能导致内存泄漏。循环引用是指两个或多个智能指针互相持有对方的引用,导致引用计数永远不为零,从而无法释放内存。

为了解决循环引用导致的内存泄漏,可以使用弱指针(weak_ptr),它不会修改引用计数的值,也不会对对象的内存进行管理。弱指针可以检测到所管理对象是否已经被销毁,从而避免访问无效的内存地址。

C++11 有哪些新特性

long long 类型,列表初始化,nullptr 常量,constexpr 常量,auto 类型指示符,类内初始化,基于范围的 for 语句,array 和 forward_list,容器的 emplace 操作,lambda 表达式,无序容器,智能指针,右值引用,虚函数的 override 和 final 运算符…

auto 和 decltype 如何使用

auto 实现自动类型推断,要求进行显示初始化,让编译器能够将变量的类型设置为初始值的类型。如 auto it = nums.cbegin();.

decltype 将变量的类型声明为表达式指定的类型。如 decltype(f()) sum = x; // sum 的类型就是函数 f 的返回类型.

简述 unique_ptr 的实现原理及使用场景

实现原理

unique_ptr 是 C++11 提供的一种智能指针,它可以防止内存泄漏,实现了独享被管理对象指针的概念。unique_ptr 中把拷贝构造函数和拷贝赋值运算符声明为 private 或 delete,它没有拷贝语义,但是可以通过移动语义进行资源所有权的转移。

使用场景

  • 如果程序不需要多个指向同一个对象的指针,则可以使用 unique_ptr;

  • 如果函数使用 new 分配内存,并返回指向该内存的指针,将其返回类型声明为 unique_ptr 是不错的选择。

简述左值、右值、左值引用、右值引用的使用场景

  • 左值是指能够取地址并且有名字的表达式,例如变量或对象。
  • 右值是指不能取地址或者没有名字的表达式,例如字面量(但是字符串字面值是左值)或函数的返回值。
  • 左值引用是一种绑定到左值上的引用,可以通过它来修改或读取左值。左值引用使用 & 符号声明。左值引用可以作为函数的参数,减少拷贝开销,并且允许修改参数。左值引用可以作为类成员变量,表示对另一个对象的别名或关联。
  • 右值引用是一种绑定到右值上的引用,可以通过它来移动或读取右值。右值引用使用 && 符号声明。右值引用可以作为函数的参数,实现移动语义和完美转发,提高性能和灵活性。

简述 C++ lambda 表达式用法及实现原理

C++ lambda 表达式是一种可以编写内嵌的匿名函数的技术,用以替换独立函数或者函数对象,并且使代码更可读。

C++ lambda 表达式的基本语法如下:

[ 捕获 ] (形参) -> ret { 函数体 }

其中:

  • 捕获是指 lambda 表达式可以访问外部作用域中的变量,有不同的方式,如值捕获、引用捕获、隐式捕获等。

  • 形参是指 lambda 表达式可以接受参数,类似于普通函数。

  • ret 是指 lambda 表达式的返回类型,可以省略,编译器会自动推断。

  • 函数体是指 lambda 表达式要执行的代码块。

C++ lambda 表达式的实现原理是编译器会自动生成一个类似于仿函数的类,并且重载了()运算符,使得该类的对象可以像函数一样调用。捕获列表中的变量会被存储在该类中作为成员变量,并且在构造函数中初始化。