【C++】vector的使用及其模拟实现

这里写目录标题

一、vector的介绍及使用
- 1. vector的介绍
- 2. 构造函数
- 3. 遍历方式
- 4. 容量操作及空间增长问题
- 5. 增删查改
- 6. vector二维数组
二、vector的模拟实现
- 1. 构造函数
- 2. 迭代器和基本接口
- 3. reserve和resize
- 4. push_back和pop_back
- 5. insert和erase
- 5. 迭代器失效问题
- 5. 浅拷贝问题
三、vector模拟实现整体源码

一、vector的介绍及使用

1. vector的介绍

vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小，为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。 就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。 不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。 对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

2. 构造函数

vector学习时一定要学会查看文档：vector文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以。当然我们使用vector之前需要包头文件#include<vector>。

下面我们来看一下vector的构造函数：

因为在vector中是重载了[]访问运算符的，所以我们可以直接使用[]访问运算符来访问，vector中的元素。下面我们直接来举几个例子来看一下构造函数的用法：

这里我们可以看到和string不同的是，这里的capacity表示的就是所开辟的空间中最多能存储的元素的个数，但在string中则需要多开辟一个空间为’\0’预留位置。

迭代器区间构造本质上是一个函数模板，所以我们可以用任意类来构造vector对象。

3. 遍历方式

💕 [ ]遍历

int main()
{
	vector<int> v2(5, 0);
	for (int i = 0; i < v2.size(); i++)
		cout << v2[i] << " ";
	cout << endl;

	return 0;
}

当然了，因为[ ]重载了const和非const两个版本，所以[ ]既可以对const对象使用又可以对非const对象使用。

💕 使用迭代器遍历

vector和string一样，也有反向迭代器rbegin和rend，他们表示获取最后一个数据位置的reverse_iterator和第一个数据前一个位置的reverse_iterator。

int main()
{
	vector<int> v2;
	v2.push_back(1);
	v2.push_back(2);
	v2.push_back(3);
	v2.push_back(4);
	v2.push_back(5);
	vector<int>::iterator it = v2.begin();
	while (it != v2.end())
	{
		cout << *it << " ";
	}
	cout << endl;

	vector<int>::reverse_iterator rit = v2.rbegin();
	while (rit != v2.rend())
	{
		cout << *rit << " ";
	}
	cout << endl;
	return 0;
}

💕 使用范围for遍历

int main()
{
	vector<int> v2;
	v2.push_back(1);
	v2.push_back(2);
	v2.push_back(3);
	v2.push_back(4);
	v2.push_back(5);
	for (auto e : v2)
		cout << e << " ";
	cout << endl;
	return 0;
}

当然范围for遍历并不是什么高深的语法，它的本质还是被替换成了迭代器进行遍历。

4. 容量操作及空间增长问题

💕 容量操作

这是vector中的容量操作的几个api接口，其中第二个max_size和shrink_to_fit是我们在之前学习string的时候没有见过的接口，其中max_size是返回这个容器中可以容纳的最多的元素的个数，这个接口我们一般都不会用。shrink_to_fit是让我们容器的容量减少到容器中元素的个数。因为缩容所消耗的代价是比较大的。一般都不会轻易缩容，所以这个接口我们一般也不会用。

最重要的两个接口还是reserve和rsize，reserve只用于扩容，不会改变size的大小，但是resize不仅会扩容，他还会改变size的个数。

💕 空间增长问题

对于不同的STL版本，他的扩容机制也是不同的。我们知道，vs下和g++分别用的是不同的STL版本，下面我们分别来看一下他们的扩容机制有什么不同。

//测试vector的默认扩容机制
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下的扩容机制：

g++下的扩容机制：

这里我们需要注意几点：

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问
题。
resize在开空间的同时还会进行初始化，影响size

5. 增删查改

push_back和push_back这两个接口我们在string中见过，表示的是尾插和尾删，这里我们不再细说。

find和swap

注意： 这里的find函数是算法库里的一个函数，而并非vector提供的接口。

这里需要提供一段迭代器区间，然后在后面跟上我们需要查找的元素，如果查找成功就返回他的迭代器，如果查找不成功，就返回end迭代器位置。

既然算法库里面已经有swap这个接口了，为什么在vector中还要再次设计一个呢？

