C 常见面试题

什么是面向对象

在C语言中，数据和函数是分开来的，语言本身并不支持数据和函数之间的关联性，这种程序就称为程序性的。它们被一组算法驱动，处理共同的外部数据。
而C++将数据和函数封装起来，用户只能通过类设计者提供的接口访问类内封装的数据。
面对对象的三大特点：封装，继承和多态。
数据抽象和封装。类的基本思想是数据抽象和封装。数据抽象是一种依赖于接口和实现分离的编程技术。类的接口包括用户所能执行的操作，类的实现则包括类的数据成员，负责接口实现的函数以及定义类所需要的各种私有函数。封装实现了类的接口和实现的分离，封装后的类隐藏了它的实现细节，类的用户只能使用接口而无法访问实现部分。
继承的三种方式：public，private和protected继承。
多态，多态分为动态多态和静态多态。静态多态是通过模板实现的，动态多态是通过虚函数和RTTI实现的。
动态绑定和静态绑定。

指针和引用的区别

1 从定义上来说，可以定义指针的指针，但是不能（直接）定义引用的引用（模板参数推导的时候可以）。定义。
2 const引用可以指向字面值常量，而指针不能（除了字符数组）。
3 指针本身可以是const的，而引用不能。底层const和顶层const。
指针可以为空，引用不能。初始化。
指针可以被重新赋值。而引用一旦被绑定就不能修改。赋值。
指针必须被解引用才能使用，而引用不需要。访问。
指针变量可以进行运算，而引用不能。运算。
指针本身是一个变量，有它自己的内存地址，以及在栈上的大小。而引用的内存地址和它绑定的对象一样，看起来是一样的，但是实际上是不一样的（编译器做了一些操作），可以把引用当做它引用对象的别名。

inline[10,11]

inline函数对于封装提供了一种必要的支持，可以有效的存取封装于class中的nonpulibc数据。避免函数调用的开销，比如说参数入栈，出栈。
它是C程序中宏函数的一个安全替代品。宏函数是由预处理器对宏进行替换，而内联函数是通过编译器控制的。内联函数是函数，会进行参数检查。只不过在调用的时候像宏一样展开，减少函数调用。
如果一个inline函数被调用太多次的话，会产生太多的扩展代码，使得程序变得的道别大。
inline函数有多个局部变量或者参数带有副作用，都会产生临时性对象。
inline中调用inline可能会使得复杂度太大，而没有办法内联。
用inline声明的函数并不一定会inline，取决于编译器。编译器通过计算各种操作的复杂度，计算是否需要内联。
inline只适合函数体代码简单的函数使用，不能有循环等语句。适用于规模小，流程直接，频繁调用。
建议inline函数的定义放在头文件中。
类内定义的函数是隐式的inline函数。
inline关键字应该和实现放在一块，只在声明中说明没有用。
慎用内联。

static关键字[4]

隐藏全局变量和函数的作用域。这一个已经被标准抛弃了。
修饰局部变量，改变变量的生命周期。
修饰类的数据成员和成员函数。

const关键字

顶层const和底层const。主要是常量指针和常量引用。
const修饰形参和const修饰返回值。
和类相关。
修饰成员变量，必须使用初始化列表赋值。
const修饰成员函数。
修饰类对象，必须调用const类型的函数。
const可以用来区分重载。

C语言结构体中的空数组[20]

声明一个不占用空间的指针，redis的sds就用到了这种方法。

include ""和`<>`区别

它们的查找路径不同，<>先查找系统目录，"“先查找当前目录。
”"查找到的会隐藏<>查找到的。

const和宏常量的区别

const常量有数据类型，而宏常量没有。编译器可以对前者进行安全检查，对后者只能进行字符替换。

内存泄露

忘记delete
array delete
虚析构函数
指针数组，没有对每个指针进行释放。

指针函数和函数指针

指针函数是一个函数，返回类型是一个指针而已。
函数指针是一个指针，是一个指向函数的指针。

数组和指针

