C++基础

class与struct区别

C++中的 struct 和 class 基本是通用的，唯有几个细节不同：

默认访问权限：struct作为数据结构的实现体，它默认的数据访问控制是public的，而class作为对象的实现体，它默认的成员变量访问控制是private的。
默认的继承访问权：class默认的是private，strcut默认的是public。
“class”这个关键字还用于定义模板参数，就像“typename”。但关建字“struct”不用于定义模板参数

虚函数实现原理

虚函数主要是通过虚函数表来实现的，每一个含有虚函数（无论是其本身的，还是继承而来的）的类都至少有一个与之对应的虚函数表，表中存放了虚函数按照声明顺序排列的地址。虚函数表的构造由编译器完成的（虚函数替换过程发生在编译时），编译器不同虚表采用数组或链表实现。

当调用一个虚函数时，首先通过实例对象的this指针访问虚表指针(vptr)，虚表指针一般放在对象的头部位置，通过vptr找到虚函数表vtbl，进而找到虚函数表内的指向被调用函数的指针，调用指针所指向的函数。在有继承关系时(子类相对于其直接父类)

一般继承时，子类的虚函数表中先将父类虚函数放在前，再放自己的虚函数指针。
如果子类覆盖了父类的虚函数，虚函数指针将被放到了虚表中原来父类虚函数的位置。
在多继承的情况下，每个父类都有自己的虚函数表，父类中没有的虚函数而子类有，填入第一个虚函数表中，且用父类指针是不能调用。当类在多重继承中时，有几个基类（前提是要有虚函数）则子类实例对象就会保存几个虚函数表指针。

虚函数和普通函数重写

基类与派生类中普通函数同名，调用哪个类的函数与指针的定义类型有关，与指针的指向无关。
基类与派生类中虚函数同名，与指针指向的类型有关，该指针必须定义为基类类型，否则必须显示转换。

c++11 新特性

auto & decltype
左值右值（一个表达式不是左值就是右值）
列表初始化
lambda表达式
模板的改进
智能指针
基于范围的for循环
继承构造函数
nullptr
final & override
explicit

引用计数实现

构造函数中创建类的新对象时，初始化引用计数为1；
拷贝构造函数复制指针，并使相应的引用计数增加1；
赋值操作减少左操作数所值对象的引用计数，增加右操作数所指对象的引用计数；
析构函数使引用计数减少1，并且当引用计数为1时，释放指针说指向的对象；

智能指针

shared_ptr：采用引用计数的智能指针。多个 shared_ptr 指针可以共同使用同一块堆内存，指向同一个对象。该对象及相关资源会在其所指对象不再使用之后，自动释放与对象相关的资源。
unique_ptr：实现独占式拥有的概念，只能有一个unique_ptr可以指向该对象，当这个unique_ptr被销毁时，指向的对象也随即被销毁。不能进行拷贝构造和拷贝赋值（实现原理），但是可以进行移动构造和移动赋值（交出控制权）。
weak_ptr：结合 shared_ptr 使用的特例智能指针。 weak_ptr 提供对 shared_ptr 实例拥有的对象的访问，但不参与引用计数。解决shared_ptr 相互引用时，两个指针的引用计数永远不会下降为0，从而导致死锁问题。
auto_ptr（抛弃）：对象所有权的转移，比如在函数传参过程中，对象所有权不会返还，从而存在潜在的内存崩溃问题；不能指向数组，也不能作为STL容器的成员。

shared_ptr线程安全

shared_ptr的引用计数本身是安全且无锁的。
多线程环境下，调用不同shared_ptr实例的成员函数是不需要额外的同步手段。
多个线程同时读同一个shared_ptr对象是线程安全的，但如果是多个线程对同一个shared_ptr对象进行读和写，则需要加锁。
shared_ptr 有两个数据成员，引用计数和原始指针。当指针发生拷贝的时候，标准库的实现是先拷贝智能指针，再拷贝引用计数对象（同时会使use_count加一），这两个操作并不是原子的。
shared_ptr 的线程安全级别和内建类型、标准库容器、std::string 一样。

完美转发

指的是函数模板可以将自己的参数“完美”地转发给内部调用的其它函数。

在定义模板函数时，采用右值引用的语法格式定义参数类型，由此该函数既可以接收外界传入的左值，也可以接收右值；其次，还需要使用 C++11 标准库提供的 forword() 模板函数修饰被调用函数中需要维持左、右值属性的参数，实现函数模板中参数的完美转发。

new和malloc的区别

使用上的区别

malloc：申请空间需要显式填入申请内存的大小；

new：无需显式填入申请的内存大小，new会根据new的类型分配内存。
内存位置的区别

new：此操作符分配的内存空间是在自由存储区；

malloc：申请的内存是在堆空间。
返回类型的区别

new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。
分配失败情况的区别

malloc分配内存失败时返回NULL，通过判断返回值可以得知是否分配成功；

new内存分配失败时，会抛出bac_alloc异常，它不会返回NULL，分配失败时如果不捕捉异常，那么程序就会异常退出。
定义对象系统调度过程的区别

