1. vector的介绍和使用
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
- vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
- 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
更为详细的可以查看vector文档介绍。
2. vector的模拟实现
vector的嵌套型别定义
|
1
2
3
4
|
typedef _Ty value_type;typedef value_type* iterator;typedef value_type& reference;typedef size_t size_type; |
vector的成员变量
|
1
2
3
4
|
private: iterator _start; iterator _last; iterator _end; |
2.1 vector构造函数和拷贝构造函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
vector():_start(nullptr),_last(nullptr),_end(nullptr){}vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr){ insert(n,value);}vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr){ insert(f,l);} vector(const vector<int>& iv){ reserve(iv.capacity()); iterator it = begin(); iterator vit = iv.end(); while (vit != iv.begin()) { *it++ = *vit--; }} |
2.2 insert函数和eraser函数
|
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
|
iterator insert(iterator pos,const _Ty& value){ //1.当size()==capacity()时，表明vector已满，再进行插入前需要进行扩容 if(size()== capacity()) { size_type oldpos = pos - begin(); //这里需要防止一种情况：若vector为空的时候，他的capacity为0，这个时候给他直接扩容2倍是行不通的， //因为2*0 = 0，因此就需要进行判断 size_type newcapacity = (capacity() == 0)? 1 : 2*capacity(); reserve(newcapacity); //这里空间发生了变化，pos迭代器会失效，因此需要重新对pos进行设置 //reserve不会使vector的成员变量失效 pos = begin() + oldpos; } //2.当size() < capacity()时，表明vector未满，插入直接在pos的位置进行插入 //需要注意的是插入是在pos指向的位置进行插入，并且插入需要挪动数据， //将pos位置之后的数据全部向后挪动一个,为防止元素被改写，则需要从后向前进行挪动 iterator tail = _last; while(tail > pos) { *tail = *(tail-1); --tail; } //这里要注意的是挪动数据时，因为没有对pos位置进行操作，所以pos位置的迭代器并没有失效， //但是pos位置之后的迭代器全部失效了，但在这里并没有关系，我们并不会用到那些迭代器 *pos = value; //插入完之后，一定要对_last指针+1，因为全部向后挪动了一个元素 ++_last; return pos;}void insert(size_type n,const _Ty& value){ for(int i = 0;i < n; ++i) { insert(end(),value); }}void insert(iterator f,iterator l){ while(f!=l) { insert(end(),*f); ++f; }}iterator erase(iterator pos){ assert(pos >= _start || pos < _last); //1.删除pos位置的元素，就是将[pos,end()]这个区间向前挪动一个即可 iterator it = pos + 1; while(it != _last) { *(it-1) = *(it); ++it; } --_last; return pos;} |
2.3 reserve函数和resize函数
|
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
|
void reserve(size_type n){ //若 n 的值大于vector的容量，则开辟空间 //若 n 的值小于等于，则不进行任何操作 if(n > capacity()) { //1.新开辟一个空间 size_type oldSize = size(); _Ty* newVector = new _Ty[n]; //2.将原空间的数值赋值到新空间 if(_start) { //注意：这里不能使用memcpy,因为memcpy是一个浅拷贝。 //memcpy(newVector,_start,sizeof(_Ty)*size()); for(size_type i = 0; i < oldSize; ++i) { newVector[i] = _start[i]; } } //3.改变三个指针的指向 //这里直接重新给三个成员进行赋值，所以调用reserve()函数不用担心迭代器失效的问题 _start = newVector; _last = _start + oldSize; _end = _start + n; }}void resize(size_type n,const _Ty& value = _Ty()){ //1.如果n的值小于等于size()的时候，则只需要将_last的指针往前移动即可 if(n <= size()) { _last = _start + n; return; } //2.如果n的值大于capacity()的时候，则需调用reserve()函数，重新设置容量大小 if(n > capacity()) { reserve(n); } //若当n的值大于size()而小于capacity()的时候，只需将_last的指针往后移即可 iterator it = _last; _last = _start + n; while(it != _last) { *it = value; ++it; } //resize()函数也不需要担心迭代器失效的问题} |
2.4 push_back函数和pop_back函数
|
1
2
3
4
5
6
7
8
|
void push_back(const _Ty& value){ insert(end(),value);}void pop_back(){ erase(end()-1);} |
2.5 begin函数和end函数
|
1
2
3
4
5
6
7
8
9
|
iterator begin()const{ return _start;}iterator end() const{ return _last;} |
2.6 size函数、capacity函数
|
1
2
3
4
5
6
7
8
9
|
size_type size(){ return end()-begin();}size_type capacity()const{ return _end-begin();} |
2.7 empty函数和operator[]重载
|
1
2
3
4
5
6
7
8
9
10
|
bool empty()const{ return end() == begin();}reference operator[](size_type n){ return *(begin() + n);} |
2.8 完整代码和相应测试
|
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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
|
#include <iostream>#include <assert.h>using namespace std;namespace mytest{ template<class _Ty> class vector { public: typedef _Ty value_type; typedef value_type* iterator; typedef value_type& reference; typedef size_t size_type; public: iterator begin()const { return _start; } iterator end() const { return _last; } size_type size() { return end()-begin(); } size_type capacity()const { return _end-begin(); } bool empty()const { return end() == begin(); } reference operator[](size_type n) { return *(begin() + n); } public: vector():_start(nullptr),_last(nullptr),_end(nullptr) {} vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr) { insert(n,value); } vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr) { insert(f,l); } vector(const vector<int>& iv) { reserve(iv.capacity()); iterator it = begin(); iterator vit = iv.end(); while (vit != iv.begin()) { *it++ = *vit--; } } public: void reserve(size_type n) { //若 n 的值大于vector的容量，则开辟空间 //若 n 的值小于等于，则不进行任何操作 if(n > capacity()) { //1.新开辟一个空间 size_type oldSize = size(); _Ty* newVector = new _Ty[n]; //2.将原空间的数值赋值到新空间 if(_start) { //注意：这里不能使用memcpy,因为memcpy是一个浅拷贝。 //memcpy(newVector,_start,sizeof(_Ty)*size()); for(size_type i = 0; i < oldSize; ++i) { newVector[i] = _start[i]; } } //3.改变三个指针的指向 //这里直接重新给三个成员进行赋值，所以调用reserve()函数不用担心迭代器失效的问题 _start = newVector; _last = _start + oldSize; _end = _start + n; } } void resize(size_type n,const _Ty& value = _Ty()) { //1.如果n的值小于等于size()的时候，则只需要将_last的指针往前移动即可 if(n <= size()) { _last = _start + n; return; } //2.如果n的值大于capacity()的时候，则需调用reserve()函数，重新设置容量大小 if(n > capacity()) { reserve(n); } //若当n的值大于size()而小于capacity()的时候，只需将_last的指针往后移即可 iterator it = _last; _last = _start + n; while(it != _last) { *it = value; ++it; } //resize()函数也不需要担心迭代器失效的问题 } void push_back(const _Ty& value) { insert(end(),value); } void pop_back() { erase(end()-1); } iterator insert(iterator pos,const _Ty& value) { //1.当size()==capacity()时，表明vector已满，再进行插入前需要进行扩容 if(size()== capacity()) { size_type oldpos = pos - begin(); //这里需要防止一种情况：若vector为空的时候，他的capacity为0， //这个时候给他直接扩容2倍是行不通的，因为2*0 = 0，因此就需要进行判断 size_type newcapacity = (capacity() == 0)? 1 : 2*capacity(); reserve(newcapacity); //这里空间发生了变化，pos迭代器会失效，因此需要重新对pos进行设置 //reserve不会使vector的成员变量失效 pos = begin() + oldpos; } //2.当size() < capacity()时，表明vector未满，插入直接在pos的位置进行插入 //需要注意的是插入是在pos指向的位置进行插入，并且插入需要挪动数据， //将pos位置之后的数据全部向后挪动一个,为防止元素被改写，则需要从后向前进行挪动 iterator tail = _last; while(tail > pos) { *tail = *(tail-1); --tail; } //这里要注意的是挪动数据时，因为没有对pos位置进行操作，所以pos位置的迭代器并没有失效， //但是pos位置之后的迭代器全部失效了，但在这里并没有关系，我们并不会用到那些迭代器 *pos = value; //插入完之后，一定要对_last指针+1，因为全部向后挪动了一个元素 ++_last; return pos; } void insert(size_type n,const _Ty& value) { for(int i = 0;i < n; ++i) { insert(end(),value); } } void insert(iterator f,iterator l) { while(f!=l) { insert(end(),*f); ++f; } } iterator erase(iterator pos) { assert(pos >= _start || pos < _last); //1.删除pos位置的元素，就是将[pos,end()]这个区间向前挪动一个即可 iterator it = pos + 1; while(it != _last) { *(it-1) = *(it); ++it; } --_last; return pos; } private: iterator _start; iterator _last; iterator _end; };};void Test1(){ mytest::vector<int> iv; cout << "iv.size() = " << iv.size() << endl; cout << "iv.capacity() = " << iv.capacity() << endl; iv.push_back(1); iv.push_back(2); iv.push_back(3); iv.push_back(4); cout << "iv.size() = " << iv.size() << endl; cout << "iv.capacity() = " << iv.capacity() << endl; mytest::vector<int>::iterator it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl; iv.pop_back(); iv.pop_back(); it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl;}void Test2(){ mytest::vector<int> iv(10,2); mytest::vector<int>::iterator it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl;}void Test3(){ int ar[] = {1,2,3,3,4,5}; mytest::vector<int> iv(ar,ar+6); mytest::vector<int>::iterator it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl;}int main(){// Test1();// Test2(); Test3(); return 0;} |
到此这篇关于C++ STL vector的模拟实现的文章就介绍到这了,更多相关C++ STL vector内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/weixin_43937101/article/details/116429162
