内存分配

  1. 静态存储区域分配。内存在程序编译时就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量、static 变量。

  2. 在栈上创建。执行函数时，函数内部的局部变量的存储单元都可以在栈上床创建，函数执行结束后这些存储单元自动被释放。栈内存分配运算内置于 CPU 的指令集中，效率很高，但是分配的内容容量很有限。

  3. 在堆上分配。亦称为动态内存分配。程序在运行的过程中用 malloc 或 new 申请任意多少的内存，程序员自己负责何时用 free 或者 delete 释放内存。动态内存的生存期由我们决定，使用非常灵活，但是问题也最多。

C++运行时各类型内存分配(堆、栈、静态区、数据段、BSS、ELF)，BSS 段，sizeof 一个类可以求大小(字节对齐原则)

STL 原理及实现

STL 包含六大组件。分别是容器(Containers)、算法(Algorithms)、迭代器(iterators)、仿函数(functors)、配接器(adapters)、配置器(allocators)。

  1. 容器(Containers)。各种数据结构，如序列式容器vector、list、deque、关联式容器set、map、multiset、multimap 用来存放数据。从实现的角度来看，STL 容器是一种 class template。

  2. 算法(Algorithms)。各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL 算法是一种 function template。注意一个问题：任何的一个 STL 算法，都需要获得由一对迭代器所标示的区间，用来表示操作范围。这一对迭代器所标示的区间都是左闭右开区间，如[first, last)。

  3. 迭代器(iterators)。容器和算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将 operator*、operator->、operator++、operator–等指针相关操作进行重载的 class template。所有 STL 容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

  4. 仿函数(functors)。行为类似函数，可作为算法的某种策略(policy)。从实现的角度来看，仿函数是一种重载了 operator()的 class 或 class template。一般的函数指针也可以视为仿函数。

  5. 配接器(adapters)。一种用来修饰容器、仿函数、迭代器接口的东西。例如：STL 提供的 queue 和 stack，虽然看似容器，但其实只能算是一种容器配接器，因为它们的底部完全借助 deque，所有操作都有底层的 deque 供应。改变 functors 接口者，称为 function adapter；改变 container 接口者，称为 container adapter；改变 iterator 接口者，称为 iterator adapter。

  6. 配置器(allocators)。负责空间的配置和管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的 class template。

这六大组件的交互关系。container(容器)通过 allocator(配置器)取得数据存储空间，algorithm(算法)通过 iterator(迭代器)存取 container(容器)内容，functor(仿函数)可以协助 algorithm(算法)完成不同的策略变化，adapter(配接器)可以修饰或套接 functor(仿函数)。

序列式容器

vector-数组，元素不够时再重新分配内存，拷贝原来数组的元素到新分配的数组中。list-单链表。deque-分配中央控制器 map(并非 map 容器)，map 记录着一系列的固定长度的数组的地址。记住这个 map 仅仅保存的是数组的地址，真正的数据在数组中存放着。duque 先从 map 中央的位置(因为是双端队列，前后都可以插入元素)找到一个数组地址，向该数组中存放数据，数组不够时继续在 map 中找空闲的数组来存放数据。当 map 也不够时重新分配内存当作新的 map，把原来 map 中的内容 copy 到新 map 中。所以使用 deque 的复杂度要大于 vector，尽量使用 vector。

stack-基于 deque。queue-基于 deque。heap-基于完全二叉树，使用最大堆排序，以数组(vector)的形式存放。priority_queue-基于 heap。slist-基于双向链表。

关联式容器

set、map、multiset、multimap-基于红黑树(RB-tree)，一种加上了额外平衡条件的二叉搜索树。

hash table-基于散列表。将待存的数据 key 经过映射函数变成一个数组(一般是 vector)的索引，例如数据的 key%数组的大小 = 数组的索引(一般文本通过算法也可以转换为数组)，然后将数据当作此索引的数组元素。有些数据的 key 经过算法的转换可能是同一个数组的索引值(碰撞问题，可以用线性探测，二次探测来解决)，STL 是用开链的方法来解决的，每一个数组维护一个 list，它把相同索引值的数据存入一个 list，当 list 比较短时执行删除、插入、搜索等算法比较快。

