在学习数据结构的时候,考虑将所有的容器自己实现一遍,可以加深对数据结构的理解,同时需要运用拷贝控制和泛型编程的知识。
vector特点:
1、占据一块连续的内存空间;
2、内部实现是通过管理了一个指针,只是当内存空间不够时,会重新分配一块更大的内存空间,通常是将容量扩大一倍;
3、vector对尾部操作很方便,对头部或者插入都需要O(n)的时间复杂度;
采用模板实现泛型类vector,为了支持大多数的编译器,将实现文件全部放在头文件中,不采用分离编译的方式。
说明:
1、只实现了部分函数的功能,但是类似的可以定义其他的函数;
2、迭代器只是采用定义为指针的方式,这种方式比较简单,但是不能实现迭代器完全的功能。不过迭代器的本质也是将这个指针封装成一个类。在我的另一篇博客里,通过实现了迭代器类来实现List可以参考:http://www.cnblogs.com/liuteng/p/6006533.html
1 /************************************************************************/
2 /* 对vector的实现 */
3 /************************************************************************/
4 #ifndef VECTOR_H
5 #define VECTOR_H
6
7 #define SPACE_CAPACITY 5
8 namespace stl
9 {
10 template<typename Object>
11 class Vector
12 {
13 public:
14 /************************************************************************/
15 /*构造函数
16 /************************************************************************/
17 explicit Vector(int initsize = 0) //选择Vector初始大小
18 :theSize(initsize)
19 ,theCapacity(initsize + SPACE_CAPACITY)
20 {
21 Objects = new Object[theCapacity]; //分配初始空间
22 }
23
24 /************************************************************************/
25 /*拷贝构造函数*/
26 /************************************************************************/
27 Vector(const Vector& V)
28 :theSize(0)
29 ,theCapacity(0)
30 ,Objects(NULL)
31 {
32 *this = V;
33 }
34
35 /************************************************************************/
36 /*析构函数 */
37 /************************************************************************/
38 ~Vector()
39 {
40 delete[ ] Objects;
41 }
42
43 /************************************************************************/
44 /*重载赋值操作符 */
45 /************************************************************************/
46 Vector &operator = (const Vector& ths) //需要定义成const型吗?????
47 {
48 if (this != ths) //防止与本身发生拷贝
49 {
50 delete [] Objects; //销毁原来的内存空间
51 theSize = ths.theSize;
52 theCapacity = ths.theCapacity;
53 Objects = new Object[theCapacity]; //重新分配内存空间
54 //进行深层次的拷贝
55 /* Objects = ths.Objects 这是潜层次的拷贝,只拷贝了指针,
56 ** 如果原对象的对象发生改变,那么拷贝对象的内容也发生改变*/
57 for (int i = 0; i < ths.theSize; ++i)
58 {
59 Objects[i] = ths.Objects[i];
60 }
61 }
62 return *this;
63 }
64
65 /************************************************************************/
66 /* 函数名:resize
67 /* 功 能:改变size大小
68 /* 说 明:改变theSize的大小,theCapacity大小不变
69 /* 时 间:2016.10
70 /************************************************************************/
71 //resize后新定义的对象会怎样被赋值????
72 void resize(int newSize)
73 {
74 if (newSize <= theSize)
75 return;
76 /*如果size大于capacity,则需要重新分配内存空间,内存空间大小是newsize的两倍*/
77 if(newSize > theCapacity)
78 reserve(2 * newSize + 1); //+1是为了保证newsize为0时,为其分配1的空间,有必要吗???
79 theSize = newSize;
80 }
81
82 /************************************************************************/
83 /* 函数名:reserve
84 /* 功 能:重新分配内存空间大小
85 /* 说 明:改变theCapacity的大小,theSize大小不变
86 /* 时 间:2016.10
87 /************************************************************************/
88 void reserve(int newCapacity)
89 {
90 if (newCapacity < theSize)
91 {
92 return;
93 }
94 /*把原有的内容拷贝到零食数组中*/
95 Object * temp = Objects;
96 /*为对象重新分配更大的内存空间*/
97 Objects = new Object[newCapacity];
98 /*把原来的数据拷贝回来,内存空间大小发生变化,但是size没有变*/
99 for (int i = 0; i < theSize; ++i)
100 {
101 Objects[i] = temp[i];
102 }
103 /*释放原来的空间*/
104 delete[] temp;
105 }
106
107 /************************************************************************/
108 /* 函数名:operate[]
109 /* 功 能:重载下标操作符
110 /* 说 明:非常量版本
111 /* 时 间:2016.10
112 /************************************************************************/
113 //下标运算符返回的是元素的引用,定义常量版本和非常量版本
114 Object& operator[] (int index)
115 {
116 return Objects[index]; //指针的下标运算
117 }
118
119 /************************************************************************/
120 /* 函数名:operate[]
121 /* 功 能:重载下标操作符
122 /* 说 明:常量版本
123 /* 时 间:2016.10
124 /************************************************************************/
125 const Object& operator[] (int index) const
126 {
127 return Objects[index];
128 }
129
130 /************************************************************************/
131 /* 函数名:isEmpty
132 /* 功 能:判断Vector是否为空
133 /* 说 明:
134 /* 时 间:2016.10
135 /************************************************************************/
136 bool isEmpty() const
137 {
138 return size() == 0;
139 }
140
141 /************************************************************************/
142 /* 函数名:size
143 /* 功 能:判断Vector的大小
144 /* 说 明:
145 /* 时 间:2016.10
146 /************************************************************************/
147 int size() const
148 {
149 return theSize;
150 }
151
152 /************************************************************************/
153 /* 函数名:capacity
154 /* 功 能:判断Vector的capacity大小
155 /* 说 明:
156 /* 时 间:2016.10
157 /************************************************************************/
158 int capacity() const
159 {
160 return theCapacity;
161 }
162
163 /************************************************************************/
164 /* 函数名:push_back
165 /* 功 能:在vector后面压入一个数据
166 /* 说 明:
167 /* 时 间:2016.10
168 /************************************************************************/
169 void push_back(Object obj)
170 {
171 //判断capacity的空间是否还有
172 if (theSize == theCapacity)
173 {
174 //如果内存空间不够,在现有size基础上扩容一倍
175 reserve(2 * theCapacity + 1);
176 }
177 //size表示元素的总个数,但是下标是从0开始计数,因此下标取不到size
178 Objects[theSize++] = obj;
179 }
180
181 /************************************************************************/
182 /* 函数名:pop_back
183 /* 功 能:在vector后面删除一个数据
184 /* 说 明:
185 /* 时 间:2016.10
186 /************************************************************************/
187 void pop_back()
188 {
189 --theSize; //是不是会导致访问越界后出现的结果不可控的原因?????
190 }
191
192 const Object & back() const
193 {
194 return Objects[size() - 1];
195 }
196
197 typedef Object* iterator;
198 typedef const Object* const_iterator;
199
200 iterator begin()
201 {
202 return &Objects[0];
203 }
204
205 iterator end()
206 {
207 return &Objects[size()];
208 }
209
210 const_iterator cbegin() const
211 {
212 return &Objects[0];
213 }
214
215 const_iterator cend() const
216 {
217 return &Objects[size()];
218 }
219
220 private:
221 int theSize;
222 int theCapacity;
223 Object* Objects; //vector内部实际上是管理了一个数组指针,指向首元素的指针
224 };
225 }
226 #endif
原文链接: https://www.cnblogs.com/liuteng/p/6001592.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/242837
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!