《STL源码剖析》常见问题总结

《STL源码剖析》在学习完了之后也总结完了，但是感觉还是有些不太明白的地方，查了一些资料，总结了一下别人面试常遇到的问题，算是复习巩固，也是为了之后的找工作准备。

一、关于容器的一些问题

1、当vector的内存用完了，它是如何动态扩展内存的？它是怎么释放内存的？用clear可以释放掉内存吗？是不是线程安全的？

如果vector内存用完了，会以当前size大小重新申请2*size的内存，然后把原来的元素复制过去，把新元素插上，然后释放原来的内存。

一般我们释放vector里的元素使用clear，其实它不能释放内存，要想释放内存要使用swap，这样，但其实这些内存也只是放到内存池，并不能被外部使用。

vector<type> v;
//.... 这里添加许多元素给v
//.... 这里删除v中的许多元素
vector<type>(v).swap(v);
//此时v的容量已经尽可能的符合其当前包含的元素数量
//对于string则可能像下面这样
string(s).swap(s);

关于线程安全，引用《effective stl》的第十二条：当涉及 STL容器和线程安全性时，你可以指望一个 STL库允许多个线程同时读一个容器，以及多个线程对不同的容器做写入操作。你不能指望 STL库会把你从手工同步控制中解脱出来，而且你不能依赖于任何线程支持。必须自己去写多线程安全措施。

2、写多读少应该用什么容器？

关于容器的使用，可以总结以下几条规律：

（1）如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；
（2）如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；
（3）如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；
（4）如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；
（5）如果打算查找一个元素是否存在于某集合中并且有序，唯一存在的情况使用set，不唯一存在的情况使用multiset。

这里应该选用链表，链表的插入操作时常数时间复杂度，访问操作是O(n)，是最适合写多读少的容器。

3、vector每次insert或erase之后，以前保存的iterator会不会失效？

理论上会失效，理论上每次insert或者erase之后，所有的迭代器就重新计算的，所以都可以看作会失效，原则上是不能使用过期的内存，实际是否失效，需要分情况讨论：

（1） insert时，假设insert位置在p，分两种情况：

(a) 容器还有空余空间，不重新分配内存，那么p之前的迭代器都有效，p之后的迭代器都失效
(b) 容器重新分配了内存，那么所有的迭代器都无效。

（2） erase时，假设erase位置在p，则p之前的迭代器都有效并且p指向下一个元素位置（如果之前p在尾巴上，则p指向无效尾end），p之后的迭代器都无效。

4、 auto_ptr可以做vector的元素呢？为什么？

不能。因为STL的标准容器规定它所容纳的元素必须是可以拷贝构造和可被转移赋值的。而auto_ptr不能，可以用shared_ptr智能指针代替。

5、为何map和set的插入删除效率比用其他序列容器高？

map和set容器的底层都是由RB-tree实现，各个节点间相互独立，由指针将其组织起来形成树结构。因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了；删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

6、为何map和set不能像vector一样有个reserve函数来预分配数据？

map和set内部存储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的Alloc并不是map声明的时候从参数中传入的Alloc。例如：

1	map<int, Alloc> intmap;

这时候在intmap中使用的allocator并不是Alloc, 而是通过了转换的Alloc，具体转换的方法时在内部通过
Alloc::rebind重新定义了新的节点分配器，详细的实现参看彻底学习STL中的Allocator。
其实你就记住一点，在map和set里面的分配器已经发生了变化，reserve方法你就不要奢望了。

7、当数据元素增多时（10000和20000个比较），map和set的插入和搜索速度变化如何？

算一下就知道了，首先你得知道map和set的底层都是红黑树，红黑树的搜索近似于二分查找，二分查找呢，平均时间复杂度是O(log2n),这里简写成logn:

1 2	log(10000) = 13.3 log(20000) = 14.3

可以看到，当数据量增大一倍的时候，搜索次数只不过多了1次,增长速度很慢。

8、为何map和set中每次insert之后，以前保存的iterator不会失效？

map和set中iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。

相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

