探索STL底层机制

问：内存泄露是什么意思？如何检测与避免内存泄漏？（提问概率：★★★★）

指由于疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，导致在释放该段内存之前就失去了对该段内存的控制，从而造成了内存的浪费

检测:windows可以使用crtdumpmemoryleaks替换free为freedebug还可以使用crtmemcheckpoint结合difference比较。

避免:智能指针，如ue垃圾回收机制。

参考书籍与资料：C/C++内存泄漏及检测

https://www.cnblogs.com/skynet/archive/2011/02/20/1959162.html

请你回答一下如何判断内存泄漏？

参考回答：
内存泄漏通常是由于调用了malloc/new等内存申请的操作，但是缺少了对应的free/delete。为了判断内存是否泄露，我们一方面可以使用linux环境下的内存泄漏检查工具Valgrind,另一方面我们在写代码时可以添加内存申请和释放的统计功能，统计当前申请和释放的内存是否一致，以此来判断内存是否泄露。

问：成员函数调用delete this会发生什么？之后再进行读写会怎么样？（提问概率：★★★★）

在类的成员函数中能不能调用delete this？答案是肯定的，能调用，而且很多老一点的库都有这种代码。假设这个成员函数名字叫release，而delete this就在这个release方法中被调用，那么这个对象在调用release方法后，还能进行其他操作，如调用该对象的其他方法么？答案仍然是肯定的，调用release之后还能调用其他的方法，但是有个前提：被调用的方法不涉及这个对象的数据成员和虚函数。

如果这时候调用普通的成员函数应该没有问题，因为这些成员函数与普通函数区别不大也在代码段，也需要走函数栈的逻辑。

如果调用虚函数，那就需要获取类内存的虚函数指针，这就涉及到堆内存的操作了，因为这时候虚函数指针也会被设置成未初始化的值，会有问题。

如果操作非指针成员变量，可能读和写都没有问题。

如果操作指针成员变量，指针可能设置成未初始化的值，很可能指向不合法的地方，强制赋值可能会导致崩溃

简单来说就是不要再去操作他的内存数据，否则很有可能崩溃，因为释放后，这个内存不确定系统如何处理。

另外，delete this会去调用本对象的析构函数，而析构函数中又调用delete this，形成无限递归，造成堆栈溢出，系统崩溃。

参考书籍与资料：what will happen if you do “deletethis;” in a member function?

https://stackoverflow.com/questions/7039597/what-will-happen-if-you-do-delete-this-in-a-member-function

在类的成员函数中调用delete this

http://blog.sina.com.cn/s/blog_4b4cf2af0100ywgv.html

STL相关

问：vector的实现与增长（提问概率：★★★★★）

vector是stl提供的动态数组，想了解他就要从他的特性开始分析。首先，他是一个模板类，意味着可以存放各种类型的元素，同时他也是一个数组，存储是连续的。 里面保存了三个指针，分别指向头、数据尾、数组尾。

内存分配:常规的数组必须在定义的时候就分配好固定的大小，而vector可以动态的改变，也就说明他可以动态的申请与释放内存。我们要知道，频繁的申请与释放内存对程序的效率影响是非常大的，因为如果当前地址空间不够用的话，就需要重新找一块更大的空间来装数据，再把数据全部都拷贝过去。所以vector为了达到比较好的效果，在添加元素的时候会多申请一定大小的内存，从而减少内存分配的次数。capacity()返回的就是包括缓冲区在内的空间大小，而size()返回的就是当前实际使用的空间大小。如果想主动的提前分配内存，可以使用reserve(n)，会强制重新分配一次内存，超出实际使用的部分就会成为缓存区。如果想直接构造出长度为n的动态数组可以使用resize(n)，实际分配的空间肯定要比n大，不过如果n比当前size小的话，大于size的数据都会被清空，如果比capacity还大的话就会重新执行一次内存分配。

关于内存释放，如果只是简单的调用 clear()全部清空数据,erase()清空部分数据都只是单纯的清空里面的数据并不会释放掉。默认只会在调用vector的析构函数的时候才会真正释放空间，所以如果想强制释放那就新建一个空的vector，然后对这个vector使用swap讲内存交换，那么原来的vector就会释放，新的vector呢？

