C++基础知识

static 静态变量

全局静态变量

在整个程序运行期间一直存在。
初始化：未经初始化的全局静态变量会被自动初始化为0（自动对象的值是任意的，除非他被显式初始化）；
作用域：全局静态变量在声明他的文件之外是不可见的，准确地说是从定义之处开始，到文件结尾。

局部静态变量

存储在静态存储区
初始化：未经初始化的全局静态变量会被自动初始化为0（自动对象的值是任意的，除非他被显式初始化）；
作用域：作用域仍为局部作用域，当定义它的函数或者语句块结束的时候，作用域结束。但是当局部静态变量离开作用域后，并没有销毁，而是仍然驻留在内存当中，只不过我们不能再对它进行访问，直到该函数再次被调用，并且值不变；

静态函数

在函数返回类型前加static，函数就定义为静态函数。函数的定义和声明在默认情况下都是extern的，但静态函数只是在声明他的文件当中可见，不能被其他文件所用。
函数的实现使用static修饰，那么这个函数只可在本cpp内使用，不会同其他cpp中的同名函数引起冲突；
warning：不要再头文件中声明static的全局函数，不要在cpp内声明非static的全局函数，如果你要在多个cpp中复用该函数，就把它的声明提到头文件里去，否则cpp内部声明需加上static修饰；

类的静态成员

在类中，静态成员可以实现多个对象之间的数据共享，并且使用静态数据成员还不会破坏隐藏的原则，即保证了安全性。因此，静态成员是类的所有对象中共享的成员，而不是某个对象的成员。对多个对象来说，静态数据成员只存储一处，供所有对象共用

类的静态函数

静态成员函数和静态数据成员一样，它们都属于类的静态成员，它们都不是对象成员。因此，对静态成员的引用不需要用对象名。
在静态成员函数的实现中不能直接引用类中说明的非静态成员，可以引用类中说明的静态成员（这点非常重要）。如果静态成员函数中要引用非静态成员时，可通过对象来引用。从中可看出，调用静态成员函数使用如下格式：<类名>::<静态成员函数名>(<参数表>);

C++和C的区别

设计思想上：C++是面向对象的语言，而C是面向过程的结构化编程语言。
语法上：（1）C++具有封装、继承和多态三种特性；（2）C++相比C，增加多许多类型安全的功能，比如强制类型转换、智能指针等；（3）C++支持范式编程，比如模板类、函数模板等。

封装

封装是在设计类的一个基本原理，就是将数据与对数据进行的操作进行有机的结合，形成“类”，其中数据和函数都是类的成员。

继承

如果一个类别B“继承自”另一个类别A，就把这个B称为“A的子类”，而把A称为“B的父类别”也可以称“A是B的超类”。继承可以使得子类具、有父类别的各种属性和方法，而不需要再次编写相同的代码。在令子类别继承父类别的同时，可以重新定义某些属性，并重写某些方法，即覆盖父类别的原有属性和方法，使其获得与父类别不同的功能。
（1）访问权限
public：父类对象内部、父类对象外部、子类对象内部、子类对象外部都可以访问。
protected：父类对象内部、子类对象内部可以访问，父类对象外部、子类对象外部都不可访问。
private：父类对象内部可以访问，其他都不可以访问。
（2）继承方式
三种继承方式不影响子类对父类的访问权限，子类对父类只看父类的访问控制权。继承方式是为了控制子类(也称派生类)的调用方(也叫用户)对父类(也称基类)的访问权限。
public、protected、private三种继承方式，相当于把父类的public访问权限在子类中变成了对应的权限。 如protected继承，把父类中的public成员在本类中变成了protected的访问控制权限；private继承，把父类的public成员和protected成员在本类中变成了private访问控制权。

多态

多态性可以简单地概括为“一个接口，多种方法”，程序在运行时才决定调用的函数，它是面向对象编程领域的核心概念。

静态多态

静态多态也称为静态绑定或早绑定。编译器在编译期间完成的，编译器根据函数实参的类型(可能会进行隐式类型转换)，可推断出要调用那个函数，如果有对应的函数就调用该函数，否则出现编译错误。
（1）函数重载
编译器根据函数不同的参数表，对同名函数的名称做修饰，然后这些同名函数就成了不同的函数（至少对于编译器来说是这样的）。函数的调用，在编译器间就已经确定了，是静态的。也就是说，它们的地址在编译期就绑定了（早绑定）。
（2）泛型编程
泛型编程就是指编写独立于特定类型的代码，泛型在C++中的主要实现为模板函数和模板类。
泛型的特性：
a) 函数模板并不是真正的函数，它只是C++编译生成具体函数的一个模子。
b) 函数模板本身并不生成函数，实际生成的函数是替换函数模板的那个函数，比如上例中的add(sum1,sum2)，这种替换是编译期就绑定的。
c) 函数模板不是只编译一份满足多重需要，而是为每一种替换它的函数编译一份。
d) 函数模板不允许自动类型转换。
e) 函数模板不可以设置默认模板实参。比如template 不可以。