数组是一块连续存放的空间，指针是一个地址，指针变量是一个变量。
初始化。
大小。
指针数组和数组指针。
作为函数参数。

vector扩容

为什么不是常数

成倍增长可以保持常数时间复杂度的插入操作。
常数增长的插入时间复杂度是O(n)。
为什么？假设要插入n个元素，成倍增长的倍数是p，常数增长的大小是q。
成倍增长总共的复制开销：
$$ \sum_{i=1}^{log_p^n } p^i $$
常数增长总共的复制开销：
$$\sum_{i=1}^{n/q} qi $$

为什么是1.5或者2

为什么是1.5？可以复用之间的空间。
为什么是2？实现简单。

strlen和sizeof的区别

sizeof是运算符。它的值在编译时就已经确定了，所以不能用来获得动态分配的内存空间的大小。
strlen是函数，在运行时计算的。
静态数组传递给strlen就会退化成指针，在传递给sizeof的时候还是数组。strlen是数组中内容的长度，而sizeof是静态数组声明时的大小。
动态数组(malloc)分配的，strlen能获得数组中内容的大小，而sizeof只能获得指针的大小。
strlen不会计算空字符，而sizeof会。

override和overload

只有虚函数能被ovrride。
override是用来实现多态的，函数的参数类型和声明和可以父类中完全一样。
而overload中，函数的参数列表必须不同。它的作用我觉得可能是方便记忆，方便理解。实现同一个功能的函数具有同样的名字。

空类的大小为1字节

标准规定空类的大小为1，因为两个不同的对象需要不同的地址表示。标准规定完整对象的大小大于0。

虚函数和虚函数表[12]

当某个类中声明了虚函数时，编译器会为该类创建一个虚函数表，存放虚函数的地址，这个是在编译时期完成的。然后编译器会在该类的对象中添加一个虚指针指向这样一个虚函数表。
当有其他类继承这个类时，编译器为这个类也创建一个虚函数表。如果派生类重写了基类的虚函数，那么编译器会更新虚函数表中的函数地址为派生类的虚函数地址。
当发生虚函数调用时，编译器会根据指针指向的对象，找到该对象的虚函数表，然后调用相应的虚函数。

虚析构函数

一个基类总是需要虚析构函数。

虚继承

为什么要有虚继承？
派生类可能多次继承同一个类。默认情况下，派生类会含有继承链上每个类对应的子部分，如果某个类在派生过程中出现了多次，派生类中将包含该类的多个子对象。比如iostream之类的类，肯定不行。
声明成虚继承的继承体系中，无论虚基类在继承体系中出现了多少次，派生类中都只含有一个共享的虚基类子对象。

多态

C++的多态分为两种，一种是静态多态，通过函数重载和模板实现。
一种是动态多态，虚函数实现。

C实现C++的多态[5,6, 29]。

RTTI[13]

C++ 缺乏安全的向下转型（将派生类指针转换成基类指针），只有类型真的可以被转型的时候，才会执行向下转型。

RTTI提供了一个安全的向下转型，但是只对那些多态类型有效（使用继承和动态绑定）。为什么？因为那些ADT和非多态类型不需要这些东西，所以，很自然的就想到，在虚函数表上进行操作，通过在虚函数表中增加一个slot（通常是第一个slot），它是通过编译器在编译器指定的，和虚函数一起。

dynamic_cast可以用来实现向下转型，，如果向下转型是安全的，就可以执行，而如果是不安全的，就返回0。
dynamic_cast可以在执行期决定真正的类型。代价是什么呢，一个就是编译时在虚函数表中增加的一项，另一个就是运行期间，获取type_info对象的地址，这个地址和指向对象的类型有关，然后获得它的类型。
对于引用和指针的异常处理不同：
对于指针，如果返回0，表示这个指针是空指针。
对于引用，如果引用不是一种真的派生类，就会抛出bad_cast异常。

type_info对象对于内置类型和非多态的类型也适用。不过这种type_info对象是编译器取得的（在需要的时候），而不是运行期。

`cast`

`static_cast`

和C中提供的强制类型转换一样。