使用new操作符来分配对象内存时会经历三个步骤：（1）调用operator new 函数（数组是operator new[]）分配一块足够的内存空间（通常底层默认使用malloc实现，除非重载new符号）以便存储特定类型的对象；（2）编译器运行相应的构造函数以构造对象，并为其传入初值；（3）对象构造完成后，返回一个指向该对象的指针。

使用delete操作符来释放对象内存时会经历两个步骤：（1）调用对象的析构函数。（2）编译器调用operator delete(或operator delete[])函数释放内存空间（通常底层默认使用free实现，除非程序员重载delete符号）。
扩张内存大小的区别

malloc：使用malloc分配内存后，发现内存不够用，那我们可以通过realloc函数来扩张内存大小。

new：new没有扩张内存的机制。

vector、list和 deque

vector底层是连续结构；list底层是非连续结构
vector支持随机访问；list不支持随机访问
vector迭代器是原生指针；list迭代器是封装结点的一个类
vector在插入和删除时可能会导致迭代器失效；list在删除的时候会导致当前迭代器指向的结点失效
vector不容易造成内存碎片，空间利用率高；list容易造成内存碎片，空间利用率低
vector在非尾插，删除的时间复杂度为O(n)，list在任何地方插入和删除的时间复杂度都为O(1)
vecotr需要高效存储，支持随机访问，不关心插入删除效率；list大量插入和删除操作，不关心随机访问

vector 底层数据结构为数组，支持快速随机访问
list 底层数据结构为双向链表，支持快速增删
deque（双端队列）底层数据结构为一个中央控制器和多个缓冲区，可以向两端发展，尾部或首部增删元素都十分迅速。在中间增删元素则比较费时，因为必须移动其它元素，也支持随机访问（每个堆保存好几个元素，然后堆和堆之间有指针指向，看起来像是list和vector的结合品）

使用场景：

如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
如果你需要大量的插入和删除，而不关心随即存取，则应使用list
如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

强制类型转换

static_cast

用于数据类型的强制转换，强制将一种数据类型转换为另一种数据类型。

c++ 的任何的隐式转换都是使用 static_cast 来实现。
const_cast

常量指针或引用被转化成非常量的指针或引用，并且仍然指向原来的对象；const_cast一般用于修改指针。如const char *p形式。
reinterpret_cast

改变指针或引用的类型、将指针或引用转换为一个足够长度的整型、将整型转换为指针或引用类型。
dynamic_cast

主要用于类层次间的上行转换和下行转换，还可以用于类之间的交叉转换。

其他三种都是编译时完成的，dynamic_cast是运行时处理的，运行时要进行类型检查。

不能用于内置的基本数据类型的强制转换。

dynamic_cast转换如果成功的话返回的是指向类的指针或引用，转换失败的话则会返回NULL。

使用dynamic_cast进行转换的，基类中一定要有虚函数，否则编译不通过。

STL六大组件

容器
适配器
算法
迭代器
函数对象
分配器

迭代器的作用

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

通过迭代器访问容器，可以避免许多错误，同时还能隐藏容器的具体实现。
迭代器可以保证对所有容器的基本遍历方式，都是一样的，实现算法时若需要遍历，则使用迭代器，则可以不用关注容器的具体类型，实现数据结构和算法的分离。
迭代器本身有很多优点，可以弥补C++语言的不足，比如它的iterator_category，可以得到迭代器所指向的类别，这样可以根据不同的类别的特性，提供不同的算法。

右值引用和std::move

左值：有名称的、可以获取到地址的、位于等号左侧的表达式
右值：无名称的、不能取地址，位于等号右边的表达式
左值引用：能指向左值，不能指向右值（&），const左值引用是可以指向右值的
右值引用：可以指向右值，不能指向左值（&&）

右值引用有办法指向左值吗？

std::move 功能是把左值强制转化为右值，让右值引用可以指向左值。其实现等同于一个类型转换：static_cast<T&&>(lvalue)。(单纯的std::move(xxx)不会有性能提升)

右值引用能指向右值，本质上也是把右值提升为一个左值，并定义一个右值引用通过std::move指向该左值。

右值引用本身既可以是左值也可以是右值，如果有名称则为左值，否则是右值。或者说：作为函数返回值的 && 是右值，直接声明出来的 && 是左值。

从性能上讲，左右值引用没有区别，传参使用左右值引用都可以避免拷贝。
右值引用可以直接指向右值，也可以通过std::move指向左值；而左值引用只能指向左值(const左值引用也能指向右值)。
作为函数形参时，右值引用更灵活。虽然const左值引用也可以做到左右值都接受，但它无法修改，有一定局限性。

如果我们没有提供移动构造函数，只提供了拷贝构造函数，std::move()会失效但是不会发生错误，因为编译器找不到移动构造函数就去寻找拷贝构造函数，也这是拷贝构造函数的参数是const T&常量左值引用的原因！

c++11中的所有容器都实现了move语义，move只是转移了资源的控制权，本质上是将左值强制转化为右值使用，以用于移动拷贝或赋值，避免对含有资源的对象发生无谓的拷贝。

move对于拥有如内存、文件句柄等资源的成员的对象有效，如果是一些基本类型，如int和char[10]数组等，如果使用move，仍会发生拷贝（因为没有对应的移动构造函数），所以说move对含有资源的对象说更有意义。

