C++初阶--自我实现vector

实现模板

#include<assert.h>
#include<string.h>
#include<iostream>
#include<list>
using namespace std;
namespace fnc
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		//构造函数
		vector()
		{

		}

		//复制拷贝
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (const auto& a : v)
			{
				push_back(a);
			}			
		}

		//迭代器区间构造
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

		vector(size_t n, const T& val = T())
		{
			resize(n, val);
		}

		vector(int n, const T& val = T())
		{
			resize(n, val);
		}


		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);

		}
		//赋值
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}
		//析构函数
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstorage = nullptr;
			}
		}
		//返回对应的位置
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}

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

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t old = size();
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * old);//不建议
					for (int i = 0; i < old; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
			    
				_start = tmp;
				_finish = _start + old;
				_endofstorage = _start + n;

			}
		}

		void resize(size_t n, T val = T())
		{
			if (n > size())
			{
				
				if (n > capacity())
				{
					reserve(n);
				}
				//先记住之前的位置
				while (_finish < _start + n)
				{
					*_finish = val;
					_finish++;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}
		void push_back(const T& x)
		{
			//满扩容
			if (_finish == _endofstorage)
			{
				size_t newcapacity =capacity() == 0 ? 1 : capacity() * 2;
				reserve(newcapacity);
			}

			*_finish = x;
			_finish++;
		}

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

		iterator insert(iterator pos,const T& x)
		{
			//确保pos是正确的范围内
			assert(pos >= _start && pos < _finish);
			if (_finish == _endofstorage)
			{
				size_t distance = pos - _start;
				size_t newcapacity = capacity() == 0 ? 1 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + distance;
			}
			//插入腾出空间
			//memmove(pos + 1, pos, sizeof(T) * (_finish - pos));//不建议
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = x;

			_finish++;

			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);

			//将对应位置挤掉
			//memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));//不建议
			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			--_finish;

			return pos;
		}

		size_t capacity()
		{
			return _endofstorage - _start;

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

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

			return _start[pos];
		}
	private:
		iterator _start=nullptr;
		iterator _finish=nullptr;
		iterator _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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228

首先我们看vector的成员函数，都是通过迭代器来确定具体位置的，

_start表示vector的起始位置，
_finish表示vector有效存储的结束位置，
_endodstorage表示当前开辟的空间指向最后的地址位置

下面通过实例来讲解一些需要注意的地方。

vector和const_vector

对于vector来说，实际上就是C语言的数组，这也就表明vector存储的元素的地址空间是连续的，所以这里的迭代器实际上表示的就是原始指针，但为了区别是否有const修饰，需要对他们进行简单的封装。

被const修饰的迭代器，只具有可读性，对于一些只读的函数，要多加const重载函数。

例子：

void print_vector(const vector<int>& v)
	{
		for (auto a : v)
		{
			cout << a << " ";
		}
		cout << endl;
	}

	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;

		for (auto a : v)
		{
			cout << a << " ";
		}
		cout << endl;

		for (int i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		v.insert(v.begin(), 111);
		print_vector(v);

		v.insert(v.begin(), 110);
		print_vector(v);

		v.erase(v.begin() + 4);
		print_vector(v);

		v.erase(v.begin());
		print_vector(v);
	}
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

如果这里没有添加const修饰的begin和end函数，那么将会报错，因为涉及到权限放大的问题。

resize()和reserve()

reserve()也就是对vector的容量进行扩容，

这里需要对原先的存储进行，方便后面进行对成员变量迭代器的定位。

这里要注意，_finish和_endofstorge都是相对于_start来取相对位置的，因为创建了一个新的空间。

resize()就是改变vector()的有效容量

T是泛型类型，T()表示取对应的默认构造参数，内置类型会取到0，或者nullptr；
自定义类型会根据构造参数进行初始化，取到对应的值；

void test_vector2()
	{
		vector<int> myvector;

		// set some initial content:
		for (int i = 1; i < 10; i++) myvector.push_back(i);

		myvector.resize(5);
		myvector.resize(8, 100);
		myvector.resize(12);

		cout << "myvector contains:";
		for (int i = 0; i < myvector.size(); i++)
			cout << ' ' << myvector[i];
		std::cout << endl;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

拷贝构造和赋值

这里会发现，我是在成员变量进行了声明，构造函数没有进行初始化；
一开始，我只是在构造函数进行了初始化，而在拷贝构造中没有进行初始化，那么由于这两个函数是构成重载的，所以像一些有指针的，由于没有进行初始化，会变成野指针，这样就会报错。
所以在这里总结：

void test_vector3()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		vector<int> v1 = v;
		cout << "原来的v1 ";
		for (auto a : v1)
		{
			cout << a << " ";
		}
		cout << endl;

		vector<int> v2;
		v2.push_back(22);
		v2.push_back(33);
		v2.push_back(44);
		v2.push_back(55);

		v1=v2;
		cout << "赋值后的v1 ";
		for (auto a : v1)
		{
			cout << a << " ";
		}
		cout << endl;
	}
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

深浅拷贝的问题

先看例子

void test_vector4()
	{
		vector<string> v;
		v.reserve(10);
		v.push_back("xxx");
		v.push_back("xxx");
		v.push_back("xxx");
		v.push_back("xxx");
		v.push_back("xxx");
		v.push_back("xxx");

		for (auto a : v)
		{
			cout << a << " ";
		}
		cout << endl;

		//n>size
		v.resize(8);
		for (auto a : v)
		{
			cout << a << " ";
		}
		cout << endl;

		//n>capacity
		v.resize(15, "yyyy");
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		//n<size
		v.resize(3);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
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

迭代器失效问题

void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);

		//要求删除所有偶数
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it=v.erase(it);
			}
			else
			{
				it++;
			}
					
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
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

vector的其他构造

void test_vector6()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		vector<int> v2(v1.begin(), v1.end());
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt;
		lt.push_back(11);
		lt.push_back(22);
		lt.push_back(33);
		lt.push_back(44);
		vector<int> v3(lt.begin(), lt.end());
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;

		int a[] = { 100,200,300 };
		vector<int> v4(a, a + 3);
		for (auto e : v4)
		{
			cout << e << " ";
		}
	}
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

void test_vector7()
	{
		vector<string> v1(5, "1234");
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2(5, 1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行：