`const_cast`

只能改变运算对象的底层const，可能去掉也可以添加底层const。

`reinterprect_cast`

为运算对象的bit mode提供新的解释。比如可以把一个整数解释成字符串。

`dynamic_cast`

dynamic_cast实现安全的动态转换。
它可以可以安全实现的执行downcast，但是需要是含有虚函数的类。

智能指针

shared_ptr实现

引用计数放在指针成员中。

template<typename T>
class shared_ptr
{

public:
    shared_ptr():pd(nullptr)
    { }

    shared_ptr(T *data): pd(data), new size_t(1)
    { } 

    // 拷贝构造函数
    explicit shared_ptr(const shared_ptr<T> &rhs)
    {
        pd = rhs.pd; 
        count = rhs.count;

        ++*rhs.count;
    }

    shared_ptr<T>& operator=(const shared_ptr<T> &rhs)
    {
        if(count && --*count == 0)
        {
            delete pd;
            delete count;
        }

        pd = rhs.pd;
        count = rhs.count;
        if(rhs.count)
            ++*count;

        return *this;
    }

    ~shared_ptr()
    {
        if(count && --*count == 0)
        {
            delete pd; 
            delete count;
        }
        
    }

    T& operator*() 
    {
        return *p;
    }
    T& operator*() const 
    {
        return *p;
    }

private:

    T *pd;
    size_t *count;

};

unique_ptr实现

template<typename T>
class unique_ptr
{
public:
    unique_ptr():p(nullptr)
    { }
    // 构造函数
    explicit unique_ptr(T *data): p(data)
    { }

    //拷贝构造
    unique_ptr(const unique_ptr&) = delete;

    //拷贝赋值
    unique_ptr& operator=(const unique_ptr &rhs) = delete;

    //析构
    ~unique_ptr()
    {
        if(p)
            delete p;
    }

    T* release()
    {
        T *q = p;

        p = nullptr;
        return q; 
    }

    T* reset(T *data)
    {
        if(p)
            delete p;
        p = data;
    }

    T& operator*() {return *p;}
    //指针本身是个常量
    // const 修饰this指针，常量指针，指向不能改变，指针指向的值可以改变。为什么这里返回值不是常量。这个指针可不可以指向常量对象，可以。
    T& operator*() const {return *p};

private:
    T *p;

};

shared_ptr和unique_ptr

它们管理保存指针的策略，前者可以共享指针，而后者则独占指针。
它们允许用户重载deleter的方式。只要在创建或者reset指针时给shared_ptr提供一个deleter即可。但是，deleter是unique_ptr对象的一部分。
shared_ptr的deleter是运行时绑定，所以需要使用指针，开销大，但是用户重载更方便。它的执行方式可能如下：del?del(p): delete p。
而unique_ptr的deleter是编译时绑定，避免了间接调用deleter的运行时开销。
shared_ptr不能动态管理数组，而unique_ptr可以动态管理数组。

智能指针和数组

shared_ptr不支持管理动态数组。需要提供自定义的delete（只要是一个可调用对象就行）。
unique_ptr支持动态管理数组，需要在类型后面加上一对方括号。当unique_ptr销毁时，会自动使用delete[]。不能使用成员访问运算符（点和箭头），但是可以使用下标访问运算符。

weak_ptr

weak_ptr可以解决循环引用问题，比如双向链表中的循环引用。[9]

类模板和函数模板的区别

类模板用来生成类，函数模板的参数是由编译器推导的，而类模板的参数必须指定。

模板特化和偏特化

模板特化的本质是模板实例化，定义特化版本时，我们实际上是接替了编译器的工作。
函数模板只能全特化。
类模板可以全特化也可以偏特化。偏特化既有类型的偏特化，也有个数的偏特化。

为什么模板的声明和实现要写在一起而类的实现和声明要分开[7]