右值引用和std::move被广泛用于在STL和自定义类中实现移动语义，避免拷贝，从而提升程序性能。
实现完美转发 std::forward（与move相比，forward更强大，move只能转出来右值，forward都可以）

volatile的使用

中断服务程序中修改的供其它程序检测的变量需要加volatile；
多任务环境下各任务间共享的标志应该加volatile；
存储器映射的硬件寄存器通常也要加volatile说明，因为每次对它的读写都可能由不同意义；

volatile 关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素（操作系统、硬件、其它线程等）更改。volatile 告诉编译器不应对这样的对象进行优化。
volatile 关键字声明的变量，每次访问时都必须从内存中取出值（没有被 volatile 修饰的变量，可能由于编译器的优化，从 CPU 寄存器中取取值）
const 可以是 volatile （如只读的状态寄存器）
指针可以是 volatile

调用析构函数场景

生命周期：对象生命周期结束，会调用析构函数。
delete：调用delete，会删除指针类对象。
包含关系：对象Dog是对象Person的成员，Person的析构函数被调用时，对象Dog的析构函数也被调用。
继承关系：当Person是Student的父类，调用Student的析构函数，会调用Person的析构函数。

内存泄露和野指针

用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元。直到程序结束。即所谓内存泄漏。

野指针的成因主要有两种：

指针变量没有被初始化
指针p被free或者delete之后，没有置为NULL，让人误以为p是个合法的指针

空类的成员函数

缺省构造函数
拷贝构造函数
析构函数
拷贝赋值运算符
取址运算符
取址运算符 const
移动构造函数（C++11）
移动赋值运算符（C++11）

在C++中空类会占1个字节，这是为了让对象的实例能够相互区别。空类同样可以被实例化，并且每个实例在内存中都有独一无二的地址。

sizeof 特殊类

空类占用1个字节
一般函数不占用空间
一般数据类型按照本身数据大小
当类有虚函数时，需要4字节的虚表指针
当多继承时，有虚函数的会生成一个虚表指针，比如继承两个有虚函数的类，那么会有两个虚表指针。如果一个虚类，一个普通类，那么有一个虚指针。

执行main函数前的工作

设置栈指针。
初始化static静态和global全局变量，即data段内容
将未初始化部分的赋初值：数值型short，int，long等为0，bool为FALSE，指针为NULL，等等，即.bss段的内容
运行全局构造器，C++中构造函数之类的
将main函数的参数，argc，argv等传递给main函数，然后才真正运行main函数

引用和指针

指针是一个实体，而引用仅是个别名
指针变量分配内存区域，而引用不需要分配内存
引用只能在定义时被初始化一次，之后不可变；指针可变
引用没有 const，指针有 const；const修饰的指针不可变
引用不能为空，指针可以为空

extern、static 和 const

extern 关键字：

声明extern的全局变量和函数以表示定义在别的文件中，提示编译器遇到此变量和函数时在其他模块中寻找其定义，可以使得它们能够跨文件被访问。
extern “C” 会指示编译器这部分代码按C语言（而不是C++）的方式进行编译和链接。

static关键字：

static 修饰局部变量时，在静态存储区分配内存；只能在首次函数调用中进行首次初始化，之后的函数调用不再进行初始化。
static 修饰全局变量和函数时，在该文件中都是可见的，而在文件外是不可见的，从而可以在多人协作时避免同名的变量和函数冲突。
static 类成员变量时，所有的对象都只维持一份拷贝，可以实现不同对象间的数据共享；不需要实例化对象即可访问；不能在类内部初始化，一般在类外部初始化，并且初始化时不加static。
static 类成员函数时，该函数不接受this指针，只能访问类的静态成员；不需要实例化对象即可访问。

extern 和 static 不能同时修饰一个变量。通常在模块的头文件中对本模块提供给其它模块使用的函数和全局变量以extern声明，一般定义static全局变量时，把它放在原文件中而不是头文件。

const 关键字：

修饰变量，说明该变量不可以被改变
修饰指针，分为指向常量的指针和自身是常量的指针（常量指针）
修饰引用，指向常量的引用，用于形参类型，即避免了拷贝，又避免了函数对值的修改
修饰类成员函数，说明该成员函数内不能修改成员变量

RAII 机制

资源获取即初始化，使用局部对象来管理资源的技术称为资源获取即初始化；这里的资源主要是指操作系统中有限的东西如内存、网络套接字等等，局部对象是指存储在栈的对象，它的生命周期是由操作系统来管理的，无需人工介入；充分的利用了C++语言局部对象自动销毁的特性来控制资源的生命周期。

如何使用 RAII

把资源用类进行封装起来，对资源操作都封装在类的内部，在析构函数中进行释放资源。当定义的局部变量的生命结束时，它的析构函数就会自动的被调用，如此，就不用程序员显示的去调用释放资源的操作了。

异常的优缺点

C++异常的优点：

清晰准确的展示出错误的信息，甚至可以包含堆栈调用的信息，可以更好的定位程序的bug
部分函数使用异常更好处理，比如构造函数没有返回值，不方便使用错误码方式处理

C++异常的缺点：

