＜C++＞详解vector类

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统一的迭代器和引用更好

2. vector的使用

2.1 vector的定义

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

	vector<double> v2;
	v2.push_back(1.1);

	vector<string> v3;
	v3.push_back("abc");
	v3.push_back("天影云光");// 单参数的构造函数支持隐式类型转换

	vector<int> v4(10, 5);// 10个5

	vector<string> v5(++v3.begin(), v3.end());// 迭代器

	string s = "hello world";
	vector<char> v6(s.begin(), s.end());// 不一定要本类型的迭代器
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2 vector遍历操作

这部分内容和string很像

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

	// 1、下标+[]
	for (size_t i = 0; i < v.size(); i++)
	{
		v[i]++;
		cout << v[i] << " ";
	}
	cout << endl;

	// 2、迭代器
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		(*it)--;
		cout << *it << " ";
		it++;
	}
	cout << endl;

	// 3、范围for
	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

2.3 vector空间增长

vs下是1.5倍增容；linux g++ SGI版本2倍增容

这样增容的原因是：单次增多了会浪费空间，增少了要频繁增容。两者均衡考虑1.5倍到2倍增容速度比较合适

void test3()
{
	//vector v;
	//cout << v.max_size() << endl;// 最大字节数÷类型大小

	// 增容机制大概是1.5倍增容
	size_t sz;
	std::vector<int> foo;
	//foo.reserve(100);// 提前扩容
	sz = foo.capacity();
	std::cout << "making foo grow:\n";
	for (int i = 0; i < 100; ++i) {
		foo.push_back(i);
		if (sz != foo.capacity()) {
			sz = foo.capacity();
			std::cout << "capacity changed: " << sz << '\n';
		}
	}

	vector<int> v1;
	v1.resize(100, 2);// 初始化
	// vector和string一样，删除数据不会主动缩容
	foo.resize(10);
	cout << foo.size() << endl;
	cout << foo.capacity() << endl;
	// 缩容（本质上是深拷贝转移数据），时间换空间
	foo.shrink_to_fit();
	cout << foo.size() << endl;
	cout << foo.capacity() << 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

2.4 vector增删查改

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

	v.insert(v.begin(), -1);// 头插
	v.insert(v.begin(), -2);
	v.insert(v.begin() + 3, 10);// 在第3个位置插入
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.erase(v.begin());// 头删
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	//vector::iterator pos = find(v.begin(), v.end(), 2);
	auto pos = find(v.begin(), v.end(), 2);
	if (pos != v.end())
	{
		cout << "find" << endl;
		v.erase(pos);
	}
	else
	{
		cout << "没找到" << endl;
	}

	//sort(v.begin(), v.end());// 升序
	// 用仿函数实现降序
	sort(v.begin(), v.end(), greater<int>());

	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

3. vector迭代器失效问题

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

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

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

以insert为例，会产生野指针导致迭代器失效

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

	auto it = v.begin();
	while (it!=v.end())
	{
		if (*it%2==0)
		{
            //v.insert(it, 20);
			it = v.insert(it, 20);// 扩容后，it不是原来的it了，迭代器失效。it变成了野指针，所以我们要更新it再++
			++it;// 插入新数据后，如果不加这句就会每次都在2之前插入20
		}
		++it;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

void test()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
    
	auto pos = find(v.begin(), v.end(), 2);
	if (pos != v.end())
	{
		v.erase(pos);// 删除pos位置的数据，导致pos迭代器失效。
	}
	cout << *pos << endl;// 导致非法访问。我们要更新pos才能正常运行，虽然更新pos好像无济于事。失效了直接用是不可以的，但是给你返回了一个可能是无效的地址，那么这个就不是失效了，只是在运行的时候可能访问出错误的数据，相当于是运行时错误
	*pos = 10;
	cout << *pos << endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

1. 意义变了，或者不在有效访问数据的范围内
2. 一般不会采用缩容方案，那么earse的失效原因，一般不会是野指针的失效

总结vector迭代器失效有两种：

1. 扩容缩容，导致野指针出现
2. 迭代器指向的位置意义变了

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

4. vector和string

vector和string有很多相似的地方，既然vector能支持那么多类型，我们为什么要有string呢

因为：string用ascii码比较大小更专业；string支持流插入的输出；string删除的是字符串……

总之术业有专攻，如果想处理字符串，用string更专业

5. vector的模拟实现

库里面是用class vector，为了区分，我们能把vector写成大写Vector；或者增加一层命名空间，在命名空间里写vector，不过在用的时候要记得调用命名空间里的vector类

以下用的是第二种写法tyyg::class vector

#pragma once
#include 
#include 
using namespace std;

namespace tyyg
{
	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)
			: _start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		//vector(const vector& v)
		vector(const vector& v)// 这样写也行
			: _start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			vector<T> tmp = vector(v.begin(), v.end());
			swap(tmp);
		}

		//vector(size_t n, const T& val = T())// size_t会导致类型错配到(InputIterator first, InputIterator last)
		vector(int n, const T& val = T())// 缺省值不确定类型，y
			: _start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			resize(n, val);
		}

		vector(size_t n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			resize(n, val);
		}

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

		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endOfStorage = nullptr;
			}
		}

		size_t size()
		{
			return _finish - _start;
		}

		size_t capacity()
		{
			return _endOfStorage - _start;
		}

		void reserve(size_t n)
		{
			size_t sz = size();
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, size() * sizeof(T));// 只能实现浅拷贝
					for (size_t i = 0; i<size(); ++i)// 解决更深层次深拷贝
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				
			}
			_finish = _start + sz;// 这里要小心，_start已经改变了，size()=_finish-_start;这里不能用size()
			_endOfStorage = _start + n;
		}

		void resize(size_t n, const T& val = T())
		{
			if (n > capacity())
			{
				reserve(n);
			}
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}

		void push_back(const T& x)
		{
			/*if (_finish == _endOfStorage)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}
			*_finish = x;
			++_finish;*/
			insert(end(), x);
		}

		void pop_back()
		{
			/*assert(size());
			_finish--;*/
			erase(end()-1);// end()返回临时变量，常性，不能--
		}

		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)// 返回值解决迭代器失效问题;pos不传引用是因为怕v.begin（）
		{
			assert(pos >= _start && pos <= _finish);
			if (size()==capacity())
			{
				size_t n = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				// 更新空间后也要更新pos地址，否则会迭代器失效
				pos = _start + n;
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}
			*pos = x;
			_finish++;
			return pos;
		}

		// 一般vector删除数据，都不考虑缩容方案
		// 缩容方案：size()
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator start = pos;
			while (start < _finish - 1)
			{
				*start = *(start + 1);
				++start;
			}
			--_finish;// 如果earse最后一个，直接--，start要小心越界
			return pos;
		}

		void clear()
		{
			_finish = _start;
		}

	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
231