其实这是因为算法库中的swap函数具有深拷贝的问题，深拷贝的代价是很大的，对于vector这样的类来说直接使用算法库里面的swap函数的拷贝代价太大，所以vector自己提供了一个自己的swap函数，其实vector中的swap函数的内部也是用了算法库中的swap。

insert和erase

这里的insert和erase和string也有所不同，string中的这两个接口在操作完成后会返回对象本身，但是在vector中则是操作完成后返回要插入或者删除的那个位置的迭代器。当然了，不光光是vector，STL中的所有容器的插入和删除接口都是这样设计的。

基本用法如下：

这里我们需要注意一点是：当我们删除一个元素的时候，删除位置的范围是【begin()，end()),但是当我们插入一个元素的时候，插入位置的范围是【begin()，end()】。

当然了，这里存在一种迭代器失效的问题，下面我们在模拟实现的时候再来细说。

6. vector二维数组

int main()
{
	//设置二维数组的行数和列数
	int row = 5, col = 5;
	
	//创建二维数组并初始化为全0
	vector<vector<int>> vv(row, vector<int>(col, 0));
	
	//获取二维数组的行数
	int size_row = vv.size();
	
	//获取二维数组的列数
	int size_col = vv[0].size();

	//插入列元素
	vv[0].push_back(100);
	
	//插入行
	vv.push_back(vector<int>(5, 1));
	
	//遍历二维数组
	for (size_t i = 0; i < vv.size(); i++)
	{
		for (size_t j = 0; j < vv[i].size(); j++)
		{
			cout << vv[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

二、vector的模拟实现

当我们在模拟实现vector容器之前，需要先来参考一下源码，主要是为了整体看一下库里面vector的底层实现逻辑。

那么我们应该如何参考源码呢？让我们完全看懂源码是不可能的，所以我们应该抓住重点核心来看，最重要的就是这个类的成员变量和核心的成员函数，下面我们来看一下我们在模拟vector之前需要关注的源码中的地方。

template <class T, class Alloc = alloc>
class vector
{
public:
	typedef T value_type;
	typedef value_type* iterator;
	typedef const value_type* const_iterator;
	//...
	size_type size() const { return size_type(end() - begin()); }
	size_type max_size() const { return size_type(-1) / sizeof(T); }
	size_type capacity() const { return size_type(end_of_storage - begin()); }
	iterator begin() {return start;}
	iterator end() {return finish;}
private:
	iterator start;
	iterator finish;
	iterator end_of_storage;
};

通过这一部分的源码我们可以看到vector中的三个成员变量是由三个迭代器实现的，在这里迭代器是一个原生指针。然后我们根据源码中的size()和capacity()等函数。可以推断出这三个指针所代表的意义：

start指向第一个元素的位置，finish指向容器中有效元素中最后一个元素后面的位置，end_of_storage指向容器能容纳最大容量之后的位置。其实和我们在C数据结构阶段实现的顺序表没有什么本质的区别，不过是使用了三个指针来维护所开辟的空间罢了。

1. 构造函数

💕 默认无参构造

//无参构造
vector()
	:_start(nullptr)
	,_finish(nullptr)
	,_end_of_storage(nullptr)
{}

💕 n个val构造

vector(size_t n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

我们在写构造函数的时候为了防止野指针的出现，需要在初始化列表中将三个指针全部初始化为空。为了减少频繁扩容所带来的消耗，可以先调用reserve函数预先开辟一块空间，然后依次将要初始化的对象进行尾插。这里我们可以要初始化的值val预先设定缺省参数，这里我们不能将缺省值设置为0，因为要初始化的对象可能是int类型、double类型、还有可能是一个自定义类型，所以这里我们可以将缺省值给定为一个T类型的匿名对象。

这里我们还需要注意的是：引用会延长匿名对象的生命周期到引用对象域结束，因为这里的val就是匿名对象的别名，如果匿名对象在当前行就之后就销毁的话，val也会被销毁。同时，因为匿名对象具有常性，所以我们需要用const来修饰val。

💕 迭代器区间构造

template <class InputIterator>		
vector(InputIterator first, InputIterator end)
	:_start(nullptr)
	,_finish(nullptr)
	,_end_of_storage(nullptr)
{
	while (first != end)
	{
		push_back(*first);
		first++;
	}
}

这里我们提供一个迭代器模板，可以提供任意类型的迭代器。

在提供以上的函数接口之后，如果我们尝试构造一个内容为5个10的对象时候，这里会出现间接寻址的错误，这是因为编译器在进行模板实例化以及函数参数匹配时会调用最匹配的那一个函数，当我们将T实例化为int之后，由于两个参数都是int，所以迭代器构造函数会直接将Inputlterator实例化为int，但是如果n个val构造来说，不仅需要将T实例化为int，还需要将第一个参数隐式转换为size_t；所以编译器会优先调用迭代器区间构造函数，直接对int类型解引用的话就会报错。

为了防止这种情况发生，我们可以采取和STL中一样的解决方式——重载一份第一个参数为int的构造函数。

vector(int n, const T& val = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

💕 拷贝构造

vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	_start = new T[v.capacity()];
	memcpy(_start, v._start, v.size() * sizeof(T));//——会导致浅拷贝问题
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();
}

2. 迭代器和基本接口

💕 迭代器的实现

为了能够使用范围for循环和其他别的功能，这里我们来实现一下vector的迭代器，同时，为了能够对const对象也使用迭代器，这里我们还需要设计一份const版本的迭代器。

typedef T* iterator;
typedef const T* const_iterator;
//迭代器的实现
iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}

const_iterator begin() const
{
	return _start;
}
const_iterator end() const
{
	return _finish;
}

💕 基本接口的实现

size_t size() const
{
	return _finish - _start;
}
size_t capacity() const
{
	return _end_of_storage - _start;
}
size_t empty() const
{
	return _start == _finish;
}
void clear()
{
	_finish = _start;
}
//析构函数
~vector()
{
	delete[] _start;
	_start = _finish = _end_of_storage = nullptr;
}

T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];
}
const T& operator[](size_t pos) const
{
	assert(pos < size());
	return _start[pos];
}

由于以上的接口比较简单，这里我们就不再做过多的解释。

3. reserve和resize

💕 reserve的实现

void reserve(size_t n)
{
	if (n > capacity())
	{
		int sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, size() * sizeof(T));
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

如果我们需要扩的容量的大小小于原来的容量时，我们默认不执行扩容操作。这里我们需要先定义一个临时变量sz将扩容之前的元素个数保存下来，因为扩容之后给finish赋值时，start已经指向了新的空间，但是finishi还未改变，所以直接使用size()会出现问题，当然了，在这个接口里面存在着一个严重的问题，我们到后面会指正。

💕 resize的实现

void resize(size_t n,T val = T())
{
	if (n < size())
	{
		//删除数据
		_finish = _start + n;
	}
	else
	{
		if (n > capacity())
		{
			reserve(n);
		}
		while (_finish != _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
}

这里我们和前面的构造函数一样，给一个匿名对象的缺省值，如果需要扩的容量比原来的容量小时，
我们只需要将容器中的有效的数据个数size()减少即可。否则的话，如果n的个数大于原来的容量时，我们可以先使用reserve函数将原来的空间扩大，然后再依次添加到finish之后即可。直到finish的大小等于capacity的大小。

4. push_back和pop_back

//push_back的实现
void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	*_finish = x;
	_finish++;
}

//pop_back的实现
void pop_back()
{
	assert(!empty());
	_finish--;
}

这两个接口的实现就非常简单了，push_back的实现，如果finish等于capacity容量的大小我们则需要先调用reserve函数进行扩容。当然在这里我们判断capacity的时候，需要特殊处理一下，因为如果第一次创建的未初始化的对象的capacity是0时，直接调用reverse(capacity)会出现问题。对于pop_back的实现我们还需要先实现一个判空操作的函数。

5. insert和erase

💕 insert

iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start && pos <= _finish);
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	*pos = val;
	_finish++;
	return pos;
}

这里的实现逻辑也很简单，先判断要插入的位置是否符合规范，在判断是否需要扩容，最后我们重后往前挪动数据即可。当然，最后别忘了finish需要++。

💕 erase

iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);
	iterator end = pos + 1;
	while (end < _finish)
	{
		*(end - 1) = *end;
		end++;
	}
	_finish--;
	return pos;
}