异常会导致程序的执行流非常的混乱，并且是运行时出错抛异常就会乱跳。这会导致我们跟踪调试时以及分析程序时，比较困难。
异常会有一些性能的开销。
C++没有垃圾回收机制，资源需要自己管理。异常非常容易导致内存泄漏、死锁等异常安全问题。
C++标准库的异常体系定义得不好，各种的异常体系非常的混乱。

resize 与 reserve

1
2
3

void reserve (size_type n);
void resize (size_type n);
void resize (size_type n, value_type val);

reserve的作用是更改vector的容量（capacity），使vector至少可以容纳n个元素。

如果n大于vector当前的容量，reserve会对vector进行扩容。容器预留空间不创建对象，需要通过insert()或push_back()等操作创建对象。
其他情况下都不会重新分配vector的存储空间。
该函数不会影响vector的size而且不会改变任何元素

resize函数重新分配大小，改变容器的size，并且创建对象。

如果n小于vector当前的size，则删除多出来的元素。
如果n大于vector的size，小于等于capacity()，则会插入相应数量的元素使得size()值达到n。
当n大于capacity()值的时候，会自动分配重新分配内存存储空间。

cpp文件到exe文件

分为四个过程：预处理、编译、汇编和链接

预处理：在预处理阶段，编译器主要作加载头文件、宏替换、条件编译的作用。
编译：在编译过程中，编译器主要作语法检查和词法分析。可以通过使用 -S 选项来进行查看，该选项预处理之后的结果翻译成汇编代码。
汇编：在汇编过程中，编译器把汇编代码转化为机器代码。
链接：链接就是将目标文件、启动代码、库文件链接成可执行文件的过程。

不能重载的运算符

. （成员访问运算符）
. *（成员指针访问运算符）
::（域运算符）
?:（条件运算符）
sizeof（长度运算符）

前两个运算符不能重载是为了保证访问成员的功能不能被改变，域运算符和sizeof 运算符的运算对象是类型而不是变量或一般表达式，不具备重载的特征。

内存布局

一个由C/C++编译的程序占用的内存分为以下几个部分：

栈区（stack）：由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆区（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS（操作系统）回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
全局区（静态区）（static）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
文字常量区：常量字符串就是放在这里的。程序结束后由系统释放。
程序代码区：存放函数体的二进制代码。

内存分配方式

从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。
在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。

动态内存的生存期由程序员决定，使用非常灵活，但如果在堆上分配了空间，就有责任回收它，否则运行的程序会出现内存泄漏，频繁地分配和释放不同大小的堆空间将会产生堆内碎块。

虚表指针和虚函数表位置

虚表指针放在对象内存的开头，是放在堆区的
虚函数表在Linux中存放在可执行文件的只读数据段中(rodata)，这与微软的编译器将虚函数表存放在常量段存在一些差别

class A {
  public:
    virtual void v_a(){}
    virtual ~A(){}
    int64_t _m_a;
};

int main(){
    A* a = new A();
    return 0;
}

虚函数表是全局共享的元素，即全局仅有一个
虚函数表类似一个数组，类对象中存储虚表指针，指向虚函数表中的第一个虚函数起始地址，即虚函数表不是函数，也不是程序代码，不可能存储在代码段
虚函数表存储虚函数的地址，即虚函数表的元素是指向类成员函数的指针，而类中虚函数的个数在编译时期可以确定，即虚函数表的大小可以确定，即大小是在编译时期确定的，不必动态分配内存空间存储虚函数表，所以不在堆中

根据以上特征，虚函数表类似于类中静态成员变量，静态成员变量也是全局共享，大小确定。所以推测虚函数表和静态成员变量一样，存放在全局静态数据区。

常用检测工具

内存泄漏检测工具

valgrind
mtrace
dmalloc
ccmalloc
memwatch
debug_new
AddressSanitizer(ASan)

静态代码检测工具

cppcheck
PC-lint
Coverity
QAC C/C++
Clang-Tidy（推荐）
Clang Static Analyzer

数据结构

B+树和B树的区别

B+树内节点不存储数据，所有 data 存储在叶节点查询时间复杂度固定为 log n，查询性能稳定。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
B+树叶节点两两相连形成了一个有序链表，增加了区间访问性，提高范围查询性能等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确

B+树对比B树的好处

IO次数少：B+树的中间结点只存放索引，数据都存在叶结点中，因此中间结点可以存更多的数据，让索引树更加矮胖；
范围查询效率更高：B树需要中序遍历整个树，只B+树需要遍历叶结点中的链表；
查询效率更加稳定：每次查询都需要从根结点到叶结点，路径长度相同，所以每次查询的效率都差不多

哈希方法和哈希冲突

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列方法：

直接定址法
平方取中法
折叠法
伪随机数法
除留余数法
斐波那契散列法
字符串转化法（多项式法）

哈希冲突解决：

拉链法（数组+链表）
开放定址法（再散列法）：线性探测、二次探测、伪随机探测
再哈希法：构造多个不同的哈希函数
公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
每个红色结点的两个子结点一定都是黑色。
任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

计算机网络

TIME_WAIT过多的问题

调整系统内核参数，加速端口回收和开启重用（/etc/sysctl.conf）
调整短链接为长链接

