---

前言

今天我们来讲一讲关于vector容器，他是一个顺序表，类似于C语言中的数组，但是容器里面的数据类型可以是内置类型或者自定义类型，其中也包含了很多的函数接口，实现增删查改等等！
接下来开始我们的学习!
OJ题的答案在文章的末尾！

---

正文开始

一、vector的介绍及使用

1.vector的介绍及使用

1.1 vector的介绍

vector的文档介绍

1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的是连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素
   进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自
   动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小
   为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是
   一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大
   小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存
   储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是
   对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增
   长。
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在
   末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和
   forward_lists统一的迭代器和引用更好。

学习方法：使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学
习

1.2 vector的使用

vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常
见的接口就可以，下面列出了哪些接口是要重点掌握的。

1.2.1 vector的定义

#include
int main()
{

	std::vector<int> first; //无参构造
	std::vector<int> second(4, 100); // 构造并初始化4个100
	std::vector<int> third(second.begin(), second.end()); //使用迭代器进行初始化构造
	std::vector<int> fourth(third); //拷贝构造
	// 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分
	int myints[] = { 16,2,77,29 };
	std::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
	for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
		std::cout << *it<<" ";
	std::cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.2.2 vector iterator 的使用

#include
void PrintVector(const vector<int>& v) {
	// const对象使用const迭代器进行遍历打印
	vector<int>::const_iterator it = v.begin();
	while (it != v.end())
	{
		//*it+=1;//error
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
int main()
{
	// 使用push_back插入4个数据
	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;
	// 使用迭代器进行修改
	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}
	// 使用反向迭代器进行遍历再打印
	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	PrintVector(v);
	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

1.2.3 vector 空间增长问题

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义
的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问
题。
resize在开空间的同时还会进行初始化，影响size。

VS下的测试结果

同样一份代码g++下

1.2.3 vector 增删查改

// push_back/pop_back
#include 
#include 
using namespace std;
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	vector<int>::iterator it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	v.pop_back();
	v.pop_back();
	it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	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

// find / insert / erase
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);

	// 在pos位置之前插入30
	v.insert(pos, 30);
	vector<int>::iterator it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(pos);
	it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	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

// operator[]+index 和 C++11中vector的新式for+auto的遍历
// vector使用这两种遍历方式是比较便捷的。
#include 
#include 
using namespace std;
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 通过[]读写第0个位置。
	v[0] = 10;
	cout << v[0] << endl;
	// 通过[i]的方式遍历vector
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
	vector<int> swapv;
	swapv.swap(v);//交换两个容器
	cout << "v data:";
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
	cout << "swapv data:";
	for (size_t i = 0; i < swapv.size(); ++i)
		cout << swapv[i] << " ";
	cout << endl;

	// C++11支持的新式范围for遍历
	for (auto x : v)
		cout << x << " ";
	cout << endl;
	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

1.2.4 vector 迭代器失效问题（重点）

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了
封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的
空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，
程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、
   push_back等。

#include 
using namespace std;
#include 
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };

	auto it = v.begin();

	// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
	v.resize(100, 8);

	// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
	v.reserve(100);

	//插入元素期间，可能会引起扩容，而导致原空间被释放
	 v.insert(v.begin(), 0);
	 v.push_back(8);

	//给vector重新赋值，可能会引起底层容量改变
	v.assign(100, 8);

	/*
	出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
   而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
   空间，而引起代码运行时崩溃。
	解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。
	*/
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	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

2. 指定位置元素的删除操作–erase

#include 
using namespace std;
#include 
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据，导致pos迭代器失效。
	v.erase(pos);
	cout << *pos << endl; // 此处会导致非法访问
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代
器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是
没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效
了。
以下代码的功能是删除vector中所有的偶数，请问那个代码是正确的，为什么？

int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}

	return 0;
}
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
			++it;
	}
	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

第一种方法erase之后会导致pos位置的意义变了，所以是不行的
第二个是可以的，因为erase的返回值是迭代器类型，重新接收即可！

迭代器失效解决办法：在使用前，对迭代器重新赋值即可

1.2.5 vector 在OJ中的使用

1. 只出现一次的数字i

2. 杨辉三角OJ

总结：通过上面的练习我们发现vector常用的接口更多是插入和遍历。遍历更喜欢用数组operator[i]的
形式访问，因为这样便捷。

二、vector深度剖析及模拟实现

图片截取至这本书，因为作者是台湾人，所以文章内容是台湾字。

2.1 std::vector的核心框架接口的模拟实现rose::vector