C++ 采用分离式编译。可以不用将所有的代码写在一个文件中，可以将他们分解为更小，更好管理的模块，可以独立的修改和编译这些模板。当我们改变这些模板时，只需要重新的编译它，并重新链接，不必重新编译其他文件。这一功能主要是通过链接器实现的。更多的内容可以查看CSAPP上介绍的。
对于普通对象和函数而言，类的声明写在头文件中，实现写在cpp文件中。cpp文件是可以单独被编译的。
但是模板函数的声明并不能直接被直接编译成二进制代码，在遇到template时编译器不会为它分配任何空间。因为只有在真正使用模板的时候，才会知道模板参数的值。编译器和链接器的某一个部分，可以去掉模板的多重定义。

哈希表

哈希表冲突严重的话会退化成单链表。这个时候哈希表的各种操作的时间复杂度都提升了一个量级，会占用大量CPU时间，降低系统响应时间，可以用来做DDos攻击。
解决冲突的方法：

内存管理

new

new一个空数组是和合法的，但是不能解引用！！！可以把它当做尾后迭代器来使用。

malloc, calloc和realloc

malloc分配指定字节的数组，初值不定。
calloc分配nobj个size字节的对象，每一位都初始化为0。
realloc在以前分配的区域的基础上扩大为新的容量。如果原来的区域后面有足够大的空间，就在那里，否则复制到一个新的空间中。

placement new

重载operator new函数。placement new可以为分配函数提供额外的信息。
Placement new允许我们将对象构造在已经分配好的内存上，分配好的内存不一定是operator new分配的内存，甚至可以是静态内存。
allocator的内存分配和构造函数的调用是分开进行的，通过两个函数allocate和construct。
对应于new，可以使用operator new进行空间分配，使用placement new调用构造函数。

stl allocator

管理的是malloc分配的虚拟内存，比如STL的alloc分配器。
大于128B的，直接malloc。
小于等于128B的，维护16个链表，每个都是8的倍数。

用户空间内存分配[22]

malloc实现[21]

管理的是虚拟内存。
除了mmap外的几种方式，一般分配大内存的话都是mmap，小内存的话都是通过bin实现的。

mmap

ptmalloc实现

tcmalloc实现

jemalloc实现

内核空间内存分配[22]

伙伴算法用于大块连续物理内存的分配。
slab和kmalloc用于小块连续物理内存的分配。
vmalloc用于连续虚拟内存的分配。
注意，这三种方法都是内核空间的内存分配。

伙伴算法[24]

什么是伙伴算法

伙伴算法，把所有的空闲页框分成11个链表，每个链表分别管理2的0到10次方大小的连续页框。伙伴算法只能分配2的幂次页的空间。通常一个页框是4K大小，所以伙伴算法维持的最大连续内存4M大小，最小是4K大小。

伙伴的回收

什么是伙伴，由同一个块分裂开来的两个块。所有大小为2的k的块，它的地址一定是2^k次方的整数倍。将它的地址除以2的k+1次方，然后再加减2的k次方，就可以得到它的伙伴的地址。
比如大小为16的块，可能是0-16，16-32，32-48，48-64。它们的地址都是16的倍数，0-16和16-32互为伙伴，而32-48和48-64互为伙伴。但是16-32和32-48不是伙伴！！！因为它们不是从同一个块分裂来的。。。。

优点和缺点[25]

优点

解决了外部碎片问题。
解决了连续页框的分配问题。
针对于大内存。

缺点：

合并的要求太严格了。
内碎片问题。
合并和拆分的开销，如果刚合并又要拆分等等。

slab[26]

slab机制通常由三类对象构成：kmem_cache，slab和slab对象构成。[27]
一个kmem_cache通常有1个或者多个slab，一个slab通常是1个或者多个连续物理页，然后它被分成多个slab对象。这个cache管理的就是相应大小的slab对象。

kmalloc实现[23]

分配的是小的连续的物理内存，基于slab实现的。
slab又是基于伙伴系统的。

vmalloc实现

分配的是连续的虚拟内存，物理内存不一定连续。

对齐

gcc 默认对齐是4字节对齐。在结构体中要注意。
malloc是16字节对齐。

cmake, make和makefile