动态多态

c++的动态多态是基于虚函数的。对于相关的对象类型，确定它们之间的一个共同功能集，然后在基类中，把这些共同的功能声明为多个公共的虚函数接口。各个子类重写这些虚函数，以完成具体的功能。客户端的代码（操作函数）通过指向基类的引用或指针来操作这些对象，对虚函数的调用会自动绑定到实际提供的子类对象上去。

C++的四种cast转换

C++中四种类型转换是：static_cast, dynamic_cast, const_cast, reinterpret_cast
(1) const_cast
用于将const变量转为非const
(2) static_cast
用于各种隐式转换，比如非const转const，void*转指针等, static_cast能用于多态向上转化，如果向下转能成功但是不安全，结果未知；
(3) dynamic_cast
用于动态类型转换。只能用于含有虚函数的类，用于类层次间的向上和向下转化。只能转指针或引用。向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。要深入了解内部转换的原理。
向上转换：指的是子类向基类的转换；
向下转换：指的是基类向子类的转换；
它通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否相同来判断是否能够进行向下转换。
(4) reinterpret_cast
几乎什么都可以转，比如将int转指针，可能会出问题，尽量少用。

为什么不使用C的强制转换？C的强制转换表面上看起来功能强大什么都能转，但是转化不够明确，不能进行错误检查，容易出错。

C++的四种智能指针

C++里面的四个智能指针: auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持，并且第一个已经被11弃用。
为什么要使用智能指针?智能指针的作用是管理一个指针，因为存在以下这种情况：申请的空间在函数结束时忘记释放，造成内存泄漏。使用智能指针可以很大程度上的避免这个问题，因为智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间，不需要手动释放内存空间。

auto_ptr（c++98的方案，cpp11已经抛弃）

auto_ptr的缺点是：存在潜在的内存崩溃问题！

unique_ptr（替换auto_ptr）

unique_ptr实现独占式拥有或严格拥有概念，保证同一时间内只有一个智能指针可以指向该对象。它对于避免资源泄露(例如“以new创建对象后因为发生异常而忘记调用delete”)特别有用。

shared_ptr

shared_ptr实现共享式拥有概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。它使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。除了可以通过new来构造，还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。当我们调用release()时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。
shared_ptr 是为了解决 unique_ptr 在对象所有权上的局限性(unique_ptr 是独占的), 在使用引用计数的机制上提供了可以共享所有权的智能指针。
成员函数：
use_count：返回引用计数的个数;
unique：返回是否是独占所有权( use_count 为 1)；
swap：交换两个 shared_ptr 对象(即交换所拥有的对象)
reset 放弃内部对象的所有权或拥有对象的变更, 会引起原有对象的引用计数的减少；
get：返回内部对象(指针), 由于已经重载了()方法, 因此和直接使用对象是一样的.如 shared_ptr sp(new int(1)); sp 与 sp.get()是等价的。

weak_ptr

weak_ptr 是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象. weak_ptr只是提供了对管理对象的一个访问手段。weak_ptr 设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少。weak_ptr可以用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr。

指针和引用的区别

定义

（1）引用：引用就是某一变量的一个别名，对引用的操作与对变量直接操作完全一样。引用是C++对C语言的重要扩充。
（2）指针：指针存储的是变量在内存区域的地址。

区别

（1）指针有自己的一块空间，而引用只是一个别名；
（2）指针可以被初始化为NULL（nullptr），而引用必须被初始化且必须是一个已有对象 的引用；
（3）作为参数传递时，指针需要被解引用才可以对对象进行操作，而直接对引 用的修改都会改变引用所指向的对象；
（4）指针在使用中可以指向其它对象，但是引用只能是一个对象的引用，不能 被改变；
（5）指针可以有多级指针（**p），而引用至多一级。

malloc 和new

