【STL】vector常见用法及模拟实现(附源码）

前言

这篇文章我们来学习一下STL容器里的vector，我们先来学习一下它的使用，然后对vector进行模拟实现。

1. vector介绍及使用

1.1vector的介绍

vector文档介绍

vector是一个大小可以更改的数组序列容器。

其实这里可以简单认为vector就是之前数据结构学的顺序表。

1.2 vector的使用

vector提供的接口跟string是非常相似的，所以经过前面string的学习，再学习vector成本降低了很多。

下面我们来介绍一下常用接口。

1.2.1 构造函数

首先看第一个：

这个是用来传空间配置器的，我们可以认为这个就是无参的构造函数，构造一个空的vector。

注意：
vector是一个类模板，类模板实例化只能显式实例化，即需要在类模板名字后跟<>，然后将实例化的类型放在<>中即可。
类模板不是真正的类，其实例化的结果才是真正的类。

这个就是支持用n个val构造一个vector对象。

这个就是支持迭代器区间构造，也不难理解我们来给大家演示一下：

这个就是拷贝构造了

1.2.2 vector对象遍历

vector也重载了[]这里可以使用for循环遍历：

也可以使用迭代器，也就是支持范围for：

1.2.3 reserve和resize

首先我们来看一下vector的扩容机制：

#include 
#include 
using namespace std;
int main()
{
	// 测试vector的默认扩容机制
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这里g++下是二倍扩：

当我们知道需要多少空间，直接用reserve把空间开好，就可以减少频繁扩容的一个消耗。


确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

我们再来看一下resize():

resize在开空间的同时还会进行初始化,当然如果传的n比size小，那它还会删除多余的数据。

1.2.4 insert和erase

与string相比vector只支持我们去传迭代器和迭代器区间了

2. vector模拟实现

2.1 vector迭代器失效问题

会引起其底层空间改变的操作，都有可能导致迭代器失效，比如：resize、reserve、insert、assign、push_back等。
出错原因：
以上操作，都有可能会导致vector扩容，迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

这里我们举个简单的例子，以下代码用于输出v1中所有偶数：

int main()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);

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

    auto it = v1.begin();
    while(it != v1.end())//错误代码
    {
       if(*it % 2 == 0)
       {
			v1.erase(it);
       }
       it++;
	}
    // while (it != v1.end())
    // {
    //     if (*it % 2 == 0)
    //     {
    //         it = v1.erase(it);
    //     }
    //     else
    //     {
    //         ++it;
    //     }
    // }
}
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

这里程序会报错出现段错误。实际上这里是因为是因为erase删除pos位置元素后，pos位置之后的元素会往前搬移，他没有接收返回值而是一味的进行++操作导致程序越界奔溃。

2.2 模拟实现reserve函数浅拷贝问题

这里主要出现错误的原因就是内部使用了memcpy来拷贝数据。

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错

但如果拷贝的是自定义类型元素，并且
自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
我们这里以vector< string >为例：

2.3模拟实现源码

2.3.1 vector.h

#include
#include
using namespace std;

namespace w
{
    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(size_t n, const T& val = T())
		{
			resize(n, val);
		}

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

		// [first, last)
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		vector()
		{}

		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, sizeof(T)*v.size());
			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}

			_finish = _start + v.size();
			_endofstorage = _start + v.capacity();
		}


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

		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);
					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, const T& val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);

				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		void push_back(const T& x)
		{
			insert(end(), x);
		}

		void pop_back()
		{
			erase(--end());
		}

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

		const T& operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;

				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);

				// 解决pos迭代器失效问题
				pos = _start + len;
			}

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

			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;

			return 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

2.3.2 test.cpp

#include "vector.h"
void test_vector1()
	{
		w:: vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);

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


		for (size_t i = 0; i < v1.size(); i++)
		{
			v1[i]++;
		}

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

	}

    void test_vector2()
	{
		w ::vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(5);
		v1.push_back(5);
		v1.push_back(5);

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

		v1.insert(v1.begin(), 100);

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

    }

int main()
{
    test_vector2();
    return 0;
}
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