cmake根据CMakeLists.txt生成makefile，make执行makefile。
makefile是文件，包含了怎么样进行编译和链接。makefile可以手动写，但是它不跨平台（即不同平台的makefile不同），而且工程大很麻烦。
CMakeLists.txt是我们自己写的。cmake指向CMakeLists.txt所在的目录，cmake可以根据CMakeList.txt跨平台自动生成makefile。
make用来执行makefile，调用makefile中用户指定的命令进行编译和链接。

void *

可以接收任意类型的赋值，无需强制类型转换。
经过类型转换可以赋值给任意类型的变量。

lambda表达式

为什么要有lambda表达式？

总共有四种可调用对象，函数，函数指针，重载了函数运算符的类和lambda表达式。
lambda表达式的声明。
auto f = [local variable](int x){return a;};
对于那种只在一两个地方使用的简单操作，lambda表达式是有用的。当在多个地方使用的话，通过应该使用一个函数，或者需要很多语句的话，也是函数比较好。
capture list中引用和值的作用。
可以和STL中的算法进行交互。

lambda的底层实现

面向对象的几大原则

单一职责原则。解耦，增强内聚，即高内聚低耦合。
开放封闭原则。对扩展开放，对修改关闭。
里氏替换原则。子类可以替换父类。
依赖倒置原则。依赖于抽象而不是依赖细节。
接口分离原则。不需要让客户程序依赖它们不需要的方法。一个接口应该只提供一种对外的功能。
合成复用原则。
迪米特原则。

设计模式

单例模式
reactor模式。是事件驱动模式，它由一个或者多个并发输入源，有一个service handler和多个request handler。这个service handler会同步的将输入多路复用给相应的request handler。
比如说redis的

数据结构相关

堆

二叉堆是完全二叉树，一般可以用数组实现。最大堆就是每个根节点的值大于其子节点的值，最小堆就是每个根节点的值小于其子节点的值。

SGI STL heap相关的算法

push_heap，将新的节点插在最后一个位置。
pop_heap，弹出最大堆的堆顶元素。（或者就是heapify）
sort_heap，就是排序。
make_heap，创建一个最大堆。

优先队列

底层实现是二叉堆，总是弹出key最大的元素。

哈希和哈希表

什么是哈希

哈希：把任意长度的输入，变成固定长度的输出，这个映射的规则就是对应的哈希算法，原始数据映射后的输出叫做哈希值。哈希值存在的目的是加速key-value的查找速度。
哈希常见的几种实现方式：顺序，链式，散列，索引。哈希表是其中的一种。
注意把哈希和哈希表区分开来。

碰撞（冲突）

什么是碰撞？输入不同的数据得到相同的输出，哈希一定会发生碰撞。

hash

好的hash要求

抗碰撞。不同的输入得到相同输出的概率要小。
抗篡改。输入数据的小的变化会得到完全不同的值，输入相同的数据会得到相同的值。（雪崩效应）。
速度要好。哈希算法的效率要高
根据输出不能反推输入。

hash的应用

保存密码，保存用户密码的哈希值。（这也是很多地方只能重置密码的原因，因为它们也不知道你的密码。。。）
数据校验。
负载均衡。在服务器扩容时，使用一致性哈希。

hashtable

哈希表是用哈希算法实现的表，提供了对任何有名字项的存取和删除操作，也可以查看是一种字典，提供常数时间的读写操作。
哈希表的扩容(rehash)，元素个数比bucket个数多，再打散，把bucket个数增加两倍（接近两倍的质数）。

hashtable碰撞的解决方法

负载系数：元素个数除以表格大小，除了开链法，都要在0,1之间。
线性探测：插入的时候，找到一个不可用的位置（被其他值占了），继续找下下一个位置，直到找到一个空位置。查找的时候，如果找到一个和当前搜索的目标不同的值，就继续往下找。删除的话，采用惰性删除，只删除记号，实际操作等到rehash时再进行。
最坏情况下，哈希表退化成链表。
二次探测：发生冲突是，而是使用H+n^2的平方寻找可用的位置。