（1）new分配内存按照数据类型进行分配，malloc分配内存按照指定的大小分配；
（2）new返回的是指定对象的指针，而malloc返回的是void，因此malloc的返回值一般都需要进行类型转化。
（3）new不仅分配一段内存，而且会调用构造函数，malloc不会。
（4）new分配的内存要用delete销毁，malloc要用free来销毁；delete销毁的时候会调用对象的析构函数，而free则不会。
（5）new是一个操作符可以重载，malloc是一个库函数。
（6）申请数组时： new一次分配所有内存，多次调用构造函数，搭配使用delete，delete多次调用析构函数，销毁数组中的每个对象。而malloc则只能sizeof(int) n。

虚函数和多态

多态的实现主要分为静态多态和动态多态，静态多态主要是重载，在编译的时候就已经确定；动态多态是用虚函数机制实现的，在运行期间动态绑定。比如说，一个父类类型的指针指向一个子类对象时候，使用父类的指针去调用子类中重写了的父类中的虚函数的时候，会调用子类重写过后的函数。
虚函数的实现：在有虚函数的类中，类的最开始部分是一个虚函数表的指针，这个指针指向一个虚函数表，表中放了虚函数的地址。当子类继承了父类的时候也会继承其虚函数表，当子类重写父类中虚函数时候，会将其继承到的虚函数表中的地址替换为重新写的函数地址。但是由于使用了虚函数，会增加访问内存开销，降低效率。

静态函数和虚函数

静态函数在编译的时候就已经确定运行时机；
虚函数在运行的时候动态绑定。虚函数因为用了虚函数表机制，调用的时候会增加一次内存开销。

基类的析构函数

为什么析构函数必须是虚函数？为什么C++默认的析构函数不是虚函数？
将可能会被继承的父类的析构函数设置为虚函数，可以保证当我们new一个子类，然后使用基类指针指向该子类对象，释放基类指针时可以释放掉子类的空间，防止内存泄漏。
C++默认的析构函数不是虚函数是因为虚函数需要额外的虚函数表和虚表指针，占用额外的内存。而对于不会被继承的类来说，其析构函数如果是虚函数，就会浪费内存。因此C++默认的析构函数不是虚函数，而是只有当需要当作父类时，设置为虚函数。

C++中析构函数的作用

析构函数与构造函数对应，当对象结束其生命周期，如对象所在的函数已调用完毕时，系统会自动执行析构函数。
析构函数名也应与类名相同，只是在函数名前面加一个位取反符~，以区别于构造函数。它不能带任何参数，也没有返回值（包括void类型）。一个类只能有一个析构函数，不能重载。
如果用户没有编写析构函数，编译系统会自动生成一个析构函数（即使自定义了析构函数，编译器也总是会为我们合成一个析构函数，并且如果自定义了析构函数，编译器在执行时会先调用自定义的析构函数再调用合成的析构函数）。
如果一个类中有指针成员，而且在使用的过程中动态的申请了内存，那么最好显示构造析构函数在销毁类之前，释放掉申请的内存空间，避免内存泄漏。

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应用中需要慎用。如果find能解决需要，尽可能用find。

Vector 和list

Vector

（1）连续存储的容器，动态数组，在堆上分配空间。
（2）底层实现：数组
（3）两倍容量增长：vector 增加（插入）新元素时，如果未超过当时的容量，则还有剩余空间，那么直接添加到最后（插入指定位置），然后调整迭代器。如果没有剩余空间了，则会重新配置原有元素个数的两倍空间，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素，最后析构并释放原空间，之前的迭代器会失效。
（4）性能：
访问：O(1)
插入：在最后插入（空间够）速度很快；在最后插入（空间不够）则需要内存申请和释放，以及对之前数据进行拷贝。
在中间插入（空间够）内存拷贝，在中间插入（空间不够）需要内存申请和释放，以及对之前数据进行拷贝。
删除：在最后删除速度很快，在中间删除则需要内存拷贝。
适用场景：经常随机访问，且不经常对非尾节点进行插入删除。

List

（1）动态链表，在堆上分配空间，每插入一个元数都会分配空间，每删除一个元素都会释放空间。
（2）底层：双向链表
（3）性能：
访问：随机访问性能很差，只能快速访问头尾节点；
插入：很快，一般是常数开销；
删除：很快，一般是常数开销；
适用场景：经常插入删除大量数据。
适用场景：经常插入删除大量数据

vector和list区别

1）vector底层实现是数组；list是双向 链表。
2）vector支持随机访问，list不支持。
3）vector是顺序内存，list不是。
4）vector在中间节点进行插入删除会导致内存拷贝，list不会。
5）vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。
6）vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