hash_map、hash_set、hash_multiset、hash_multimap-基于 hash table 实现。

list 和 vector 的区别

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

关键字

volatile

volatile 关键词第一个特性：易变性。所谓的易变性，在汇编层面反映出来，就是两条语句，下一条语句不会直接使用上一条语句对应的 volatile 变量的寄存器内容，而是重新从内存中读取。

volatile 关键词的第二个特性：“不可优化”特性。volatile 告诉编译器，不要对我这个变量进行激进的优化，甚至将变量直接消除，保证程序员写在代码中的指令，一定会被执行。

volatile 关键词的第三个特性：“顺序性”。能够保证 volatile 变量间的顺序性，编译器不会进行乱序优化。

C/C++ volatile 变量，与非 volatile 变量之间的操作，是可能被编译器交换顺序的。C/C++ volatile 变量间的操作，是不会被编译器交换顺序的。哪怕将所有的变量全部声明为 volatile，哪怕避免了编译器的乱序优化，但是针对生成的汇编代码，CPU 有可能仍旧会乱序执行指令，导致程序依赖的逻辑出错，volatile 对此无能为力。针对这种多线程的应用，真正正确的做法是，构建一个 happens-before 语义。

static

控制变量的存储方式和可见性。

修饰局部变量

一般情况下，对于局部变量是存放在栈区的，并且局部变量的生命周期在该语句块执行结束时便结束了。但是如果用 static 进行修饰的话，该变量便存放在静态数据区，其生命周期一直持续到整个程序执行结束。但是在这里要注意的是，虽然用 static 对局部变量进行修饰过后，其生命周期以及存储空间发生了变化，但是其作用域并没有改变，其仍然是一个局部变量，作用域仅限于当前语句块。

修饰全局变量

对于一个全局变量，它既可以在本源文件中被访问到，也可以在同一个工程的其他源文件中被访问到(只需要用 extern 进行声明即可)。用 static 对全局变量进行修饰改变了其作用域的范围，由原来的整个工程可见变为本源文件可见。

修饰函数

用 static 修饰函数的话，情况和修饰全局变量大同小异，就是改变了函数的作用域。

C++中的 static

如果在 C++中对类中的某个函数用 static 进行修饰，则表示该函数属于一个类而不是属于此类的任何特定对象；如果对类中的某个变量进行 static 修饰，表示该变量为类以及其所有的对象所有，它们在存储空间中都只存在一个副本，可以通过类和对象去调用。

const

const 名叫常量限定符，用来限定特定变量，以通知编译器该变量是不可修改的。习惯性的使用 const，可以避免在函数中对某些不应修改的变量造成可能的改动。

const 修饰基本数据类型

const 修饰一般常量及数组。const 修饰符可以用在类型说明符前，也可以用在类型说明符后，结果是一样的。只要在使用这些常量的时候，不改变这些常量就好。

const 修饰指针变量*以及引用变量&。如果 const 位于星号*左侧，则 const 就是用来修饰指针所指向的变量，即指针指向为常量；如果 const 位于星号*的右侧，const 就是修饰指针本身，即指针本身是常量。

const 应用到函数中

作为参数的 const 修饰符。调用函数的时候，用相应的变量初始化 const 常量，则在函数体中，按照 const 所修饰的部分进行常量化，保护了原对象的属性。注意：参数 const 通常用于参数为指针或引用的情况。

作为函数返回值的 const 修饰符。声明了返回值后，const 按照“修饰原则”进行修饰，起到相应的保护作用。

const 在类中的写法

不能在类声明中初始化 const 数据成员。正确的使用 const 实现方法为：const 数据成员的初始化只能在类构造函数的初始化表示中进行。类中的成员函数：A fun4()cosnt; 其意义上是不能修改所在类中的任何变量。

const 修饰类对象

const 修饰类的对象，定义常量对象。常量对象只能调用常量函数(用 const 修饰的函数)，别的成员函数都不能调用。