#include
#include
#include
using namespace std;
namespace ROSE
{

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	vector()
		:_start(nullptr)
		,_finish(nullptr)
		,_endofstorage(nullptr)
	{}
	vector(size_t n, T val)
	{
		reserve(n);
		for (size_t i = 0; i < n; i++)
		{
			push_back(val);
		}
	}
	//类模板的成员函数，还可以再是函数模板
	template<class InputIterator>
	vector(InputIterator first, InputIterator last)
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstorage(nullptr)
	{
		while (first!=last)
		{
			push_back(*first);
			first++;
		}
	}
	void swap(vector<T> v)
	{
		::swap(_start, v._start);
		::swap(_finish, v._finish);
		::swap(_endofstorage, v._endofstorage);
	}
	vector(const vector<T>& v)
		:_start(nullptr)
		,_finish(nullptr)
		,_endofstorage(nullptr)
	{
		//reserve(v.capacity());
		//for (auto& e : v)
		//{
		//	push_back(e);
		//}
		_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();
	}
	v1=v2
	//vector& operator=(const vector& v)
	//{
	//	/*if (this != &v)
	//	{
	//		delete[] _start;
	//		_start = new T[v.capacity()];
	//		memcpy(_start, v._start, sizeof(T) * v.size());
	//		_finish = _start + v.size();
	//		_endofstorage = _start + v.capacity();
	//	}*/
	//	if (this != &v)
	//	{
	//		vector tmp(v);
	//		swap(_start, tmp._start);
	//		_finish = _start + v.size();
	//		_endofstorage = _start + v.capacity();
	//	}
	//	return *this;
	//}
	//v1=v2
	vector<T>& operator=(vector<T> v)
	{
		swap(v);
		return *this;
	}
	~vector()
	{
		if (_start != nullptr)
		{
			delete[] _start;			
		}
		_start =_finish=_endofstorage= nullptr;
	}
	iterator begin()
	{
		return _start;
	}
	const_iterator begin() const
	{
		return _start;
	}
	iterator end()
	{
		return _finish;
	}
	const_iterator end() const
	{
		return _finish;
	}
	size_t capacity()const
	{
		return _endofstorage - _start;
	}
	size_t size()const
	{
		return _finish - _start;
	}
	bool empty()const
	{
		return _start == _finish;
	}
	T& operator[](size_t i) 
	{
		assert(i<size());
		return _start[i];
	}
	const T& operator[](size_t i)const
	{
		assert(i < size());
		return _start[i];
	}
	void reserve(size_t n)
	{
		if (n > capacity())
		{
			size_t sz = _finish - _start;
			T* tmp = new T[n];
			if (_start)
			{
				//memcpy(tmp,_start,sz*sizeof(T));
				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++;
			}
		}
	}
	void push_back(const T& x)
	{
		if (_finish == _endofstorage)
		{
			size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
			reserve(newcapacity);
		}
		*_finish = x;
		_finish++;
	}
	void pop_back()
	{
		assert(!empty());
		_finish--;
	
	}
	void insert(iterator pos,const T& x)
	{
		assert(pos <= _finish);
		if (_finish == _endofstorage)
		{
			size_t len = pos - _start;
			size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
			reserve(newcapacity);
			//更新pos,解决增容后pos失效的问题
			pos = _start + len;
		}
		iterator end = _finish- 1;
		while (end >= pos)
		{
			*(end + 1) = *end;
			end--;
		}
		*pos = x;
		_finish++;
	}
	iterator erase(iterator pos)
	{
		assert(pos < _finish);
		iterator cur = pos+1;
		while (cur <_finish)
		{
			*(cur-1) = *cur;
			cur++;
		}
		_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
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
229
230

2.2 使用memcpy拷贝问题

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main()
{
	 rose::vector<string> v;
	 v.push_back("1111");
	 v.push_back("2222");
	 v.push_back("3333");
	 v.push_back("4444");
	 v.push_back("5555");
 return 0;
}
1
2
3
4
5
6
7
8
9
10

问题分析：

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是内置类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且
   自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

2.2 对rose::vector核心接口的测试

template<class T>
void PrintVector(const vector<T>& v)
{
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	/*for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;*/
}

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

	v.resize(3);
	PrintVector(v);
	v.resize(6);
	PrintVector(v);
	v.resize(10);
	PrintVector(v);
}
void test_vector3()
{
	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);
	v.push_back(7);
	v.push_back(8);
	PrintVector(v);

	vector<int>::iterator pos = find(v.begin(),v.end(),3);
	//在pos  之前插入
	v.insert(pos,30);
	//insert以后pos就失效了
	//1.pos指向位置的意义就变了，pos不是指向3
	//2.pos成为了野指针
	PrintVector(v);


}
void test_vector4()
{
	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);
	PrintVector(v);
	//删除掉所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.erase(it);
		}
		else
		{
			it++;
		}
	}
	PrintVector(v);
}

void test_vector5()
{
	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(6);

	vector<int> v2(v1);
	PrintVector(v2);

	vector<int> v3;
	v3.push_back(10);
	v3.push_back(20);
	v3.push_back(30);
	v3.push_back(40);
	v3.push_back(50);
	v3.push_back(60);
	vector<int> v4;
	v3 = v1;
	v4 = v1;
	PrintVector(v3);
	PrintVector(v4);

}
void test_vector6()
{
	vector<string> str;
	str.push_back("11111");
	str.push_back("22222");
	str.push_back("33333");
	str.push_back("44444");
	str.push_back("55555");
	for (const auto& e : str)
	{
		cout << e << " ";
	}
	//memcpy引发的深层次深浅拷贝
	//总结:T是内置类型或者浅拷贝类型(Date)，他们增容或者拷贝构造中，我们要memcpy是没有问题的
	//但是T是深拷贝的自定义类型(string)，他们增容或者拷贝构造中，我们用memcpy是有问题的
}

}
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

2.3 动态二维数组理解

// 以杨辉三角的前n行为例：假设n为5
void test5(size_t n) {
	 // 使用vector定义二维数组vv，vv中的每个元素都是vector
	 rose::vector<rose::vector<int>> vv(n);
	 
	 // 将二维数组每一行中的vecotr中的元素全部设置为1
	 for (size_t i = 0; i < n; ++i)
	 vv[i].resize(i + 1, 1);
	 // 给杨辉三角出第一列和对角线的所有元素赋值
	 for (int i = 2; i < n; ++i)
	 {
		 for (int j = 1; j < i; ++j)
		 {
		 	vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
		 }
	 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

rose::vector vv(n); 构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类
型的，每行没有包含任何元素，如果n为5时如下所示：

---

总结

例如：以上就是今天要讲的内容，本文仅仅简单介绍了vector的使用和模拟实现，文章的内容有点多和难于理解，尤其在拷贝构造和memcpy浅拷贝导致程序崩溃的问题，需要下去多多理解和多多消化.
OJ链接在我的码云仓库，里面都是leetcode和牛客网的题大家也可以看看别的题目仓库入口！！！