前言:
什么是vector？
它是动态分配的元素数组,从数据结构类型分类来说,vector属于“线性表”中连续存储结构类型.因为它内部的元素是存储在一片连续的内存区域(一个元素紧挨着下一个元素),并且会预留一定空余的空间备用,一旦元素数量超过capacity所指定的值,vector会向操作系统一次性申请更多的内存已被后续新增元素的使用。
我们从一个空的整数向量开始,然后在vector容器添加了一些整数。 现在让我们通过vector对象的成员方法size()和capacity()来看一下它的内存块是如何扩容的：
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
vector<int> v;
//空的vector容器
cout << "v size:" << v.size() << " v capacity" << v.capacity() << endl;
v.push_back(111);
v.push_back(123);
cout << "v size:" << v.size() << " v capacity" << v.capacity() << endl;
v.push_back(133);
cout << "v size:" << v.size() << " v capacity" << v.capacity() << endl;
v.push_back(55);
v.push_back(63);
v.push_back(55);
cout << "v size:" << v.size() << " v capacity" << v.capacity() << endl;
v.push_back(63);
v.push_back(77);
v.push_back(98);
cout << "v size:" << v.size() << " v capacity" << v.capacity() << endl;
v.push_back(63);
v.push_back(77);
v.push_back(98);
v.push_back(63);
v.push_back(77);
v.push_back(98);
v.push_back(98);
cout << " v endnode:" << *v.end() << endl;
return 0;
}
输出如下图:
尝试在每次push_back之后打印出元素个数,和已分配缓存空间的尺寸,会得出如下数据表.
从程序的输出来看,随着向vector容器插入新的元素,已经可以找到一些规律了
- 那就是需要内存扩容的增长量是当前动态数组的.内存尺寸的2倍
- 而触发内存扩容的条件是当前容器的size()返回的值大于capacity()返回的值
end、begin、capacity、size的关系
现在我们用如下图表示:
vector内部有三个指针维护着vector的缓存区域
_M_start,被封装在begin()内,它指向已分配的缓存区的第一个块区
_M_finish:备封装在end()内,它指向缓存块区中已插入的最后一个元素的下一个内存块.
_M_end_of_storage,它指向已分配缓存区的末端的下一个内存块，这个内存块并非当前已分配缓存块区的有效区域.
capacity()方法返回当前vector对象内已分配缓冲区的尺寸,从vector的头文件stl_vector.h可知,其方法内部就是返回_M_end_of_storage -_M_start,这两个指针的**差值。
size()方法返回当前vector对象内已分配缓存区中已插入的元素的个数,从vector的头文件stl_vector.h可知,其方法内部就是返回_M_finish-_M_start,这两个指针的**差值。
vector扩容示意图
上文从示例代码中得到我们知道size()返回的值大于capacity()返回的值,更确一步说,就要vector的内部指针_M_finish在随着元素的插入会不断逼近 _M_end_of_storage指针,只要 _M_finish和 _M_end_of_storage指向的内存块是一样的时候,就会触发内存扩容.
如下图所示是插入连续插入6个元素时的vector的内部运行示意图
性能问题:
现在我们知道,内存会按照已分配的缓存区的尺寸的2倍增长,假设我们有无限的元素插入,这个过程一直持续下去，但实际上是受计算机的物理随机内存的容量和计算机寻址的限制的。上面的示意图并非事实上的全部,对于不同的操作会出现不同性能表现。
- push_back()插入操作,在缓存区还有备用空间的情况下,它的成本消耗是O(1).否则按下面第二种情况的表现。
- 缓存区的元素已满并且size()>capacity()的条件的话,每当触发内存扩容操作,vector会在堆内开辟一个全新的内存块区,当然是之前分配缓存区长度的2倍,然后将旧的缓存区上的所有元素拷贝到新的缓存区,最后旧的缓存区会被释放，此时的成本消耗的O(n);
- 除了元素尾部(也就是插入前end()所返回的迭代器所指向的位置)的其他位置执行insert()操作,插入前必须移动其他元素，因此成本消耗也是O(n)
- 从vector容器中取出最后一个元素,该操作不会改变缓存区的尺寸,因此时间成本是O(1)
如何避免频繁的重新分配内存
对于一个长期驻留在RAM中的程序而言,在使用vector作为内存中的长期的数据转运仓库,应该在初始化vector的时候,预留足够的缓存空间给vector, 避免元素达到capacity具体你是预留多少是看你的程序平均一次批量性插入操作需要处理多少数据量以及容器存储的数据类型所决定的,
例如你的vector的存储的基本类型是Person类型,而每个Person的对象涉及姓名(string类型),年龄(unsign int类型),地址(string类型),收入(float类型)等信息...,那么一个vector初始化预留的备用内存也和一个复合的数据结构类型的内存对齐也有很大的关系.
最后:其实C++的几乎所有顺序存储结构的容器类来源于STL中的container的基类，std::string容器和std::vector不论从迭代操作的相关API还是内存分配机制几乎是一样的，你可以看我之前写关于对[C/C++]指针与字符串的总结 一文。
