C++ArrayList类手写

  1 #ifndef _ARRAY_LIST_
  2 #define _ARRAY_LIST_
  3 
  4 #pragma warning (disable : 26444)
  5 #pragma warning (disable : 6386)
  6 
  7 #include <iterator>
  8 
  9 
 10 template<typename T>
 11 class arraylist{
 12 public:
 13 struct _iterator;//general pointors
 14 using uint_32 = unsigned int;
 15 using _rank = unsigned int;//std::rank is used to measure dimension
 16 
 17 protected:
 18 static const int minCapacity = 8;
 19 T *_item;//pointer
 20 uint_32 _size;//the numbers of elements
 21 uint_32 _capacity;//capacity >= size
 22 
 23 bool checkSize() const{ return _size < _capacity; }//illegal if return true and can make pushing
 24 void expand();//expand capacity
 25 
 26 #if ITERATOR_SWITCH
 27 void copy_elem(_iterator,_iterator,_iterator);//copy
 28 #endif // iterator switch
 29 void copy_elem(_rank,_rank,_rank);
 30 public:
 31 
 32 //construction and destruction
 33 arraylist();//default
 34 explicit arraylist(const uint_32 &);//default value
 35 arraylist(const uint_32 &,T const &);//size and value 
 36 arraylist(const arraylist<T> &);//copy
 37 arraylist(_iterator,_iterator);//iterator
 38 ~arraylist(){ delete[] _item; };//delete every elements(include classes inside)
 39 
 40 //some opreators
 41 T &operator[](const uint_32 &rank){ return _item[rank]; }//return item[_index]
 42 const T &operator[](const uint_32 &rank) const{ return _item[rank]; }
 43 arraylist<T> &operator=(const arraylist<T> &);//cover
 44 bool operator==(const arraylist<T> &);//whether the elem inside is completely equal
 45 
 46 //get variable
 47 uint_32 size() const{ return _size; }//size
 48 uint_32 capacity() const{ return _capacity; }//capacity
 49 bool empty()const{ return _size == 0; }//is empty?
 50 
 51 void clear();//clear all elements
 52 void reserve(const uint_32 &);//reserve size
 53 void shrink();//shrink capacity to save room
 54 
 55 
 56 T &back(){ if(!empty()) return _item[_size - 1]; }
 57 const T &back() const{ if(!empty()) return _item[_size - 1]; }//last elem
 58 T &front(){ if(!empty()) return _item[0]; }
 59 const T &front() const{ if(!empty()) return _item[0]; }//first elem
 60 const T *date() const{ return _item; }//*item add const is ok
 61 T *date(){ return _item; }//*item add const is ok
 62 
 63 void push_back(const T &value);//push a element to tail
 64 void pop_back();//pop a element of tail
 65 _rank erase(const _rank,const _rank);//eraser elements by rank
 66 _rank erase(const _rank);
 67 
 68 
 69 _iterator erase(_iterator);
 70 _iterator erase(_iterator,_iterator);
 71 _iterator begin(){ return _iterator(_item); }//vector must be non-empty!
 72 _iterator end(){ return _iterator(_item + _size); }//only logical end
 73 
 74 };
 75 
 76 
 77 template<typename T>
 78 void arraylist<T>::expand(){
 79 T *olditem = _item;
 80 _item = new T[_capacity <<= 1];
 81 for(register uint_32 i(0); i < _size; ++i){
 82 _item[i] = olditem[i];
 83 }
 84 delete[] olditem;
 85 }
 86 
 87 
 88 template<typename T>
 89 void arraylist<T>::shrink(){
 90 if(_capacity < (_size << 2) || _capacity <= minCapacity) return;
 91 T * olditem = _item;
 92 _item = new T[_capacity = _size << 1];
 93 for(register uint_32 i(0); i < _size; ++i){
 94 _item[i] = olditem[i];
 95 }
 96 delete[] olditem;
 97 }
 98 
 99 
