vector详解

在开始学习C++的STL之后，相信大家都学会通过查文档来了解一些库函数，今天我来给大家介绍vector，从基本的使用到vector背后的源码实现，迭代器等展开讲，仔细阅读，一定有所收获！

 

vector基本介绍

首先大家要知道，vector是一个序列式容器，什么是序列式容器：

所谓序列式容器，就是其中的元素都有序，但是这里的有序不是通常意义上我们理解的有序，而是元素被存储的顺序和容器中存储的顺序一致。C++中的序列式容器有C++语言提供一个序列式容器array，同时STL还提供了 vector,list,deque,stack,queue等等序列式容器。

vector是一个什么样的容器？

vector这个容器理解起来就像一个大小可变的数组，与数组不同的地方就是数组是一块静态的空间，而vector是一块动态的空间，随着元素的假如，vector的内部机制会自行扩充空间大小以收纳更多的元素。

vector的使用

通过查阅文档，我们来了解一下vector的使用：

构造函数

首先来介绍一下构造函数，第二个空间配置器我们这里先不讲，主要说一下基本的构造函数的使用。

最常见的第一个构造函数，你可以什么都不写，直接构造一个vector对象：

vector<int> v1;

 

默认构造的对象，size和capacity都为0。

还可以一次构造多个对象：

vector<int> v2(10);

 

 但是这些元素都会调用他们自己的构造函数，这里要明确一点，vector这个容器可是很强大的，里面不仅可以放内置类型的元素，还可以放自定义类型的元素。所以放元素的时候，就会涉及到调用元素的构造函数。在C语言中我们可能没见过下面这行代码：

int a = int();
cout << a;

最终打印的结果是0，也就是默认a被初始化为0，这样大家就很好理解为什么上面的监视窗口的元素都是0了。

拷贝构造也说的很简单，可以直接传被拷贝对象的引用，也可以传递两个迭代器分别指向要拷贝的begin和end。

其他接口

vector文档

 这里有两个值得一说的接口：resize和reserve

 

对比发现，reserve是对capacity进行调整，所以参数也之后一个n，n比capacity大就扩容，但是不回发生对空间的回收。

resize主要是对元素进行调整，如果n比size大， 发生扩容，并且这里要对元素进行初始化，调用对应的构造函数。

assign这个接口可以让之前vector容器中的内容完全被改变，改变的方式有两种：

用另一个vector对象的迭代器来标定区间

用n个值为val的对象进行填充 

	vector<int> v1;
	vector<int> v2(10);
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	//v2.assign(v1.begin(),v1.end());
	v2.assign(4, 5);
	for (auto E : v2)
	{
		cout << E;
	}

其他的类函数这里就不一一列举了。接下来聊一下vector的迭代器

vector的迭代器

大家在一开始学C++的时候可能都看过这样一段代码（如下图），这段代码看起来很厉害，我们之前C语言需要很多行代码才能实现的效果它很容易就实现了，其实很简单，就是使用了迭代器。迭代器是一个类，里面实现了很多的运算符重载。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> ret;
	ret.push_back(1);
	ret.push_back(2);
	ret.push_back(3);
	ret.push_back(4);
	for (auto R : ret)
	{
		cout << R << " ";
	}
	return 0;
}

vector是一个连续的线性空间，就像数组一样，区别于数组之处在于vector是可以对数组的大小进行动态修改的。但是在访问和操作上也可以像数组一样提供一种指针的访问方式，那么这就是vector迭代器，但是迭代器千万不可以被理解为它就是指针，在之后的list的文章中我们还会再次提及。

vector迭代器可以实现的操作行为有：operator*,operator->,operator++,operator--,operator+,operator-,operator+=,operator-=,是的，这不就是指针都能实现的嘛。

vector是支持随机存取的。所以迭代器指向的每个位置的操作都是可以被执行的。

上面的范围for是怎么实现的呢？本质就是使用了迭代器对ret这个容器进行了遍历。总的来说，在vector中，由于vector的数据结构，vector迭代器甚至可以直接认为是指针。

int main()
{
	vector<int> ret;
	ret.push_back(1);
	ret.push_back(2);
	ret.push_back(3);
	ret.push_back(4);
	//通过迭代器找到值为2的元素并对其进行修改
	vector<int>::iterator it = ret.begin();
	while (it != ret.end())
	{
		if (*it == 2)
			*it = 10;
		++it;
	}
	for (auto R : ret)
	{
		cout << R << " ";
	}
	return 0;
}

大家应该都注意到了代码中的两个函数：begin()和end()

begin返回的是一个指向容器第一个元素的迭代器，而end返回的是一个指向最后一个元素的下一个位置的迭代器。所以begin与end维护的是一段前闭后开的区间，这一点要格外注意，之后的练题中很容易出现越界访问的问题。

而rbegin和rend则和begin与end相反，也就是rbegin和end一个意思，而rend和begin一个意思。

vector的数据结构

vector采用的数据结构非常简单，线性连续空间，以两个迭代器start和finish分别指向连续空间中已经被使用的范围的头尾，而迭代器end_of_storage指向整块连续的空间的尾端，所以模拟实现vector需要三个迭代器实现：

