请教关于vector性能和自增长的问题

C++ Primer 3 P216最下面有这么一句话。

“根据经验发现用一个非1的缺省值来调整vector的容量看起来总会引起性能退化。例如对于string和double型的vector
通过reserve()增加容量导致很差的性能。”

不理解这里所说的性能是什么意思，是指这时候的vector再次自增长时性能会很差么？为什么呢？


还有一个就是P215表格中说vector<int>插入1个元素的时候capacity是256，然后成倍增长。为什么我用vs2008看的时候capacity是1，然后增长也没发现规律呢？是这么增长的1，2，3，4，6, 6，9, 9, 9，13, 13, 13, 13....


希望各位能帮忙解释一下，谢谢！

15 个解决方案

#1

每增加一个元素，会导致大量的拷贝和删除事件发生，性能肯定很差。不过元素都是按数组的方式排列的，随即访问速度快。

#2

我觉得我发现增长的规律了，每次增长当前长度的1/2向下取整。

#3

当空间不足时，VECTOR自动扩大一倍（有的是1倍多1点，有的是1倍少一点，这个根据编译器而定），capacity获得的就是VECTOR的容量。

#4

楼主不必担心这个问题。
即使你增加一个元素，也没有书上提到的“性能很差”的问题。
库的设计者会预留内存空间，以保证效率。
而且，不同的库，其实现是不一样的。

#5

我没看得这么细。向楼主学习

#6

看源代码一目了然

_Capacity = max_size() - _Capacity / 2 < _Capacity
				? 0 : _Capacity + _Capacity / 2;	// try to grow by 50%

#7

(1)初始化阶段vector里面是没有分配任何内存的，如果使用缺省值的话则导致了分配内存，初始化变量等一些不必要的操作，所以说性能比较差。
(2)reserve调整容量的逻辑是，如果当前调整的容量比当前已经分配的容量小，则直接在原有的基础上调整即可，这种情况性能尚可。
如果reserve调整的容量大于当前已经分配的容量，则会导致从内存池中得到新的内存，将数据拷贝过去，并将原有的内存放回内存池，如果当前内存池中没有内存，则会引起一次内存池申请内存的动作，所以说性能会比较差！！！
(3)不同版本的capacity增加是没有规律的，而且其计算方法各有各的不同，所以lz没必要在这上面计较。

#8

看到一本书说过一般是1.5倍的增长

#9

引用 4 楼 loaden 的回复:

楼主不必担心这个问题。
即使你增加一个元素，也没有书上提到的“性能很差”的问题。
库的设计者会预留内存空间，以保证效率。
而且，不同的库，其实现是不一样的。

哦，谢谢~~

#10

性能不会太差，一般都是预留空间和自动增加容量的，会插入的数据到达一定值会调节的。
具体倍数关系要看源码是什么实现的，你可以看看STL的源码中vector如何增加的。

#11

1.5倍长度没错

#12

引用 6 楼 fanster28_ 的回复:

看源代码一目了然


C/C++ code
_Capacity = max_size() - _Capacity / 2 < _Capacity
                ? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%

非常感谢！！！我怎么就记不起来跟进去看呢....学习学习...

#13

看来就是1.5倍了，我记得hash_map的容量增长也是当负载因子0.5的时候增长容量。

#14

引用 12 楼 dadun 的回复:

引用 6 楼 fanster28_ 的回复:
看源代码一目了然


C/C++ code
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%


非常感谢！！！我怎么就记不起来跟进去看呢....学习学习...

这只是GCC的实现，不同编译器不一样。
同一编译器，不同版本，也可能不一样。

#15

我不觉得主流编译器会更改STL的设计