对于二次探测，假设表格大小为质数，负载因子为0.5，保持负载因子在0.5以下，超过0.5就rehash，可以保证插入每一个元素的探测次数不多于2。
二次探测本身所需的计算量其实和一次探测差不多。
rehash的时候，必须重新计算表中的每一个元素。

开链(seperate chaining)：在每一个表格中维护一个链表。表格的负载系数会大于1。

hashtable的桶

SGI使用开链法，表格（桶的集合）使用vector（为了动态扩容），而链表使用自定义的结构体。

SGI使用bkt_num()获得每个元素应该存放在哪个bucket中，这个函数负责调用hash function取得一个可以执行取模运算的值。为什么不直接使用hash_function，因为有些元素类型无法直接拿来对hashtable的大小进行模运算，这时候需要做一些转换。
开链法没有要求表格的大小为质数，但是SGI依然这么做了，并且准备了28个质数的表，并且提供一个函数去获取最接近并大于某个数的质数。
在创建一个hashtable对象时，首先要进行实例化，指明hashtable的各个模板参数，然后提供参数给构造函数（没有默认构造函数数）。其中有一个参数大小为n，表明要创建的hashtable的桶的个数（它会自动寻找一个接近n的质数）。
插入元素的时候，每插入一个就会判断是否需要resize。这个是一个很常用的操作，插入操作，首先判断需不要扩容，比如vector等。
扩容的原则：元素数量大于bucket的数量就resize。
复制和删除，删除的时候需要对bucket中每一个链表都删除。而复制的时候需要先把原有的给删除掉，然后保留和复制对象至少一样的空间。
hashtable的示例，在新版本的STL中，不能直接使用hashtable，unordered_set和unordered_map都是对hashtable的封装，调用构造函数时传入一个n是桶的数量，这个n必须指定（STL会自动改成比n大的最小质数）。

hash函数

STL定义了很多仿函数，都是模板。hash也是一个仿函数，返回size_t类型。对于char, int,等类型，通常就返回原值，而对字符串和string等设计了相应的转换函数，对于浮点数，怎么办，没有说，STL源码剖析的版本没有实现，但是cppreference上说有，应该是新增加的。

其他

unordered类容器和非ordered类容器最大的区别就是一个是默认有序，一个是默认无序。

树

二叉搜索树：任何节点的键值一定大于它的左子树中的所有节点，小于右子树中每一个节点的键值。
关联式容器的内部结构是平衡二叉树，平衡二叉树有AVL树，红黑树，AA树等。平衡的大概意思就是没有一个节点过深。

AVL树

确保整颗树的深度是logn，任何节点的左右子树高度最多相差1。
AVL利用单旋和双旋，可以将所有不平衡的情况转换为平衡的情况。
对于深度最深的节点X，造成节点X不平衡只有四种情况：
插入点在X的左子节点的左子树。
插入点在X的左子节点的右子树。
插入点在X的右子节点的左子树。
插入点在X的右子节点的右子树。
双旋第一步做完，第二步就是单旋了。

红黑树[17]

红黑树需要满足以下规则：

所有节点非红即黑。
根节点为黑色。
如果节点为红，子节点必须为黑。
任一节点到叶子节点的任何路径，所包含的黑色节点必须相同。

为什么有了AVL还要有红黑树。AVL的条件太苛刻了，基本上每次插入和删除都需要重新调整。这样子在插入和删除比较频繁的情况下代价太大了。就提出了AVL树，查找的时间复杂度也是logn的，但是它的平衡条件要比AVL树宽松一些，插入和删除时也不会像AVL那样频繁破坏规则。
查找的代价：最长路径长度不超过最短路径长度的2倍。
插入代价：插入节点最多只需要两次操作，和AVL一样，变色的时间复杂度是O(logN)。
删除代价：删除一个节点最多只需要旋转3次，但是变色操作的时间复杂度在O(logN)。

插入有四种情况：