TCP可靠的原因

校验和
确认应答与序列号
超时重传
数据排序
流量控制
拥塞控制

UDP如何实现可靠传输

添加seq/ack机制，确保数据发送到对端
添加发送和接收缓冲区，主要是用户超时重传
添加超时重传机制

发送端发送数据时，生成一个随机seq=x，然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存，并发送一个ack=x的包，表示对方已经收到了数据。发送端收到了ack包后，删除缓冲区对应的数据。时间到后，定时任务检查是否需要重传数据。

DNS用的是TCP还是UDP

DNS在区域传输的时候使用TCP协议，其他时候使用UDP协议。

DNS区域传输的时候使用TCP协议：

辅域名服务器会定时（一般3小时）向主域名服务器进行查询以便了解数据是否有变动。如有变动，会执行一次区域传送，进行数据同步。区域传送使用TCP，因为数据同步传送的数据量比一个请求应答的数据量要多得多。
TCP是一种可靠连接，保证了数据的准确性。

域名解析时使用UDP协议：

客户端向DNS服务器查询域名，一般返回的内容都不超过512字节，用UDP传输即可。不用经过三次握手，这样DNS服务器负载更低，响应更快。理论上说，客户端也可以指定向DNS服务器查询时用TCP，但事实上，很多DNS服务器进行配置的时候，仅支持UDP查询包。

GET 和 POST 比较

GET 用于获取资源，而 POST 用于传输实体主体
GET请求参数是通过URL传递的，POST请求放在request body中。
浏览器及服务器对GET请求的URL是有长度限制的，而POST没有。
GET只接受ASCII字符，而POST没有限制。
GET请求会被缓存，而POST请求不会，除非手动设置。
GET 方法是安全的，也是幂等的，而 POST 却不是。
GET产生一个TCP数据包；POST产生两个TCP数据包。（对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

数据库

ACID

原子性（Atomicity）

事务被视为不可分割的最小单元，事务的所有操作要么全部提交成功，要么全部失败回滚。
一致性（Consistency）

数据库在事务执行前后都保持一致性状态。在一致性状态下，所有事务对同一个数据的读取结果都是相同的。
隔离性（Isolation）

一个事务所做的修改在最终提交以前，对其它事务是不可见的。
持久性（Durability）

一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。

索引的优缺点

大大加快了数据的检索速度；
可以显著减少查询中分组和排序的时间；
通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性；
将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）
缺点：建立和维护索引耗费时间空间，更新索引很慢。

操作系统

协程

节省 CPU，避免系统内核级的线程频繁切换，造成的 CPU 资源浪费。而协程是用户态的线程，用户可以自行控制协程的创建于销毁，极大程度避免了系统级线程上下文切换造成的资源浪费。
节约内存，在 64 位的 Linux 中，一个线程需要分配 8MB 栈内存和 64MB 堆内存，系统内存的制约导致我们无法开启更多线程实现高并发。而在协程编程模式下，可以轻松有十几万协程，这是线程无法比拟的。
稳定性，前面提到线程之间通过内存来共享数据，这也导致了一个问题，任何一个线程出错时，进程中的所有线程都会跟着一起崩溃。
开发效率，使用协程在开发程序之中，可以很方便的将一些耗时的 IO 操作异步化，例如写文件、耗时 IO 请求等。

池化技术

池是在计算技术中经常使用的一种设计模式，其内涵在于：将程序中需要经常使用的核心资源先申请出来，放到一个池内，有程序自管理，这样可以提高资源的利用率，也可以保证本程序占有的资源数量，经常使用的池化技术包括内存池，线程池，和连接池等，其中尤以内存池和线程池使用最多。

线程池

当进行并行的任务作业操作时，线程的建立与销毁的开销是阻碍性能的关键，线程池由此产生。使用多个线程，无限制循环等待队列，进行计算和操作，帮助快速降低和减少性能损耗。

空间换时间，消耗服务器的硬件资源换取运行效率
池是一组资源的集合，这组资源在服务器启动之初就被完全创建好并初始化，这称为静态资源
当服务器进入正式运行阶段，开始处理客户请求的时候，如果它需要相关的资源，可以直接从池中获取，无需动态分配
当服务器处理完一个客户连接后，可以把相关的资源放回池中，无需执行系统调用释放资源

线程池的组成

线程池管理器：初始化和创建线程，启动和停止线程，调配任务，管理线程池
工作线程：线程池中等待并执行分配的任务
任务接口：添加任务的接口，以提供工作线程调度任务的执行。
任务队列：用于存放没有处理的任务，提供一种缓冲机制，同时具有调度功能，高优先级的任务放在队列前面