这里我们首先需要注意的是，pos位置不能等于finish，因为finish是最后一个有效元素的后一个位置，重前往后挪动数据。最后记得finish–。

5. 迭代器失效问题

💕 野指针问题

这里我们可以看到，当我们插入一个元素后，再次打印的时候就会出现问题，其实本质上还是我们的insert函数写的有问题。

这里我们修改一下insert函数，当需要扩容的时候先使用一个变量记录一下pos位置相对于第一个元素的位置，再扩容之后更新一下pos指针的位置。这样第一种迭代器失效的问题就得到解决了。

iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start && pos <= _finish);
	if (_finish == _end_of_storage)
	{
		int sz = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + sz;
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	*pos = val;
	_finish++;
	return pos;
}

💕 扩容之后pos位置的迭代器失效

这里我们可以看到在我们将某个位置插入一个数字后，迭代器可能会失效，因为是传值传递所以insert之后pos的地址可能已经发生改变了，所以insert之后，默认pos迭代器失效了的，因为不知道哪一次会进行扩容操作。所以insert之后的我们需要用pos接受一下就可以解决这种问题。

vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);

func(v2);
auto pos = find(v2.begin(), v2.end(), 3);
if (pos != v2.end())
{
	pos = v2.insert(pos, 100);
}
(*pos)++;
func(v2);