父节点为黑色，直接插入一个红色节点就好了。
父节点为红色，这个时候，取决于叔节点的颜色。
- 叔节点为红色，这个时候还取决祖父节点的父节点的颜色。如果那个节点是黑，把新增加的节点和父节点（叔节点）交换一下就好了。如果那个节点是红色，还需要更改祖父节点的颜色。
- 叔节点为黑色，
- 叔节点为黑色，

一个有n个节点的红黑树的高度至多为2log(n+1)。

B树[18]

B树是对二叉树的推广，B树一般有一个阶数m，m阶代表每个树节点最多有m个查找路径，其实就是有多少个分叉，有m个分叉，最多就能存储m-1个数据。m=2时，就是二叉树，二叉树每个节点能分两叉，只能存1个数据。

如果根节点不是叶子节点，必须有两个叶节点，一个数据，也就是两个分叉。
每个非叶子节点的子节点数大于等于m/2的上界，小于m；每个节点的关键字个数必须大于m/2-1（这里除法是有小数的）的上界小于m-1，就是对应的分叉数-1。
所有的叶子节点都位于同一层，不包含关键字信息。

B+树[18]

B+树和B树的区别：

每个节点有n个子节点，n个关键字，而B树n个子节点有n-1个关键字。
还有就是根节点和叶子节点关键字和子节点的个数范围。
叶子节点包含全部关键字，所有非叶子节点都只起到了索引的作用。非叶子节点上有关键字，但是只用来索引，没有对应记录的存储地址。
非叶子节点中出现的关键字是会重复出现在叶子节点中的。

B+树的好处，扫库的时候直接顺序查找就好了，而B树需要中序遍历。B+树还支持区间查询，而B树不支持。
通常在B+树中有两个头指针，一个指向根节点，一个指向关键字最小的叶节点。所以支持顺序查找，也支持多路查找。

gcc和gdb[14]

gcc 常用选项：
-O编译器优化，Og最低等级的优化，On，数字越大优化等级越高。
-Wall发出所有警告
-g产生调试信息
-o指定输出文件。
-E只进行预处理
-S编译，就是产生汇编代码
-c之汇编，不链接，就是产生目标代码
-static禁止使用动态链接库，只链接静态库，编译后可独立执行，不需要动态库，但是得到的可执行目标文件比较大。
-L dir在库文件的搜索列表添加dir目录
-I dir在头文件的搜索列表添加dir目录
-shared

使用gdb调试时，需要使用使用gcc -g选项添加调试信息。

gdb program，
gdb program core，用gdb查看core dump文件
gdb program pid，用gdb查看已经开始运行的进程。

使用quit或者q退出。

gdb调试选项
help
run，开始调试程序
break，设置断点。
info break，查看断点信息。
watch，为一个表达式设置一个检视点，可以加上-l选项，当监视的变量改变时，就会自动打印。
catch,
list，打印源码展示出指定的函数或者行。
print，打印出表达式的值。
display，每次程序停止的时候打印出
bt，显示程序的调用栈信息。
framen，简要查看第n帧的信息。
info frame，详细查看当前帧的信息
info registers，查看寄存器
info args，查看当前帧的参数。
info locals，查看当前帧中的局部变量。
continue
step

移动(move)语义和右值引用[16]

移动语义，是为了避免无用的复制开销。右值引用的出现，让移动语义变得可能。将指针指向的内存直接拿过来使用。
Move semantics is a new way of moving resources around in an optimal way by avoiding unnecessary copies of temporary objects, based on rvalue references. In my opinion, the best way to understand what move semantics is about is to build a wrapper class around a dynamic resource (i.e. a dynamically allocated pointer) and keep track of it as it moves in and out functions. Keep in mind however that move semantics does not apply only to classes!

布隆过滤器

布隆过滤器，它可以用来判断一个东西一定不存在或者可能存在。

C++ 的异常安全性[28]

基本承诺。不破坏数据和资源泄露。比如说锁，使用析构函数。
强烈保证。如果异常被抛出，对象的状态保持不变。
不抛出异常保证。不抛出异常，比如vector的移动构造函数。

可执行文件的执行过程

[30]

参考文献