C++中vector的底层机制以及size和capacity的区别

admin管理员组

文章数量:1611973

vector底层机制

vector可以看做是一个动态的数组，是一段连续的线性内存空间。

它使用3个迭代器来表示：

//_Alloc 表示内存分配器，此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

 其中，：

1. _Myfirst 指向的是 vector 容器对象的起始字节位置；
2. _Mylast 指向当前最后一个元素的末尾字节；
3. _Myend 指向整个 vector 容器所占用内存空间的末尾字节。

 在此基础上，将 3 个迭代器两两结合，还可以表达不同的含义，例如：

• _Myfirst 和 _Mylast 可以用来表示 vector 容器中目前已被使用的内存空间；
• _Mylast 和 _Myend 可以用来表示 vector 容器目前空闲的内存空间；
• _Myfirst 和 _Myend 可以用表示 vector 容器的容量。

对于空的 vector 容器，由于没有任何元素的空间分配，因此 _Myfirst、_Mylast 和 _Myend 均为 null。 

 通过灵活运用这 3 个迭代器，vector 容器可以轻松的实现诸如首尾标识、大小、容器、空容器判断等几乎所有的功能，比如：

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
public：
    iterator begin() {return _Myfirst;}
    iterator end() {return _Mylast;}
    size_type size() const {return size_type(end() - begin());}
    size_type capacity() const {return size_type(_Myend - begin());}
    bool empty() const {return begin() == end();}
    reference operator[] (size_type n) {return *(begin() + n);}
    reference front() { return *begin();}
    reference back() {return *(end()-1);}
    ...
};

vector扩大容量的本质 

当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：

1. 完全弃用现有的内存空间，重新申请更大的内存空间；
2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
3. 最后将旧的内存空间释放。

 为什么 vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效？

因为扩容后，旧的内存空间被释放了，原来指向其的指针、引用和迭代器都失效。

vector 扩容是非常耗时的。为了降低再次分配内存空间时的成本，每次扩容时 vector 都会申请比用户需求量更多的内存空间（这也就是 vector 容量的由来，即 capacity>=size），以便后期使用。

vector 容器扩容时，不同的编译器申请更多内存空间的量是不同的。以 VS 为例，它会扩容现有容器容量的 50%。

 vector的size和capacity

size() – 返回目前存在的元素数。即： 元素个数
capacity() – 返回容器能存储 数据的个数。 即：容器容量
reserve() --设置capacity 大小
resize() --设置 size ，重新指定有效元素的个数 ，区别与reserve()指定容量的大小

capacity 一般大于size的原因是为了避免 每次增加数据时都要重新分配内存，所以一般会 生成一个较大的空间，以便随后的数据插入。
size是当前vector容器真实占用的大小，也就是容器当前拥有多少个元素。
capacity是指在发生realloc前能允许的最大元素数，即预分配的内存空间。
这两个属性分别对应两个方法：resize()和reserve()。
使用resize()，容器内的对象内存空间是真正存在的。
使用reserve()仅仅只是修改了capacity的值，容器内的对象并没有真实的内存空间(空间是"野"的)。
此时切记使用[]操作符访问容器内的对象，很可能出现数组越界的问题。
针对capacity这个属性，STL中的其他容器，如list map set deque，由于这些容器的内存是散列分布的，因此不会发生类似realloc()的调用情况，因此我们可以认为capacity属性针对这些容器是没有意义的，因此设计时这些容器没有该属性。
在STL中，拥有capacity属性的容器只有vector和string。

#include <iostream>
#include<vector>
using namespace std;
using std::cout;
using std::cin;
using std::endl;

int main()
{
	vector<int> ivec;

	cout << "空vector的capacity: " << ivec.capacity() << "  size: " << ivec.size() << endl;

	//添加10个元素,此过程中也在不断扩容
	for (int i = 0; i < 10; ++i)
	{
		ivec.push_back(i);
		cout << "capacity: " << ivec.capacity() << "  size: " << ivec.size() << endl;
	}
	//保存扩容前的迭代器
	vector<int>::iterator it = ivec.begin();

	cout << "将容量用完:" << endl;
	while (ivec.size() != ivec.capacity())
		ivec.push_back(0);

	cout << "扩容前保存的迭代器所指向的值：" << *it << endl;

	
	//添加1个元素
	cout << "当size==capacity后，接着插入元素，会导致扩容：\n";
	ivec.push_back(0);
	cout << "扩容后的capacity:" << ivec.capacity() << "  size:" << ivec.size() << endl;
	//cout << "扩容前保存的迭代器所指向的值：" << *it << endl; 扩容后将失效
	it = ivec.begin();
	ivec.reserve(100);
	cout << "reserve capacity 100\n";
	cout << "capacity:" << ivec.capacity() << "  size:" << ivec.size() << endl;

	//将容量用完
	while (ivec.size() != ivec.capacity())
		ivec.push_back(42);
	//添加1个元素
	cout << "size = capacity. insert one element\n";
	ivec.push_back(0);
	cout << "capacity:" << ivec.capacity() << "  size:" << ivec.size() << endl;

	ivec.resize(50);
	cout << "resize size 50\n";
	cout << "capacity:" << ivec.capacity() << "  size:" << ivec.size() << endl;
	return 0;
}
/*
空vector的capacity: 0  size: 0
capacity: 1  size: 1
capacity: 2  size: 2
capacity: 3  size: 3
capacity: 4  size: 4
capacity: 6  size: 5
capacity: 6  size: 6
capacity: 9  size: 7
capacity: 9  size: 8
capacity: 9  size: 9
capacity: 13  size: 10
将容量用完:
扩容前保存的迭代器所指向的值：0
当size==capacity后，接着插入元素，会导致扩容：
扩容后的capacity:19  size:14
reserve capacity 100
capacity:100  size:14
size = capacity. insert one element
capacity:150  size:101
resize size 50
capacity:150  size:50
*/

本文标签： 底层区别机制VectorCapacity