template<class T,class Alloc = alloc>
class vector
{
    //...
protected:
    iterator start;            //表示目前使用空间的头
    iterator finish;           //表示目前使用空间的尾
    iterator end_of_storage;   //表示目前可用空间的尾
//...
}

为了降低空间配置时的速度成本，vector实际配置的空间大小可能比客户端需求的更大，一旦容量等于大小，便是满载，下次再有新增元素，整个vector就要扩容。

画一张图方便大家理解：

扩容中的一些问题

上面提到了空间不够用的时候会出现扩容的现象，但是实际上扩容的过程中有很多我们要注意的事情。整个扩容的过程不像顺序表中的简单的扩容，直接使用realloc就扩容完成了，实际中会遇到一些问题我也会一一展开说，最后我们再一起看一下源码的一些实现方法。

迭代器失效问题

设想我们一直在一块空间中插入元素，很快finish所指向的位置就到了end_of_storage，空间需要扩容，那么在插入数据完成后，就不可以简单的将迭代器进行++的操作，这里画一张图大家理解一下：

 迭代器失效就是没有更新迭代器所指向的位置，导致出现了程序的报错。

#include <iostream>
#include <vector>

using namespace std;
int main()
{
	vector<int> V1;
	V1.push_back(1);
	V1.push_back(2);
	V1.push_back(3);
	V1.push_back(4);
	vector<int>::iterator it = V1.begin();
	while (it != V1.end())
	{
		if ((*it) % 2 == 0)
			V1.erase(it);
		else
			++it;
	}
	for (auto& num : V1)
	{
		cout << num;
	}
	return 0;
}

上面的代码会出现报错，当然这里举例的是一个erase的例子，insert的例子图片表示的很清楚了。上面的代码会不会报错大家猜一下。

答案是在VS平台下会报错，但是在g++下不会报错。这是为什么？

VS平台下的stl的实现是和g++下的实现是不一样的，stl会对插入和删除后的迭代器进行强制的检查，删除后迭代器指向的位置可能是非法的，所以VS下的stl的实现防止非法的访问直接进行了强制检查，而g++的erase则返回删除元素的下一个，并不会进行强制检查，这也就是为什么在g++下不会报错的原因。但本质上还是这就是一段错误的代码，erase本身是由返回值的，会返回删除后的迭代器，如果不接受而是自己进行迭代器的调整就会导致迭代器失效

所以当你写一个程序在有的环境下可以跑过有的环境下跑不过，先别怪编译器，一定是代码有问题。

扩容出现的浅拷贝问题

扩容的时候会出现数据拷贝的问题，当我们模拟实现的时候，如果就单纯的使用memcpy就会出现浅拷贝问题。

如果被拷贝的对象是自定义类型，如果单纯的拷贝自定义类型对象的地址，在拷贝结束后就会对之前的对象内容进行回收，那么再去使用已经被回收的对象就会报错。

 源码中的扩容

void push_back(const T& x)
{
	if (_fininsh != end_of_storage)
	{
		construct(finish, x);
		++finish;
	}
	else//没有备用空间
		insert_aux(end(), x);
}

template<class T,class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x)
{
	if (_finish != end_of_storage)//还有备用空间
	{
		//在备用空间起始处构造一个元素，并以vector最后一个元素值为初始值
		construct(finish, *(finish - 1));
		//调整水位
		++_finish;
		T x_copy = x;
		copy_backward(position, finish - 2, finish - 1);
		*position = x_copy;
	}
	else//已无备用空间
	{
		const size_type old_size = size();
		const size_type len = old_size != 0 ? 2 * old_size : 1;
		//如果原大小为0，那么就配置为大小为1
		//如果大小不为0，就配置大小为原大小的两倍

		iterator new_start = data_allocator::allocate(len);
		iterator new_finish = new_start;
		try
		{
			//将原来vector中的内容拷贝到新的vector中
			new_finish = unintialized_copy(start, position, new_start);
			//为新元素设定初始值x
			construct(new_finfish, x);
			//调整finish位置
			++new_finfish;
			new_finfish = uninitalized_copy(position, finish, new_finish);
		}
		catch(...)
		{
			destroy(new_start, new_finish);
			data_allocator::deallocate(new_start, len);
			throw;
		}
		//析构并释放原vector
		destroy(begin(), end());
		deallocate();
		//调整迭代器指向新的vector
		start = new_start;
		finish = new_finish;
		end_of_storage = new_start + len;
	}
}

源码其实没必要全部看懂，我们可以大概了解源码扩容的思路：

如果有空间就进行正常的插入操作，如果空间已满，就进行扩容，然后讲原空间内容复制到新的空间中，再讲新空间中的内容进行回收操作。因此，对vector中的任何操作，一旦引起空间重新配置，就会导致指向原先vector中的所有迭代器都会失效。上面我已经提到过了这里再次说明。

重要的东西基本上都提到了，如果有什么不足还希望大家能在评论区提出宝贵意见，其实在学习STL的过程中，我们发现迭代器在容器中起着很重要的作用，迭代器在容器的访问上提供了一致的接口，在之后的博客中大家可以慢慢体会到迭代器的重要作用。

今天的博客内容就到这里啦，谢谢大家支持！