vector和list应用

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

STL

STL主要由：以下几部分组成：
容器、迭代器、仿函数、算法、分配器、配接器
他们之间的关系：
1）分配器给容器分配存储空间；
2）算法通过迭代器获取容器中的内容；
3）仿函数可以协助算法完成各种操作；
4）配接器用来套接适配仿函数。
在C++标准中，STL被组织为下面的13个头文件：、、、、、、

STL中迭代器的作用

迭代器

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。
由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。

迭代器和指针的区别

迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、、++、—等。迭代器封装了指针，是一个“可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象， 本质是封装了原生指针，是指针概念的一种提升（lift），提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，—等操作。
迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

迭代器产生原因

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

C++源文件从文本到可执行文件经历的过程

对于C++源文件，从文本到可执行文件一般需要四个过程：
（1）预处理阶段：对源代码文件中文件的头文件、宏定义进行分析和替换，生成预编译文件；
（2）编译阶段：将经过预处理后的预编译文件转换成特定汇编代码，生成汇编文件；
（3）汇编阶段：将编译阶段生成的汇编文件转化成机器码，生成可重定位目标文件；
（4）链接阶段：将多个目标文件及所需要的库连接成最终的可执行目标文件。

include头文件

双引号和尖括号的区别：编译器预处理阶段查找头文件的路径不一样。
对于使用双引号包含的头文件，查找头文件路径的顺序为：
1）当前头文件目录；
2）编译器设置的头文件路径（编译器可使用-I显式指定搜索路径）；
3）系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径。
对于使用尖括号包含的头文件，查找头文件的路径顺序为：
1）编译器设置的头文件路径（编译器可使用-I显式指定搜索路径）；
2）系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径。

内存溢出和内存泄漏

内存溢出

指程序申请内存时，没有足够的内存供申请者使用。内存溢出就是你要的内存空间超过了系统实际分配给你的空间，此时系统相当于没法满足你的需求，就会报内存溢出的错误。
内存溢出原因：
（1）内存中加载的数据量过于庞大，如一次从数据库取出过多数据；
（2）集合类中有对对象的引用，使用完后未清空，使得不能回收；
（3）代码中存在死循环或循环产生过多重复的对象实体
使用的第三方软件中的BUG；
（4）启动参数内存值设定的过小。

内存泄漏

在编写应用程序的时候，程序分配了一块内存，但已经不再持有引用这块内存的对象（通常是指针），虽然这些内存被分配出去，但是无法收回，将无法被其他的进程所使用，我们说这块内存泄漏了，被泄漏的内存将在整个程序声明周期内都不可使用。
主要原因：是在使用new或malloc动态分配堆上的内存空间，而并未使用delete或free及时释放掉内存。
内存泄漏情况：
（1）不匹配使用new[] 和 delete[]；
（2）delet void * 的指针，导致没有调用到对象的析构函数，析构的所有清理工作都没有去执行从而导致内存的泄露；
（3）没有将基类的析构函数定义为虚函数，当基类的指针指向子类时，delete该对象时，不会调用子类的析构函数。

C++内存管理

在C++中，虚拟内存分为代码段、数据段、BSS段、堆区、文件映射区以及栈区六部分。
（1）代码段:包括只读存储区和文本区，其中只读存储区存储字符串常量，文本区存储程序的机器代码。
（2）数据段：存储程序中已初始化的全局变量和静态变量
（3）bss 段：存储未初始化的全局变量和静态变量（局部+全局），以及所有被初始化为0的全局变量和静态变量。
（4）堆区：调用new/malloc函数时在堆区动态分配内存，同时需要调用delete/free来手动释放申请的内存。
（5）映射区:存储动态链接库以及调用mmap函数进行的文件映射。
（6）栈：使用栈空间存储函数的返回地址、参数、局部变量、返回值。

C++11新特性

C++11 最常用的新特性如下：
（1）auto关键字：编译器可以根据初始值自动推导出类型。但是不能用于函数传参以及数组类型的推导；
（2）nullptr关键字：nullptr是一种特殊类型的字面值，它可以被转换成任意其它的指针类型；而NULL一般被宏定义为0，在遇到重载时可能会出现问题。
（3）智能指针：C++11新增了std::shared_ptr、std::weak_ptr等类型的智能指针，用于解决内存管理的问题。
（4）初始化列表：使用初始化列表来对类进行初始化。
（5）右值引用：基于右值引用可以实现移动语义和完美转发，消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率。
（6）atomic原子操作用于多线程资源互斥操作。
（7）新增STL容器array以及tuple。