//需要注意，线程处理函数和运行函数设置为私有属性
template <typename T>
class threadpool{
public:
    /*thread_number是线程池中线程的数量，
    max_requests是请求队列中最多允许的、等待处理的请求的数量，
    connPool是数据库连接池指针*/
    threadpool(int actor_model, connection_pool *connPool, int thread_number = 8, int max_request = 10000);
    ~threadpool();
    //向请求队列中插入任务请求
    bool append(T *request, int state);
    bool append_p(T *request);

private:
    /*工作线程运行的函数，它不断从工作队列中取出任务并执行*/
    static void *worker(void *arg);
    void run();

private:
    int m_thread_number;        //线程池中的线程数
    int m_max_requests;         //请求队列中允许的最大请求数
    pthread_t *m_threads;       //描述线程池的数组，其大小为m_thread_number
    std::list<T *> m_workqueue; //请求队列
    locker m_queuelocker;       //保护请求队列的互斥锁
    sem m_queuestat;            //是否有任务需要处理
    connection_pool *m_connPool;  //数据库
    int m_actor_model;          //模型切换
};

内存池

内存池（Memory Pool）是一种动态内存分配与管理技术，通常情况下，程序员习惯直接使用new，delete，malloc,free等API申请和释放内存，这样导致的后果就是：当程序运行的时间很长的时候，由于所申请的内存块的大小不定，频繁使用时会造成大量的内存碎片从而降低程序和操作系统的性能。

内存池则是在真正使用内存之前，先申请分配一大块内存（内存池）留作备用。当程序员申请内存时，从池中取出一块动态分配，当程序员释放时，将释放的内存放回到池内，再次申请，就可以从池里取出来使用，并尽量与周边的空闲内存块合并。若内存池不够时，则自动扩大内存池，从操作系统中申请更大的内存池。

内存池的实现方式

最简单的内存分配器

做一个链表指向空闲内存，分配就是取出一块来，改写链表，返回，释放就是放回到链表里面，并做好归并。注意做好标记和保护，避免二次释放，还可以花点力气在如何查找最适合大小的内存快的搜索上，减少内存碎片，有空你了还可以把链表换成伙伴算法。
优点：实现简单
缺点：分配时搜索合适的内存块效率低，释放回归内存后归并消耗大，实际中不实用。
定长内存分配器

即实现一个 FreeList，每个 FreeList 用于分配固定大小的内存块，比如用于分配 32字节对象的固定内存分配器，之类的。每个固定内存分配器里面有两个链表，OpenList 用于存储未分配的空闲对象，CloseList用于存储已分配的内存对象，那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户，释放又是从 CloseList 移回到 OpenList。分配时如果不够，那么就需要增长 OpenList：申请一个大一点的内存块，切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候，统一把先前向系统申请的内存块全部还给系统。
优点：简单粗暴，分配和释放的效率高，解决实际中特定场景下的问题有效。
缺点：功能单一，只能解决定长的内存需求，另外占着内存没有释放。
哈希映射的FreeList 池

在定长分配器的基础上，按照不同对象大小(8，16，32，64，128，256，512，1k…64K),构造十多个固定内存分配器，分配内存时根据要申请内存大小进行对齐然后查H表，决定到底由哪个分配器负责，分配后要在内存头部的 header 处写上 cookie，表示由该块内存哪一个分配器分配的，这样释放时候你才能正确归还。如果大于64K，则直接用系统的 malloc作为分配，如此以浪费内存为代价你得到了一个分配时间近似O(1)的内存分配器。这种内存池的缺点是假设某个 FreeList 如果高峰期占用了大量内存即使后面不用，也无法支援到其他内存不够的 FreeList，达不到分配均衡的效果。
优点：这个本质是定长内存池的改进，分配和释放的效率高。可以解决一定长度内的问题。
缺点：存在内碎片的问题，且将一块大内存切小以后，申请大内存无法使用。多线程并发场景下，锁竞争激烈，效率降低。
范例： sgi stl 六大组件中的空间配置器就是这种设计实现的。

内存泄漏和内存溢出

内存溢出是指程序在申请内存时，没有足够的内存空间供其使用
内存泄漏是指的是程序在申请内存后，无法释放已经申请的内存空间，内存泄露的积累往往会导致内存溢出

内存泄漏分类

常发性内存泄漏

引起内存泄漏的代码会被很多次执行，每次执行的时候都会导致内存泄漏
偶发性内存泄漏

在某些特定的环境下执行引起内存泄漏的代码，才会引起内存泄漏

从以上两种内存泄漏的方式来看，测试环境和测试方法在程序生命周期的重要性是不可或缺的。
一次性内存泄漏

代码只会执行一次，但总有一块内存发生泄漏，多见于构造类的时候，析构函数没有释放内存。
隐式泄漏

程序运行过程中不断的分配内存，直到结束时才释放内存，但一般服务器程序会运行较长的时间，不及时释放也会导致内存耗尽以至于内存泄漏。

综上所述，一次性内存泄漏对用户的程序维护是没有什么实质性的伤害，但在实际生活中，我们还是尽可能要避免此类的事件发生。

内存溢出原因

在类的构造函数和析构函数中没有匹配的调用new和delete函数
没有正确地清除嵌套的对象指针
在释放对象数组时在delete中没有使用方括号
指向对象的指针数组不等同于对象数组
缺少拷贝构造函数
缺少重载赋值运算符
没有将基类的析构函数定义为虚函数
析构的时候使用void*
构造的时候浅拷贝，释放的时候调用了两次delete

锁的种类

互斥锁（mutex）

