vector的介绍
1、vector是表示可变大小数组的序列容器。
2、就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3、本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5、因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6、与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
vector是C++ STL中一个非常重要的容器，了解 vector 的底层实现原理，可以很好的帮助我们更加熟练的使用vector。
c++ vector 模拟实现代码：
|
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
|
#include<iostream>using namespace std;namespace bit{ template<typename T> class vector { public: typedef T* iterator; public: T operator[](int i) { return start[i]; } public: vector() :start(nullptr), finish(nullptr), end_of_sorage(nullptr) { } vector(size_t n, const T& value = T()) :start(nullptr), finish(nullptr), end_of_sorage(nullptr) { reserve(n);//先扩容 while (n--!=0) //再填充 { push_back(value); } } template<class InPutIterator> //由前后指针来创建 vector(InPutIterator first, InPutIterator last):start(nullptr), finish(nullptr), end_of_sorage(nullptr) { reserve(last-first);//先申请空间 while (first != last) { push_back(*first); first++; } } ~vector() { delete[]start; start = finish = end_of_sorage = nullptr; } public: int size() { return finish - start; } int capacity() { return end_of_sorage - start; } bool empty() { return finish == start; } void swap(vector<T>& v) { std::swap(start, v.start); std::swap(finish, v.finish); std::swap(end_of_sorage, v.end_of_sorage); } void reserve(size_t new_capacity) // 扩容 { if (new_capacity > capacity()) { int old_size = size(); //原来的大小 T* newV = new T[new_capacity]; //新申请空间 if (start)//当原有内容不空时 { for (int i = 0; i < size(); i++) //复制进新空间 { newV[i] = start[i]; } } delete[]start;//删除原有空间 start = newV;//指向新空间 finish = start + old_size; end_of_sorage = start + new_capacity; } } void resize(int new_size, const T& value = 0) //扩充大小 { if (new_size <= size()) { finish = start + new_size; } if (new_size > capacity()) { reserve(new_size * 2); } iterator p = finish; finish = start + new_size;//指向新大小 while (p != finish) //填充value { *p = value; p++; } } public: void push_back(const T &c) { insert(end(), c); } public: typedef T* iterator; iterator begin() { return start; } iterator end() { return finish; } public: iterator insert(iterator pos, const T &x) //在pos位置前插入x { if (size() + 1 >= capacity()) { size_t oldpos = pos - start; size_t new_capacity = capacity() ? (capacity() * 2) : 1; reserve(new_capacity); pos = start + oldpos; } T* p = finish; for (; p != pos; p--) { *p = *(p - 1); } *p = x; finish++; return pos; } iterator erase(iterator pos) //删除pos位置值 { T* p = pos; while (p != finish - 1) { *p = *(p + 1); p++; } finish--; return pos; } private: T* start;//指向最开始 T* finish;//指向最后一个元素的下一个位置 T* end_of_sorage;//指向最大容量的下一个位置 };}int main(){ int ar[] = { 1,2,3,4,5,6,7,7 }; bit::vector<int>v1(ar, ar + 6); bit::vector<int>v2; bit::vector<int>v3(10,'a'); v1.erase(v1.end()-1); v1.insert(v1.begin(), 0); v1.swap(v3); for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0;} |
总结
以上所述是小编给大家介绍的c++ vector模拟实现代码，希望对大家有所帮助，也非常感谢大家对服务器之家网站的支持！
原文链接：https://blog.csdn.net/qq_42517365/article/details/104416139
