vector扩容机制

在学习了vector的时候，总说linux下是以二倍扩容的，VS是以1.5倍扩容的。

但是想一想为什么扩容是这样的呢，为什么不能是3倍或者其他倍数呢？? 所以带着这些疑问，接着往下看。

首先，我们要知道vector的扩容机制：当向vector插入元素的时候，即当_finish == _end_of_storage，可能就会触发扩容机制。

扩容有二种方式：

• 等长个数扩容
• 倍数扩容

等长个数扩容

等长个数扩容，新空间都是在原来的空间基础上增加K个空间。每当触发扩容的时候，就会将旧空间的数据移动到新空间去，同时将旧空间释放掉。

倍数扩容

假设向vector中插入n个元素，每当_finish== 2 ^k（0,1,2,3....）时，就会出现扩容。下面以VS和linux来观察看。

void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

VS下的测试结果：

linux下的测试结果：

可以看出，VS下的扩容差不多是以1.5倍来扩容的，而linux下的扩容是以2倍来扩容的。那么问题来了，为什么这样？？？

为什么都会选择倍数扩容

这是因为以等长个数来扩容的话，需要插入元素和移动元素操作总和是O（N），而以倍数扩容是O（1）。

而且VS和linux下都是以倍数扩容，还有一些原因是如果以等长个数扩容，那么个数应该是多少呢？如果太小的话，就可能导致频繁的扩容；如果太大的话，就可能出现一种情况，如果有100个元素，这是只需要再插入一个元素，但是需要扩容100个，这就导致了浪费了99个的空间。

为什么选择1.5倍或者2倍来扩容，而不是3倍或者其他倍数

最佳的扩容倍数

要想对空间的利用率最高，就是F（N-1） + F（N-2） >=?F（N) ，时间上是F（N-1） + F(N-2) = F(N),这不就是1, 2 3 5 8....，所以最佳的扩容机制就是1.618

linux下为什么选择二倍扩容

我们都知道linux下都是通过页来管理内存的，通常是4KB，都是2的倍数。

这样做有三个好处:

• 减少内存分配次数：以二倍的方式扩容可以减少内存分配的次数，每次扩容后，可以容纳更多的容量。
• 提高性能：二倍的扩容机制可以更好的利用linux系统分配的机制，减少内存分配和释放的频率，提高性能。
• 减少内存碎片：以二倍的方式扩容可以减少内存碎片，因为如果每次扩容都是增加一些小的容量，就有可能导致小的内存散布在堆上，增加了内存碎片的风险。

像linux下的伙伴系统就是以2的幂次方来分配内存和管理的一种算法，综合考虑，就理解了为什么linux下为什么要选择以二倍的扩容机制。