有线程访问进程空间中的公共资源时，该线程执行“加锁”操作，阻止其它线程访问。访问完成后，该线程负责完成“解锁”操作，将资源让给其它线程。当有多个线程想访问资源时，谁最先完成“加锁”操作，谁就最先访问资源。可以避免多个线程在某一时刻同时操作一个共享资源，标准C++库提供了std::mutex类模板。依据同一线程是否能多次加锁，把互斥量又分为如下两类：递归互斥量和非递归互斥量，也称可重入锁和不可重入锁。
条件变量（condition_variable）

利用线程间共享的全局变量进行同步的一种机制，某一个线程因为某个条件未满足时可以使用条件变量使该程序处于阻塞状态。一旦条件满足了，即可唤醒该线程（常和互斥锁配合使用），唤醒后，需要检查变量，避免惊群和虚假唤醒。
读写锁（read-write lock）

读写锁也称共享-互斥锁、多读者-单写者锁，就是对于临界区区分读和写操作。在读多写少的场景下，不加区分的使用互斥量是很大的浪费。多个线程可以同时读数据，但写数据时需要获得一个独占的锁。当写者写数据时，其它写者或读者需要等待，直到这个写者完成写操作。在C++17中出现了一种新锁：std::shared_mutex。用它可以模拟实现出读写锁。
自旋锁（spinlock）

当一个线程尝试去获取某一把锁的时候，如果这个锁此时已经被别人获取(占用)，那么此线程就无法获取到这把锁，该线程将会等待，间隔一段时间后会再次尝试获取。这种采用循环加锁 -> 等待的机制就是自旋锁。自旋锁尽可能的减少线程的阻塞，这对于锁的竞争不激烈，且占用锁时间非常短的代码块来说性能能大幅度的提升，因为自旋的消耗会小于线程阻塞挂起再唤醒的操作的消耗，这些操作会导致线程发生两次上下文切换。但是如果锁的竞争激烈，或者持有锁的线程需要长时间占用锁执行同步块，则会导致CPU在这个线程的时间片用尽之前一直消耗在无意义的忙等上，造成计算资源的浪费。
递归锁（recursive_mutex）

递归锁是一种在上锁时会先检查当前锁是否已经被持有，如果已经被持有则允许代码递归地获取它的锁。主要用在可能被连续多次上锁（期间未解锁）的情形。若同一线程对非递归互斥量多次加锁，可能会造成死锁，递归互斥量则无此风险。C++11中有递归互斥量的API：std::recursive_mutex。对于pthread则可以通过给mutex添加PTHREAD_MUTEX_RECURSIVE 属性的方式来使用递归互斥量。

虚假唤醒

当一定的条件触发时会唤醒很多在阻塞态的线程，但只有部分的线程唤醒是有用的，其余线程的唤醒是多余的。

我们都知道，wait方法的作用是将线程停止执行并送入到阻塞队列中，但是wait方法还有一个操作就是释放锁。因此当生产者A执行wait方法时，该线程就会把它持有的对象锁释放，这样生产者B就可以拿到锁进入synchronized修饰的push方法中，即使它被卡在if判断，但被唤醒后它就会又添加一个产品了。

导致虚假唤醒的原因主要就是一个线程直接在if代码块中被唤醒了，这时它已经跳过了if判断。我们只需要将if判断改为while，这样线程就会被重复判断而不再会跳出判断代码块，从而不会产生虚假唤醒这种情况了。

同步异步&阻塞非阻塞

同步和异步关注的是消息通信机制。

同步是用户线程发起I/O请求后需要等待或者轮询内核I/O操作完成后才能继续执行
异步是用户线程发起I/O请求后仍需要继续执行，当内核I/O操作完成后会通知用户线程，或者调用用户线程注册的回调函数

阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态。

阻塞是指调用结果返回之前，当前线程会被挂起，I/O操作需要彻底完成后才能返回用户
非阻塞是指I/O操作被调用后立即返回一个状态值，无需等I/O操作彻底完成

浅拷贝与深拷贝

浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。

赋值和浅拷贝

当我们把一个对象赋值给一个新的变量时，赋的其实是该对象的在栈中的地址，而不是堆中的数据。也就是两个对象指向的是同一个存储空间，无论哪个对象发生改变，其实都是改变的存储空间的内容，因此，两个对象是联动的。

浅拷贝是按位拷贝对象，它会创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的就是基本类型的值；如果属性是内存地址（引用类型），拷贝的就是内存地址，因此如果其中一个对象改变了这个地址，就会影响到另一个对象。即默认拷贝构造函数只是对对象进行浅拷贝复制(逐个成员依次拷贝)，即只复制对象空间而不复制资源。

同步和互斥

同步是一种更为复杂的互斥，而互斥是一种特殊的同步。

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

线程同步方式

临界资源/关键段

当多个线程访问一个独占性共享资源时，可以使用临界区对象。

拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止。(临界区只能同一进程中线程使用，不能跨进程使用)。

临界区一般使用锁的方式来实现，常见的互斥锁和读写锁。
互斥锁/互斥量

互斥量多用于多进程之间的线程互斥，用来确保一个线程独占一个资源的访问。而且能正确处理资源遗弃的问题（占有某种资源的进程意外终止后，其它等待该资源的进程能否感知）
事件/条件变量

事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。或者按照条件变量的说法，提供线程之间的一种通知机制。
信号量

