STL源码剖析之vector

Author	Guodong Zhu
Version	1.0.0

vector特点

支持索引，可随机访问

各元素的内存空间连续

支持动态扩容

关键技术点：扩容策略以及扩容时的数据搬运效率

设计逻辑

逻辑递进关系:

==> 要求内存空间连续
        ==> 扩容时需要重新分配连续空间
                ==> 需要将旧数据搬运到新的空间中，并释放旧空间

扩容流程 1 

分配新空间
搬运旧数据到新空间
释放旧空间

Hint

详细流程请参考《STL源码剖析》

扩容策略分析

（1）最简单的策略： 用多少分配多少，根据实际使用量严格按需分配。比如，定义一个 vectot<uint32_t>，当存放1个元素时，内部分配4个字节；当扩充到两个元素时，扩容到8个字节；增加到3个元素时，扩容到12字节，以此类推，容量为：0, 4, 8, 12, … ,4n, …。每次都只增加一个元素，最后达到n个元素，这种情况下扩容的操作最多，也就是所谓的最差情况。

vector元素个数	0	1	2	3	…	n
vector容量（byte）	0	4	8	12	…	4n

元素数量变化	0->1	1->2	2->3	3->4	…	n->n+1
分配新空间（byte）	4	8	12	16	…	4(n+1)
搬移数据（byte）	0	4	8	12	…	4n
释放旧空间（byte）	0	4	8	12	…	4n

假设每次搬移只处理作一个字节（如果使用 memcpy，可以优化搬移操作），根据累计搬移数据的字节数计算分摊时间复杂度：

\[F_{avg}(n)=0+4+8+12+...+4n=\frac{4n(n-1)}{2*n}=2(n-1)\]

\[T_{avg}(n)=O(n)\]

（2） 每次扩容为上一次2倍容量

vector元素个数	0	1	2	3	…	n
vector容量（byte）	0	4	8	16	…	\(2^{\lceil {\log_2n} \rceil}\)

其中， \(\lceil\), \(\rceil\) 表示向上取整。

元素数量变化	0->1	1->2	2->3	3->4	…	n->n+1 （假设n是2的幂级数）
分配新空间（byte）	4	8	12	16	…	8n
搬移数据（byte）	0	4	8	12	…	4n
释放旧空间（byte）	0	4	8	12	…	4n

假设每次搬移只处理一个字节（如果使用memcpy，可以优化搬移操作），根据累计搬移数据的字节数计算分摊时间复杂度：

\[F_{exp\_avg}(n) = \frac{0+4+8+16+...+4n}{n} = \frac{2^1+2^2+2^3+...+2^{\lfloor log_2n \rfloor}}{n} = \frac{2^{\lceil log_2n \rceil}-2}{n} \approx 1\]

\[T_{exp\_avg}(n)=O(1)\]

其中，\(\lfloor\), \(\rfloor\) 表示向下取整。

通过策略（1）和策略（2）对比可以发现，采用每次扩容为上一次2倍容量方式，分摊时间复杂度更低，这也是vector采用的扩容策略。

参考

1: 《C++ STL源码剖析》第4.2节