extern

在 C 语言中，修饰符 extern 用在变量或者函数的声明前，用来说明“此变量/函数是在别处定义的，要在此处引用“。

注意 extern 声明的位置对其作用域也有关系，如果是在 main 函数中进行声明的，则只能在 main 函数中调用，在其他函数中不能调用。其实要调用其他文件中的函数和变量，只需要把该文件用#include 包含进来即可，为啥要用 extern？因为 extern 会加速程序的编译，这样可以节省时间。

在 C++中 extern 还有另外一种作用，用于指示 C 或者 C++函数的调用规范。比如 C++中调用 C 库函数，就需要在 C++程序中用 extern “C“ 声明要引用的函数。这是给链接器用的，告诉链接器在链接的时候用 C 函数规范来链接。主要原因是 C++和 C 程序编译完成后在目标代码中命名规则不同，用此来解决名字匹配的问题。

虚函数

虚析构函数

一般情况下，类的析构函数里面都是释放内存资源，而析构函数不被调用的话就会造成内存泄漏。这样做是为了当用一个基类的指针删除一个派生类的对象时，派生类的析构函数会被调用。当然，并不是要把所有类的析构函数都写成虚函数。因为当类里面有虚函数的时候，编译器会被类添加一个虚函数表，里面用来存放需函数指针，这样就会增加类的存储空间。所以，只有当一个类被用来作为基类的时候，才把析构函数写成虚函数。

虚函数的作用和实现原理，什么是虚函数，有什么作用。

C++的多态分为静态多态(编译时多态)和动态多态(运行时多态)两大类。静态多态通过重载、模版来实现；动态多态就是通过虚函数来体现的。

虚函数实现原理：包括虚函数表、虚函数指针等。

虚函数的作用是：当调用一个虚函数时，被执行的代码必须和调用函数的对象的动态类型一致。编译器需要做的就是如何高效的实现提供这种特性。不同编译器实现细节也不相同。大多编译器通过 vtbl(virtual table)和 vptr(virtual table pointer)来实现的。当一个类声明了虚函数或者继承了虚函数，这个类就会有自己的 vtbl。vtbl 实际上就是一个函数指针数组，有的编译器用的是链表，不过方法都是差不多。vtbl 数组中的每一个元素对应一个函数指针指向该类的一个虚函数，同时该类的每一个对象都会包含一个 vptr，vptr 指向该 vtbl 的地址。

结论：每个声明了虚函数或者继承了虚函数的类，都会有一个自己的 vtbl，同时该类的每个对象都会包含一个 vptr 去指向该 vtbl，虚函数按照其声明顺序放于 vtbl 表中，vtbl 数组中的每一个元素对应一个函数指针指向该类的虚函数，如果子类覆盖了父类的虚函数，将被放到虚函数表中原来父类虚函数的位置。在多继承的情况下，每个父类都有自己的虚表。子类的成员函数被放到了第一个父类的表中。

为什么 C++里访问虚函数比访问普通函数要慢

单继承时性能差不多，多继承的时候慢。

调用性能方面

调用虚函数时过程如下：

通过对象的 vptr 找到类的 vtbl。这是一个简单的操作，因为编译器知道在对象内，哪里能找到 vptr(毕竟是由编译器放置的它们)。因此这个代价只是一个偏移调整(以得到 vptr)和一个指针的间接寻址(以得到 vtbl)。找到对应的 vtbl 内的指向被调用函数的指针。这也是很简单的，因为编译器为每个虚函数在 vtbl 内分配了一个唯一的索引。这步的代价只是在 vtbl 数组内的一个偏移。调用第二步找到的指针所指向的函数。

在单继承的情况下，调用虚函数所需的代价基本上和非虚函数效率一样，在大多数计算机上它只是多执行了很少的一些指令，所以有很多人一概而论说虚函数性能不行是不太科学的。

