C++ vector模拟实现

使用insert时迭代器失效

在模拟vector插入的时候会遇到扩容后pos失效的问题，需要更新pos

vector()
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
	{}
	
void insert(iterator pos, const T& value = T())
		{
			assert(pos >= _start && pos <= _finish);
			if (size() == capacity())
			{
				//pos位置的空间可能在扩容的时候被delete，要记录相对位置更新pos
				int len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = value;
			_finish++;
		}
void test2()
	{
		vector<int> v;
		v.insert(v.begin(), 1);
		vector<int>::iterator it = v.begin();
		v.insert(it, 2);
		v.insert(it, 3);
		v.insert(it, 4);
		v.insert(it, 5);//这句代码之后it就失效了

		v.insert(it, 6);//报错，因为it传给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
28
29
30
31
32
33
34
35
36
37

insert插入后it就失效了，我们不知道什么时候扩容
给pos加引用的话，v.insert(v.begin(), 1);是不行的，因为begin返回的是临时变量的拷贝不可以修改
如果再给pos加const，那pos不能更改了

所以insert之后it失效，尽量不要再使用

库里的insert会返回新插入元素所在位置的迭代器

void test_vector9()
	{
		std::vector<int> v3;
		v3.push_back(10);
		v3.push_back(20);
		v3.push_back(30);
		v3.push_back(40);

		for (auto e : v3)
		{
			cout << e << " ";//结果是10 20 30 40
		}
		cout << endl;
		std::vector<int>::iterator it = v3.begin()+3;
		int n = 6;
		while (n--)
		{
			it = v3.insert(it, n);
		}
		for (auto e : v3)
		{
			cout << e << " ";//结果是10 20 30 0 1 2 3 4 5 40
		}
		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

使用erase时迭代器失效

iterator erase(iterator pos)//返回被删位置的下一个位置
	{
		assert(pos >= _start && pos <= _finish);
		iterator it = pos + 1;
		while (it < _finish)
		{
			*(it - 1) = *it;
			it++;
		}
		_finish--;
		return pos;
	}
		
void test4()
	{
		// 1 2 3 4 5
		// 1 2 3 4 5 6
		// 2 2 3 4 5
		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);

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

		auto it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				v.erase(it);
			}

			++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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

不仅会漏检查，删最后一个的时候会出现 it 比_finish大的情况


vs2019会进行强制检查，erase以后认为it失效了，不能访问，我们模拟实现的跟g++下运行结果一样

erase返回被删位置的下一个位置

void test5()
	{
		//std::vector v;
		vector<int> v;

		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);

		auto 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
31
32

使用memcpy浅拷贝的问题

模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝会出现问题

memcpy会将一段内存空间中内容拷贝到另外一段内存空间中，这种拷贝是浅拷贝，如果T是内置类型不会有问题，但如果是自定义类型就会出错

delete的时候如果是自定义的数据类型，会去调用这个对象的析构函数，释放的空间置成随机值，查编码表之后可能就是我们不认识的字

tmp中string对象的_str和_start中string对象的_str是一样的，所以_start中string对象的_str变了，tmp中的也会变

调string的赋值的时候，是深拷贝，就可以解决问题了，引用计数的浅拷贝也可以解决
库里面实现是拷贝构造的，因为库里的T[]是内存池来的(就像malloc来的没有初始化)，要初始化就用定位new调拷贝构造。

所以自定义类型拷贝数据不能用memcpy

如果不加也可以过，但是推荐加上，因为类名不是类型

调用最匹配的函数可能出现的问题

出现编译错误的原因是：

会找最匹配的去调用
上面的是int和int
下面的是unsigned int 和int
上面的更匹配所以会调用模板

如果都是int，那么有更匹配的就不会去实例化模板：

vector(int n, const T& val = T())
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}
1
2
3
4
5
6
7
8

模拟实现vector

#include
#include
using namespace std;

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

		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const iterator begin()const
		{
			return _start;
		}
		const iterator end()const
		{
			return _finish;
		}
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		vector(size_t n, const T& value = T())
		{
			reserve(n);
			while (n--)
			{
				push_back(value);
			}
		}
		vector(int n, const T& value = T())
		{
			reserve(n);
			while (n--)
			{
				push_back(value);
			}
		}
		vector(const vector<T>& v)//拷贝构造
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(v.capacity());
			for (auto e : v)
			{
				push_back(e);
			}
		}
		vector<T>& operator=(vector<T> tmp)
		{
			swap(tmp);
			return *this;
		}
		~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
		T& operator[](size_t pos)
		{
			assert(pos < size());
			return *(_start + pos);
		}
		const T& operator[](size_t pos)const
		{
			assert(pos < size());
			return *(_start + pos);
		}
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}
		size_t size() const
		{
			return _finish - _start;
		}
		size_t capacity() const
		{
			return _endofstorage - _start;
		}
		void resize(size_t n, const T& value = T())
//调用默认构造函数然后拷贝构造给value，匿名对象具有常性要加const，
//const会延长生命周期，内置类型也可以认为有构造函数
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = value;
					_finish++;
				}
			}
		}
		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);//memcpy是浅拷贝，自定义类型会出错
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = tmp + sz;
				_endofstorage = tmp + n;
			}
		}
		void push_back(const T& x)
		{
			if (size() == capacity())
			{
				reserve(capacity()==0?4:2*capacity());
			}
			*_finish = x;
			_finish++;
		}
		void pop_back()
		{
			assert(size() > 0);
			_finish--;
		}
		iterator insert(iterator pos, const T& value = T())//返回新插入元素所在位置的迭代器
		{
			assert(pos >= _start && pos <= _finish);
			if (size() == capacity())
			{
				//pos位置的空间可能在扩容的时候被delete，要记录相对位置更新pos
				int len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = value;
			_finish++;
			return pos;
		}
		iterator erase(iterator pos)//返回被删位置的下一个位置
		{
			assert(pos >= _start && pos <= _finish);
			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			_finish--;
			return pos;
		}
	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
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