💕 erase之后默认迭代器失效

其实不仅仅是insert，erase之后迭代器也会失效，下面我们来看一下erase之后迭代器失效的问题，这里我们先来举三个例子——删除一个序列中所有的偶数。

为什么同样的代码当数据不同时会出现截然不同的结果呢？

第一份代码能够运行出正确的结果完全是一个偶然。可以看到，第二份代码由于删除元素后 pos 不再指向原位置，而是指向下一个位置，所以 erase 之后会导致一个元素被跳过，导致部分偶数没有被删除，但好在末尾是奇数，所以程序能够正常运行。
但是最后一份代码就没那么好运了，由于最后一个元素是偶数，所以 erase 之后 pos 直接指向了 _finish 的下一个位置，循环终止条件失效，发生越界。

所以，我们统一认为 insert 和 erase 之后迭代器失效，必须更新后才能再次使用。

那么正确的做法就是当每次插入或者删除数据后都是用pos来接受一下。更新一下pos位置的数据，如果没有插入或者删除数据，则直接pos++即可。

	auto it2 = v3.begin();
	while (it2 != v3.end())
	{
		if (*it2 % 2 == 0)
		{
			it2 = v3.erase(it2);
		}
		else
		{
			it2++;
		}
	}
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;

5. 浅拷贝问题

💕 拷贝构造问题

//拷贝构造
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	_start = new T[v.capacity()];
	memcpy(_start, v._start, v.size() * sizeof(T));//——会导致浅拷贝问题
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();
}

这份代码在我们看来并没有什么问题，但其实它存在一个隐藏的问题，当我们实例化的对象是内置类型时，并不会发生浅拷贝，但是如果我们实例化的对象是自定义类型时，特别是自定义类型的对象中有资源分配的时候，这份代码就会导致严重的问题。

当我们的vector中的元素是string类型时，直接这样写就会导致浅拷贝问题，这里我们来看一下原因。

在这里我们确实是开辟了一块新的空间，同时也将原来对象中的数据拷贝到了新的空间中，但是由于这个对象是一个string字符串类型，直接使用memcpy进行拷贝是按照字节进行了拷贝，也就是说两个对象中的vector中的string中的_str同时指向了一块空间，所以最后调用自定义类型的析构函数时，同一块空间会被析构两次。最后程序奔溃。

正确的写法：

vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	_start = new T[v.capacity()];
	for (size_t i = 0; i < v.size(); i++)
	{
		_start[i] = v._start[i];
	}
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();
}

💕 reserve问题

//reserve扩容
void reserve(size_t n)
{
	if (n > capacity())
	{
		int sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, size() * sizeof(T));
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

这份代码和上面的代码的原因大同小异，也是因为memcpy会带来浅拷贝问题，下面我们来看一个例子：当我们大量插入元素的时候，会导致扩容的出现，那么扩容又会带来什么样的问题呢？

当在push_back内部调用 reserve 函数进行扩容时，扩容时我们虽然进行了深拷贝，但是空间里面的内容我们是使用 memcpy 按字节拷贝过来的，这就导致原来的 v 里面的 string 元素和临时空间里面的string元素指向的是同一块空间。所以当拷贝完数据就会delete掉原来的空间，由于二者指向的是同一块空间，所以现在v中的string元素指向的是一块已经被释放掉的空间，当最后出了作用域调用析构的时候就会出现问题。