另外，由于涉及到模板，也就会涉及到迭代器，凡是重新申请过内存，插入删除数据的，迭代器都会失效，理解上也很容易就是指针可能指向的不是你原来的那个位置了。

参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS自己看，读起来比较吃力）

问：map的实现 unordered_map的原理；如果从空的table开始一直增加元素，会出现什么情况？（提问概率：★★★★★）

map分为有序map和无序map（unordered_map），实现的基本数据结构分别是红黑树与哈希表。(set同理)里面每一个元素是一个pair< const key_type,mapped_type >类型，注意key是const的，不可以修改。对于一个数据结构，常见的操作无非是查找，插入，删除。红黑树作为一种二叉搜索树，具有log(n)的查找效率，不过前提是数据具有足够的随机性。！！！

hashmap理想上则是具有常数平均时间的效率，或者说一次或几次就可以查到，当然如果数据量过大，散列表空间就不能和数据量保持1：1，这时候就要靠hash函数来处理数据，将数据尽可能的分散在不同的桶bucket里面。

sgi stl的hash使用的是开链操作来避免hash表空间过大又想保持一定效率的问题，开链就是在一个位置用链表来存储所有冲突项。其实hashmap里面常说的桶bucket就是vector数组的一个元素，每个桶里面的数据是以链表(开链)的形式存储，进一步来说这些操作与定义都是通过一个基本的数据结构hashtable来实现的，所有的无序关联容器都是。hashtable里面的hash函数就是常说的取模函数，根据存储数据key值(注意，是对key而不是value)对桶的长度取余数来存放。默认提供的hash函数无法处理常见内置类型以外的数据，如各种自定义类，其实string本身也算是特殊类型，但是语言内部可以转为const char*处理，他经过函数处理也会得到一个size类型（一般对字符串的哈希函数比较特别，参考各种字符串Hash函数比较）。

什么时候需要rehash？当你的桶里面的平均数量（Map大小/桶的数量）大于max(这个可以自己设置)，就需要rehash。也可以主动调用rehash(n),保证桶的数量大于n，注意n是桶的数量。改变桶的数量就相当于改变Vector的长度，如果超过vector的capacity就会调用Vector的扩容机制（但是实际上他每次hash的时候都会直接调用vector的reserve进行扩容）。

什么时候执行reserve（Java里好像是resize）？注意reserve与vector的reserve不一样，他的目的并不是扩容，而是希望当前哈希表里面可以容纳n个元素。如果n>桶的数量*负载因子的时候就会触发rehash，否则不会触发。rehash有可能进一步触发vector的扩容。参考下面的英文注释。

Request acapacity change Sets the number of buckets in the container

(bucket_count) to the most appropriate to contain at least n elements.

If n is greater than the current bucket_count multiplied by the

max_load_factor, the container’s bucket_count is increased and a

rehash is forced. If n is lower than that, the function may have no

effect.

不过我发现 VC的STL里面的处理方式好像不太一样，他是自动先检测是否满足当前负载因子>最大负载因子，满足就会先触发重新设置桶的数量，如果桶的数量小于512就直接乘以8，否则如果小于Vector容量的一半的话就乘以2。这个过程我们看到他直接设置桶的数量并没有调用rehash函数，如果是主动调用rehash的话是直接翻倍的。而且不论是手动还是自动调整桶的数量，他都会触发Vector的扩容函数。

//手动调用：重新分配桶的数量

void rehash(size_type _Buckets)

