C++之STL中vector模拟实现

前言

上一篇文章给大家讲了关于库中的vector的一些使用方法，但是其实只知道它如何使用还远远不够，我们只有在尝试自己实现了一下以后才能了解其中的更多细节，这样也会让我们更好地去使用vector容器。

一、vector基本结构

知道他的底层结构后，就能更容易的将其模拟实现出来了，下面我们一起来看看吧。

二、定义vector结构及实现析构函数

template
class vector
{
public:
	//因为析构函数很简单，所以就一起放在这里了
	~vector()//析构函数
	{
		delete[] _start;
		_start = _finish = _end_of_storage;
	}
private:
	iterator _start;//顺序表的头
	iterator _finish;//顺序表有效元素的下一个位置
	iterator _end_of_storage;//顺序表的末尾
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、构造函数

在这里我会实现三种构造函数，但是其中有的构造函数需要用到我们后面实现的函数，所以在这里简单的给大家先说一下。
push_back(): 尾插
reserve(): 扩容(增大capacity())

//构造函数1:
vector()
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{}
1
2
3
4
5
6

这个构造函数非常简单，大家也一定都知道是什么意思，所以我就不多说的，我们直接看下面的。

//构造函数2:
//用n个val值来构造vector
vector(size_t n, const T& val = T())//匿名对象
//因为我们实现的是一个模板类，所以我们也不知道传进来的数据是什么类型的，可以使用匿名对象对val进行初始化
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);//扩容
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);//尾插
	}
}
/
//在C++的函数库中重载了一个构造函数，解决构造函数3中模板出现的问题
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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//构造函数3:
template//模板
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last)
	{
		push_back(*first);//尾插
		first++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这个构造函数是通过传指针来进行构造，因为我们不知道传入的指针的类型，所以还需要定义一个模板。

---

你以为到了这里就结束了么？其实不是的，构造函数二和构造函数三在定义对象的时候会造成很大的麻烦。来看下面的例子。

这里很明显报出了错误，而且在编译的时候就无法通过，说明出现了语法错误，那这个到底是怎么回事呢？我们一起来分析一下。

四、拷贝构造函数

这里的拷贝构造有两种写法，我们将其称为老式写法与现代写法。
我们会依次对两种写法进行实现，其实只是听名字就能感觉到两种写法的差距很大，让我们一起来看看吧。

//拷贝构造老式写法
vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
//先开辟出与传入的对象同样大小的空间
	_start = new T[v.size()];
//利用memcpy函数将传入的对象的数据拷贝到新对象中
	memcpy(_start, v._start, v.size() * sizeof(T));
	_finish = _start + v.size();
	_end_of_storage = _start + v.size();
}
//
//拷贝构造现代写法
vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
//这里还要用到我们之前利用迭代器写的构造函数3
	vector tmp(v.begin(), v.end());
	swap(tmp);
}

