vector模拟(C++)和注意问题

关于vector的模拟首先根据原码可以看出vector的成员并不是像string类的一个指针加一个size和一个capacity。
而是三个指针，_start , _finish , _endofstorage.

所以size和capacity也是很容易计算得到，让_finish - _start就是size，_endofstorage - _start就是capacity。

迭代器框架和成员变量

namespace xzj
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin()
		{
			return _start;
		}
		const_iterator begin() const
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator end()const
		{
			return _finish;
		}
    private:
		iterator _start;//指向内存块的开始位置
		iterator _finish;//指向最后一个元素的下一个位置
		iterator _endofstorage;//指向最后一个有效空间的下一个位置
	};
}
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

为了实现存储任意类型的元素，这里使用了模板参数。

基础成员函数

//构造and析构
		vector()
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstorage(nullptr)
		{}

		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_endofstorage = _start + v.capacity();
		}
			
		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{ 
			while (n--)
				push_back(val);
		}

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

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		~vector()
		{
			if (_start)
				delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
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

关于string类的构造这里使用的是循环赋值，可能有人会使用memcpy，再某些情况下memcpy赋值是没有问题的，但是有时候会出现问题，后面会提到。

第四个构造函数是使用迭代器区间来构造一个对象，因为这个迭代器可以是任意类型的迭代器，所以定义成为一个模板参数，这也说明了，在类模板里面可以嵌套定义模板供成员函数使用

这里的赋值运算符重载函数使用的是现代写法，相比于传统写法来说，现代写法更加的简单，但是存在一个问题就是不能避免自己给自己赋值的问题，因为参数并不是引用，所以传参的时候就已经发生了深拷贝，后面交换与否都不会有效率的提升，但是一般情况下不会出现自己给自己赋值。
现代写法的思路就是：传参过来的这个值是要赋值给this的，参数不用引用，传参的时候就发生了拷贝构造，构造出现的这个对象的内容正式this想要的，所以使用自己实现的swap进行内容的交换，将旧的内容给v这个局部变量，并且让v帮忙释放这块空间（生命周期结束调用析构函数完成资源清理）
传统写法就是按照正常的思路我想要一个和v一样大的空间就自己new一个，将旧空间释放，然后将v的数据拷贝到新空间，这样就完成了。传统写法的思路简单易于理解，但是写起来较为复杂。

容量相关的成员函数

//capacity(内容相关的函数)
		size_t size()const
		{
			return _finish - _start;
		}

		size_t capacity() const
		{
			return _endofstorage - _start;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * sz);//更深层次关于vector内元素的深拷贝比如string
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}

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

		}

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

对于resize的实现分为几种情况，一种就是n小于size，这直接将多余的元素删除就好了。对于n大于size小于capacity的时候不需要增容，只需要将多出来的位置补上val可以，对于n大于capacity的时候就需要增容，这时候增容可以复用reserve，然后将多余的位置补上val，因为这里补val的过程和上一个情况一样，所以说可以合并，只需要判断是否需要增容即可。
对于reserve和拷贝构造的时候为什么不适用memcpy下面会给出解释。

关于深拷贝中的深拷贝问题

什么是深拷贝中的深拷贝问题呢？就是在reserve和拷贝构造函数中为什么使用了循环赋值没用使用memcpy。
来思考一下这个场景就是vector里面存放的是string类对象，这时候如果发生了增容或者是拷贝构造就会导致程序崩溃。我们知道memcpy使用的是值拷贝也就是浅拷贝画图理解。

这里可以看到如果使用的是memcpy增容后和增容前，这些旧数据指向的是同一块内存空间，但是增容后旧的空间被释放了，所以打印的时候会出现随机值，最后扩容后的对象声明周期结束的时候，对同一块内存空间释放了两次导致了程序崩溃。

当我们去vs里面测试的时候会发现，哎嗨，最后程序崩溃了，但是内容打印了出来并不是随机值，这里就跟vs中string类的存储方式有关了。

这里的s1是存储在buf里面的，vs中的buf是一个16个字节大小的字符数组。

再看这里的s2是存储在ptr中，ptr是一个char*的指针。所以可以在vs中再次尝试发现，在memcpy的时候那个字符串过长，那个字符串最后打印就变成了随机值。这就是因为memcpy发生了值拷贝的原因。
因此，为了解决这种深拷贝类型问题，在拷贝和扩容的时候使用循环赋值，虽然循环赋值就会调用深拷贝类型的赋值运算符重载完成深拷贝。虽然循环赋值效率低于memcpy（循环要遍历所有元素时间复杂度是O（N）memcpy只需要计算字节一次拷贝过去就可以了）所以在早期的C++STL中，为了追求极致的效率，使用了类型萃取，也就是区分了内置类型和自定义类型，对于内置类型使用memcpy，自定义类型使用循环+赋值。

operator[ ]重载和modify类型函数

//赋值运算符重载
		T& operator[](size_t n)
		{
			return _start[n];
		}

		const T& operator[](size_t n) const
		{
			return _start[n];
		}

/
//modify
		void push_back(const T& val)
		{
			if (_finish == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}
			*_finish = val;
			_finish++;
		}

		void pop_back()
		{
			assert(size());
			_finish--;
		}

		iterator insert(iterator pos, const T& val)
		{
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = val;
			_finish++;
			return pos;
		}
		iterator erase(iterator pos)
		{
			iterator l = pos + 1;
			while (l < _finish)
			{
				*(l - 1) = *l;
				l++;
			}
			_finish--;
			return pos;
		}
		void swap(vector<T>& v)
		{
			::swap(_start, v._start);
			::swap(_finish, v._finish);
			::swap(_endofstorage, v._endofstorage);
		}
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
62
63
64
65

这里的insert和erase返回值按照官方文档要求，为了解决迭代器失效的问题。需要使用返回值给迭代器重新赋值。

swap使用的是三次浅拷贝：：域作用限定符限定了访问全局域中的swap，因为std在vector这个头文件之前展开了。所以在全局域中可以找到swap，如果在vector这个头文件之后展开就会找不到，可以使用std::指定访问std里面的swap。

类模板内的嵌套类型

定义了一个可以打印任何类型的模板函数

	template<class Con>
	void PrintV(const Con& v)
	{
		typename Con::const_iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}

1
2
3
4
5
6
7
8
9
10
11
12

这里在去取Con这个类模板里面内嵌的const迭代器的时候，前面必须加上typename，因为这里的类模板还没有实例化，也就是不知到具体的类型。所以这时候取类模板里面的内嵌类型是不可行的。编译器不认识后面的迭代器类型，加上typename就是告诉了编译器这个Con是一个类型，等到类模板实例化之后再去里面取内嵌类型。
如果不加会报如下错误：记住就好了