stl容器

vector

size()函数返回当前vector所容纳元素的数目，即使用的空间大小

capacity()函数返回当前vector在重新进行内存分配以前所能容纳的元素数量，即返回的是总的容量大小，capacity()-size()后就是未使用的空间大小。

push元素时, 是增加size()的大小, 当size()==capacity()时, 触发扩容

使用者可以通过reserve()来改变capacity()，resize()改变size()。

resize，即重置容器空间。当设置值小于当前容器空间时，会将目前容器中超出设置值的空间释放掉；当设置值大于当前容器空间时，会在当前空间的基础上增加容量。

vector扩容

不同编辑器扩容因子不一样, vs 为 1.5, gcc 为 2

push_back的话，一般来说，都是按两倍来扩容，因为push_back每次都是只插入一个数据

insert的话，因为可以一次插入多个数据，所以要复杂一些。

触发扩容时，如果要插入的数据量比旧容量小，则按两倍扩容；

如果要插入的数据量比原来的旧容量还要大，会按照旧容量加要插入的数据量来扩容，保证一次扩容就能容下要插入的数据；

即 new_capacity = max ( old_capacity * 2, n + old_capacity )

扩容因子

从空间上来分析，扩容因子越大，意味着预留空间越大，浪费的空间也越多，所以从空间考虑，扩容因子因越小越好。

从时间上来分析，如果预留空间不足的话，就需要重新开辟一段空间，把原有的数据复制到新空间，如果扩容因子无限大的话，那显然就不再需要额外开辟空间了。所以时间角度看，扩容因子越大越好

不考虑一次性插入大量数据的情况,只考虑N次push_back()

总消耗 = 每次插入消耗+ 扩容消耗

每次插入消耗

显然每次常规插入操作需要1的时间，插入n个数据的常规时间为N

扩容消耗

现在考虑额外的消耗，扩容因子为K，意味着一共需要扩容$\log_kN$，为简化计算，假设是容量是从1开始，也就是要对下面的等比序列求和

S = 1 + k + $k^2$ + $k^3$ + $k^4$ + …… + $k^{log_kN}$= (N-1)/(K-1)

显然，也就意味着扩容因子K越大，额外的消耗越小。总消耗为N+(N-1)/(K-1) 。当K大于1时，K越大总消耗越小。

顺便可以再求一下push_back的摊还时间复杂度。即为 (N+(N-1)/(K-1))/N = (NK-1)/(K-1)

最普遍的情况下，当扩容因子为2时，最好的评价时间复杂度为2N，发生在N等于2的n次幂时，最差为3N，发生在N等于2的n次幂加1时

k=2与k=1.5的比较

K = 2时

每次扩容后capacity的情况如下：1，2，4，8，16，32 ……..

当我们释放了4的空间，我们寻找8的新空间，再次扩容，释放8，寻找16。。

仔细分析，第5次扩容时，需要寻找16的新空间，第4次释放了8，第3次释放了4，第2次释放了2，第1次释放了1，所以 1 + 2 + 4 + 8 = 15 < 16，也就意味着，之前释放的空间，永远无法被下一次的扩容利用，这对内存与cache是非常不友好的。

K = 1.5时

每次扩容之后capacity的情况为：1，2，3，4，6，9，13，19，28 ……

再按刚才的思路分析一遍，1 + 2 >= 3; 3 + 4 >= 6; 6 + 9 >= 13 …….

所以，当K为1.5时，显然对内存和cache要友好很多，至少从容量上来说，是存在重复利用的可能性的。

因此，我们可以得出结论，当K = 2时，时间上要比 K = 1.5 占优，而空间上比 1.5 稍有劣势。

那么，那个最佳的数是多少呢？

继续刚才的分析，我们希望的是，上几次的空间，存在被下一次扩容时利用的可能性。

也就是 X(n-2) + X(n-1) >= X(n)，显然我们也希望时间上也要更好，即X(n-2) + X(n-1) = X(n)

即：1，2，3，5，8，13，21，34，55 。。。。

是不是很熟悉。。。是的，这就是我们的斐波那契数列。。。

那么当N趋于无限大时，取极限，最佳的扩容因子也就是那个最美的数，黄金分割率，1.618

如何避免扩容

对于构造开销比较大的类, vector的频繁扩容开销会很大

因为每次扩容都会重新调用构造函数

所以需要使用reserve()函数为vector预留空间, 来避免使用过程中的频繁扩容

list

list是基于双向链表，内存是不连续的，不支持下标访问，支持指针访问

deque

deque是一个double-ended queue，它具有以下两个特点：

支持[]操作符，也就是支持随即存取，并且和vector的效率相差无几

支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多

map和unordered_map

map	unordered_map
内部用红黑树实现，具有自动排序功能	内部用哈希表实现，内部元素无序杂乱
查询删除等操作复杂度为$o(logN)$	查找速度非常快（适用于大量的查询操作）
占用空间，红黑树里每个节点需要保存父子节点和红黑性质等信息，空间占用较大	建立哈希表比较耗时