扩容原理
- vector以连续的数组存放数据，当vector空间已满时会申请新的空间并将原容器中的内容拷贝到新空间中，并销毁原容器
- 存储空间的重新分配会导致迭代器失效
- 因为分配空间后需要进行拷贝，编译器会预分配更多空间以减少发生拷贝影响程序效率
- 扩容的大小叫做扩容因子，扩容因子由编译器决定，VS的扩容因子为1.5，G++中，扩容因子为2
vector<int> v = { 1,2,3,4,5,6 };
cout << v.capacity()<<' ';
v.push_back(7);
cout << v.capacity();
vs中，扩容后容器大小为原来的1.5倍
g++中，扩容后容器大小为原来的2倍
不同扩容因子的比较
- 扩容因子大，每次需要分配的新内存空间越多，分配空间耗时。空闲空间较多，内存利用率低。
- 扩容因子小，需要再分配的可能性更高，扩容耗时。空闲空间较少，内存利用率较。
一般认为扩容因子1.5优于2.0，原因是以1.5作为扩容因子可以实现复用释放的内存空间。
以2为扩容因子时，分配空间为
0 1 2 4 8 16...
每次分配新空间时所需空间与释放的空闲空间
| 分配空间 | 空闲空间 |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 4 | 1+2=3 |
| 8 | 3+4=7 |
| 16 | 7+8=15 |
空闲的空间始终要小于需要分配的空间
以1.5为扩容因子时，分配空间为
0 1 2 3 4 6 9...
| 分配空间 | 空闲空间 |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 1+2=3 |
| 4 | 3+3=6 |
| 6 | 6+4=10 |
| 9 | 10+6=16 |
随着分配空间增大，之前释放的空闲空间能够满足当次扩容所需的空间，实现内存的复用
版权声明：本文为Rengachan原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。