【C++笔记】C++STL vector类模拟实现

一、实现模型和基本接口

实现模型我们选择模拟库中的模型——使用三个指针来管理数据：

template<calss T>
class Vector {
public :
	// Vector迭代器
	typedef T* iterator;
private :
	iterator _start; // 指向数据块起始位置
	iterator _finish; // 指向有效数据结束位置
	iterator _end; // 指向存储容量结尾位置
};
1
2
3
4
5
6
7
8
9
10

只不过这里是把指针重定义成了迭代器，因为vector本质就是一个数组，所以vector的迭代器也是使用原生指针即可。
这三个指针的指向如下：

_start就是指向的数据段开始位置，但是_finish却是只指向的最后一个有效数据的下一个位置，这也是为了之后我们插入数据的时候更方便，也符合了迭代器的要求。因为现在大多的迭代器都是左闭右开的，所以当我们要返回迭代器的结束位置end时我们就可以直接返回_finsh，然后当迭代器变量==end时我们的遍历就完成了。
同理，_end也类似这样。

1.1、各种构造和析构

无参构造
当我们需要创建一个vector对象而不清楚它具体要求存储多少个数据的时候，就可以先使用无参构造。
无参构造其实很简单啦，就是将三个指针却都初始化成空指针即可：

Vector() 
	:_start(nullptr)
	,_finish(nullptr)
	,_end(nullptr)
{
}
1
2
3
4
5
6

以n相同值初构造

Vector(size_t n, const T& val = T()) {
	// 申请空间
	T* temp = new T[n];
	// 插入数据
	for (size_t i = 0; i < n; i++) {
		temp[i] = val;
	}
	_start = temp;
	_finish = temp + n;
	_end = _finish;
}
1
2
3
4
5
6
7
8
9
10
11

我们直接申请一段长度为n的新空间，然后再将要初始化的值依次插入进去即可。
由于这里使用到了模板，也就是说构造函数并不知道我们要存储的值具体是什么类型，所以我们这里val的值就可以使用一个匿名对象。

还有一点需要注意的是，我们这里的插入数据并不能直接使用memcpy。
memcpy对内置类型是没什么影响的，但是对于一些自定义类型特别是有指向额外空间的自定义类型，直接使用memcpy就会导致浅拷贝的问题。
就拿string类来举例子：

如上图，每个string对象中的_str都会指向一块额外申请的char的空间。如果我们直接使用memcpy进行拷贝的话，它就会将_str的值原封不动而拷贝过去，这样就是的新的空间和旧的空间都指向了相同的char空间，这样当程序结束调用析构函数的时候就会对同一段char*空间释放两次，这样程序就崩溃了。

所以我们这里使用的是依次使用赋值的方式就行拷贝，因为库中的自定义类型是一定重载了赋值运算符的，也一定是进行深拷贝的。

以一段迭代器区间构造
有时候我们可能想要用一个同类型对象的一段区间来初始化另一个同类型对象，但对象中的成员又都是私有的，我们不能直接访问，但我们可以使用迭代器啊。
所以也就有了迭代器区间构造的方式。
这个其实听起来很复杂，但实现起来就很简单了，因为迭代器肯定是支持++操作的，所以我们就直接让起始的迭代器一直++然后对迭代器解引用，像上面的构造一样依次将数据插入新空间即可：

