C++vector模拟实现

vector官方库实现的是一个模板类，因此我们也写个模板类。
在前面模拟实现过string类，string和vector都是动态增长的数组，有点类似。

vector把这个三个成员变量都换成了指针。

template<class T>
class Vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;

private:

	iterator _start;
	iterator _finish;
	iterator _endofstorage;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

1.构造函数

	//第一种无参构造
	Vector()
		:_start(nullptr)
		,_finish(nullptr)
		,_endofstorage(nullptr)
	{}
1
2
3
4
5
6

	//第二种构造
	Vector(size_t n, const T& val = T())
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstorage(nullptr)
	{
		//扩容
		if (_finish == _endofstorage)
		{
			//因为这里没有size,capacity所以自己写个size，capacity
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
		}
		while (n--)
		{
			push_back(val);
		}
	}

	
	void reserve(size_t n)
	{
		if (n > capacity())
		{
			T* tmp = new T[n];
			//_start不为nullptr再拷贝
			if (_start)
			{
				memcpy(tmp, _start, sizeof(T) * size());
				delete[] _start;
			}
			_start = tmp;
			_finish = _start + size();
			_endofstorage = _start + n;
		}
	}

	size_t size() const
	{
		//指针减指针等于元素个数
		return _finish - _start;
	}
	
	size_t capacity() const
	{
		return _endofstorage - _start;
	}
	
	void push_back(const T& val = T())
	{
		//扩容
		if (_finish == _endofstorage)
		{
			//因为这里没有size,capacity所以自己写个size，capacity
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
		}
		*_finish = val;
		++_finish;
	}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

写完一段代码先测试测试，看看有没有错误。

这里的_finish报错了，调试一下找原因。如果不能确定到底是哪里错误，就一段一段屏蔽代码，这里我们最终确定是扩容出现了问题。