在多继承的情况下，由于会根据多个父类生成多个 vptr，在对象里为寻找 vptr 而进行的偏移量计算会变得复杂一些，但这些并不是虚函数的性能瓶颈。虚函数运行时所需的代价主要是虚函数不能是内联函数 inline。这也是非常好理解的，是因为内联函数是指在编译期间用被调用的函数体本身来代替函数调用的指令，但是虚函数的“虚”是指直到运行时才能知道要调用的是哪一个函数。但虚函数的运行时多态特性就是要在运行时才知道具体调用哪个虚函数，所以没法在编译时进行内联函数展开。当然如果通过对象直接调用虚函数，它是可以被内联，但是大多数虚函数是通过对象的指针或引用被调用的，这种调用不能被内联。因为这种调用是标准的调用方式，所以虚函数实际上不能被内联。

占用空间方面

简单来说就是虚标重复问题以及虚指针占用内存。

虚函数的一个代价就是会增加类的体积。在虚函数接口较少的类中这个代价并不明显，虚函数表 vtbl 的体积相当于几个函数指针的体积，如果你有大量的类或者在每个类中有大量的虚函数，你会发现 vtbl 会占用大量的地址空间。但这并不是主要的代价，主要的代价是发生在类的继承过程中，在上面的分析中，可以看到，当子类继承父类的虚函数时，子类会有自己的 vtbl，如果子类只覆盖父类的一两个虚函数接口，子类 vtbl 的其余部分内容会与父类重复。这在如果存在大量的子类继承，且重写父类的虚函数接口只占总数的一小部分的情况下，会造成大量地址空间浪费。在一些 GUI 库上这种大量子类继承自同一父类且只覆盖其中一两个虚函数的情况是经常有的，这样就导致 UI 库的占用内存明显变大。由于虚函数指针 vptr 的存在，虚函数也会增加该类的每个对象的体积。在单继承或者没有继承的情况下，类的每个对象会多一个 vptr 指针的体积，也就是 4 个字节；在多继承的情况下，类的每个对象会多 N 个(N = 包含虚函数的父类个数)vptr 的体积，也就是 4N 个字节。当一个类的对象体积较大时，这个代价并不是很明显，但当一个类的对象很轻量的时候，如成员变量只有 4 个字节，那么再加上 4(或 4N)个字节的 vptr，对象的体积相当于翻了 1(或 N)倍，这个代价是非常大的。

总结：

1:虚函数是动态绑定的，也就是说，使用虚函数的指针和引用能够正确找到实际类的对应函数，而不是执行定义类的函数。这就是虚函数的基本功能，就不再解释了。

2:构造函数不能是虚函数。而且，在构造函数中调用虚函数，实际执行的是父类的对应函数，因为自己还没有构造好，多态是被 disable 的。

3:析构函数可以是虚函数。而且，在一个复杂的类结构中，这往往是必须的。

4:将一个函数定义为纯虚函数，实际上是将这个类定义为抽象类，不能实例化对象。

5:纯虚函数通常没有定义体，但也完全可以拥有。

6:析构函数可以是纯虚的，但纯虚析构函数必须有定义体，因为析构函数的调用是在子类中隐含的。

7:非纯的虚函数必须有定义体，不然是一个错误。

8:派生类的 override 虚函数定义必须和父类完全一致。除了一个特例，如果父类中返回值是一个指针或者引用，子类 override 时可以返回这个指针(或引用)的派生。例如，在上面的例子中，在 Base 中定义了 virtual Base* clone()；在 Derived 中可以定义为 virtual Derived* clone()。可以看到，这种放松对于 Clone 模式是非常有用的。

抽象类是为了建立一个公共使用的类，将子类的公共操作抽象出来，然后子类们通过继承这个抽象基类，可以在它的基础上完成更加具体的实现。因此，这个抽象基类是不需要实现的，即纯虚函数 = 0 的形式就可以理解了。

基类本身就是提炼出子类一些公共的操作，但是已经实现了，子类就可以访问，不用自己在每个类中写一遍。抽象类本质上也是提炼出子类一些公共的操作，但是还没有实现，留给子类去实现，定义的函数叫做纯虚函数(没有函数体，不加花括号，直接=0)。如果一个类中两种都有，那么就是抽象基类。