{ // rebuild table with at least _Bucketsbuckets

size_type _Maxsize = _Vec.max_size() / 4;

size_type _Newsize = _Min_buckets;

for (; _Newsize < _Buckets && _Newsize <_maxsize>

_Newsize *= 2; // doubleuntil big enough

if (_Newsize< _Buckets)

_Xout_of_range("invalid hash bucket count");

while (!(size() / max_load_factor() < _Newsize)

&& _Newsize < _Maxsize)

_Newsize *= 2; // doubleuntil load factor okay

_Init(_Newsize);

_Reinsert();

}

//自动检查：设置桶的数量

void _Check_size()

{ // grow table as needed

if(max_load_factor() < load_factor())

{ // rehash to bigger table

size_type _Newsize = bucket_count();

if (_Newsize <512)

_Newsize *= 8; //multiply by 8

elseif (_Newsize <_vec.max_size>

_Newsize *= 2; //multiply safely by 2

_Init(_Newsize);

_Reinsert();

}

}

//重新分配桶的数量，同时进行扩容

void _Init(size_type _Buckets = _Min_buckets)

{ // initialize hash table with _Bucketsbuckets, leave list alone

_Vec.reserve(2 * _Buckets); // avoidcurdling _Vec if exception occurs

_Vec.assign(2 * _Buckets, _Unchecked_end());

_Mask = _Buckets - 1;

//赋值_Maxidx，重新设置桶的数量

_Maxidx = _Buckets;

}

参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）

std::map::erase http://www.cplusplus.com/reference/map/map/erase/

问：stl里deque是如何实现的？（提问概率：★★★）

其实deque由一段一段内存构成的，他是分段连续,而不是内存连续。当走向段的尾端时候自动跳到下一段。map记录着一系列的固定长度的数组的地址，这个map仅仅保存的是数组的地址,真正的数据在数组中存放着。deque先从map中央间的位置(因为双向队列，前后都可以插入元素，前面需要留出一定的空间)找到一个数组地址，向该数组中放入数据，数组不够时继续在map中找空闲的数组来存数据。当map也不够时重新分配内存当作新的map,把原来map中的内容copy的新map中。所以使用deque的复杂度要大于vector，尽量使用vector。（图片来自网络，侵删）

参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）

问：stl里heap与priority_queue？（提问概率：★★）

heap是基于vector来实现的，不过他不属于容器组件，因为他的主要是为优先级队列priority_queue的实现提供基础结构。所谓的优先级队列，其实就是队首元素一定是当前队列中优先级最高的那一个，只能通过 top() 函数来访问队首元素。我们知道最大堆与最小堆拥有这种特性，所以很适合用来实现priority_queue，当然其他数据结构也可以实现，不过从实现复杂度与计算复杂度等方面heap最为合适。

参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）

std::priority_queue https://en.cppreference.com/w/cpp/container/priority_queue

问：stl里面各个容器的基础数据结构是？（提问概率：★★★★）

图截自STL源码分析一书，常问的是优先级队列，hashmap，map底层的数据结构是什么。答案分别是Vector，hashtable以及RB—tree（红黑树），具体细节大家可以仔细看一下关于容器的这两章内容。

参考书籍与资料：“STL源码”，《STL源码剖析》

问：std::shared_ptr的实现，reference count在哪里定义（提问概率：★★★）

shared_ptr作为一种智能指针，本质上一个模板类，表现上与指针相同，是因为重载了&以及*这两个运算符（当然还有=等运算符）。由于其本身的计数机制，防止资源泄露上面很有意义。

Shareptr在实现上有两个核心的成员，一个是指向资源对象的指针变量，另一个是指向引用计数的指针变量。第一个参数不言而喻，第二个参数为什么也是指针？因为多个shared_ptr对象指向同一资源时，其中一个shared_ptr对象析构了count = count -1,是不会影响到其他shared_ptr对象的，所以使用指针可以达到多个shared_ptr对象指向同一资源的能够共享count目的。另外，原生的shared_ptr的读写在多线程当中是不安全的，因为读写不具有原子性，所以多线程使用shared_ptr一定要加锁。循环引用会造成内存泄露。

参考书籍与资料：

std::shared_ptr

https://en.cppreference.com/w/cpp/memory/shared_ptr

为什么多线程读写 shared_ptr 要加锁？

https://blog.csdn.net/solstice/article/details/8547547

问：new expression,operator new和malloc的联系（提问概率：★★★★）

malloc：是从C语言移植过来的语义，表示申请一定大小的内存并返回void*指针，在堆上申请内存，申请失败会返回Null

new：C++里的关键字，针对对象而言，申请一块内存的然后并在内存上构造对应的对象，最后返回该对象的指针。深入：new是从自由存储区分配的内存，自由存储区可能不在堆上，在静态存储区（全局变量做的对象池）。申请失败会抛出异常。可以通过new[]对数组进行内存申请与构造

Operator new：C++里面与Malloc类似的语义，只申请内存而不构造对象

New操作的第一步就是调用OperatorNew来执行内存的申请。深入：operator new可以基于malloc实现，一般也都是这么做的，可以被重载

参考书籍与资料： 《C++ Primer》《The Design and Evolution of C++》（C++语言的设计与演化）

http://blog.csdn.net/wudaijun/article/details/9273339

http://blog.jobbole.com/102002/#article-comment

请你说一说C++ STL 的内存优化

参考回答：

1）二级配置器结构
STL内存管理使用二级内存配置器。
1、第一级配置器
第一级配置器以malloc()，free()，realloc()等C函数执行实际的内存配置、释放、重新配置等操作，并且能在内存需求不被满足的时候，调用一个指定的函数。
一级空间配置器分配的是大于128字节的空间
如果分配不成功，调用句柄释放一部分内存
如果还不能分配成功，抛出异常
2、第二级配置器
在STL的第二级配置器中多了一些机制，避免太多小区块造成的内存碎片，小额区块带来的不仅是内存碎片，配置时还有额外的负担。区块越小，额外负担所占比例就越大。
3、分配原则

1、空间配置函数allocate
首先先要检查申请空间的大小，如果大于128字节就调用第一级配置器，小于128字节就检查对应的空闲链表，如果该空闲链表中有可用数据块，则直接拿来用（拿取空闲链表中的第一个可用数据块，然后把该空闲链表的地址设置为该数据块指向的下一个地址），如果没有可用数据块，则调用refill重新填充空间。
2、空间释放函数deallocate
首先先要检查释放数据块的大小，如果大于128字节就调用第一级配置器，小于128字节则根据数据块的大小来判断回收后的空间会被插入到哪个空闲链表。
3、重新填充空闲链表refill
在用allocate配置空间时，如果空闲链表中没有可用数据块，就会调用refill来重新填充空间，新的空间取自内存池。缺省取20个数据块，如果内存池空间不足，那么能取多少个节点就取多少个。
从内存池取空间给空闲链表用是chunk_alloc的工作，首先根据end_free-start_free来判断内存池中的剩余空间是否足以调出nobjs个大小为size的数据块出去，如果内存连一个数据块的空间都无法供应，需要用malloc取堆中申请内存。
假如山穷水尽，整个系统的堆空间都不够用了，malloc失败，那么chunk_alloc会从空闲链表中找是否有大的数据块，然后将该数据块的空间分给内存池（这个数据块会从链表中去除）。

使用allocate向内存池请求size大小的内存空间，如果需要请求的内存大小大于128bytes，直接使用malloc。

如果需要的内存大小小于128bytes，allocate根据size找到最适合的自由链表。
a. 如果链表不为空，返回第一个node，链表头改为第二个node。
b. 如果链表为空，使用blockAlloc请求分配node。
x. 如果内存池中有大于一个node的空间，分配竟可能多的node(但是最多20个)，将一个node返回，其他的node添加到链表中。
y. 如果内存池只有一个node的空间，直接返回给用户。
z. 若果如果连一个node都没有，再次向操作系统请求分配内存。
①分配成功，再次进行b过程。
②分配失败，循环各个自由链表，寻找空间。
I. 找到空间，再次进行过程b。
II. 找不到空间，抛出异常。

用户调用deallocate释放内存空间，如果要求释放的内存空间大于128bytes，直接调用free。

否则按照其大小找到合适的自由链表，并将其插入。

请你介绍一下C++中的智能指针

参考回答：
智能指针主要用于管理在堆上分配的内存，它将普通的指针封装为一个栈对象。当栈对象的生存周期结束后，会在析构函数中释放掉申请的内存，从而防止内存泄漏。C++ 11中最常用的智能指针类型为shared_ptr,它采用引用计数的方法，记录当前内存资源被多少个智能指针引用。该引用计数的内存在堆上分配。当新增一个时引用计数加1，当过期时引用计数减一。只有引用计数为0时，智能指针才会自动释放引用的内存资源。对shared_ptr进行初始化时不能将一个普通指针直接赋值给智能指针，因为一个是指针，一个是类。可以通过make_shared函数或者通过构造函数传入普通指针。并可以通过get函数获得普通指针。

请你回答一下智能指针有没有内存泄露的情况

参考回答：
当两个对象相互使用一个shared_ptr成员变量指向对方，会造成循环引用，使引用计数失效，从而导致内存泄漏。例如：

请你来说一下智能指针的内存泄漏如何解决

参考回答：
为了解决循环引用导致的内存泄漏，引入了weak_ptr弱指针，weak_ptr的构造函数不会修改引用计数的值，从而不会对对象的内存进行管理，其类似一个普通指针，但不指向引用计数的共享内存，但是其可以检测到所管理的对象是否已经被释放，从而避免非法访问。

问：memory alignmentand padding, 内存对齐的原理与意义（提问概率：★★★★）

结构体以及类成员对齐，意义就是减少cpu读取的次数，提高效率。比如一个int变量长度为4个字节，cpu一次读4个字节，当然是一次读取比较好。但是如果前面有一个char，地址为0-1。那么这个int的地址就为1-4。导致cpu，分两次读取int值。

具体的对齐规则，要说的非常准确可能比较麻烦，简单来讲就是，每个变量看后面的变量，如果后面的变量大，就和后面的大小对齐并补充字节。最后一个变量，按照成员内最大的对齐值，对齐并补充字节。

参考书籍与资料：

对内存对齐的深一步理解

https://www.cnblogs.com/coding-my-life/p/5374562.html

５分钟搞定内存字节对齐

https://blog.csdn.net/hairetz/article/details/4084088

内存对齐与内存分配原则

https://blog.csdn.net/tingyun_say/article/details/51443803

问：类的内存布局是什么样的？考虑有虚函数、多继承、虚继承几种情况。（提问概率：★★★★★）

简单总结一下就是类只有成员变量占用内存（静态成员不占类内部内存，函数不占内存）。如果有虚函数，每个类对象都会有一个虚函数指针Vptr（占用一个指针大小的内存），vptr指向一个虚函数表，表里面记录了各项标记virtual的函数，子类如果覆盖父类虚函数，对应虚表位置的虚函数会被子类的替换（虚表在运行时其位置与大小就被决定了，一个类只有一个虚表）

https://www.cnblogs.com/demian/p/6538301.html，侵删

单继承GrandChild->Child-> Parent

多继承Derive->Base1Derive->Base2; Derive->Base1

多继承菱形继承D->Base1 D->Base2;Base1->B; Base2->B

多继承菱形虚继承D->Base1 D->Base2;Base1->B; Base2->B

参考书籍与资料：《The Design and Evolution of C++》（C++语言的设计与演化）《Inside the C++ Object Model》（深度探索C++对象模型）

虚继承及继承的内存布局

https://www.cnblogs.com/demian/p/6538301.html

问：vector的实现与增长（提问概率：★★★★★）

vector是stl提供的动态数组，想了解他就要从他的特性开始分析。首先，他是一个模板类，意味着可以存放各种类型的元素，同时他也是一个数组，存储是连续的。 里面保存了三个指针，分别指向头、数据尾、数组尾。

内存分配:常规的数组必须在定义的时候就分配好固定的大小，而vector可以动态的改变，也就说明他可以动态的申请与释放内存。我们要知道，频繁的申请与释放内存对程序的效率影响是非常大的，因为如果当前地址空间不够用的话，就需要重新找一块更大的空间来装数据，再把数据全部都拷贝过去。所以vector为了达到比较好的效果，在添加元素的时候会多申请一定大小的内存，从而减少内存分配的次数。capacity()返回的就是包括缓冲区在内的空间大小，而size()返回的就是当前实际使用的空间大小。如果想主动的提前分配内存，可以使用reserve(n)，会强制重新分配一次内存，超出实际使用的部分就会成为缓存区。如果想直接构造出长度为n的动态数组可以使用resize(n)，实际分配的空间肯定要比n大，不过如果n比当前size小的话，大于size的数据都会被清空，如果比capacity还大的话就会重新执行一次内存分配。

关于内存释放，如果只是简单的调用 clear()全部清空数据,erase()清空部分数据都只是单纯的清空里面的数据并不会释放掉。默认只会在调用vector的析构函数的时候才会真正释放空间，所以如果想强制释放那就新建一个空的vector，然后对这个vector使用swap讲内存交换，那么原来的vector就会释放，新的vector呢？

另外，由于涉及到模板，也就会涉及到迭代器，凡是重新申请过内存，插入删除数据的，迭代器都会失效，理解上也很容易就是指针可能指向的不是你原来的那个位置了。

参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS自己看，读起来比较吃力）

问：map的实现 unordered_map的原理；如果从空的table开始一直增加元素，会出现什么情况？（提问概率：★★★★★）

map分为有序map和无序map（unordered_map），实现的基本数据结构分别是红黑树与哈希表。(set同理)里面每一个元素是一个pair< const key_type,mapped_type >类型，注意key是const的，不可以修改。对于一个数据结构，常见的操作无非是查找，插入，删除。红黑树作为一种二叉搜索树，具有log(n)的查找效率，不过前提是数据具有足够的随机性。！！！

hashmap理想上则是具有常数平均时间的效率，或者说一次或几次就可以查到，当然如果数据量过大，散列表空间就不能和数据量保持1：1，这时候就要靠hash函数来处理数据，将数据尽可能的分散在不同的桶bucket里面。

sgi stl的hash使用的是开链操作来避免hash表空间过大又想保持一定效率的问题，开链就是在一个位置用链表来存储所有冲突项。其实hashmap里面常说的桶bucket就是vector数组的一个元素，每个桶里面的数据是以链表(开链)的形式存储，进一步来说这些操作与定义都是通过一个基本的数据结构hashtable来实现的，所有的无序关联容器都是。hashtable里面的hash函数就是常说的取模函数，根据存储数据key值(注意，是对key而不是value)对桶的长度取余数来存放。默认提供的hash函数无法处理常见内置类型以外的数据，如各种自定义类，其实string本身也算是特殊类型，但是语言内部可以转为const char*处理，他经过函数处理也会得到一个size类型（一般对字符串的哈希函数比较特别，参考各种字符串Hash函数比较）。

什么时候需要rehash？当你的桶里面的平均数量（Map大小/桶的数量）大于max(这个可以自己设置)，就需要rehash。也可以主动调用rehash(n),保证桶的数量大于n，注意n是桶的数量。改变桶的数量就相当于改变Vector的长度，如果超过vector的capacity就会调用Vector的扩容机制（但是实际上他每次hash的时候都会直接调用vector的reserve进行扩容）。

什么时候执行reserve（Java里好像是resize）？注意reserve与vector的reserve不一样，他的目的并不是扩容，而是希望当前哈希表里面可以容纳n个元素。如果n>桶的数量*负载因子的时候就会触发rehash，否则不会触发。rehash有可能进一步触发vector的扩容。参考下面的英文注释。

Request acapacity change Sets the number of buckets in the container

(bucket_count) to the most appropriate to contain at least n elements.

If n is greater than the current bucket_count multiplied by the

max_load_factor, the container’s bucket_count is increased and a

rehash is forced. If n is lower than that, the function may have no

effect.

不过我发现 VC的STL里面的处理方式好像不太一样，他是自动先检测是否满足当前负载因子>最大负载因子，满足就会先触发重新设置桶的数量，如果桶的数量小于512就直接乘以8，否则如果小于Vector容量的一半的话就乘以2。这个过程我们看到他直接设置桶的数量并没有调用rehash函数，如果是主动调用rehash的话是直接翻倍的。而且不论是手动还是自动调整桶的数量，他都会触发Vector的扩容函数。

//手动调用：重新分配桶的数量

void rehash(size_type _Buckets)

{ // rebuild table with at least _Bucketsbuckets

size_type _Maxsize = _Vec.max_size() / 4;

size_type _Newsize = _Min_buckets;

for (; _Newsize < _Buckets && _Newsize <_maxsize>

_Newsize *= 2; // doubleuntil big enough

if (_Newsize< _Buckets)

_Xout_of_range("invalid hash bucket count");

while (!(size() / max_load_factor() < _Newsize)

&& _Newsize < _Maxsize)

_Newsize *= 2; // doubleuntil load factor okay

_Init(_Newsize);

_Reinsert();

}

//自动检查：设置桶的数量

void _Check_size()

{ // grow table as needed

if(max_load_factor() < load_factor())

{ // rehash to bigger table

size_type _Newsize = bucket_count();

if (_Newsize <512)

_Newsize *= 8; //multiply by 8

elseif (_Newsize <_vec.max_size>

_Newsize *= 2; //multiply safely by 2

_Init(_Newsize);

_Reinsert();

}

}

//重新分配桶的数量，同时进行扩容

void _Init(size_type _Buckets = _Min_buckets)

{ // initialize hash table with _Bucketsbuckets, leave list alone

_Vec.reserve(2 * _Buckets); // avoidcurdling _Vec if exception occurs

_Vec.assign(2 * _Buckets, _Unchecked_end());

_Mask = _Buckets - 1;

//赋值_Maxidx，重新设置桶的数量

_Maxidx = _Buckets;

}

参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）

std::map::erase http://www.cplusplus.com/reference/map/map/erase/

问：stl里面各个容器的基础数据结构是？（提问概率：★★★★）

图截自STL源码分析一书，常问的是优先级队列，hashmap，map底层的数据结构是什么。答案分别是Vector，hashtable以及RB—tree（红黑树），具体细节大家可以仔细看一下关于容器的这两章内容。

请你回答一下STL里resize和reserve的区别

参考回答：
resize()：改变当前容器内含有元素的数量(size())，eg: vectorv; v.resize(len);v的size变为len,如果原来v的size小于len，那么容器新增（len-size）个元素，元素的值为默认为0.当v.push_back(3);之后，则是3是放在了v的末尾，即下标为len，此时容器是size为len+1；
reserve()：改变当前容器的最大容量（capacity）,它不会生成元素，只是确定这个容器允许放入多少对象，如果reserve(len)的值大于当前的capacity()，那么会重新分配一块能存len个对象的空间，然后把之前v.size()个对象通过copy construtor复制过来，销毁之前的内存；
测试代码如下：

#include <iostream>
#include <vector>
using namespace std;
int main() {
vector a;
a.reserve(100);
a.resize(50);
cout<<a.size> //50 100
a.resize(150);
cout<<a.size> //150 200
a.reserve(50);
cout<<a.size> //150 200
a.resize(50);
cout<<a.size> //50 200
}/<vector>/<iostream>

请你来说一下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应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

请你来介绍一下STL的allocaotr

参考回答：STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中，其内存配置和释放如下：new运算分两个阶段：(1)调用::operator new配置内存;(2)调用对象构造函数构造对象内容

delete运算分两个阶段：(1)调用对象希构函数；(2)掉员工::operator delete释放内存

为了精密分工，STL allocator将两个阶段操作区分开来：内存配置有alloc::allocate()负责，内存释放由alloc::deallocate()负责；对象构造由::construct()负责，对象析构由::destroy()负责。

同时为了提升内存管理的效率，减少申请小内存造成的内存碎片问题，SGI STL采用了两级配置器，当分配的空间大小超过128B时，会使用第一级空间配置器；当分配的空间大小小于128B时，将使用第二级空间配置器。第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放，而第二级空间配置器采用了内存池技术，通过空闲链表来管理内存。

请你来说一说STL迭代器删除元素

参考回答：这个主要考察的是迭代器失效的问题。1.对于序列容器vector,deque来说，使用erase(itertor)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器；2.对于关联容器map set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。3.对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。

閱讀更多 技匠志 的文章

關鍵字: Windows 设计 泄漏