100 template<typename T>
101 arraylist<T>::arraylist() : _size(0),_capacity(minCapacity){
102 _item = new T[_capacity];
103 }
104 
105 
106 template<typename T>
107 arraylist<T>::arraylist(const uint_32 & size) : _size(size){
108 _item = new T[_capacity = _size];
109 for(register uint_32 i(0); i < _size; ++i){
110 _item[i] = T();//default value
111 }
112 }
113 
114 template<typename T>
115 arraylist<T>::arraylist(const uint_32 & size,T const &value){
116 this->_size = size;
117 _item = new T[_capacity = size];
118 for(uint_32 i = 0; i < size; ++i)
119 _item[i] = T(value);//copy
120 }
121 
122 
123 template<typename T>
124 arraylist<T>::arraylist(const arraylist<T> & arr){
125 this->_size = arr._size;
126 _item = new T[_capacity = arr._capacity];
127 for(register uint_32 i(0); i < arr._size; ++i){
128 _item[i] = arr._item[i];
129 }
130 }
131 
132 template<typename T>
133 arraylist<T> &arraylist<T>::operator=(const arraylist<T> & arr){
134 delete[] _item;
135 _size = arr._size;
136 _item = new T[_capacity = arr._capacity];
137 for(register uint_32 i(0); i < _size; ++i){
138 _item[i] = arr._item[i];
139 }
140 return *this;
141 }
142 
143 
144 template<typename T>
145 void arraylist<T>::copy_elem(_rank start,_rank end,_rank to){
146 for(register uint_32 distance = end - start; distance > 0; --distance,++start,++to){
147 _item[to] = _item[start];
148 }
149 }
150 
151 
152 template<typename T>
153 void arraylist<T>::clear(){
154 while(!empty()){
155 _item[--_size].~T();
156 }
157 delete[] _item;
158 _size = 0;
159 _item = new T[_capacity = minCapacity];
160 }
161 
162 template<typename T>
163 void arraylist<T>::reserve(const uint_32 & size){
164 if(size <= _capacity) return;
165 T * olditem = _item;
166 _item = new T[_capacity = size];
167 for(register uint_32 i(0); i < _size; ++i){
168 _item[i] = olditem[i];
169 }
170 delete[] olditem;
171 }
172 
173 template<typename T>
174 void arraylist<T> ::push_back(const T & value){
175 if(!checkSize())
176 expand();
177 _item[_size++] = value;
178 }
179 
180 template<typename T>
181 void arraylist<T>::pop_back(){
182 if(empty()) return;
183 _item[--_size].~T();
184 }
185 
186 template<typename T>
187 typename arraylist<T>::_rank arraylist<T>::erase(const _rank first,const _rank last){
188 if(first == 0 && last == _size){
189 clear();
190 return first;
191 }
192 copy_elem(last,_size,first);
193 for(uint_32 i = last - first; i > 0; --i){
194 _item[--_size].~T();
195 }
196 return first;
197 }
198 
199 template<typename T>
200 typename arraylist<T>::_rank arraylist<T>::erase(const _rank loc){
201 if(loc == _size - 1){
202 _item[--_size].~T();
203 return _size - 1;
204 }
205 copy_elem(loc + 1,loc);
206 _item[--_size].~T();
207 return loc;
208 }
209 
210 template<typename T>
211 bool arraylist<T>::operator==(const arraylist<T> &arr){
212 if(_size != arr._size) return false;
213 for(register uint_32 i(0); i < _size; ++i){
214 if(_item[i] != arr._item[i])
215 return false;
216 }
217 return true;
218 }
219 
220  
221 
222 #if ITERATOR_SWITCH
223 
224 template<typename T>
225 arraylist<T>::arraylist(_iterator first,_iterator last) : _size(0){
226 _capacity = last - first;
227 _item = new T[_capacity];
228 while(first != last){
229 _item[_size++] = *first++;///6386
230 }
231 }
232 
233 
234 template<typename T>
235 struct arraylist<T>::_iterator :
236 public std::iterator<std::random_access_iterator_tag,T>{
237 public:
238 //equivalently
239 //using iterator_category = std::random_access_iterator_tag;
240 //using value_type = T;
241 //using difference_type = std::ptrdiff_t;
242 //using pointer = T *;
243 //using reference = T &;
244 protected:
245 T *ptr;
246 public:
247 
248 T &operator*() const{ return *ptr; }
249 T *operator->() const{ return ptr; }
250 
251 _iterator &operator=(const _iterator &iter){
252 ptr = iter.ptr;
253 return *this;
254 }
255 _iterator &operator=(const T *array_elem_point){
256 return iterator(array_elem_point);
257 }
258 bool operator<(const _iterator &y) const{
259 return ptr < y.ptr;
260 }
261 bool operator==(const _iterator &iter) const{
262 return ptr == iter.ptr;
263 }
264 bool operator<=(const _iterator &y) const{
265 return ptr <= y.ptr;
266 }
267 bool operator!=(const _iterator &y) const{
268 return ptr != y.ptr;
269 }
270 bool operator>(const _iterator &y) const{
271 return ptr > y.ptr;
272 }
273 bool operator>=(const _iterator &y) const{
274 return ptr >= y.ptr;
275 }
276 
277 _iterator operator+(const uint_32 &rank)const{
278 return _iterator(ptr + rank);
279 }
280 _iterator operator-(const uint_32 & rank){
281 return _iterator(ptr - rank);
282 }
283 uint_32 operator-(const _iterator & iter) const{//must last - front
284 return ptr - iter.ptr;
285 }
286 _iterator &operator+=(const uint_32 & rank){
287 this->ptr += rank;
288 return *this;
289 }
290 _iterator &operator-=(const uint_32 & rank){
291 this->ptr -= rank;
292 return *this;
293 }
294 
295 bool operator!() const{
296 return !ptr;
297 }
298 _iterator &operator++(){//++it return reference
299 ++ptr;
300 return *this;
301 }
302 _iterator operator++(int){//it++ non-reference
303 _iterator old = *this;
304 ++ *this;
305 return old;
306 }
307 _iterator &operator--(){
308 --ptr;
309 return *this;
310 }
311 _iterator operator--(int){//it-- non-reference
312 _iterator old = *this;
313 -- *this;
314 return old;
315 }
316 
317 _iterator() :ptr(nullptr){ }
318 _iterator(T * p) :ptr(p){ }
319 _iterator(const _iterator & iter) :ptr(iter.ptr){ }//useless
320 ~_iterator(){ }
321 };
322 
323 template<typename T>
324 void arraylist<T>::copy_elem(_iterator start,_iterator end,_iterator to){
325 for(register uint_32 distance = end - start; distance > 0; --distance,++to){
326 *to = *start;
327 }
328 }
329 
330 
331 template<typename T>
332 typename arraylist<T>::_iterator arraylist<T>::erase(_iterator loc){
333 if(loc == end() - 1){
334 _item[--_size].~T();
335 return _iterator(_item + _size - 1);
336 }
337 copy_elem(loc + 1,end(),loc);//好迷
338 //https://docs.microsoft.com/zh-cn/visualstudio/code-quality/c26444?view=vs-2017
339 _item[--_size].~T();
340 return loc;
341 }
342 
343 template<typename T>
344 typename arraylist<T>::_iterator arraylist<T>::erase(_iterator first,_iterator last){
345 if(first == begin() && last == end()){
346 clear();
347 return begin();
348 }
349 copy_elem(last,first);
350 for(uint_32 i = last - first; i > 0; --i){
351 _item[--_size].~T();
352 }
353 return first;
354 }
355 
356  
357 
358  
359 
360  
361 
362 #endif // !_ARRAY_LIST_
363 
364 /*
365 arraylist<double> arr;
366 for(int i = 0; i < N; ++i){
367 arr.push_back(rand() % 20);
368 }
369 cout << "size: " << arr.size() << " capacity :" << arr.capacity() << endl;
370 sort(arr.begin(),arr.end());
371 arr.erase(unique(arr.begin(),arr.end()),arr.end());
372 arr.shrink();
373 cout << "After shrink size: " << arr.size() << " capacity :" << arr.capacity() << endl;
374 print(arr);
375 arraylist<double> buf(arr.begin(),arr.begin() + 5);
376 print(buf);
377 arr.erase(0,arr.size());
378 buf.erase(1,3);
379 print(arr);
380 print(buf);
381 
382 
383 */