右值引用

右值引用是C++11中引入的新特性 , 它实现了转移语义和精确传递。它的主要目的有两个方面：
1）消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率。
2）能够更简洁明确地定义泛型函数。

左值和右值的概念：
左值：能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。
右值：不能对表达式取地址，或匿名对象。一般指表达式结束就不再存在的临时对象。

LRU缓存

LRU缓存是一种以LRU策略(距离当前最久没使用过的数据应该被淘汰)为缓存策略的缓存。
而所谓的缓存策略，就是当缓存满了之后，又有新数据需要加入到缓存中时，我们怎么从缓存中删除旧数据为新数据腾出空间的策略。
LRU，Least Recently Used的简写，即近期最少使用算法。该算法依据于程序的局部性原理， 其淘汰旧数据的策略是，距离当前最久没有被访问过的数据应该被淘汰。

实现原理

实现LRU的数据结构设计：unordered_map + double linked list。
（1）维护一个双向链表，该链表将缓存中的数据块按访问时间从新到旧排列起来（由于双向链表节点的交换代价很低，所以使用双向链表作为主要数据结构），节点为包含key,value的结构体（一条记录）；
（2）使用哈希表（map）保证缓存中数据的访问速度（由于引入哈希表可以提高查询速度，所以使用哈希表作为辅助数据结构）。map中的一个元素包含键值key以及链表中键值为key的迭代器（指针），通过key查找记录的地址，即可O(1)时间内访问链表中访问的记录。
接口描述
int get(int key)
功能:在哈希表中查找键值为key的元素，如果不存在返回-1；如果存在返回该key对应的value值.
实现:
这里说存在key的情况，如何get：
step1: 将键值为key的记录与链表首元交换位置;
step2: 更新哈希表中键值为key的迭代器
void put(int key, int value)
将key,value这条记录放入缓存，如果该记录已经在缓存中，更新该记录到缓存链表头部；如果不在缓存中且缓存未满，插入缓存链表头部，如果缓存满，删除尾部数据。

class LRUCache {
private:
    typedef int key_t;
    typedef int value_t;
    typedef struct{
        key_t key;
        value_t value;
    } Node_t;
    typedef list<Node_t> cacheList_t;
    typedef map<key_t,cacheList_t::iterator> map_t;
    
    int m_capacity;
    cacheList_t m_cacheList;
    map_t m_mp;    
    
public:
    LRUCache(int capacity) : m_capacity(capacity){
        
    }
    
    int get(int key) {
        auto it = m_mp.find(key);
        // not cached
        if(it == m_mp.end()) return -1;
        // cached
        else{
            auto list_it = m_mp[key];
            Node_t node = {key,list_it->value};
            m_cacheList.erase(list_it);
            m_cacheList.push_front(node);
            m_mp[key] = m_cacheList.begin();
            return m_cacheList.begin()->value;
        }
    }
    
    void put(int key, int value) {
        auto it = m_mp.find(key);
        // cached
        if(it != m_mp.end()){
            auto listIt = m_mp[key];
            // delete the cached node, and then insert it to the list head
            Node_t node = {key, value};
            m_cacheList.erase(listIt);
            m_cacheList.push_front(node);
            m_mp[key] = m_cacheList.begin();
            
        }
        // not cached
        else{
            // cache is full
            if(m_cacheList.size() == m_capacity){
                m_mp.erase(m_cacheList.back().key);
                m_cacheList.pop_back();
            }
            // cache is not full
            Node_t node = {key,value};
            m_cacheList.push_front(node);
            m_mp[key] = m_cacheList.begin();
            
        }
        
    }
};

C++_inline函数（内嵌函数）

在上下文切换中过程中需要一定的时间和空间开销（保护现场和恢复现场），C++提供了一种更高效的方法，即在编译时将所调用函数的代码直接嵌入到主调函数中，而不是将流程转出去。这种嵌入到主调函数中的函数称为内嵌函数，用inline 声明。
如：inline int max(int a, int b);
如果在类体中定义的成员函数（注：需在类体中定义函数体）中不包括循环等控制结构，C++系统自动的对它们作为内嵌函数来处理，无需显式的声明。
如果成员函数不在类体内定义，而在类体外定义，系统并不把它默认为内嵌函数，此时需作显式的声明。