//我在这里先将swap()的实现告诉大家，让大家更好的理解现代拷贝构造，同时也可以理解其强大之处
void swap(vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

swap()函数只是单纯的将两个对象中的指针变量数值进行交换，但是在现代拷贝构造函数中发挥着很重要的作用。
我们提前创建的对象tmp其实就是一个打工人，将我们需要的数据对其进行写入以后，让它和我们初始化的空指针进行交换，就很简单的实现了拷贝构造，最后在函数退出的时候局部变量tmp就会被销毁，我们也不需要额外的操作去控制它。

---

你以为到这里就结束了么？？？其实远远没有，老式拷贝构造函数其实是存在问题的，这里就涉及到了深浅拷贝的问题，在前一篇文章中我们已经学会了vector基本的使用方法，下面通过一道题来给大家讲解一下关于这里的深浅拷贝的问题。

既然问题已经分析清楚了，那么我们就可以想办法来解决了，因为我们这里调用的是老式拷贝构造写法，所以先对它进行修改。

//拷贝构造老式写法改造
vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	_start = new T[v.size()];
	//memcpy(_start, v._start, v.size() * sizeof(T));
	//不用memcpy进行拷贝
	//memcpy会涉及到vector>类型的深拷贝问题，所以需要依次赋值
	for (size_t i = 0; i < v.size(); i++)
	{
		_start[i] = v._start[i];
	}
	_finish = _start + v.size();
	_end_of_storage = _start + v.size();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

既然老式方法的问题已经解决了，那么现代方法是不是也存在类似的问题呢？？其实是的，但是这个问题与我们后面所写的reserve()函数有关系，因为我们在利用迭代器区间调用构造函数的时候，会进行尾插入数据的操作，这里就会涉及到扩大原对象容量的问题，所以我会在reserve()模块进行讲解。

五、迭代器

在前面讲述vector的使用的时候我们就提到了，vector的迭代器其实就是原生态指针T*，因此在这里我们可以直接将 T* typedef为iterator，以const修饰的对象我们还要给出const T*，所以我们将其typedef为const_iterator。

typedef T* iterator;//普通迭代器
typedef const T* const_iterator;//const迭代器
//因为这几个函数的实现十分简单，所以就一起写出来了
//普通接口
iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
//const接口
const_iterator begin() const
{
	return _start;
}
const_iterator end() const
{
	return _finish;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

六、空间操作

1.获取有效数据size()

这里的size()获取的数据就是我们已经定义的对象中的有效元素的数量

//普通接口
size_t size()
{
	return _finish - _start;
//我们C语言中的指针阶段可知，两个指针相减就可以获取二者间元素的数量
}
//const接口
size_t size()
{
	return _finish - _start;
}
1
2
3
4
5
6
7
8
9
10
11

2.resize()改变对象中有效元素size()的值

n为调用函数后对象中元素数量的个数
1.若n > 原size()
val则为在原来空间的基础上在末尾元素后插入的值。
2.若n< 原size()，val无效

void resize(size_t n, const T& val = T())
{
	if (n > capacity())
		reserve(n);//扩容
	if (n > size())
	{
		while (_finish < _start + n)
		{
		//n > 原size()，则插入n个val
			*_finish = val;
			_finish++;
		}
	}
	//n < 原size(),则直接缩小size()
	else
	{
		_finish = _start + n;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.capacity(),获取数据容量

与size()的实现类似，直接让两个指针相减即可

size_t capacity()//普通接口
{
	return _end_of_storage - _start;
}

size_t capacity() const//const接口
{
	return _end_of_storage - _start;
}
1
2
3
4
5
6
7
8
9

4.empty()判空函数

判断vector是否为空
十分简单，只需要判断_start与_finish是否相等就可以了。

bool empty()
{
	return _start == _finish;
}
1
2
3
4

5.reverse()增大vector的容量

通过前面对STL库中vector的讲解，我们知道vector有插入数据的操作，既然要插入数据，那么就需要开辟空间，我们在刚开始创建一个对象的时候，默认开辟的容量一定是比较小的，因为如果开辟空间很大的话，你插入的元素个数却很少，那么多开出来的空间就都被浪费了，所以reserve()这个增大容量的函数是一定要有的，并且在模拟实现它的时候也是一个难点。我们一起来看看吧。

//原reserve()函数
void reserve(size_t n)
{
//n > 原capacity()，则扩容，n < 原capacity(),不做任何操作
	if (n > capacity())
	{
		size_t sz = size();//记录原来已有元素的个数，为后续操作做准备
		T* tmp = new T[n];//先开辟一块空间
//如果_start不为空的话，说明以前的对象是有数据的，所以我们要把原对象的数据都拷贝过来。若为空的话，我们就只开辟空间就可以了。(这里的判断很重要)		
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * sz);//拷贝数据
			delete[] _start;//释放原来的空间
		}
		_start = tmp;//移交空间
		_finish = _start + sz;//更新数据
		_end_of_storage = _start + n;//更新数据
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

看到这里大家是否还记得我们上面的拷贝构造函数的现代写法中遗留问题？
有了对老式写法的分析，相信大家在这里一眼就能看我们的reserve存在什么问题。
没错，就是memcpy(),如果是类似于vector>这样形式的对象，其内部的数据还是会进行浅拷贝，那么最后也会出现程序崩溃的结果。所以我们这里只需要把reserve()函数内部拷贝数据部分的代码进行简单的修改就可以了。

//修改后的reserve()函数
void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy会涉及到vector>类型的深拷贝问题，所以要依次赋值
			//memcpy(tmp, _start, sizeof(T) * sz);
			for (size_t i = 0; i < sz; i++)
			{ 
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6.swap()交换数据

这里只是单纯的将两个对象中的指针变量数值进行交换。

void swap(vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}
1
2
3
4
5
6

七、数据操作

1.尾插push_back()

void push_back(const T& x)
{
//容量不够要进行扩容，同时还要考虑到最开始没有数据的时候，两个指针也是相等的。
//所以我们还需要判断如果capacity()为0的话，需要自己先给定一个初始空间的大小，我们这里以4作为初始空间大小
	if (_finish == _end_of_storage)
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	*_finish = x;
	_finish++;
}
1
2
3
4
5
6
7
8
9

2.尾删pop_back()

void pop_back()
{
//这里最重要的一点就是要判断该对象中是否有数据可以删除
	assert(_finish > _start);
	_finish--;
}
1
2
3
4
5
6

3.某一个位置插入insert()

iterator insert(iterator pos, const T& x)
{
	//先判断给定地址的合理性
	assert(pos >= _start);
	assert(pos <= _finish);
	//数据满了要进行扩容
	if (_finish == _end_of_storage)
	{
		//如果要进行扩容的话，需要提前记录pos与_start之间的数据的多少，
		//因为扩容以后_start会发生改变，此时pos对应的位置也无效(指针失效)
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		pos = _start + len;//重新给pos原来的位置
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		//进行数据的挪动
		*(end + 1) = *end;
		end--;
	}
	//为pos(即要插入的位置)赋值	
	*pos = x;
	_finish++;

	return pos;//返回值为新插入的数据的位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4.删除某一个位置的值erase()

这里我先给大家一个经常出现的代码，下面这个代码是不支持大家去使用的，为什么要给他呢，因为我们要将其与正确的代码进行一下对比，这样也有利于大家对代码的理解。正确的代码就在分析完迭代器失效问题模块的后面

void erase(iterator pos)
{
	iterator begin = pos + 1;
	while (begin < _finish)
	{
		*(begin - 1) = *begin;
		begin++;
	}
	--_finish;
}
1
2
3
4
5
6
7
8
9
10

---

关于insert()与erase()两个函数，其实并不是只有这几行代码这么简单，他们还涉及到了迭代器失效的问题。

5.迭代器失效问题

1.insert()迭代器失效问题

处理办法:
既然已经知道了这里可能会出现的错误，那么我们在以后插入数据后不管要不要进行扩容的操作，都不要再去访问it位置的数据，再想访问的话可以再次调用find()函数去寻找他的位置。

2.erase()迭代器失效问题及erase()的正确定义

(1)迭代器失效问题分析

在研究迭代器失效问题中我会通过三个例子来向大家演示问题。

(2)erase()的正确定义

由于以上情况的出现，所以STL库中在实现erase()函数的时候，要有返回值iterator，这样就很好的解决了这一块的问题。

// stl 规定erase返回删除位置下一个位置迭代器
//说是下一个位置，其实返回的还是删除数据的位置，因为后面的数据会向前移动，所以下一各元素的位置就在pos。
iterator erase(iterator pos)
{
	iterator begin = pos + 1;
	while (begin < _finish)
	{
		*(begin - 1) = *begin;
		begin++;
	}
	--_finish;
	return pos;
1
2
3
4
5
6
7
8
9
10
11
12

八、以[]的形式访问数据

//普通接口
T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];
}
//const接口
const T& operator[](size_t pos) const
{
	assert(pos < size());
	return _start[pos];
}
1
2
3
4
5
6
7
8
9
10
11
12

九、=赋值操作

vector& operator=(vector v)
{
	swap(v);
	return *this;
}
1
2
3
4
5

总结

到这里关于vector的模拟实现就已经结束了，在模拟实现vector时主要的难点就是迭代器失效的问题，别的相信大家还是很容易理解的，大家看完以后可以尝试自己去实现一下相对应的函数，然后再认真的分析一下迭代器失效的问题，相信大家一定能从中学习到新的知识。
如果大家觉得我的文章有用的话，那就给一波三连吧，你们的支持就是我写下去的最大的动力，谢谢大家。