9、map是怎么实现的？查找的复杂度是多少？能不能边遍历边删除？

map用红黑实现。
用红黑树的效率为O(logn)
map不可以边遍历边插入，map不像vector，它在对容器执行erase操作后不会返回后一个元素的迭代器，所以不能遍历地往后删除。

10、 hash_map和map的区别在哪里？

hash_map底层是散列的所以理论上操作的平均复杂度是常数时间，map底层是红黑树，理论上平均复杂度是O(logn)。

选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。如果查询次数比较少看中单个效率，那么更偏向于选择map，这是因为map的每一次查询时间基本稳定，此时如果用hash_map可能会因为碰撞而导致O(N)的时间复杂度。如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。

二、关于迭代器的一些问题

1、 traits技术原理及应用

traits技术原理主要为：模板参数推导机制+内嵌类型定义+模板偏特化。

在STL算法中用到迭代器时，会用到迭代器所指之物的型别，假设算法要设定返回值类型，以迭代器所指之物为型别，但是C++只支持sizeof()、并未
支持typeof()，即使typeid()，也只能获得型别名称，不能拿来声明变量，所以这里就要用到作为”特性萃取机“的traits技术。为了解决原生指针问题，引入了萃取层模板偏特化。

三、关于算法的一些问题

1、快排算法的枢轴位置是怎么选择的？

三点中值法，取整个序列的头、尾、中央三个位置的元素，以其中值作为枢轴。函数栈达到一定层数后会选择插入排序避免递归过多。

2、简单说一下next_permutation和partition的实现？

（1）next_permutation（下一个排列）
首先，从最尾端开始往前寻找两个相邻元素，另第一个元素为i，第二个元素为ii，且满足i<ii。找到这样一组相邻元素后，再从尾端开始往前检验，找出第一个大于i的元素j，将i，j元素对调，再将ii之后的所有元素颠倒排列。此即所求“下一个”排列组合。
（2）partition
令头端迭代器first向尾部移动，尾部迭代器last向头部移动。当first所指的值大于或等于枢轴时就停下来，当last所指的值小于或等于枢轴时也停下来，然后检验两个迭代器是否交错。如果first仍然在last左边，就将连着元素互换，然后各自调整一个位置（向中央逼近），再继续进行相同的行为。如果发现两个迭代器交错了，表示整个序列已经调整完毕。

四、关于内存配置的一些问题

1、stl对于小内存块请求与释放怎么处理的？

STL考虑到小型内存区块的碎片问题，设计了双层级配置器，第一级配置直接使用malloc()和free()；第二级配置器则视情况采用不同的策略，当配置区大于128bytes时，直接调用第一级配置器；当配置区块小于128bytes时，便不借助第一级配置器，而使用一个memory pool来实现。究竟是使用第一级配置器还是第二级配置器，由一个宏定义来控制。SGI STL中默认使用第二级配置器。

二级配置器会将任何小额区块的内存需求量上调至8的倍数，并且在它内部会维护16个free-list，各自管理大小分别为8， 16，24，…，128bytes的小额区块，这样当有小额内存配置需求时，直接从对应的free list中拔出对应大小的内存(8的倍数)；当客户端归还内存时，将根据归还内存块的大小，将需要归还的内存插入到对应free list的最顶端。

有点主要体现在：

1）小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后，对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作，相比于直接调用malloc/free，开销小。
2）避免内存碎片的产生。零乱的内存碎片不仅会浪费内存空间，而且会给OS的内存管理造成压力。
3）尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时，分配算法会将其链入到对应的空闲列表中，然后会尝试从空闲列表中寻找是否有合适大小的区域，

但是，这种内存分配器局限于STL容器中使用，并不适合一个通用的内存分配。因为它要求在释放一个内存块时，必须提供这个内存块的大小，以便确定回收到哪个free list中，而STL容器是知道它所需分配的对象大小的，比如上述：

1	stl::vector array;

array是知道它需要分配的对象大小为sizeof(int)。一个通用的内存分配器是不需要知道待释放内存的大小的，类似于free(p)。