STL总结与答疑
简介
STL是Standard Template Library的简称，中文名标准模板库。其提供了许多计算机科学的基础算法和数据结构。下面主要是收集一些网上以及自己在使用过程中关于STL的一些注意事项以及问题答疑总结
STL组成部分
1.容器：
容器是容纳、包含一组元素或元素集合的对象,主要分为两大类序列式容器和关联式容器
序列式容器：容器提供顺序访问、随机访问其中的元素
| 名称 | 说明 |
|---|---|
array |
c++内建 |
vector |
|
heap |
以算法形式呈现 |
priority_queue |
|
list |
|
slist |
非标准 |
deque |
|
stack |
配接器 |
queue |
配接器 |
关联式容器：通过优化关键值访问
| 名称 | 说明 |
|---|---|
RB-tree |
非公开 |
set |
|
map |
|
multiset |
|
multimap |
|
hashtable |
非标准 |
hash_set |
非标准 |
hash_map |
非标准 |
hash_multiset |
非标准 |
hash_multimap |
非标准 |
2.算法：
算法Algorithms，用来处理群集内的元素,它们可以出于不同的目的而搜寻、排序、修改、使用那些元素。通过迭代器的协助，我们可以只需编写一次算法，就可以将它应用于任意容器，这是因为所有的容器迭代器都提供一致的接口,常见算法如sort/search/copy/erase/next_permutation/partion等
3.迭代器：
扮演容器与算法之间的胶合剂，用来在一个对象群集的元素上进行遍历。这个对象群集或许是个容器，或许是容器的一部分。迭代器的主要好处是，为所有容器提供了一组很小的公共接口,每种容器都提供了自己的迭代器，而这些迭代器能够了解容器内部的数据结构
4. 容器配接器：
一种用来修饰容器或者仿函数或迭代器接口的东西。比如queue和stack，看着像容器，其实就是deque包了一层封装
5.仿函数：
行为类似函数，可作为算法的某种策略（Policy）,从实现的角度来看，仿函数是一种重载了Operator()的Class 或 Class Template。一般函数指针可视为狭义的仿函数
6.空间配置器：
负责空间配置与管理,是一个实现了动态空间配置、空间管理、空间释放的class template
STL使用总结与注意事项
vector的底层机制
vector就是一个动态数组,里面有一个指针指向一片连续的内存空间,当空间不够装下数据时,会自动申请一份双倍于当前容量的空间,然后把原来的数据拷贝过去,接着释放原来的那片空间,当释放或者删除里面的数据时,其存储空间不释放,仅仅是清空了里面的数据。对vector的任何操作,一旦硬气空间重新配置,指向原vector的所有迭代器都失效
list的底层机制
以节点为单位存储数据,结点的地址在内存中不一定连续,每次插入或者删除一个元素,就配置或者释放一个元素空间
什么情况下用vector,什么情况下使用list
vector可以随机存储元素,但是非尾部插入删除数据时效率很低,适合对象简单、对象数量变化不大、随机访问频繁的场景
list不支持随机存储访问,适用于对象大、对象数量变化频繁、插入和删除频繁的场景
list自带排序函数排序原理
将前2个元素合并,再将后2个元素合并,然后合并这2个子序列成为4个元素序列的子序列,重复这一过程,得到8个，16个....子序列，最后得到的就是排序后的序列。时间复杂度O(logn)
deque的底层机制
deque动态地以分段连续空间组合而成，随时可以增加一段新的连续空间并链接起来，不提供空间保留功能(底层数据结构为一个中央控制器和多个缓冲区)
注意:
1.除非必要，我们尽可能选择使用vector而非deque，因为deque的迭代器比vector迭代器复杂很多。对duque的排序，为了提高效率，可先将deque复制到一个vector上排序，然后再复制到deque
2.deque采用一块map(不是STL的map容器)作为主控，其为一小块连续空间，其中每个元素都是指针，指向另一段较大的连续空间(缓冲区)
3.包含四个内容：
cur：迭代器当前所指元素
first：此迭代器所指的缓冲区的头
last：缓冲区尾
node：指向管控中心
deque与vector的区别
1.vector是单向开口的连续空间,deque是双向开口的连续线性空间
2.deque没有提供空间保留功能,vector则提供空间保留功能
3.deque也提供随机访问迭代器,但是deque迭代器比vector要复杂
map底层机制、查找时间复杂度、能否边遍历边插入
红黑树、O(logN)、不可以,它在容器进行erase操作后不会返回后一个元素的迭代器
hashtable如何避免地址冲突
1.hash函数计算某个元素的插入位置后，如果该位置的空间已经被占用，则继续向下寻找，直到找到一个可用空间为止
2.二次探测：如果计算的位置被占用，就依次尝试H+12,H+22 等
3.开链：每一个表格元素中维护一个list，在那个list中执行插入、删除
hash_set与set的区别
hash_set以hashtable为底层，不具有排序功能，能快速查找，其键值就是实值
set以红黑树为底层，具有排序功能
hash_map与map区别
构造函数：hash_map需要hash function 和等于函数，而 map需要比较函数（大小或小于）
存储结构：hash_map以hashtable为底层，而map以红黑树为底层
hash_map与map选择性
查找角度:hash_map查找速度比map快，而且查找速度基本和数据量大小无关，属于常数级别。而map的查找速度是logN级别,但不一定常数就比log小，而且hash_map还有hash function耗时,如果考虑效率，特别当元素达到一定数量级时，用hash_map。选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。如果是少数次的操作，使用 hash_map可能造成不确定的O(N)，那么使用平均处理时间相对较慢、单次处理时间恒定的map，考虑整体稳定性应该要高于整体效率，因为前提在操作次数较少。如果在一次流程中，使用hash_map的少数操作产生一个最坏情况O(N)，那么hash_map的优势也因此丧尽了
map和set的插入效率为啥必其他序列容器高
不需要内存拷贝和移动
map和set每次insert之后,之前保存的iterator会不会失效
因为插入操作只是结点指针换来换去，结点内存没有改变，而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变
当元素增多时例如从10000到20000,map和set查找速度会有怎样的变化
红黑树用二分查找法，时间复杂度为logN，所以查找次数从log100000=14变为log20000=15,多了1次而已
auto_ptr是否可以做vector的元素
不能,因为STL的标准容器规定它所容纳的元素必须是可以拷贝构造和可被转移赋值的,而auto_ptr不能，可以用shared_ptr智能指针代替
不允许遍历行为(不提供迭代器)的容器有哪些
queue：除了头部外，没有其他方法存取deque的其他元素
stack：(底层以deque实现),除了最顶端外，没有任何方法可以存取stack的其他元素
heap：所有元素都必须遵循特别的排序规则，不提供遍历功能
vector、list、map、deque用erase（it）后，迭代器的变化
vector和deque是序列式容器，其内存分别是连续空间和分段连续空间，删除迭代器it后，其后面的迭代器都失效了，此时it及其后面的迭代器会自动加1，使it指向被删除元素的下一个元素
list删除迭代器it时，其后面的迭代器都不会失效，将前面和后面连接起来即可
map也是只能使当前删除的迭代器失效，其后面的迭代器依然有效
为何map和set不能像vector一样有个reserve函数来预分配数据
引起它的原因在于在map和set内部存储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的Alloc并不是map<Key, Data, Compare, Alloc>声明的时候从参数中传入的Alloc
set, multiset区别
1.set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复
2.因为是排序的，所以set中的元素不能被修改，只能
map，multimap区别
1.map和multimap将key和value组成的pair作为元素，根据key的排序准则自动将元素排序，map中元素的key不允许重复，multimap可以重复
2.因为是排序的，所以map中元素的key不能被修改，只能删除后再添加。key对应的value可以修改
3.向map中添加的元素的key类型必须重载<操作符用来排序
