vector insert_C++标准库 | 假装我的Vector更好

本文使用 Zhihu On VSCode 创作并发布

相信长期以C++作为主要开发语言的同学都几乎实现过一次标准库，至少实现过简单的容器。本文记录我实现Vector容器insert功能的时候遇到的性能问题。

我们知道，Vector管理的是一段连续的内存，若非从尾部添加元素，必须进行繁重的拷贝，从而为要插入的元素腾出空间。当容器总体控制的内存不够新的插入时，必须重新申请一块空间，再进行繁重的拷贝。

奇怪的insert

我使用一段简单的代码比较我的实现和标准库实现，在容器开头不断添加元素，总共添加了1e5个元素：

// 我的实现

分别对这两段代码计时，发现运行时间相差甚远。

inserting at 0: my vector 17.758048, std vector 1.561731

相差超过十倍，就算再优化，也不至于这么远呀。我查了代码，当时写的时候可能很仓促，导致部分功能不完善，没有经过优化，趁着这个机会好好优化一下。

我发现我的“向后拷贝”函数存在缺陷。“向后拷贝”就是在给insert的元素腾空间，要是发现现有空间不够，就要重新申请空间。实现这个功能的函数，在进行重新申请空间时，申请了满足插入后刚好填满的需要，而没有更多地向后申请。一般来说，Vector容器扩容必须申请一个原来空间两倍的空间，以保证性能。这里把要申请的空间乘2，容器的性能立马提升了很多。

inserting at 0: my vector 2.583674, std vector 1.355900

进一步优化insert

为了进一步减小我的实现和标准库实现之间的差距，我把断点打进了标准库文件。标准库的代码跳来跳去，实在烦人，我还是耐着性子读完了。

最后的结论是，标准库的实现和我的几乎一致。当insert发现当前占有的内存不足以支持insert之后的元素，就重新分配一块更大的空间。分配的大小是原来空间大小的两倍。在把元素从旧空间拷贝到新空间的时候，先拷贝insert位置之前的元素，再拷贝要insert的元素，最后拷贝insert位置之后的元素，从而避免了重复拷贝。

那么为什么标准库还是这么快？？？这我就不知道了，只能猜测，可能是标准库的分配器给它加速了。虽然不知道自己为什么慢，但是和标准库不相上下还是非常令人开心的。

怀着不服的倔强，改了一下测试参数，重新对上面的代码计时。原来是插入1e5个元素，现在是插入2e5个元素。跑了一会，得到结果：

inserting at 0: my vector 10.118405, std vector 5.964099

还是差了两倍左右。

比比别的

在Vector容器头部insert元素，在实际工程中不是一个明智的操作，拷贝实在是太繁重，也没必要。要比就比常用操作push_back，分别push_back 1000000次，得到结果如下：

push_back: my vector 0.015197, std vector 0.020511

多次测试得到的结果不尽相同，但和标准库之间的差距，或者说相对于标准库的优势，更加明显了。（逃