在学习了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的倍数。
这样做有三个好处:文章来源：https://www.toymoban.com/news/detail-791654.html
- 减少内存分配次数：以二倍的方式扩容可以减少内存分配的次数，每次扩容后，可以容纳更多的容量。
- 提高性能：二倍的扩容机制可以更好的利用linux系统分配的机制，减少内存分配和释放的频率，提高性能。
- 减少内存碎片：以二倍的方式扩容可以减少内存碎片，因为如果每次扩容都是增加一些小的容量，就有可能导致小的内存散布在堆上，增加了内存碎片的风险。
像linux下的伙伴系统就是以2的幂次方来分配内存和管理的一种算法，综合考虑，就理解了为什么linux下为什么要选择以二倍的扩容机制。文章来源地址https://www.toymoban.com/news/detail-791654.html
到了这里，关于vector扩容机制的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![java八股文面试[数据结构]——HashMap扩容优化](https://imgs.yssmx.com/Uploads/2024/02/671057-1.png)
