目录
一.指针数组与数组指针的区别
区分方法:
二.Static与Const的区别：
1.static
2.const
3.static关键字的作用：
4.const关键字的作用：
三.C++三大特性：
1.封装：
2.继承：
3.多态：
分类：
其实现条件：
含义：
原理：
构造函数：
析构函数：
四.二叉搜索树：
1.定义：
2.操作：
1.查找：
2.插入：
3.删除：
五.哈希(主要应用于频繁查找的场景)：
1.定义：
2.插入元素：
3.查找元素：
4.负载因子：
六.哈希冲突或哈希碰撞：
1.如何解决：
1.在哈希函数的选择上：
2.从存储空间上：
七.红黑树：
1.定义：
2.结构：
3.性质：
4.实现：
1.带头节点的红黑树：
2.红黑树的节点：
3.红黑树插入节点的分析(最关键一步)：
八.模板：
1.定义：
2.原理：
3.使用：
4.规则：
5.模板函数：
6.模板特化：
7.类模板特化：
8.应用：类型萃取：
9.分离编译：
(1)预处理：
(2)编译:
(3)汇编
(4)链接
9.优缺点：
优点：
缺点：
九.内存泄漏：
1.什么是内存泄漏：
2.内存泄漏的原因：
1.malloc/new申请的内存没有主动释放
2. 使用free释放new申请的内存
3. 使用delete去删除数组
4. 基类的析构函数没有定义为虚函数
3.内存泄露的危害：
十.map：
十一.set：
十二.unorderedmap：
十三.unorderedset：
十六.数据库索引
1.B树，一般叫B-树：
概述：
特点：
定义：
由来：
2.B+树：
概述：
3.MySQL的索引所用的数据结构：
4.为什么常用B+树：
(1)B+树的磁盘读写代价更低：
(2)B+树的查询效率更加稳定：
(3)由于B+树的数据都存储在叶子结点中，
5.B树和B+树的区别：
(1)B+树内节点不存储数据，
(2)B+树叶节点两两相连可大大增加区间访问性，
(3)B+树更适合外部存储。
七.面试题：
1.C和C++的区别：
(1)C面向对象C++面向过程（解释面向过程和面向对象）:
(2)C++具有封装、继承、多态的性质
(3)C++具有STL
2.#define和const的区别:
3.程序编译的过程（4个）:
4.内存的布局：
5.进程间的通信方式有哪些？用过哪些？
6.malloc、calloc、realloc、new、free、delete的区别与联系:
(1)malloc函数
(2)calloc函数
(3)realloc函数
(4)new和delete
(5)相同之处:
(6)不同之点:
7.堆和栈的区别:
(1)管理方式不同。
(2)空间大小不同。
(3)生长方向不同。
(4)分配方式不同。
(5)分配效率不同。
(6)存放内容不同。
8.vector和list区别:
1.区别：
2.适用场景：
9.map和unordered_map区别:
10.哈希桶
11.vector扩容
一.指针数组与数组指针的区别
a、指针数组：是指一个数组里面装着指针，也即指针数组是一个数组；定义形式:int *a[10]；
b、数组指针:是指一个指向数组的指针，它其实还是一个指针，只不过是指向数组而已；
定义形式:int (*p)[10]; 其中，由于[]的优先级高于*,所以必须添加(*p).
区分方法:
主要看后面的两个字是什么（前面是修饰作用），因此指针数组是数组，而数组指针是指针。
指针数组：首先它是一个数组，数组的元素都是指针，数组占多少个字节由数组本身的大小决定，每一个元素都是一个指针，在32位系统下任何类型的指针永远是占4个字节。它是“储存指针的数组”的简称。
数组指针：首先它是一个指针，它指向一个数组。在32位系统下任何类型的指针永远是占4个字节，至于它指向的数组占多少字节，不知道，具体要看数组大小。它是“指向数组的指针”的简称。
二.Static与Const的区别：
1.static
static局部变量 ：将一个变量声明为函数的局部变量，那么这个局部变量在函数执行完成之后不会被释放，而是继续保留在内存中
static 全局变量 ：表示一个变量在当前文件的全局内可访问
static 函数 ：表示一个函数只能在当前文件中被访问
static 类成员变量 ：表示这个成员为全类所共有
static 类成员函数 ：表示这个函数为全类所共有，而且只能访问静态成员变量
2.const
const 常量：定义时就初始化，以后不能更改。
const 形参：func(const int a){};该形参在函数里不能改变
const修饰类成员函数：该函数对成员变量只能进行只读操作
3.static关键字的作用：
（1）函数体内static变量的作用范围为该函数体，该变量的内存只被分配一次，因此其值在下次调用时仍维持上次的值；
（2）在模块内的static全局变量和函数可以被模块内的函数访问，但不能被模块外其它函数访问；
（3）在类中的static成员变量属于整个类所拥有，对类的所有对象只有一份拷贝；
（4）在类中的static成员函数属于整个类所拥有，这个函数不接收this指针，因而只能访问类的static成员变量。
4.const关键字的作用：
（1）阻止一个变量被改变
（2）声明常量指针和指针常量
（3）const修饰形参，表明它是一个输入参数，在函数内部不能改变其值；
(4)对于类的成员函数，若指定其为const类型，则表明其是一个常函数，不能修改类的成员变量；
（5）对于类的成员函数，有时候必须指定其返回值为const类型，以使得其返回值不为”左值”。
三.C++三大特性：
1.封装：
把客观事物封装成抽象的类，且类可以把自己的数据和方法只让可信的类或者对象操作，
对不可信的进行信息隐藏。
含义：仅向用户暴露接口而降实现细节隐藏
public成员，外部可以直接访问，修改成员变量
private成员，通过实例化对象，调用函数访问修改成员变量
protected成员，与private成员类似，区别在于派生类可访问修改成员变量
注意：this指针，每个对象可通过this指针访问自己的地址
重载：
含义：将之前已经声明过的函数或运算符重载声明，得到名称一样，参数不同或者定义不同的函数
原理：C++底层重命名机制，将参数个数，类型，返回值类型做重命名，尽管函数名一致，但底层解析不同；而C语言对不同参数相同函数名的函数，解析的值一致
重写(覆盖)：
1.必须在继承的体系当中。
2.基类的成员函数必须是虚函数，子类重写的函数不是虚函数也可与基类函数构成重写。
3.子类和基类的虚函数的原型，即返回值的类型/函数名/参数列表必须一致子类中的函数加不加virtual关键字都可以。
4.与访问权限无关，但若将基类的虚函数设置为private就会导致无法访问，因为所构成多态是用基类的指针或引用，去调用函数，而在运行阶段形成不同效果，构成函数重写，将基类虚函数设为private就会导致无法调用重写函数。
例外：
(1)返回值协变：返回值类型可以不同，但基类对象必须返回基类对象的指针或引用，子类对象必须要返回子类对象的指针或引用。 此处基类对象和子类对象指的不一定必须是同一继承体系下的对象，可以是别的继承体系下的同一继承体系的基类和子类的对象。
(2)函数名字可以不同，但指的是基类和子类的析构函数他们函数名字不同
重定义(隐藏)：
1.两个函数分别在基类和派生类的作用域
2.函数名相同
3.两个基类和派生类的同名函数不构成重写就是重定义
2.继承：
主要工作就是共性抽取
具体地讲：
①继承机制是面向对象程序设计使代码可以复用的最重要的手段;
②允许程序员在保持原有类特性的基础上进行扩展，增加功能。这样实现的类称为派生类/子类。基于实现该类的原有类称为基类/父类。
③继承呈现了面向对象程序设计的层次结构，体现了由简单到复杂的认知过程。（比如：animal—>dog---->kinds of dogs）
④继承是类层次设计的复用
定义方式：class 派生类：继承方式 基类
继承方式可以是 public、protected、private三种，他们在继承基类时，所具有特性以及表现出的结果也有所不同，
具体如下：
1.以public的方式继承基类：
(1)继承了所有普通成员变量
(2)基类中public修饰的成员变量。在子类中依旧是public，可以在类外访问
(3)被private修饰的成员变量，在子类中的访问权限是不可见的。这里的不可见指基类的私有成员还是被继承到了派生类对象中，但语法上限制派生类对象不管在类里还是类外都不能去访问。
2.以protected的方式继承基类：
①基类中public修饰的成员在子类中访问权限为protected
②基类中protected修饰的成员。在子类中的访问权限依旧是protected
③父类中的private访问权限的变量在子类中不可见
3.以private的方式继承基类：
①基类中public修饰的 成员在子类中访问权限为private
②基类中protected修饰的成员在子类中的访问权限为private
③父类中的private访问权限的变量在子类中不可见
总的来说，类在设计的时候，可以按照三点原则来选择：
1.成员如果想要在类外被访问，将其设置为public
2.成员不想在类外直接被访问。但需要在子类中被访问，将其设置为protected
3.成员既不想在类外直接被访问，也不想在子类中被访问，将其设置为private
3.多态：
通俗来说，就是多种形态，具体点就是去完成某个行为，当不同的对象去完成时会产生出不同的状态。例如同样是动物都会叫，但不同动物叫时会发出不同叫声。
分类：
1.静态多态：程序在编译期间就已经确定了函数的行为
如：函数重载：对一个函数重载之后将不同的参数传入函数，就会调用不同的函数重载，在编译期间就确定要调用的函数。
2.动态多态：程序运行时才可以确定函数的行为，即在编译期间无法确定到底要调用那个函数
其实现条件：
1.必须要处于继承体系下。
2.基类中必须要有虚函数，即被virtual关键字修饰的成员函数称为虚函数，在子类中必须要对基类中的虚函数进行重写
3.虚函数调用必须要通过基类的指针或者引用来进行调用
含义：
父类声明虚函数，子类在继承父类之后会根据子类对象的不同，
调用同一虚函数时执行不同的操作
原理：
在声明类时，编译器会为每个包含虚函数的类建立一个虚表来存放虚函数的地址，类的每个对象在调用构造函数时初始化虚表和虚指针，虚指针指向对象所对应的虚表，从而实现正确调用虚函数。
构造函数：
类的构造函数是类的一种特殊的成员函数，它会在每次创建类的新对象时执行。构造函数的名称与类的名称是完全相同的，并且不会返回任何类型，也不会返回 void。构造函数可用于为某些成员变量设置初始值。
析构函数：
类的析构函数是类的一种特殊的成员函数，它会在每次删除所创建的对象时执行。析构函数的名称与类的名称是完全相同的，只是在前面加了个波浪号（~）作为前缀，它不会返回任何值，也不能带有任何参数。析构函数有助于在跳出程序（如关闭文件、释放内存等）前释放资源。
四.二叉搜索树：
1.定义：
二叉搜索树又称二叉排序树，它可以是一颗空树，亦可以是一颗具有如下性质的二叉树：
①若根节点的左子树不为空，则左子树上的所有节点的值域都小于根节点的值
②若根节点的右子树不为空，则右子树上的所有节点的值域都大于根节点的值
③根节点的左右子树分别也是一颗二叉搜索树
2.操作：
二叉搜索树中节点值唯一
1.查找：
利用二叉搜索树的特性，即右子树的value大于根节点，左子树的value小于根节点
若根节点不为空：
如果根节点的key == 查找的key----->返回true
如果根节点的key > 查找的key----->转到根节点的右子树查找
如果根节点的key < 查找的key----->转到根节点的左子树查找
否则（根节点为空），直接返回false，表示树中不存在要查找的key
2.插入：
分为两大类：
(1)树为空，直接插入；
(2)树不空：
①按照二叉搜索树的性质查找插入的位置
②插入新的节点，如：在二叉树中插入-1
第一步，查找插入位置：必须标记当前访问的节点的双亲，否则，就算找到了插入位置，由于无法访问其双亲，也是无法进行插入的。一般使用parent来标记当前访问节点的双亲节点。
第二步，插入新节点：判断待插入节点(node)的值与parent标记的节点值的大小关系。
3.删除：
分为两步：
(1)找到待删除结点，并标记其双亲：用delNode标记待删除节点，parent表基待删除结点的双亲。查找之后delNode存在两种情况，delNode为空和不为空。
(2)删除该节点：分为两种情况：
a.delNode为空：说明在二叉搜索树中不存在要删除的结点。直接return false；
b.delNode不为空：在二叉搜索树中找到了删除结点，开始删除。删除时，对于待删除结点要根据其孩子节点分情况讨论：
(1)待删除结点是叶子结点：可以直接删除。
(2)待删除结点只有左孩子：在此前提下，有两类情形:
a.delNode的双亲存在:
删除节点在右子树：
parent->right=delNode->left;
delete delNode
删除节点在左子树：
parent->left=delNode->left;
delete delNode;
b.delNode的双亲不存在:与上述仅存在叶子节点时存在的问题一样，需要在delete待删除结点之前，判断delNode与parent的位置关系，进而确定是更新parent的left指针域还是right指针域。
(3)待删除结点只有右孩子：该情况与只有左孩子的分析过程一样，存在两类情形，分别是
a.delNode的双亲存在：
删除节点在右子树：
parent->right=delNode->right;
delete delNode;
删除节点在左子树：
parent->left=delNode->right;
delete delNode;
b.delNode的双亲不存在：在delete待删除结点之前，判断delNode与parent的位置关系，进而确定是更新parent的left指针域还是right指针域。
(4)待删除结点左右孩子均存在：这种情况无法直接删除，需要在其子树中寻找替代结点
具体删除步骤如下：
1、找替代节点：在delNode的右子树（左子树）找最左侧（最右侧）的结点并保存其双亲
2、将替代节点中的值域赋值给待删除结点;
3、将替代节点删除掉:
①如果替代节点找的是delNode右子树的最左侧结点，那么待删除的替代节点一定不会有左子树，可能会有右子树
②如果替代节点找的是delNode左子树的最右侧结点，那么待删除的替代节点一定不会有右子树，可能会有左子树
一般情况下采用delNode右子树的最左侧结点作为替代节点，
具体如下：
a.找到替代节点replaceNode并记录其双亲：
Node* parent=delNode;
Node* replaceNode=delNode->right;
while(replaceNode->left)
{
parent=replaceNode;
replaceNode=replaceNode->left;
}
b.将替代节点的值赋给待删除结点：
delNode->value=replaceNode->value;
c.删除替代节点：
if(replaceNode==parent->right)
{
parent->right=replaceNode->right;
}
else
parent->left=replaceNode->right;
delNode=replaceNode;
delete delNode;
delNode=nullptr;
实现：采用模板方式实现
template<class T>
struct BSTNode//每一个结点的结构
{
BSTNode<T>* _left;//左指针域
BSTNode<T>* _right;//右指针域
T _value;//值域
BSTNode(const T& value = T())
:_left(nullptr)
, _right(nullptr)
, _value(value)
{}
};
性能分析：
插入和删除操作都需先查找，查找效率代表了二叉搜索树中各个操作的性能。对于有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数。即结点越深，比较次数越多。但对于同一个关键码的集合，如果各关键码插入的次序不同，
可能会得到不同的二叉搜索树。
最优情况下：二叉搜索树为完全二叉树，其平均比较次数为log2N
最差情况下：二叉搜索树退化为单支树，其平均比较次数为N/2
因此，二叉搜索树的时间复杂度为O(log2N)
五.哈希(主要应用于频繁查找的场景)：
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中时间复杂度为树的高度，
即O(log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，
1.定义：
通过哈希函数使元素存储位置与关键码之间建立一一映射的关系，在查找时通过该函数可以很快找到该元素。
2.插入元素：
有了定义的哈希函数就可以将当前要存储值当作函数参数，
将其传入哈希函数之后就可由哈希函数计算出一个值作为要存储的函数位置。
3.查找元素：
按照当前函数得出存储位置直接到相应位置来查找即可。
4.负载因子：
散列表装满程度的标志因子。越大，元素越多，冲突可能性越大。由哈希函数中插入元素个数/哈希存储空间大小得到。对于开放定址法，应限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中按指数曲线提升，如JAVA系统库限制为0.75，超过将resize散列表。
六.哈希冲突或哈希碰撞：
不同关键字通过相同哈希函数计算出相同的哈希地址。具有不同关键码而具有相同哈希地址的数据元素称为同义词。假设将一组数据元素2,5,8,10,9,7，由于最大值为10，所以将哈希表初始大小定为10，依据数据元素的值对哈希表当前大小值求余得到的值按序插入哈希表中。此时，如果新增一个元素77，那么通过哈希函数计算得出的值是7，要存储到7位置，但此时7位置已有元素，就产生了哈希冲突。
1.如何解决：
首先造成哈希冲突的原因主要有两个方面：
第一是哈希函数设计会导致在存储元素时计算元素存储位置时，导致两个元素存储的位置相同；
第二是空间问题，导致哈希冲突的主要原因是在计算元素存储位置时，当前元素要存储位置已经有了元素，但相同存储位置只能存储一个元素。
1.在哈希函数的选择上：
(1)直接定址法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况。
(2)除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数（最好取素数作除数取余这样产生的哈希冲突相对较少）p作为除数，按哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
(3)平方取中法：假设关键字为1234，对它平方就是1522756，抽取中间3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
使用场景：不知道关键字的分布，而位数又不是很大的情况
(4)折叠法：将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
使用场景：适合事先不需要知道关键字的分布，关键字位数比较多的情况。
(5)随机数法：选一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) =random(key),其中random为随机数函数。
使用场景：通常应用于关键字长度不等时。
(6)数学分析法
总结：哈希函数设计越精妙，产生哈希冲突的可能性就越低，但无法避免哈希冲突，所以真正解决哈希冲突的方式是解决数据的存储空间问题
2.从存储空间上：
(1)闭散列：即开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
a.线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入元素：
通过哈希函数获取待插入元素在哈希表中的位置。如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
删除元素：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
伪删除法：将所需要删除的元素位置标记为delete状态。
优点：实现非常简单，
缺点：一旦发生哈希冲突，所有冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需多次比较，导致搜索效率降低。
b.二次探测(缓解线性探测缺点)：
为避免产生冲突的数据堆积在一块，找下一个空位置的方法为：
Hi=(H0+i^2)%m或Hi=(H0-i^2)%m,其中i=1,2,3,...,是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表大小。如果探测次数较多就会出现越界的情况，需要将H(i)%=capacity。
虽然二次探测可以一定程度上解决数据堆积问题，但当表中大部分空间都被占用之后，二次探测每次探测可能取到重复数据，那么就要探测多次，但最终一定会将所有的位置都探测到。所以二次探测要求更大的空间。当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。所以二次探测就是以空间换时间的探测方法
优点：可以解决线性探测的数据堆积问题。
缺点：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷
(2)开散列：
即链地址法或开链法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每个子集合称为一个桶，各个桶中元素通过一个单链表链接起来，各链表头结点存储在哈希表中。即解决哈希冲突的方法变成了将节点组织成一个链表挂在哈希冲突的位置。
a.范型模板兼容问题：
如果哈希中放入string类，但string类不是一个整数，那么想用整数方式获取当前string类存入位置是不可能的，所以要找到一个办法来将整数转化为字符串，
可以采用将string类转化为字符串的方法解决：首先给一个仿函数，然后再给一个获取默认类型的仿函数。接着在模板中增加一个类型，如果想放入string类就要在构造对象时将其传入模板参数列表。最后获取桶的位置，在获取桶的位置时按传入参数类型转化为不同类。
b.容量为素数时候模除计算桶位置哈希冲突最少：
当计算桶的位置的时候容量为素数的时候哈希冲突的位置较少，那么即使在最一开始的时候将哈希表的容量设置为一个素数但在扩容时如果二倍扩容那么容量就会变为一个非素数的数字，那么就需要在二倍的容量左右找到一个素数来设置为新的容量。这里事先将要扩容的素数作为一个数组给出，然后写一个寻找素数的方法。每次扩容时新的容量就取最接近当前容量的素数作为新容量。
c.开散列增容：
桶个数一定，随着元素不断插入，每个桶中元素个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响哈希表的性能，因此在一定条件下需要对哈希表进行增容，具体可以根据开散列的最好情况，即每个哈希桶中刚好挂一个节点，继续插入元素时，每次都会发生哈希冲突，因此，在元素个数刚好等于桶个数时，就可以给哈希表增容。这里增容时采用的不是像闭散列那样直接新创建一个对象，然后调用对象中的insert函数，接着遍历每一个节点将节点插入到新的开散列中。因为如果调用insert函数就会重新创建一遍节点，那么当前已存在的节点就没利用到，不仅使程序需重新创建节点消耗时间，而且如果没释放旧节点还会造成内存泄漏。所以采用的是在创建新的哈希桶之后,直接将当前桶中节点挂到新哈希桶中。
d.假如黑客闲着没事攻击你的哈希表：
如果现在有黑客知道了你解决哈希冲突的办法和哈希函数，那么他针对哈希函数存入一堆元素使得这些元素都集中在一条链表上。
解决方案：
实现哈希其实就是要作为map和set的底层容器来实现map和set，那么就可以想到红黑树，如果有大部分元素集中在一条链表上，那么可以将这些元素转为一棵红黑树，即使所有元素集中在一条链表上，那么最次的查找效率就是红黑树的查找效率O(log2N)。具体实现是给每条链表加一个阈值，例如阈值为8，即链表中元素超过八个时，就将链表结构转化为红黑树，如果元素被删除后，剩余元素为6个时将结构转化为链表，因为对红黑树的删除需要复杂的旋转操作，当元素个数不是对查找效率影响不是那么大时，可以考虑将结构转化回来。
七.红黑树：
1.定义：
一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是红或黑。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
a.空树
b.二叉搜索树+节点增加颜色(红色||黑色)+性质的约束，最终可以保证最长路径下的节点数一定不超过最短路径下节点数的两倍，故为近似平衡的二叉树。
节点定义：
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType()，
Color color = RED)
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode<ValueType>* _pLeft;
// 节点的左孩子
RBTreeNode<ValueType>* _pRight;
// 节点的右孩子
RBTreeNode<ValueType>* _pParent;
// 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
};
2.结构：
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并让头结点的 pParent域指向根节点，pLeft域指向最小的节点，_pRight域指向最大的节点
3.性质：
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不会出现连在一起的红色节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点，在计算一条路径中黑色节点个数的时候要带上叶子节点，因为叶子节点也是黑色的，也就是空节点。
5. 每个叶子结点都是黑色的，此处的叶子结点指的是空结点，目的是为了保证空树也是红黑树
6.红黑树确保没有一条路径会比其他路径长出俩倍（红黑树前面的性质保证了当前的性质）
4.实现：
1.带头节点的红黑树：
将红黑树的实现给为带头的红黑树，因为红黑树是map和set的底层数据结构，这里实现出来红黑树就可以直接用当前实现的带头红黑树实现map和set，至于头节点的给出是为了方便于map和set的遍历，在STL中区间给出都是左闭右开区间的，既然红黑树作为map和set的底层数据结构，那么就一定有位置要来放map和set的迭代器，那么就可以将begin位置的迭代器放在head的左，end位置的迭代器可以放在head位置。这里将红黑树头节点的颜色给为红色。
2.红黑树的节点：
构造节点时默认为红色，如果为黑色有可能破坏当前红黑树的性质，导致每条路径的黑色节点个数不同。
3.红黑树插入节点的分析(最关键一步)：
红黑树节点构造时默认为红色，再插入时需考虑性质三，即不可以有两个红色节点连在一起。
可分为两大类：
1.将节点插入红黑树的左子树中：叔叔节点指要插入元素的parent节点的左边或右边的相邻节点。
第一种情况：叔叔节点存在且为红色，这里将节点插入红黑树内侧或外侧处理方式一样：
(1)插入结点的parent节点为黑色，则不需要调整
(2)插入节点的parent节点为红色，且插入结点的叔叔节点存在且为红色，那么当前节点插入后就违反红黑树性质，此时需调整当前树，即将当前parent节点和叔叔节点的颜色变为黑色
原因：将cur节点插入之后要解决当前parent和cur颜色都为红色的问题，那么只能将cur和parnet其中一个节点的颜色变为黑色，但不能将cur节点变为黑色，因为这样在包含cur的路径中就多一个黑色节点，则要将除包含cur之外的路径中的黑色节点全部都减少一个，又因为此时cur是新插入的节点，如果将cur颜色变为黑色，则此时就只有一条路径黑色节点个数+1，如果要调整的话，其他所有节点中黑色节点个数都要减少一个这样肯定是不行的，那么只能将parent节点的颜色变为黑色，当parent节点变为黑色后就看到在包含parent的路径中黑色节点增加，但包含parent节点的路径一定包含parent的双亲节点即g节点。将g节点颜色改为红色，那么就将包含parent路径的黑色节点个数减少一个了。但又出现新的问题，即原本包含叔叔节点的路径因为g节点变为了红色，那么包含叔叔节点的路径中少了一个黑色节点因为包含叔叔节点的路径一定包含g节点，那么此时只要将叔叔节点的颜色变为黑色即可。将parent节点和叔叔节点更新为红色之后，还要考虑g节点让更新为红色之后其双亲节点是否存在，是否是红色节点。
如果g的双亲不存在：那么此时g就是根节点那么我们此时需要将g颜色更新为黑色，因为红黑树的根节点必须是黑色的。
如果g的双亲存在：分为两种情况：
1、g的双亲为黑色那么调整结束直接退出。
2、如果g的双亲为红色且g的叔叔为红色，那么更新cur和parent继续当前的调整过程。
第二种情况：叔叔节点存在且一定为黑色或者叔叔节点不存在
(1)cur节点是新插入节点，那么叔叔节点一定是不存在的
(2)cur节点不是新插入节点，则和第一种情况类似，即更新完祖父节点后，祖父节点和叔叔节点均为黑色。
解决方法：共三步
a.将parent节点改为黑色；只能将parent修改为黑色原因：因为若叔叔节点存在且为黑色，cur之前的颜色一定是黑色，往上调整时，才将cur由黑色改为红色，cur及其子树满足红黑树性质，若将cur改成黑色，则会导致cur子树不满足红黑树的性质，故只能将parent修改为黑色。
b.将g节点改为红色；
原因：将parent修改为黑色后在parent的每条路径多了一个黑色节点，则要想办法减少一个节点，但不能动下面的节点，因为已经被调整过，那么只能能动上面的节点，即将g节点改为红色。
c.将g节点右单旋。
原因：更改后发现包含g的右边的路径少了一个黑色节点，则直接用右旋的方式解决。原本u的下层每条路径因g变为红色，而缺少一个黑色节点，右旋后，g单旋到parent下面，刚好给g的每条路径增加了一个黑色节点parent。且不影响g节点其他路径，因为从g出发只有两条路一条是左子树通向叶子节点，即parent这条路，而parent已变为黑色节点相当于代替了g节点，而另一条路径为右子树路径，已通过右单旋解决问题。叔叔节点不存在做法同上。
第三种情况：cur在parent的右侧，实际是第二种情况的变种。
解决方案：将情况三经过左旋变成情况二，但经过一次左旋和情况二仍有一点区别，即parent和cur的位置互换了，若要完全将当前情况转为情况二，那么就要将cur和parent交换。之后就可以按照情况二的解决方案解决。
2.将节点插入红黑树的右子树中：(基本与第一类相同)
第一种情况：插入节点的parent节点为红色且叔叔节点存在为红色，将节点插入红黑树的内侧或外侧处理方式相同。
解决方案：直接将parent节点改为黑色，g节点改为红色，原因同第一大类。则同第一类分为g有双亲(g叔叔为红色和黑色两种情况)和没有双亲。
(1)g没有双亲节点：没有双亲节点将g更新为黑色然后插入结束。
(2)g有双亲节点：分为两种情况：
a.g的双亲节点为黑色：若g双亲节点为黑色，那么g更新为红色就调整结束。
b.g的双亲节点为红色：
又分为两种情况：
x.叔叔节点为红色：重复当前的调整步骤。
y.叔叔节点存在且为黑色或叔叔节点不存在：若叔叔节点u为黑色节点则当前节点一定不是新插入节点。
原因：如果当前cur是新插入节点，则叔叔节点一定不存在，因为若叔叔节点存在，则在cur没插入之前就不满足红黑树的性质。
解决方案：与第一类中第二种情况类似，叔叔节点不存在也是相同做法：
首先将g和parent颜色交换，然后对g左旋即可。
第二种情况：叔叔节点存在且为黑色或叔叔节点不存在的情况。
第三种情况：叔叔节点存在且为黑色或将节点插入内侧。直接对parent右单旋转化为第二种情况，之后按照第二种情况解决即可。
八.模板：
1.定义：
函数模板代表了一个函数家族，该函数模板与类型无关，在使用时被参数化，根据实参类型产生函数的特定类型版本。
2.原理：
函数模板是一个蓝图，它本身并不是函数，是编译器根据使用方式产生特定具体类型函数的模具。本质上模板就是将本来由我们自己做的重复事情交给了编译器。在编译器编译阶段，对于模板函数的使用编译器需要根据出传入的实参类型来推演生成对应类型的函数以供调用。
3.使用：
template<class T>//要将类型用template<class+模糊的类型名>
T Add(T a, T b)
{
return a+b;
}
S Add(S a, S b)
{
return a+b;
}
template<class A, typename B>
/*一个template可放多个参数类型，但要用逗号隔开，
可用class，也可用typename*/
void test(A a,B b)
{
cout << a << endl;
cout << b << endl;
}
当传入类型为自定义类型时需要调用自定义类型的重载函数
模板的隐式类型转化和显式类型转化：
隐式类型转化：让编译器根据实参推演模板参数的实际类型
显式类型转化：在函数名后加上<>并在<>里面指定模板参数的实际类型
如果类型不匹配，编译器会尝试进行隐式类型转换。若无法转换成功，就会报错
4.规则：
(1)一个非模板函数和模板函数同时存在时，如果调用函数时传递的参数与非模板函数的参数相同时，就会直接调用非模板参数.但如果模板函数比非模板函数可以产生更好的匹配函数，就会调用模板函数。
(2)模板函数不允许自动类型转换，但普通函数可以进行自动类型转换
(3)一个非模板函数可以和一个同名的函数模板同时存在，而且该函数模板还可以被实例化为这个非模板函数
5.模板函数：
(1)template<class T>//T：类型参数
(2)template<class T,size_t N>
//T:类型参数 N：非类型参数，实际是一个常量
要注意的是：
(1)浮点数，类对象，以及字符串是不允许作为非类型模板参数的。
(2)非类型的模板参数必须在编译期间就可以确认结果。
6.模板特化：
定义：虽然模板可以解决大多数问题，但在一些特殊情况下，某些问题无法用通用模板解决，此时就需要将模板特化来解决特殊情况下的问题。比如相比较两个字符串大小，但传入的是两个指针，那么比较时，比较的是指针中保存的地址大小，而不是字符串大小，此时就需要特化模板也可以通过写一个非模板类型的函数，当遇到特殊类型时，直接调用非模板类型的函数。
7.类模板特化：
(1)全特化：将模板参数列表中所有参数都确定化。
(2)偏特化：任何针对模版参数进一步进行条件限制设计的特化版本。
8.应用：类型萃取：
使用模板技术来萃取类型(包含自定义类型和内置类型)的某些特性，用以判断该类型是否含有某些特性，从而在泛型算法中来对该类型进行特殊的处理用来提高效率或者其他。
9.分离编译：
生成一份可执行程序经历的过程
预处理、编译、汇编、链接
(1)预处理：
主要做6件事情，分别是：
①头文件展开： 处理“#include”预编译指令，
将被包含的文件插入到该预编译指令的位置。
注意：这个过程是递归进行的，也就是说被包含的文件还可以包含其他文件
②宏替换：将所有的“#define”删除，并且展开所有的宏定义
③条件编译：处理所有的条件编译指令，比如“#if”、“#ifdef”、“#elif”、“#else” 、“#endif”
④去注释：删除所有注释 “//”和“/**/”
⑤添加行号和文件名标识：目的是以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或者警告时能够显示行号
⑥保留所有的#pragma编译器指令，因为编译器要使用它们
(2)编译:
编译器将预处理完的文件进行一系列词法分析、语法分析、语义分析以及优化后生成相应的汇编代码文件。这个过程往往是整个程序构建的核心部分
(3)汇编
通过汇编器将汇编代码转变成机器可以执行的指令，相较于编译器的工作，该过程是一种比较简单的翻译。
(4)链接
主要内容是把各个模块之间相互作用的部分都处理好，使得各个模块之间能够正确的衔接
该过程主要包括三个方面：
①地址和空间分配：
模块：由若干个变量和函数构成
对于一个项目来说以C举例，它有若干个.c文件，每一个.c源文件由若干个模块构成。这些源代码按照文件目录结构来组织。每个模块之间相互依赖又相互独立。这样的存储方式使得代码更容易阅读、理解和重用。每个模块可以单独开发、编译、测试，改变部分代码不需要编译整个程序这些模块被编译好之后如何组合在一起形成一个单一的程序是需要解决的问题。模块之间的组合问题可以归结为模块之间如何通信的问题。
最常见的属于静态语言的C/C++模块之间的通信方式有两种：
Ⅰ：模块间的函数调用：需要知道目标函数的入口地址
Ⅱ：模块间的变量访问：需要知道目标变量的地址
综上：这两种方式可以归结为一种方式，那就是模块间符号的引用。这种通过符号来通信的方式类似于”拼图“，而这个拼接的过程就是链接的过程。
②符号决议:
符号决议有时候也被称为符号绑定、名称绑定、名称决议,甚至还有叫做地址绑定 、指令绑定的但是大体上他们都是一个意思。但是从细节上来说还是有些许差别的，比如“决议”更倾向于静态链接，“绑定”更倾向于动态链接。在静态链接部分，我们统一称为符号决议。每个模块的源代码经过编译器编译成目标代码，目标文件和库一起链接成最终的可执行文件。
库：一组目标文件的包，其实是一些最常用代码编译成目标文件后打包存放。最常见的库就是运行时库，他是支持程序运行的基本函数的集合。
③重定向：
比如某个项目的头文件fun.h声明一个函数foo，源文件fun.c包含头文件fun.h，对foo函数的定义；源文件main.c包含头文件fun.h，调用foo函数。源文件fun.c和main.c独立编译，汇编，生成目标文件。源文件fun.c中包含了函数foo的入口地址；源文件main.c中由于该函数内有对foo函数的声明(引入了fun.h头文件)因此编译器看到调用foo函数时，尽管编译器不知道foo函数的入口地址，但不会报错，而是将该函数的入口地址搁置，等到链接的时候再去修正。这两个源文件的相关库文件经链接器链接得到可执行程序。对于一些变量如全局变量也是如此。地址的修正过程被称为重定位，每个要被修正的目标地址叫重定位入口。重定位所做的是给程序中每个这样的绝对地址引用的位置“打补丁”，使他们指向正确的地址。
定义：一个程序（项目）由若干个源文件共同实现，而每个源文件单独编译生成目标文件，最后将所有目标文件链接起来形成单一的可执行文件的过程。模板的声明在头文件中，而其实现在其他源文件中，这就会导致在其他文件中，如果调用模板但不实例化模板时就会出错。
过程：将头文件中内容展开到其他文件中。
预处理：将头文件展开，宏替换。
编译：将文件编译为.obj文件
模板编译：
a.编译器只会对模板进行简单的语法检测，并不会深入检测语法问题
b.当用户实例化模板后，编译器会根据用户实例化类型借助模板生成处理具体类型的代码导出符号表。
总结：通过模板分离编译可以得出，当前函数中调用一个函数，但在当前文件夹中只有它的声明，而没有函数实体，就会产生一个call [函数名]命令。
9.优缺点：
优点：
(1)模板复用了代码，节省资源，更快的迭代开发，C++的STL因此产生
(2)增加了代码的灵活性
缺点：
(1)模板会导致代码膨胀问题，也会导致编译的时间变长
(2)出现模板编译错误时，错误信息非常凌乱，不易定位错误
九.内存泄漏：
1.什么是内存泄漏：
用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果一直占据该内存单元，直到程序结束。即该内存空间使用完毕之后未回收。内存泄漏形象的比喻是“操作系统可提供给所有的进程的存储空间正被某个进程榨干”，最终结果是程序运行时间越长，占用存储空间越来越多，最终用尽全部存储空间，整个系统崩溃。“内存泄漏”是从操作系统的角度来看的。这里的存储空间并不是指物理内存，而是指虚拟内存大小，这个虚拟内存大小取决于磁盘交换区设定的大小。由程序申请的一块内存，如果没有任何一个指针指向它，那么这块内存就泄漏了。内存泄漏一般指的是堆内存的泄漏。堆内存是指程序从堆中分配的、大小任意的（内存块的大小可以在程序运行期决定），使用完后必须显示的释放的内存。应用程序一般使用malloc、realloc、new等函数从堆中分配到一块内存，使用完后，程序必须负责相应的调用free或delete释放该内存块。否则，这块内存就不能被再次使用，我们就说这块内存泄露了。
2.内存泄漏的原因：
1.malloc/new申请的内存没有主动释放
2. 使用free释放new申请的内存
malloc/free以及new/delete必须是各自成对出现，如果混用，就会导致意想不到的情况出现。另外，如果用delete释放void指针指向的对象同样也会造成内存泄露。
3. 使用delete去删除数组
使用 new 申请的数组，释放的时候要用 delete[] 删除，如果错误地使用 delete 删除，就会造成内存泄漏。
4. 基类的析构函数没有定义为虚函数
当基类指针指向子类对象时，如果基类的析构函数不是virtual，那么子类的析构函数将不会被调用，子类的资源没有正确是释放，因此造成内存泄露。
3.内存泄露的危害：
内存泄漏的堆积，最终消耗尽系统所有的内存。从这个角度讲，一次性内存泄漏并没有什么危害，因为它不会堆积，而隐式内存泄漏的危害性则非常大，因为较之于常发性和偶发性内存泄漏它更难被检测到。长期运行的程序出现内存泄漏，影响很大，如操作系统、后台服务等等，出现内存泄漏会导致响应越来越慢，最终卡死。
十.map：
十一.set：
十二.unorderedmap：
十三.unorderedset：
十六.数据库索引
1.B树，一般叫B-树：
概述：
这里的B表示 balance(平衡的意思),B-树是一种多路自平衡的搜索树(B树是一颗多路平衡查找树)它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。
特点：
(1)所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
(2)任何一个关键字出现且只出现在一个结点中；
(3)搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
(4)在关键字全集内做一次查找,性能逼近二分查找；
定义：
B-树是一类树，包括B-树、B+树、B*树等，是一棵自平衡的搜索树，它类似普通的平衡二叉树，
不同的一点是B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。B-树允许每个节点有更多的子节点即可（多叉树）。子节点数量一般在上千，具体数量依赖外部存储器的特性。
(1)B树中的每个节点的元素和子树数量是有限的，除了根节点外，所有节点最多拥有M-1个元素，所有非叶子非根节点最多拥有M个子树,即为M阶树。
(2)根节点至少有两个子树，除根节点之后的非叶子节点拥有K个子树及K-1个元素((M+1)/2<K<M),元素按照递增或递减顺序排列
(3)所有叶子节点属于同一层
由来：
传统用来搜索的平衡二叉树有很多，如AVL树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为50ns，而磁盘在10ms左右。速度相差了近5个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘IO上。那么我们如何提高程序性能？减少磁盘IO次数，像AVL树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
2.B+树：
概述：
B+树是B-树的变体，也是一种多路搜索树, 它与B-树的不同之处在于:
(1)所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的data)
(2)为所有叶子结点增加了一个链指针。因为内节点并不存储 data，所以一般B+树的叶节点和内节点大小不同，而B-树的每个节点大小一般是相同的，为一页。为了增加 区间访问性，一般会对B+树做一些优化。
3.MySQL的索引所用的数据结构：
B树和B+树。
4.为什么常用B+树：
(1)B+树的磁盘读写代价更低：
B+树内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
(2)B+树的查询效率更加稳定：
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
(3)由于B+树的数据都存储在叶子结点中，
分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。
5.B树和B+树的区别：
(1)B+树内节点不存储数据，
所有data存储在叶节点导致查询时间复杂度固定为logn。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。B树的由于每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况是O(1)就可以找到数据，而B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据。
(2)B+树叶节点两两相连可大大增加区间访问性，
可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
根据空间局部性原理：
如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。B+树可以很好的利用局部性原理，若访问节点key为50，则key为55、60、62的节点将来也可能被访问，可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘IO的次数。
(3)B+树更适合外部存储。
由于内节点无data域，每个节点能索引的范围更大更精确。由于B-树节点内部每个key都带着data域，而B+树节点只存储key的副本，真实的key和data域都在叶子节点存储。前面说过磁盘是分block的，一次磁盘IO会读取若干个 block，具体和操作系统有关，那么由于磁盘IO数据大小是固定的，在一次IO中，单个元素越小，量就越大。这就意味着B+树单次磁盘IO的信息量大于B-树，从这点来看B+树相对B-树磁盘IO次数少。由于B树的节点都存了key和data，而B+树只有叶子节点存data，非叶子节点都只是索引值，没有实际的数据，这就时B+树在一次IO里面，能读出的索引值更多。从而减少查询时候需要的IO次数。
七.面试题：
1.C和C++的区别：
(1)C面向对象C++面向过程（解释面向过程和面向对象）:
A. 面向过程
面向过程是一种以事件为中心的编程思想，编程时把解决问题的步骤分析出来，然后用函数把这些步骤实现，在一步一步的具体步骤中再按顺序调用函数。
B.面向对象
在日常生活或编程中，简单的问题可以用面向过程的思路来解决，直接有效，但当问题的规模变得更大时，用面向过程的思想是远远不够的。所以慢慢就出现了面向对象的编程思想。世界上有很多人和事物，每个都可以看做一个对象，而每个对象都有自己的属性和行为，对象与对象之间通过方法来交互。面向对象是一种以“对象”为中心的编程思想，把要解决的问题分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个对象在整个解决问题的步骤中的属性和行为。
C.优缺点比较
面向过程:
优点：a.流程化使得编程任务明确，在开发之前基本考虑了实现方式和最终结果，
具体步骤清楚，便于节点分析。
b.效率高，面向过程强调代码的短小精悍，善于结合数据结构来开发高效率的程序。
缺点：需要深入的思考，耗费精力，代码重用性低，扩展能力差，后期维护难度比较大。
面向对象:
优点:
a.结构清晰，程序是模块化和结构化，更加符合人类的思维方式；
b.易扩展，代码重用率高，可继承，可覆盖，可以设计出低耦合的系统；
c.易维护，系统低耦合的特点有利于减少程序的后期维护工作量。
缺点：
a.开销大，当要修改对象内部时，对象的属性不允许外部直接存取，所以要增加许多没有其他意义、只负责读或写的行为。这会为编程工作增加负担，增加运行开销，并且使程序显得臃肿。
b.性能低，由于面向更高的逻辑抽象层，使得面向对象在实现时，不得不做出性能上面的牺牲，计算时间和空间存储大小都开销很大。
(2)C++具有封装、继承、多态的性质
(3)C++具有STL
2.#define和const的区别:
(1)一个发生在预处理阶段，一个发生在编译阶段
(2)#define只是简单的字符串替换没有进行类型的安全检查，const进行类型的安全检查
(3)#define的字符串会替换多份，更占用内存，const常量只保存一份（保存在常量区）
3.程序编译的过程（4个）:
预处理：头文件展开，宏替换，条件编译，去注释
编译：语义分析，语法分析，目标代码生成，优化，生成汇编代码
汇编：生成二进制文件
链接：将目标文件进行链接形成可执行程序（解决符号表的问题）
4.内存的布局：
从高地址到低地址（自顶向下），栈区，共享区，堆区，代码段，数据段
5.进程间的通信方式有哪些？用过哪些？
管道，消息队列，共享内存，信号量，Socket网络通信，项目中使用了Socket网络通信
6.malloc、calloc、realloc、new、free、delete的区别与联系:
(1)malloc函数
void* malloc(int n)；n表示要申请空间的字节数。如果函数执行成功则返回申请空间的首地址，并且malloc函数的返回值是void*,因此使用时必须根据数据类型进行强制转换，函数执行失败则返回NULL。malloc函数申请的空间是没有初始化的，需要使用memset函数进行初始化
(2)calloc函数
void* calloc(int n, int size)n表示需要申请元素的个数，size表示一个元素的大小，申请空间的总大小则是n与size的乘积。如果函数执行成功则返回申请空间的首地址，且realloc函数的返回值void*,因此使用时必须根据数据类型进行强制转换，函数执行失败则返回NULL。calloc函数申请的空间是经过初始化的，全部初始化为0。
(3)realloc函数
void* realloc(void* p, int n)；p表示已经在堆上存在的一块空间的地址，n表示调整后空间的字节数。realloc函数的作用是将p指向的空间调整为n个字节大小。常与以上两个函数搭配使用。在增容时，如果此时该空间之后的空闲空间足够，则直接扩容，如果其之后的空闲空间不够，那么会去重新找一块足够大的空间，将旧空间的内容全部复制到新空间上，然后返回新空间的地址，释放原来的旧空间。realloc函数申请的空间也是没有初始化的。
(4)new和delete
int* p1 = new int; //申请一个 int 型的空间
int* p2 = new int(1); // 申请一个 int 型的空间并初始化为 1
int* p3 = new int[10]; // 申请10个类型为 int 的空间
delete p1;
delete p2;
delete[] p3;
申请和释放单个元素的空间，使用new和delete操作符，申请和释放连续的空间，使用new[]和delete[]
(5)相同之处:
malloc、calloc、realloc和new的共同点是:都是从堆上申请空间，并且需要用户手动释放。
(6)不同之点:
a.malloc、calloc、realloc和free是函数，new和delete是操作符
b.malloc、realloc申请的空间不会初始化，new可以初始化
c.malloc申请空间时，需要手动计算空间大小并传递，new只需在其后跟上空间的类型即可
d.malloc的返回值为void*, 在使用时必须强转，new不需要，因为new后跟的是空间的类型
e.malloc申请空间失败时，返回NULL，因此使用时必须判空，new不需要，但new需要捕获异常
f.申请自定义类型对象时，malloc/free只会开辟空间，不会调用构造函数与析构函数，而new在申请空间后会调用构造函数完成对象的初始化，delete在释放空间前会调用析构函数完成空间中资源的清理
g.new/delete比malloc和free的效率稍微低点，因为new/delete的底层封装了malloc/free
7.堆和栈的区别:
(1)管理方式不同。
栈由操作系统自动分配释放,无需手动控制;堆的申请和释放工作由程序员控制，会产生内存泄漏；
(2)空间大小不同。
每个进程拥有的栈的大小要远远小于堆的大小。理论上，程序员可申请的堆大小为虚拟内存的大小，进程栈的大小64bits的Windows默认1M，64bits的Linux默认10M；
(3)生长方向不同。
堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。
(4)分配方式不同。
堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由操作系统进行释放，无需手工实现。
(5)分配效率不同。
栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。
(6)存放内容不同。
栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对当前函数执行断点进行保存，需要使用栈来实现，首先入栈的是主函数下一条语句的地址，即扩展指针寄存器的内存，然后是当前栈帧的底部地址，即扩展基址指针寄存器内容，再然后是被调函数的实参等，一般情况下是按照从右向左的顺序入栈，之后是调用函数的局部变量，注意静态变量是存放在数据段或者BSS段，是不入栈的。出栈的顺序正好相反，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。
栈是一种运算受限的线性表，其限制是指只仅允许在表的一端进行插入和删除操作，这一端被称为栈顶，相对地，把另一端称为栈底。把新元素放到栈顶元素的上面，使之成为新的栈顶元素称作进栈、入栈或压栈；把栈顶元素删除，使其相邻的元素成为新的栈顶元素称作出栈或退栈。这种受限的运算使栈拥有“先进后出”的特性。
栈分顺序栈和链式栈两种。栈是一种线性结构，所以可以使用数组或链表作为底层数据结构。使用数组实现的栈叫做顺序栈，使用链表实现的栈叫做链式栈，二者的区别是顺序栈中的元素地址连续，链式栈中的元素地址不连续。
堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小根堆，如果根节点最大，称之为大根堆。
堆的左右孩子没有大小的顺序。
8.vector和list区别:
1.区别：
1.vector底层实现是数组，list 是双向链表
2.vector支持随机访问，list 不支持
3.vector是顺序内存，list 不是
4.vector在中间节点进行插入删除会导致内存拷贝，list 不会
5.vector一次性分配好内存，不够时才进行扩容，list每次插入新节点都会进行内存申请
6.vector随机访问性能好，插入删除性能差，list 随机访问性能差，插入删除性能好
2.适用场景：
1. vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
2. list 拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。
9.map和unordered_map区别:
map、unordered_map 是 C++ STL 中的两个容器
区别：
1. 导入的头文件<map> 、<unordered_map>
2. 原理及特点
map：内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了 map 的效率。
unordered_map：内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的。
10.哈希桶
unordered_map容器和map容器一样，以键值对（pair类型）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。底层采用哈希表实现无序容器时，会将所有数据存储到一整块连续的内存空间中，并且当数据存储位置发生冲突时，解决方法选用的是“链地址法”（又称“开链法”）。
可以看到，当使用无序容器存储键值对时，会先申请一整块连续的存储空间，但此空间并不用来直接存储键值对，而是存储各个链表的头指针，各键值对真正的存储位置是各个链表的节点。不仅如此，在C++STL标准库中，将图中的各个链表称为桶，每个桶都有自己的编号（从 0 开始）。当有新键值对存储到无序容器中时，
整个存储过程分为如下几步：
1. 将该键值对中键的值带入设计好的哈希函数，会得到一个哈希值（一个整数，用 H 表示）；
2. 将 H 和无序容器拥有桶的数量 n 做整除运算（即 H % n），该结果即表示应将此键值对存储到的桶的编号；
3. 建立一个新节点存储此键值对，同时将该节点链接到相应编号的桶上。
另外，哈希表存储结构还有一个重要的属性，称为负载因子。该属性同样适用于无序容器，用于衡量容器存储键值对的空/满程序，即负载因子越大，意味着容器越满，即各链表中挂载着越多的键值对，这无疑会降低容器查找目标键值对的效率；反之，负载因子越小，容器肯定越空，但并不一定各个链表中挂载的键值对就越少。如果设计的哈希函数不合理，使得各个键值对的键带入该函数得到的哈希值始终相同（所有键值对始终存储在同一链表上）。这种情况下，即便增加桶数是的负载因子减小，该容器的查找效率依旧很差。无序容器中，负载因子的计算方法为：负载因子 = 容器存储的总键值对 / 桶数.默认情况下，无序容器的最大负载因子为 1.0。如果操作无序容器过程中，使得最大复杂因子超过了默认值，则容器会自动增加桶数，并重新进行哈希，以此来减小负载因子的值。需要注意的是，此过程会导致容器迭代器失效，但指向单个键值对的引用或者指针仍然有效。这也就解释了，为什么我们在操作无序容器过程中，键值对的存储顺序有时会“莫名”的发生变动。
11.vector扩容
当vector的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么vector就需要扩容。vector容器扩容的过程需要经历以下3步：
1. 完全弃用现有的内存空间，重新申请更大的内存空间；
2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
3. 最后将旧的内存空间释放。因为vector扩容需要申请新的空间，所以扩容以后它的内存地址会发生改变。vector扩容是非常耗时的，为了降低再次分配内存空间时的成本，每次扩容时vector都会申请比用户需求量更多的内存空间（这也就是vector容量的由来，即capacity>=size），以便后期使用。
