C/C++ 面试题目总结
const知道吗?解释其作用
- 修饰变量,说明该变量不可以被改变;
- 修饰指针,分为指向常量的指针(pointer to const)和自身是常量的指针(常量指针,const pointer);
- 修饰引用,指向常量的引用(reference to const),用于形参类型,既避免了拷贝,又避免了函数对值的修改;
- 修饰成员函数,说明该成员函数内不能修改成员变量。
宏定义 #define 和 const 常量
宏定义 #define const 常量 宏定义,相当于字符替换 | 常量声明 | 预处理器处理 | 编译器处理 | 无类型安全检查 | 有类型安全检查 | 不分配内存 | 要分配内存 | 存储在代码段 | 存储在数据段 | 可通过 #undef
取消 |不可取消 | static的作用
- 修饰普通变量,修改变量的存储区域和生命周期,使变量存储在静态区,在 main 函数运行前就分配了空间,如果有初始值就用初始值初始化它,如果没有初始值系统用默认值初始化它。
- 修饰普通函数,表明函数的作用范围,仅在定义该函数的文件内才能使用。在多人开发项目时,为了防止与他人命名空间里的函数重名,可以将函数定位为 static。
- 修饰成员变量,修饰成员变量使所有的对象只保存一个该变量,而且不需要生成对象就可以访问该成员。
- 修饰成员函数,修饰成员函数使得不需要生成对象就可以访问该函数,但是在 static 函数内不能访问非静态成员。
说说this指针
this
指针是一个隐含于每一个非静态成员函数中的特殊指针。它指向调用该成员函数的那个对象。- 当对一个对象调用成员函数时,编译程序先将对象的地址赋给
this
指针,然后调用成员函数,每次成员函数存取数据成员时,都隐式使用this
指针。 - 当一个成员函数被调用时,自动向它传递一个隐含的参数,该参数是一个指向这个成员函数所在的对象的指针。
this
指针被隐含地声明为:ClassName *const this
,这意味着不能给this
指针赋值;在ClassName
类的const
成员函数中,this
指针的类型为:const ClassName* const
,这说明不能对this
指针所指向的这种对象是不可修改的(即不能对这种对象的数据成员进行赋值操作);this
并不是一个常规变量,而是个右值,所以不能取得this
的地址(不能&this
)。- 在以下场景中,经常需要显式引用
this
指针:- 为实现对象的链式引用;
- 为避免对同一对象进行赋值操作;
- 在实现一些数据结构时,如
list
。
说说inline内联函数
相当于把内联函数里面的内容写在调用内联函数处,即不用执行进入函数的步骤,直接执行函数体;相当于宏,却比宏多了类型检查,真正具有函数特性;编译器一般不内联包含循环、递归、switch 等复杂操作的内联函数;在类声明中定义的函数,除了虚函数的其他函数都会自动隐式地当成内联函数(但虚函数也可以是内联函数,但是当虚函数表现出多态性时不能内联)。
优点:
- 内联函数同宏函数一样将在被调用处进行代码展开,省去了参数压栈、栈帧开辟与回收,结果返回等,从而提高程序运行速度。
- 在类中声明同时定义的成员函数,自动转化为内联函数,因此内联函数可以访问类的成员变量,宏定义则不能。
- 内联函数在运行时可调试,而宏定义不可以。
缺点:
- 代码膨胀。内联是以代码膨胀(复制)为代价,消除函数调用带来的开销。如果执行函数体内代码的时间,相比于函数调用的开销较大,那么效率的收获会很少。另一方面,每一处内联函数的调用都要复制代码,将使程序的总代码量增大,消耗更多的内存空间。
- inline 函数无法随着函数库升级而升级。inline函数的改变需要重新编译,不像 non-inline 可以直接链接。
- 是否内联,程序员不可控。内联函数只是对编译器的建议,是否对函数内联,决定权在于编译器。
说说volatile关键字
- volatile 关键字是一种类型修饰符,用它声明的类型变量表示可以被某些编译器未知的因素(操作系统、硬件、其它线程等)更改。所以使用 volatile 告诉编译器不应对这样的对象进行优化。
- volatile 关键字声明的变量,每次访问时都必须从内存中取出值(没有被 volatile 修饰的变量,可能由于编译器的优化,从 CPU 寄存器中取值)
- const 可以是 volatile (如只读的状态寄存器)
- 指针可以是 volatile
说说assert()
断言,是宏,而非函数。assert 宏的原型定义在
<assert.h>
(C)、<cassert>
(C++)中,其作用是如果它的条件返回错误,则终止程序执行。可以通过定义NDEBUG
来关闭 assert,但是需要在源代码的开头,include <assert.h>
之前。static_assert
是一个编译时断言,用于在编译期间检查常量表达式是否为true
。它定义在 C++11 及更高版本的标准中。static_assert
通常用于模板编程和常量表达式中,以确保某些编译时条件成立。与assert
不同的是,static_assert
在编译时进行检查,因此它不会影响运行时性能。说说sizeof()
- sizeof 对数组,得到整个数组所占空间大小。
- sizeof 对指针,得到指针本身所占空间大小。
#pragma pack(n)
设定结构体、联合以及类成员变量以 n 字节方式对齐,
#pragma pack(pop)
恢复对齐状态extern "C"
被
extern
限定的函数或变量是extern
类型的,被 extern “C” 修饰的变量和函数是按照 C 语言方式编译和链接的C++ 中 struct 和 class
总的来说,struct 更适合看成是一个数据结构的实现体,class 更适合看成是一个对象的实现体。
最本质的一个区别就是默认的访问控制,struct 默认的数据访问控制是 public 的,class 默认的成员变量访问控制是 private 的。
union 联合
联合(union)是一种节省空间的特殊的类,一个 union 可以有多个数据成员,但是在任意时刻只有一个数据成员可以有值。当某个成员被赋值后其他成员变为未定义状态。联合有如下特点:
- 默认访问控制符为 public
- 可以含有构造函数、析构函数
- 不能含有引用类型的成员
- 不能继承自其他类,不能作为基类
- 不能含有虚函数
- 匿名 union 在定义所在作用域可直接访问 union 成员
- 匿名 union 不能包含 protected 成员或 private 成员
- 全局匿名联合必须是静态(static)的
C 实现 C++ 类
C 实现 C++ 的面向对象特性(封装、继承、多态)
- 封装:使用函数指针把属性与方法封装到结构体中
- 继承:结构体嵌套
- 多态:父类与子类方法的函数指针不同
explicit(显式)关键字
- explicit 修饰构造函数时,可以防止隐式转换和复制初始化
- explicit 修饰转换函数时,可以防止隐式转换,但 按语境转换 除外
friend 友元类和友元函数
- 能访问私有成员
- 破坏封装性
- 友元关系不可传递
- 友元关系的单向性
- 友元声明的形式及数量不受限制
谈谈using
using 关键字在 C++ 中有多种用途,主要包括类型别名、引入命名空间中的标识符。并且C++11 引入了别名模板,可以使用
using
创建模板的别名。尽量少使用 using 指示:
using namespace std;
,会污染命名空间::
范围解析运算符全局作用域符(
::name
):用于类型名称(类、类成员、成员函数、变量等)前,表示作用域为全局命名空间1 2
int count = 11; // 全局(::)的 count ::count = 12; // 测试 1:设置全局的 count 的值为 12
类作用域符(
class::name
):用于表示指定类型的作用域范围是具体某个类的1 2 3 4 5
class A { public: static int count; // 类 A 的 count(A::count) }; int A::count = 21;
命名空间作用域符(
namespace::name
):用于表示指定类型的作用域范围是具体某个命名空间的1
std::cout << "Hello, World!" << std::endl;
谈谈
decltype
关键字decltype 关键字用于检查实体的声明类型或表达式的类型及值分类,返回值为所属类型。语法:
decltype ( expression )
谈谈引用
在 C++ 中,引用(reference)是一种为已存在的变量创建别名的机制。引用可以让你通过另一个名字访问同一个变量。C++ 中的引用主要分为以下几种类型:
左值引用(L-value References):左值引用用于引用内存中已经存在的对象,通常用于函数参数传递和返回值。
右值引用(R-value References):右值引用在 C++11 引入(
int&& rvalueRef = 10
),主要用于引用临时对象(右值),支持移动语义和完美转发,优化性能。引用折叠(Reference Collapsing):引用折叠是一种复杂的规则,决定了多层引用的结果。它在模板编程和完美转发中非常重要。
X& &
、X& &&
、X&& &
可折叠成X&
X&& &&
可折叠成X&&
成员初始化列表 好处
- 更高效:少了一次调用默认构造函数的过程。
- 有些场合必须要用初始化列表:
- 常量成员,因为常量只能初始化不能赋值,所以必须放在初始化列表里面
- 引用类型,引用必须在定义的时候初始化,并且不能重新赋值,所以也要写在初始化列表里面
- 没有默认构造函数的类类型,因为使用初始化列表可以不必调用默认构造函数来初始化
谈谈面向对象
面向对象程序设计(Object-Oriented Programming,OOP)是一种程序设计范式,基于“对象”的概念,用于组织代码和数据。OOP 提供了一种更自然和直观的方法来解决复杂的软件问题,使程序设计更加模块化和可维护。面向对象的三大特性:
- 封装(Encapsulation) :封装是将数据和操作数据的方法捆绑在一起,形成一个自包含的单元—对象。封装通过定义类中的私有成员变量和公有成员函数,隐藏内部实现细节,只暴露必要的接口。封装提高了代码的安全性和可维护性。
- 继承(Inheritance) :继承是一种机制,通过创建一个新的类(子类),该类可以继承一个或多个已有类(基类)的属性和方法,从而实现代码的重用和扩展。继承支持多态性,并且使得代码更具层次性。
- 多态(Polymorphism):多态是指一个函数或方法可以有多种不同的表现形式。在C++中多态主要通过虚函数和函数重载实现,使得不同的对象可以用统一的接口进行操作,从而提高代码的灵活性和扩展性。
C++多态
C++ 多态分类及实现:
- 重载多态(Ad-hoc Polymorphism,编译期):函数重载、运算符重载
- 子类型多态(Subtype Polymorphism,运行期):虚函数
- 参数多态性(Parametric Polymorphism,编译期):类模板、函数模板
- 强制多态(Coercion Polymorphism,编译期/运行期):基本类型转换、自定义类型转换
谈谈虚析构函数
虚析构函数(Virtual Destructor)是面向对象编程中一个重要的概念,特别是在 C++ 中。它的主要目的是确保在通过基类指针删除派生类对象时,派生类的析构函数能够正确调用,从而防止资源泄漏和未定义行为。
在C++中,希望一个类不能被实例化,可以怎么做?
将类声明为抽象基类(Abstract Base Class, ABC): 如果一个类至少有一个纯虚函数,那么这个类就是抽象基类,无法被实例化。纯虚函数是在基类中声明但不定义的虚函数,它在基类中的声明形式如下:
virtual void func() = 0;
。纯虚函数使得派生类必须提供自己的实现,否则派生类也将成为抽象基类。如果其中没有其他合适的函数,可以把析构函数定义为纯虚析构函数
声明类的构造函数为protected或private: 如果一个类的构造函数被声明为
protected
或private
,那么在类的外部就不能直接调用这个构造函数来创建类的对象。只有类本身和它的友元函数或类可以访问它的私有或保护成员。
虚函数、纯虚函数
- 类里如果声明了虚函数,这个函数是实现的,哪怕是空实现,它的作用就是为了能让这个函数在它的子类里面可以被覆盖(override),这样的话,编译器就可以使用后期绑定来达到多态了。而纯虚函数只是一个接口,是个函数的声明而已,它要留到子类里去实现。
- 虚函数在子类里面可以不重写;但纯虚函数必须在子类实现才可以实例化子类。
- 虚函数的类用于 “实作继承”,继承接口的同时也继承了父类的实现。纯虚函数关注的是接口的统一性,实现由子类完成。
- 带纯虚函数的类叫抽象类,这种类不能直接生成对象,而只有被继承,并重写其虚函数后,才能使用。抽象类被继承后,子类可以继续是抽象类,也可以是普通类。
- 虚基类是虚继承中的基类,具体见下文虚继承。
谈谈虚函数指针、虚函数表
虚函数指针是存储在对象中的特殊指针,用于指向对象的虚函数表。每个对象都有一个虚函数指针,它指向对象的虚函数表的首地址。通过虚函数指针,可以在运行时动态地调用适当的虚函数。
虚函数表是存储在内存中的一张表格,用于存储类的虚函数地址。每个类(含有虚函数的类)都有一个对应的虚函数表,其中存放了该类所有虚函数的地址。虚函数表是在编译阶段创建的,每个类的虚函数表在程序运行时都会存在于内存中。
虚函数指针指向虚函数表的首地址,通过虚函数指针可以访问到对象的虚函数表。当调用对象的虚函数时,编译器会使用虚函数指针找到对象的虚函数表,然后根据函数在虚函数表中的索引找到相应的虚函数地址,并进行调用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
#include <iostream> class Base { public: virtual void foo() { std::cout << "Base::foo()" << std::endl; } }; class Derived : public Base { public: void foo() override { std::cout << "Derived::foo()" << std::endl; } }; int main() { Base* basePtr = new Derived(); basePtr->foo(); // 调用 Derived::foo() // 获取虚函数表指针 long long* vptr = *(long long**)basePtr; // 获取虚函数表中第一个虚函数地址 long long funcAddr = vptr[0]; // 转换为函数指针并调用 void (*func)() = (void (*)())funcAddr; func(); // 调用 Derived::foo() delete basePtr; return 0; }
谈谈虚继承
虚继承用于解决多继承条件下的菱形继承问题(浪费存储空间、存在二义性)。
底层实现原理与编译器相关,一般通过虚基类指针和虚基类表实现,每个虚继承的子类都有一个虚基类指针(占用一个指针的存储空间,4字节)和虚基类表(不占用类对象的存储空间)(需要强调的是,虚基类依旧会在子类里面存在拷贝,只是仅仅最多存在一份而已,并不是不在子类里面了);当虚继承的子类被当做父类继承时,虚基类指针也会被继承。
实际上,vbptr 指的是虚基类表指针(virtual base table pointer),该指针指向了一个虚基类表(virtual table),虚表中记录了虚基类与本类的偏移地址;通过偏移地址,这样就找到了虚基类成员,而虚继承也不用像普通多继承那样维持着公共基类(虚基类)的两份同样的拷贝,节省了存储空间。
虚继承、虚函数
- 相同之处:都利用了虚指针(均占用类的存储空间)和虚表(均不占用类的存储空间)
- 不同之处:
- 虚继承
- 虚基类依旧存在继承类中,只占用存储空间
- 虚基类表存储的是虚基类相对直接继承类的偏移
- 虚函数
- 虚函数不占用存储空间
- 虚函数表存储的是虚函数地址
- 虚继承
谈谈C++中的抽象类、接口类、聚合类
- 抽象类:含有纯虚函数的类
- 接口类:仅含有纯虚函数的抽象类
- 聚合类:用户可以直接访问其成员,并且具有特殊的初始化语法形式。满足如下特点:
- 所有成员都是 public
- 没有定义任何构造函数
- 没有类内初始化
- 没有基类,也没有 virtual 函数
谈谈C++中的模板机制
在C++中,模板(Template)是一种通用的代码生成机制,允许程序员编写通用的代码来处理不同类型的数据,而不需要为每种数据类型编写特定的代码。模板是C++中强大的特性之一,它提高了代码的重用性、可读性和可维护性。
类模板(Class Templates):类模板是一种用于创建通用类的模板,允许类中的数据成员和成员函数的类型参数化。通过类模板,可以定义一个通用的类,可以处理多种不同类型的数据。
函数模板(Function Templates):函数模板是一种用于创建通用函数的模板,允许函数中的参数类型参数化。通过函数模板,可以定义一个通用的函数,可以处理多种不同类型的数据。
1 2 3 4
template<typename T> T maximum(T a, T b) { return (a > b) ? a : b; }
模板特化(Template Specialization):模板特化是指针对某些特定的类型,为模板定义一个特殊的实现。当模板在处理特定类型时需要特殊的行为时,可以使用模板特化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
template<> class Stack<std::string> { private: std::vector<std::string> elements; public: void push(const std::string& element) { elements.push_back(element); } std::string pop() { if (elements.empty()) { throw std::out_of_range("Stack<std::string>::pop(): empty stack"); } std::string element = elements.back(); elements.pop_back(); return element; } };
模板参数(Template Parameters):模板参数是在定义模板时指定的参数,它可以是类型参数或非类型参数。类型参数指定了模板中的数据类型,而非类型参数可以是整数、指针等。
1 2 3 4 5
template<typename T, int N> class Array { private: T data[N]; };
C++的new/delete和malloc/delete有什么区别?
C++中的
new
和malloc()
都用于在堆上动态分配内存,但它们之间有一些重要的区别:new
是C++中的关键字,可以为指定的类型动态分配内存,并返回相应类型的指针。而malloc()
是C标准库函数,它返回void*
类型的指针,需要手动进行类型转换,将其转换为所需类型的指针。这样的操作在C++中不够安全,可能导致编译器无法检测到的类型错误。new
分配内存时会调用对象的构造函数,确保对象被正确初始化。malloc()
只是简单地分配一块内存,并不会调用对象的构造函数。new
可以根据所需类型的大小自动计算要分配的内存空间大小,无需手动计算。而malloc()
需要手动指定要分配的内存空间大小,需要调用sizeof
函数来计算所需的字节数。- 在内存分配失败时,
new
会抛出异常(std::bad_alloc
),需要使用异常处理机制来处理。而malloc()
分配内存失败时会返回空指针(NULL
),需要手动检查返回值并进行错误处理。 - 使用
new
分配的内存需要使用delete
关键字进行释放,而使用malloc()
分配的内存需要使用free()
函数进行释放。
本质:
new / new[]
:完成两件事,先底层调用 malloc 分配了内存,然后调用构造函数(创建对象)。delete/delete[]
:也完成两件事,先调用析构函数(清理资源),然后底层调用 free 释放空间。delete this 合法吗?
合法,但:
- 必须保证 this 对象是通过
new
(不是new[]
、不是 placement new、不是栈上、不是全局、不是其他对象成员)分配的 - 必须保证调用
delete this
的成员函数是最后一个调用 this 的成员函数 - 必须保证成员函数的
delete this
后面没有调用 this 了 - 必须保证
delete this
后没有人使用了
- 必须保证 this 对象是通过
C++如何定义一个只能在堆上(栈上)生成对象的类?
- 只能在堆上:将析构函数设置为私有。C++ 是静态绑定语言,编译器管理栈上对象的生命周期,编译器在为类对象分配栈空间时,会先检查类的析构函数的访问性。若析构函数不可访问,则不能在栈上创建对象。
- 只能在栈上:将 new 和 delete 重载为私有。在堆上生成对象,使用 new 关键词操作,其过程分为两阶段:第一阶段,使用 new 在堆上寻找可用内存,分配给对象;第二阶段,调用构造函数生成对象。将 new 操作设置为私有,那么第一阶段就无法完成,就不能够在堆上生成对象。
介绍一下C++的智能指针
C++中的智能指针是一种特殊的指针对象,可以自动管理动态分配的内存,避免内存泄漏和悬空指针等常见问题。智能指针通过包装原始指针,提供了自动释放内存的机制,从而简化了内存管理的工作。常见的智能指针包括
std::unique_ptr
、std::shared_ptr
和std::weak_ptr
(auto_ptr
被 c++11 弃用,原因是缺乏语言特性如 “针对构造和赋值” 的std::move
语义,以及其他瑕疵。)。std::unique_ptr
是一种独占式智能指针,即同一时间只能有一个std::unique_ptr
拥有某个对象的所有权。当std::unique_ptr
超出作用域或被显式释放时,它所管理的对象会被自动释放。不能复制或赋值给其他std::unique_ptr
,但可以通过std::move()
来转移所有权。适用于需要严格所有权管理的情况,例如资源管理类对象。std::shared_ptr
是一种共享式智能指针,可以拥有多个std::shared_ptr
共享同一个对象。使用引用计数来跟踪对象的引用次数,当引用次数为0时,对象会被自动释放。可以复制和赋值给其他std::shared_ptr
,引用计数会增加。适用于需要多个指针共享同一资源的情况,例如多个对象共享一个动态分配的对象。std::weak_ptr
是一种弱引用智能指针,它不会增加对象的引用计数,也不会影响对象的生命周期。用于解决std::shared_ptr
的循环引用问题,通过打破循环引用,防止内存泄漏。可以通过lock()
方法获取一个指向被管理对象的std::shared_ptr
,如果对象已经被释放,则返回空指针。
谈谈C++的强制类型转换
在C++中,有四种主要的强制类型转换方式:
static_cast
、dynamic_cast
、const_cast
和reinterpret_cast
。用法:static_cast<typename>(object)
static_cast
用于进行静态类型转换,通常用于较为安全的转换,例如基本数据类型之间的转换、类层次结构中的向上转换(派生类指针转为基类指针)和向下转换(基类指针转为派生类指针)等。静态转换在编译时进行,不提供运行时类型检查。dynamic_cast
用于进行动态类型转换,用于安全地在类层次结构中进行向上或向下转换,并且提供了运行时类型检查。当进行向下转换时,如果指针不指向有效的派生类对象,则返回空指针。只能用于具有虚函数的类(即多态类)之间的转换。const_cast
用于添加或删除对象的const属性、volatile属性,主要用于消除类型的const限制。注意:不应该用于修改本来就不可修改的对象。1 2 3
const int x = 10; int* ptr = const_cast<int*>(&x); // 去除const属性 *ptr = 20; // 合法,修改了const对象
reinterpret_cast
用于进行底层的重新解释转换,例如将一个指针转换为一个整数,或者一个整数转换为一个指针。这种转换非常危险,可能会导致未定义的行为,因此应该尽量避免使用。1 2 3
int x = 10; void* ptr = reinterpret_cast<void*>(&x); // 将int指针转换为void指针 int* newXPtr = reinterpret_cast<int*>(ptr); // 将void指针转换为int指针
谈谈运行时类型信息 (RTTI)
运行时类型信息(RTTI, Runtime Type Information)是C++提供的一种机制,用于在运行时识别对象的类型。RTTI允许程序在运行时获取关于对象类型的信息,主要包括两个关键特性:
typeid
操作符和dynamic_cast
操作符。typeid
操作符用于获取表达式或对象的类型信息。typeid
返回一个std::type_info
对象,该对象包含了类型的信息,可以通过其成员函数来获取类型名等信息。dynamic_cast
用于多态类型的转换
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
#include <iostream> class Base { public: virtual ~Base() {} }; class Derived : public Base {}; class AnotherDerived : public Base {}; int main() { Base* b = new Derived(); Derived* d = dynamic_cast<Derived*>(b); // 成功转换 AnotherDerived* ad = dynamic_cast<AnotherDerived*>(b); // 转换失败,返回nullptr if (d) { std::cout << "b is a Derived" << std::endl; } if (!ad) { std::cout << "b is not an AnotherDerived" << std::endl; } delete b; return 0; }
RTTI通常用于以下场景:
- 安全类型转换:在复杂的类层次结构中,使用
dynamic_cast
进行安全的向下转换,确保类型转换的正确性。 - 类型检查:使用
typeid
进行类型检查,调试和记录对象的实际类型信息,帮助诊断问题。
谈谈C++中怎么处理异常
在C++中,异常处理是一种机制,用于捕获和处理程序运行过程中发生的错误或异常情况,从而避免程序崩溃。C++通过
try
、catch
和throw
关键字来实现异常处理。1 2 3 4 5 6 7 8 9 10 11 12
try { // 可能抛出异常的代码 } catch (const std::exception& e) { // 处理标准库异常 std::cerr << "Standard exception: " << e.what() << std::endl; } catch (int e) { // 处理整型异常 std::cerr << "Integer exception: " << e << std::endl; } catch (...) { // 处理其他所有类型的异常 std::cerr << "Unknown exception caught" << std::endl; }
throw
表达式用于抛出异常,可以抛出任何类型的对象。C++允许用户定义自己的异常类,通常继承自
std::exception
,并重写what()
方法来提供异常信息。STL容器
容器 底层数据结构 时间复杂度 有无序 可不可重复 其他 array 数组 随机读改 O(1) 无序 可重复 支持随机访问,大小固定,不能动态调整 vector 数组 随机读改、尾部插入、尾部删除 O(1) 头部插入、头部删除 O(n) 无序 可重复 支持随机访问,动态调整大小,使用连续内存存储,插入删除效率视位置而定 deque 双端队列 头尾插入、头尾删除 O(1) 无序 可重复 一个中央控制器 + 多个缓冲区,支持首尾快速增删,支持随机访问,但随机访问效率略低于vector forward_list 单向链表 插入、删除 O(1) 无序 可重复 不支持随机访问,只能单向遍历,适用于只需前向访问和修改的场景 list 双向链表 插入、删除 O(1) 无序 可重复 不支持随机访问,支持双向遍历,适用于频繁插入和删除的场景 stack deque / list 顶部插入、顶部删除 O(1) 无序 可重复 适用于后进先出(LIFO)的场景,使用deque或list实现,不用vector的原因是扩容耗时 queue deque / list 尾部插入、头部删除 O(1) 无序 可重复 适用于先进先出(FIFO)的场景,使用deque或list实现,不用vector的原因是扩容耗时 priority_queue vector + max-heap 插入、删除 O(log2n) 有序 可重复 使用最大堆实现,适用于需要动态获取最大元素的场景,底层使用vector存储 set 红黑树 插入、删除、查找 O(log2n) 有序 不可重复 自动排序且元素唯一,适用于需要有序且无重复元素的场景 multiset 红黑树 插入、删除、查找 O(log2n) 有序 可重复 自动排序,允许重复元素,适用于需要有序且可重复元素的场景 map 红黑树 插入、删除、查找 O(log2n) 有序 不可重复 键值对存储,键唯一,自动按键排序,适用于需要按键有序访问且键唯一的场景 multimap 红黑树 插入、删除、查找 O(log2n) 有序 可重复 键值对存储,键可重复,自动按键排序,适用于需要按键有序访问且键可重复的场景 unordered_set 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复 使用哈希表实现,元素唯一,无序存储,适用于快速查找和插入的场景 unordered_multiset 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复 使用哈希表实现,允许重复元素,无序存储,适用于需要快速查找和插入且元素可重复的场景 unordered_map 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复 键值对存储,键唯一,使用哈希表实现,无序存储,适用于需要快速按键查找和插入的场景 unordered_multimap 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复 键值对存储,键可重复,使用哈希表实现,无序存储,适用于需要快速按键查找和插入且键可重复的场景
相关内容
- 如何使用C语言从一定范围内生成随机整数?
- C++11多线程 Std::thread详解
- 【MIT 6.5840(6.824)学习笔记】GFS
- 【MIT 6.5840(6.824)学习笔记】 测试分布式系统的线性一致性
- 【MIT 6.5840(6.824)学习笔记】使用Go进行线程和RPC编程