一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。

IPC方式中也有信号量，常常配合ipc共享内存来使用，作为进程之间以及同一进程不同线程间的同步手段。

总结一下：

临界区和互斥量都有“线程所有权”的概念，所以它们是不能用来实现线程间的同步的，只能用来实现互斥。
事件和信号量都可以实现线程和进程间的互斥和同步。
临界区的效率是最高的，因为它不是内核对象。但是临界区不能跨进程使用。

信号量与互斥锁

互斥量用于线程的互斥，信号量用于线程的同步。这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。
互斥量值只能为0/1，信号量值可以为非负整数。互斥锁使用对同一个资源的互斥的方式达到线程同步的目的，信号量可以同步多个资源以达到多线程同步。
互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。

设计模式

设计模式分类

种类	设计模式	特点

单例模式

最常用的设计模式之一，保证一个类仅有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。

实现思路：私有化它的构造函数，以防止外界创建单例类的对象；使用类的私有静态指针变量指向类的唯一实例，并用一个公有的静态方法获取该实例。

单例模式有两种实现方法，分别是懒汉和饿汉模式。

懒汉模式，即非常懒，不用的时候不去初始化，所以在第一次被使用时才进行初始化；
饿汉模式，即迫不及待，在程序运行时立即初始化。

//懒汉式
class Singleton{
    private:
        Singleton(){};    
        ~Singleton(){};          
        Singleton(const Singleton&);
        Singleton& operator=(const Singleton&);

    public:
        static Singleton* getInstance(){
            static Singleton instance;
            return &instance;
        }    
};

//饿汉式
class Singleton{
    private:
        Singleton(){};
        ~Singleton(){};
        Singleton(const Singleton&);
        Singleton& operator=(const Singleton&);
        static Singleton* instance;

    public:
        static Singleton* getInstance(){
            return instance;
        }       
}; 
Singleton* Singleton::instance = new Singleton();

Tips

大小写转换

大小写对换 : 字符 ^= 32;
全转小写 : 字符 |= 32;
全转大写 : 字符 &= -33;

二叉树先中后序

已知先序和后序，不能唯一确定二叉树；
已知先序或后序，而又知中序，则能唯一确定二叉树；
先序、中序相同时，二叉树没有左子树；
后序、中序相同时，二叉树没有右子树；
后序、先序相同时，只有一个根节点；

烤面筋

阿里巴巴

混合云一面

C++多态的实现方式
纯属函数的定义
基类的析构函数需要定义为虚函数？
析构函数能抛出异常吗
A是B的父类，C是B成员对象，构造函数调用顺序
指针和引用的区别
const char* 和 char* const 区别
重写与重载的区别
static关键字有什么作用？修饰全局变量，修饰局部变量，修饰类成员变量
#define和函数参数处理的区别（#define宏没有类型，不做任何类型检查）
strcpy与memcpy 的区别
strcpy判断拷贝结束（strcpy 是依据/0 作为结束判断的）
vector 和 map 底层数据结构
vector 内存管理，容量满了
头文件#ifdef 作用（防止重复包含头文件的宏）
设计模式，单类模式，懒汉式和饥汉式，观察者模式，工厂模式
描述快排，时间复杂度，稳定吗
数据库，左连接和右链接区别
先序遍历，中序，后序
判断是否是完全二叉树
vector 和 map 迭代器失效场景
重写String类，构造函数，拷贝构造函数，析构函数，重载运算符
最小栈的实现
链表O(1) 删除一个结点，已知结点的地址

云一面

C++版本新特性
nullptr 解决什么问题的
- nullptr什么可以转换成任何指针类型，可以用于抛出异常。
- 使用nullptr整型和指针类型的重载，不会产生二义性导致编译失败。
- 0和空指针分别表示不同的含义，使用nullptr可以更好的支持模板编程。
- 使用nullptr使代码更安全，让用户编写代码更清晰直观。
智能指针有哪些
内存空间上unique_ptr 和普通指针有什么区别
智能指针的自定义删除器
多线程同时读或者修改一个变量的问题
多线程同步机制
多线程同时操作一个int类型，有没有其他办法（原子变量）
C++的容器，适合什么场景
如何判断链表有环
数字n的阶乘结尾有多少连续的0

深信服

C++多态，面向对象讲一下
虚函数为什么能实现多态？实现原理
webserver线程设计
Proactor 模式和Reactor 模式区别
读写锁的特点，与其它锁的区别
线程设置数量
OSI七层模型简单讲一下
IP分类
TCP和UDP区别
TCP粘包问题

字节

TCP三次握手，两次握手？
同步异步？阻塞非阻塞？
select、poll和epoll
B+树和B树区别
指针和引用的区别
析构函数为虚函数
浅拷贝和深拷贝
一个类的对象的成员是另一个类的对象，深浅拷贝
赌博游戏：1、一次一元，一万次就停止；2、一万元本金不停的投
字符串反转 www.toutiao.com –>com.toutiao.www

百度

哈希表底层实现
get、post方法
http和https
短链接和长连接
左值右值
constexpr和const
unique_ptr原理
判断是否为子串
2^x + 2^8 +2^11 为完美平方数求x