我们开辟空间之后，_finish还指向nullptr，也就是根本没有更新_finish的位置。

	void reserve(size_t n)
	{
		if (n > capacity())
		{
			//记录_finish的相对位置
			int Oldsize = size();
			T* tmp = new T[n];
			//_start不为nullptr再拷贝
			if (_start)
			{
				memcpy(tmp, _start, sizeof(T) * size());
				delete[] _start;
			}
			_start = tmp;
			//对_finish特殊处理。
			//_finish=_start+_finish-_start导致的错误。
			//_finish = _start + size();
			_finish = _start + Oldsize;
			_endofstorage = _start + n;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这样写，也防止了_start本身有空间，然后异地扩容，_finish位置不对的情况。

这里的reserve内部memcpy还有一个浅拷贝的问题，等最后说到这个成员函数再具体谈。

	//第三种扩容
	template <class InputIterator>
	Vector(InputIterator first, InputIterator last)
		:_start(nullptr)
		,_finish(nullptr)
		,_endofstorage(nullptr)
	{
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}
	
	iterator begin() const
	{
		return _start;
	}

	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
22
23

注意看图片的对比，右边没有屏蔽第二种构造函数，竟然报错了。

把1换成字符‘c’就不报错了。

其原因是因为10，1都是int类型，走的是模板参数的构造。
不是走的Vector(size_t n, const T& val = T())，因为int转换成size_t涉及算术转换。
而Vector(InputIterator first, InputIterator last) 这里都是同一类型，所以编译器会选择模板。
这里和库的解决方法一样，在加一个Vector(int n, const T& val = T())。
这样由于由现成的，编译器就不再会走模板了。

Vector(int n, const T& val = T())
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstorage(nullptr)
	{
		//扩容
		if (_finish == _endofstorage)
		{
			//因为这里没有size,capacity所以自己写个size，capacity
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
		}
		while (n--)
		{
			push_back(val);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.拷贝构造

在string模拟实现，拷贝构造实现了现代写法，是比较方便的，我们这里就继续用起来。

void swap(Vector<T> x)
	{
		//这里调用的是库里面swap,关于这里可以看看string类模拟实现
		std::swap(_start, x._start);
		std::swap(_finish, x._finish);
		std::swap(_endofstorage, x._endofstorage);
	}
	
	Vector(const Vector<T>& val)
		:_start(nullptr)
		,_finish(nullptr)
		,_endofstorage(nullptr)
	{
		Vector<T> tmp(val.begin(), val.end());
		//这里调用的是自己写的swap，如果直接用库里面的就会调用构造和拷贝构造。
		swap(tmp);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.析构+赋值运算符重载

	~Vector()
	{
		delete[] _start;
		_start = _finish = _endofstorage = nullptr;
	}

	//赋值运算符重载现代写法
	//v1=v2
	//v1=v1  虽然这里没有判断，但是很少有人会自己给自己赋值
	//即使赋值了，也是使用了一次拷贝构造
	Vector<T>& operator=(Vector<T> val)
	{
		swap(val);
		return *this;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.iterator

	iterator begin() const
	{
		return _start;
	}
	const_iterator begin() const
	{
		return _start;
	}

	iterator end() const
	{
		return _finish;
	}

	const_iterator end() const
	{
		return _finish;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.modifiers

5.1push_back

void push_back(const T& val = T())
	{
		//扩容
		if (_finish == _endofstorage)
		{
			//因为这里没有size,capacity所以自己写个size，capacity
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
		}
		*_finish = val;
		++_finish;
	}
1
2
3
4
5
6
7
8
9
10
11
12

5.2pop_back

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

5.3empty

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

5.4insert

	void insert(iterator pos, const T& val)
	{
		assert(pos >= _start);
		assert(pos < _finish);
		//扩容
		if (_finish == _endofstorage)
		{
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
		}
		iterator begin = end();
		while (begin > pos)
		{
			*begin = *(begin - 1);
			--begin;
		}
		*pos = val;
		++_finish;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这样写就没有问题了吗？
测试一下看看。

发现和我们预想的结果不一样，分析一下，找原因

请问pos，在扩容之后应该在哪里呢？

这里是迭代器失效：野指针问题。
扩容导致，插入pos位置还是原空间的位置。
解决方法：
更新pos的位置。

	void insert(iterator pos, const T& val)
	{
		assert(pos >= _start);
		assert(pos < _finish);
		//扩容
		if (_finish == _endofstorage)
		{
			//记录pos的相对位置
			size_t n = pos - _start;
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
			//更新pos
			pos = _start + n;
		}
		iterator begin = end();
		while (begin > pos)
		{
			*begin = *(begin - 1);
			--begin;
		}
		*pos = val;
		++_finish;

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.5erase

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

在来测试一下。

发现自己实现的vector没报错，库里面的vector，删除it位置，然后再读it位置，就报错了。这是也是因为迭代器失效问题。

再看看linux环境下同样代码是上面情况。


linux环境下读it位置可以再次读，说明这个位置没有失效。

那么erase删除位置到底失效不失效呢？

erase删除it位置，失效不失效，由编译器自己决定。

再看这样一种情况。

两个平台出现不一样的结果，为了代码能够再不同平台都能正常运行。所以，

erase，删除it位置元素，统一认为it失效了。it就不能再读写访问了，更新it才能继续访问，所以erase返回被删元素的下一个位置

更新了lt位置，就不会报错了。

正确写法。

	iterator erase(iterator pos)
	{
		assert(pos < _finish);
		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

5.6swap

	void swap(Vector<T>& x)
	{
		std::swap(_start, x._start);
		std::swap(_finish, x._finish);
		std::swap(_endofstorage, x._endofstorage);
	}
1
2
3
4
5
6

6.Capacity

6.1size

	size_t size() const
	{
		//指针减指针等于元素个数
		return _finish - _start;
	}
1
2
3
4
5

6.2capacity

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

6.3reserve

void reserve(size_t n)
	{
		if (n > capacity())
		{
			//记录_finish的相对位置
			int Oldsize = size();
			T* tmp = new T[n];
			//_start不为nullptr再拷贝
			if (_start)
			{
				memcpy(tmp, _start, sizeof(T) * size());
				delete[] _start;
			}
			_start = tmp;
			//对_finish特殊处理。
			//_finish=_start+_finish-_start导致的错误。
			//_finish = _start + size();
			_finish = _start + Oldsize;
			_endofstorage = _start + n;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6.4resize

resize有三种情况；
n size() n>capacity()；扩容+插入元素

void resize(size_t n, const T& val=T())
	{
		if (n > size())
		{
			//这里在reserve已经判断过了是否扩容
			reserve(n);
			//插入数据
			while (_finish < _start + n)
			{
				*_finish = val;
				++_finish;
			}
		}
		else
		{
			_finish = _start + n;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6.5empty

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

7.Element access

7.1operator[]

	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
10
11

7.2at

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

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

剩下接口比较简单，这里就不再模拟实现了。

8.在谈reserve

在谈reserve之前，做一道LeetCode的题
118. 杨辉三角

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);

        for(int i=0;i<vv.size();++i)
        {
            vv[i].resize(i+1);
            //放数据
            for(int j=0;j<vv[i].size();++j)
            {
                if(j == 0 || j ==  vv[i].size()-1)
                {
                    vv[i][j]=1;
                }
                else
                {
                    vv[i][j]=vv[i-1][j-1]+vv[i-1][j];
                }
            }
        }

        return vv;
    }
};
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

注意这道题，vector < T > ,T是自定义类型，不是内置类型；我们用自己写的vector来跑一下类似的代码，看看有没有什么问题。

void test_Vector4()
{
	Vector<Vector<int>> vv;
	Vector<int> v(5, 1);
	vv.push_back(v);
	vv.push_back(v);
	vv.push_back(v);
	vv.push_back(v);
	vv.push_back(v);


	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;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

为什么会有随机值的出现呢？
画图分析。

原因在于，reserve中memcpy拷贝的时候是浅拷贝，delete[ ] _start会把原有空间给释放掉了，所以出现随机值问题，

解决方法：浅拷贝换成深拷贝。

void reserve(size_t n)
	{
		if (n > capacity())
		{
			//记录_finish的相对位置
			int Oldsize = size();
			T* tmp = new T[n];
			//_start不为nullptr再拷贝
			if (_start)
			{
				//浅拷贝
				//memcpy(tmp, _start, sizeof(T) * size());
				//深拷贝
				for (size_t i = 0; i < Oldsize; ++i)
				{
					tmp[i] = _start[i];
				}
				delete[] _start;
			}
			_start = tmp;
			//对_finish特殊处理。
			//_finish=_start+_finish-_start导致的错误。
			//_finish = _start + size();
			_finish = _start + Oldsize;
			_endofstorage = _start + n;
		}
	}
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

自此关于vector类模拟实现结束了。里面有很多值得多多思考的东西，希望能给你带来一份收获，喜欢的小伙伴，点赞，评论，收藏+关注！下篇博文再见！