template <class InputIterator>
Vector(InputIterator first, InputIterator last) {
	// 开空间
	T* temp = new T[last - first];
	// 插入数据
	int i = 0;
	while (first < last) {
		temp[i] = *first;
		first++;
		i++;
	}
	_start = temp;
	_finish = _end = temp + i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

拷贝构造
拷贝构造的逻辑其实也和上面那些构造的逻辑差不多：

Vector(const Vector<T>& v) {
	// 申请新空间
	T* temp = new T[v.capacity()];
	// 拷贝数据
	int i = 0;
	for (auto it : v) {
		temp[i] = it;
		i++;
	}
	_start = temp;
	_finish = _start + v.size();
	_end = _start + v.capacity();
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里用到的范围for需要我们实现了迭代器起始和结束才行，并且是const迭代器。
析构函数
析构函数我们只需要释放_start即可：

~Vector() {
	delete[] _start;
	_start = _finish = _end = nullptr;
}
1
2
3
4

1.2、迭代器

迭代器我们需要实现非const和const版本的：

// Vector迭代器
typedef T* iterator;
// const版本
typedef const T* const_iterator;
1
2
3
4

然后起始位置我们就直接返回_start即可，结束位置我们返回_finish即可：

// 迭代器起始位置
	iterator begin() {
		return _start;
	}
	// 迭代器结束位置
	iterator end() {
		return _finish;
	}

	// cosnt版本迭代器起始位置
	const_iterator begin() const {
		return _start;
	}
	// const版本迭代器结束位置
	const_iterator end() const {
		return _finish;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

返回长度
计算长度我们直接使用指针相减即可，即_finish - _start:

size_t size() const {
	return _finish - _start;
}
1
2
3

返回容量
容量即_end - _start:

size_t capacity() const {
	return _end - _start;
}
1
2
3

二、各种插入和删除接口

2.1、插入接口

扩容
一样的，正式插入之前我们都需要检查扩容，所以我们先来看看扩容的实现。
这里的扩容并不是直接申请新空间在拷贝数据这么简单了，因为使用的是三个指针来管理数据，所以我们需要时刻关注指针的变化。

如果你觉得这里的扩容只是简单的申请一个新空间然后拷贝数据，再让_start指向新的空间，那你就犯大错了：

不要忘了，这里是三个指针啊，如果只是像上图这样处理那_finsh和_end的指向都没变化：

之后在遍历的时候插入数据的时候是一定会出问题的。

所以我们需要先保存原来数据段中，_finish相对_start的偏移量，在_start指向新空间之后就可以加上这个偏移量，这样就更新了_finish的正确位置了。

void reverse(size_t newCapacity) {
	if (newCapacity > capacity()) {
		// 保存原来的偏移量
		size_t offset = size();
		// 申请新空间
		T* temp = new T[newCapacity];
		// 拷贝数据
		int i = 0;
		for (auto it : *this) {
			temp[i] = it;
			i++;
		}
		// 释放原来的空间
		delete[] _start;
		_start = temp;
		_finish = _start + offset;
		_end = _start + newCapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

尾插
因为_finish指向的就是最后一个有效数据的下一个位置，所以尾插要做的就是在_finish位置放上要插入的数据然后再让_finish++即可：

void push_back(const T& val) {
	// 检查扩容
	if (size() == capacity()) {
		reverse(capacity() == 0 ? 4 : 2 * capacity());
	}
	*_finish = val;
	_finish++;
}
1
2
3
4
5
6
7
8

随机插入
在pos位置插入一个数据，并返回新插入的值的位置。
随机插入除了要检查扩容之外，还需要检查pos位置是否合法，也就是pos位置不能大于end()（等于end()就变成了尾插）。
那为什么要返回新插入的值的位置呢？
因为如果发生了扩容，那pos位置就失效了。

iterator insert(iterator pos, const T& val) {
	assert(pos <= end());
	size_t offset = pos - _start;
	// 检查扩容
	if (size() == capacity()) {
		reverse(capacity() == 0 ? 4 : 2 * capacity());
	}
	// 更新pos
	pos = _start + offset;
	iterator end = _finish - 1;
	// 挪动数据
	while (end >= pos) {
		*(end + 1) = *end;
		end--;
	}
	*pos = val;
	_finish++;
	return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.1、删除接口

尾删
尾删就更简单了，直接让_finish–即可，但是还要注意当vector为空时候就不能再删了，所以我们先要进行判空：

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

void pop_back() {
	assert(!empty());
	_finish--;
}
1
2
3
4

随机删除
删除pos位置的数据，并返回删除位置的下一个元素在删除后的位置。
随机删除判断pos位置是否合法就和insert不一样了，这里的判断是pos不能大于等于end()，因为end()即是_finish，而_finish指向的是最后一个有效数据的下一个位置，这个位置并不是有效数据的位置。
然后然后我们就直接挪动后面的数据进行覆盖即可：

iterator erase(iterator pos) {
	assert(!empty());
	assert(pos < end());
	iterator begin = pos;
	// 挪动数据
	while (begin < end() - 1) {
		*begin = *(begin + 1);
		begin++;
	}
	_finish--;
	return pos + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3、resize接口

resize接口其实和string的resize逻辑是一样的：

void resize(size_t newLen, const T& val = T()) {
	if (newLen > size()) {
		if (newLen > capacity()) {
			// 扩容
			reverse(newLen);
		}
		// 填充数据
		while (_finish < (_start + newLen)) {
			*_finish = val;
			_finish++;
		}
	}
	_finish = _start + newLen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、运算符重载

3.1、方括号运算符重载

方括号运算符重载也是要实现非const和const版本的，还有不要忘了判断下标的合法性：

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

	const T& operator[](size_t pos) const {
		assert(pos < size());
		return _start[pos];
	}
1
2
3
4
5
6
7
8
9

3.2、赋值运算符重载

赋值运算符重载其实和拷贝构造差不多，只不过我们这里是赋值，所以我们需要释放掉原来的空间：

Vector<T>& operator=(const Vector<T>& v) {
	// 申请新空间
	T* temp = new T[v.capacity()];
	// 拷贝数据
	int i = 0;
	for (auto it : v) {
		temp[i] = it;
		i++;
	}
	if (_start) {
		// 释放原来的空间
		delete[] _start;
	}
	_start = temp;
	// 这里并没有释放掉v的空间，所以偏移量我们直接加上v的size即可
	_finish = _start + v.size(); 
	_end = _start + v.capacity();
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19