1 #ifndef VECTOR_H  2 #define VECTOR_H   3   4 #include <memory>  5 #include <algorithm>  6 #include <stddef.h>  7 #include <limits>  8 template <typename T, typename Alloc>  9 class Vector; 10  11 template <typename T, typename Alloc> 12 bool operator== (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 13 template <typename T, typename Alloc> 14 bool operator!= (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 15 template <typename T, typename Alloc> 16 bool operator> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 17 template <typename T, typename Alloc> 18 bool operator>= (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 19 template <typename T, typename Alloc> 20 bool operator< (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 21 template <typename T, typename Alloc> 22 bool operator<= (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 23  24  25 template <typename T, typename Alloc = std::allocator<T> > 26 class Vector 27 { 28     friend bool operator==<T, Alloc> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 29     friend bool operator!=<T, Alloc> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 30     friend bool operator> <T, Alloc> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 31     friend bool operator>=<T, Alloc> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 32     friend bool operator< <T, Alloc> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 33     friend bool operator<=<T, Alloc> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b); 34     35     class reverse_iterator; 36     class const_reverse_iterator; 37 public: 38     typedef T value_type; 39     typedef T *iterator; 40     typedef const T *const_iterator; 41     typedef reverse_iterator reverse_iterator; 42     typedef const_reverse_iterator const_reverse_iterator; 43     typedef T &reference; 44     typedef const T &const_reference; 45     typedef T *pointer; 46     typedef const T *const_pointer; 47     typedef size_t size_type; 48     typedef ptrdiff_t difference_type; 49     typedef Alloc allocator_type; 50 private: 51     //逆序迭代器 52     class reverse_iterator           53     { 54     public: 55         reverse_iterator(iterator it = NULL) :_current(it) { } 56         iterator base() const {return _current; } 57         reverse_iterator &operator++ () 58         { 59             -- _current; 60             return *this; 61         } 62         reverse_iterator operator++ (int) 63         { 64             reverse_iterator tmp(*this); 65             -- _current; 66             return tmp; 67         } 68         reverse_iterator &operator-- () 69         { 70             ++ _current; 71             return *this; 72         } 73         reverse_iterator operator-- (int) 74         { 75             reverse_iterator tmp(*this); 76             ++ _current; 77             return tmp; 78         } 79  80         reference operator*() 81         { 82             return *(_current - 1); 83         } 84  85         const_reference operator*() const 86         { 87             return *(_current - 1); 88         } 89      90         pointer operator-> () 91         { return _current - 1; } 92  93         const_pointer operator-> () const 94         { return _current - 1; } 95  96         friend bool operator== (reverse_iterator i, 97                                 reverse_iterator j) 98         { 99             return i._current == j._current;100         }101 102         friend bool operator!= (reverse_iterator i,103                                 reverse_iterator j)104         {105             return i._current != j._current;106         }107 108 109         friend difference_type operator-(reverse_iterator i,110                                          reverse_iterator j)111         {112             return i._current - j._current;113         }114     private:115             iterator _current;116     };117     //逆序迭代器118 119 120     //const逆序迭代器121     class const_reverse_iterator          122     {123     public:124         const_reverse_iterator(const_iterator it = NULL) :_current(it) { }125         const_reverse_iterator(reverse_iterator it) :_current(it.base()) { }126         const_iterator base() const {return _current; }127         const_reverse_iterator &operator++ ()128         {129             -- _current;130             return *this;131         }132         const_reverse_iterator operator++ (int)133         {134             reverse_iterator tmp(*this);135             -- _current;136             return tmp;137         }138         const_reverse_iterator &operator-- ()139         {140             ++ _current;141             return *this;142         }143         const_reverse_iterator operator-- (int)144         {145             reverse_iterator tmp(*this);146             ++ _current;147             return tmp;148         }149 150         const_reference operator*() const151         {152             return *(_current - 1);153         }154     155 156         const_pointer operator-> () const157         { return _current - 1; }158 159         friend bool operator== (const_reverse_iterator i,160                                 const_reverse_iterator j)161         {162             return i._current == j._current;163         }164 165         friend bool operator!= (const_reverse_iterator i,166                                 const_reverse_iterator j)167         {168             return i._current != j._current;169         }170 171 172         friend difference_type operator-(const_reverse_iterator i,173                                          const_reverse_iterator j)174         {175             return i._current - j._current;176         }177     private:178             const_iterator _current;179     };180     //const逆序迭代器181 182 183 184 public:185     //三种构造Vector的方法186     Vector() { create(); }187 188     explicit Vector(size_type n, const value_type &val = value_type())189     { create(n, val); }190 191     template <typename In>192     Vector(In i, In j)193     { create(i, j); }194     195     //复制v对象196     Vector(const Vector &v)197     { create(v.begin(), v.end()); }198     //赋值函数199     Vector &operator= (const Vector &v);200     //析构函数201     ~Vector() { uncreate(); }202     //assign操作的几种形式203     template <typename In>204     void assign(In i, In j)205     {206         uncreate();207         create(i, j);208     }209 210     void assign(size_type n, const T &val)211     {212         uncreate();213         create(n, val);214     }215     //下标操作216     reference operator[] (size_type index) { return _data[index]; }217     const_reference operator[] (size_type index) const { return _data[index]; }218     //at操作219     reference at(size_type index) { return _data[index]; }220     const_reference at(size_type index) const { return _data[index]; }221     //front、back操作222     reference front() { return *begin(); }223     reference back() { return *rbegin(); }224     const_reference front() const { return *begin(); }225     const_reference back() const { return *rbegin(); }226     227     //pop_back操作228     void pop_back()229     { _alloc.destroy(-- _avail); }230     //insert函数的几种操作231     iterator insert (iterator pos, const value_type &val);232 233     void insert(iterator pos, size_type n, const value_type &val);234 235     template <typename InputIterator>236     void insert(iterator pos, InputIterator first, InputIterator last);237 238     //erase的几种操作239     iterator erase(iterator pos);240 241     iterator erase(iterator first, iterator last);242 243 244     //resize和reserve的操作245     void resize(size_type n, value_type val = value_type());246     void reserve(size_type n);247     248     //判断是否为空、查看元素个数、查看空间大小249     bool empty() const { return _data =http://www.mamicode.com/= _avail; }250     size_type size() const { return _avail - _data; }251 252     size_type capacity() const { return _limit - _data; }253 254     size_type max_size() const255     { return std::numeric_limits<size_type>::max() / sizeof(T); }256     //begin、end迭代器操作257     iterator begin() { return _data; }258     const_iterator begin() const { return _data; }259 260     iterator end() { return _avail; }261     const_iterator end() const { return _avail; }262 263     //rbegin、rend迭代器操作264     reverse_iterator rbegin() { return reverse_iterator(_avail); }265     reverse_iterator rend() { return reverse_iterator(_data); }266 267     const_reverse_iterator rbegin() const { return const_reverse_iterator(_avail); }268     const_reverse_iterator rend() const { return const_reverse_iterator(_data); }269     //push_back操作270     void push_back(const T &t)271     {272         if(_avail == _limit)273             grow();274         unCheckdAppend(t);275     }276 277     //与other对象进行交换278     void swap(Vector &other)279     {280         std::swap(_data, other._data);281         std::swap(_avail, other._avail);282         std::swap(_limit, other._limit);283     }284     //  285     allocator_type get_allocator() const286     { return _alloc; }287 288 289 private:290     iterator _data;             //数组首元素291     iterator _avail;            //数组最后一个元素的下一个位置292     iterator _limit;            //最后一块内存的下一块位置293 294     std::allocator<T> _alloc;   //内存分配器295 296 297     void create();298     void create(size_type, const value_type &);299 300     template <typename In>301     void create(In i, In j);302 303 304     void uncreate();305 306     void grow();            //内存增长307     void unCheckdAppend(const T &val);308 309     void growTon(size_type n);310 };311 //复制构造函数312 template <typename T, typename Alloc>313 Vector<T, Alloc> &Vector<T, Alloc>::operator= (const Vector &v)314 {315     if(this != &v)316     {317         uncreate();318         create(v.begin(), v.end());319     }320 321     return *this;322 }323 324 325 //三个构造函数326 template <typename T, typename Alloc>327 void Vector<T,Alloc>::create()328 {329     _data = http://www.mamicode.com/_avail = _limit = NULL;330 }331 332 333 template <typename T, typename Alloc>334 void Vector<T, Alloc>::create(size_type n, const T &val)335 {336     //先分配内存337     _data =http://www.mamicode.com/ _alloc.allocate(n);338     //初始化赋值339     std::uninitialized_fill(_data, _data + n, val);340     _avail = _limit = _data + n;341 }342 343     344 template <typename T, typename Alloc>345 template <typename In>346 void Vector<T, Alloc>::create(In i, In j)347 {348     _data = http://www.mamicode.com/_alloc.allocate(j - i);349 350     _avail = _limit = std::uninitialized_copy(i, j, _data);351 352 }353 354     355 //析构函数356 template <typename T, typename Alloc>357 void Vector<T, Alloc>::uncreate()358 {359     //先执行析构函数360     if(_data)361     {362         iterator it(_avail);363         while(it != _data)364         {365             _alloc.destroy(-- it);366         }367     }368 369     //释放内存370     _alloc.deallocate(_data, _limit - _data);371     _data = http://www.mamicode.com/_avail = _limit = NULL;372 }373 374 375 376 //grow函数377 template <typename T, typename Alloc>378 void Vector<T, Alloc>::grow()379 {380     //确定size381     size_type new_size = std::max(2 * (_limit - _data), difference_type(1));382     383     growTon(new_size);384 }385 386 387 //unCheckdAppend函数388 template <typename T, typename Alloc>389 void Vector<T, Alloc>::unCheckdAppend(const T &val)390 {391     _alloc.construct(_avail ++, val);392 }393 394 395 //growTon函数396 template <typename T, typename Alloc>397 void Vector<T, Alloc>::growTon(size_type n)398 {399     iterator new_data =http://www.mamicode.com/ _alloc.allocate(n);400     iterator new_avail = std::uninitialized_copy(_data, _avail, new_data);401 402     uncreate();403 404     _data =http://www.mamicode.com/ new_data;405     _avail = new_avail;406     _limit = _data + n;407 }408 409 410 //insert函数411 412 template <typename T, typename Alloc>413 typename Vector<T, Alloc>::iterator Vector<T, Alloc>::insert(iterator pos, const value_type &val)414 {415     difference_type i = pos - _data;416     insert(pos, 1, val);417     return pos + i;418 }419 420 421 template <typename T, typename Alloc>422 void Vector<T, Alloc>::insert(iterator pos, size_type n, const value_type &val)423 {424     difference_type i = pos - _data;425     while(static_cast<size_type>(_limit - _avail) < n)426         grow();427     pos = _data + i;428 429     size_type left = _avail - pos;430 431     if(n < left)432     {433         size_type len = _avail - pos;434         size_type copyLen = len - n;435         std::uninitialized_copy(pos + copyLen, _avail, _avail);436         std::copy_backward(pos, pos + copyLen, _avail);437 438         std::fill_n(pos, n, val);439     }440     else if(n > left)441     {442         std::uninitialized_copy(pos, _avail, pos + n);443 444         std::fill_n(pos, _avail - pos, val);445         std::uninitialized_fill(_avail, pos + n, val);446     }447     else448     {449         std::uninitialized_copy(pos, _avail, _avail);450         std::fill_n(pos, n, val);451     }452 453     _avail = _avail + n;454 }455 456 template <typename T, typename Alloc>457 template <typename InputIterator>458 void Vector<T, Alloc>::insert(iterator pos, InputIterator first, InputIterator last)459 {460     difference_type i = pos - _data;461     size_type n = last - first;462     while(static_cast<size_type>(_limit - _avail) < n)463         grow();464     pos = _data + i;465 466     size_type left = _avail - pos;467     if(n < left)468     {469         size_type len = _avail - pos;470         size_type copyLen = len - n;471         std::uninitialized_copy(pos + copyLen, _avail, _avail);472         std::copy_backward(pos, pos + copyLen, _avail);473 474         std::copy(first, last, pos); 475     }476     else if(n > left)477     {478         std::uninitialized_copy(pos, _avail, pos + n);479         480         std::copy(first, first + left, pos);481         std::uninitialized_copy(first + left, last, _avail);482     }483     else484     {485         std::uninitialized_copy(pos, _avail, _avail);486 487         std::copy(first, last, pos);488     }489 490     _avail = _avail + n;491 }492 493 494 //erase函数495 496 template <typename T, typename Alloc>497 typename Vector<T, Alloc>::iterator Vector<T, Alloc>::erase(iterator pos)498 {499     std::copy(pos + 1, _avail, pos);500     _alloc.destroy(-- _avail);501     return pos;502 }503 504 template <typename T, typename Alloc>505 typename Vector<T, Alloc>::iterator Vector<T, Alloc>::erase(iterator first, iterator last)506 {507     difference_type left = _avail - last;508     std::copy(last, _avail, first);509 510     iterator it(first + left);511     while(_avail != it)512         _alloc.destroy(-- _avail);513     return first;514 }515 516 517 //resize函数518 template <typename T, typename Alloc>519 void Vector<T, Alloc>::resize(size_type n, value_type val)520 {521     size_type cur_size = size();522     if(n < cur_size)523     {524         size_type diff = cur_size - n;525         while(diff --)526             _alloc.destroy(-- _avail);527     }528     else if(n > cur_size)529     {530         size_type diff = n - cur_size;531         size_type left = static_cast<size_type>(_limit - _avail);532         if(left < diff)533             growTon(n);534 535         while(size() < n)536             unCheckdAppend(val);537     }538 }539 540 template <typename T, typename Alloc>541 void Vector<T, Alloc>::reserve(size_type n)542 {543     size_type cur_cap = capacity();544     if(n > cur_cap)545         growTon(n);546 }547 548 549 //运算符重载550 template <typename T, typename Alloc>551 bool operator== (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b)552 {553     return a.size() == b.size() && 554            std::equal(a.begin(), a.end(), b.begin() );555 }556 557 558 template <typename T, typename Alloc>559 bool operator!= (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b)560 {561     return !(a == b);562 }563 564 565 template <typename T, typename Alloc>566 bool operator< (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b)567 {568     typedef typename Vector<T, Alloc>::size_type size_type;569     size_type size1 = a.size();570     size_type size2 = b.size();571     size_type min =(size1 < size2) ? size1 : size2;572     size_type i = 0;573     for(; i != min; ++ i)574     {575         if(a[i] < b[i])576             return true;577         else if(a[i] > b[i])578             return false;579     }580     if(i != size2)581         return true;582     return false;583 }584 585 586 template <typename T, typename Alloc>587 bool operator<= (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b)588 {589     return !(a > b);590 }591 592 593 template <typename T, typename Alloc>594 bool operator> (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b)595 {596     return b < a;597 }598 599 600 template <typename T, typename Alloc>601 bool operator>= (const Vector<T, Alloc> &a, const Vector<T, Alloc> &b)602 {603     return !(a < b);604 }605 606 607 #endif  /*VECTOR_H*/

 1 #include "Vector.hpp" 2 #include <iostream> 3 #include <string> 4 using namespace std; 5  6 //测试const reverse迭代器 7 void print(const Vector<string> &vec) 8 { 9     for(Vector<string>::const_reverse_iterator it = vec.rbegin();10         it != vec.rend();11         ++it)12     {13         cout << *it << " ";14     }15     cout << endl;16 }17 18 int main(int argc, char const *argv[])19 {20     Vector<string> vec(3, "hello");21 22     for(Vector<string>::const_iterator it = vec.begin();23         it != vec.end();24         ++it)25     {26         cout << *it << " ";27     }28     cout << endl;29 30     cout << "size = " << vec.size() << endl;31     cout << "capacity = " << vec.capacity() << endl;32     vec.push_back("foo");33     vec.push_back("bar");34 35     cout << "size = " << vec.size() << endl;36     cout << "capacity = " << vec.capacity() << endl;37 38     for(Vector<string>::reverse_iterator it = vec.rbegin();39         it != vec.rend();40         ++it)41     {42         cout << *it << " ";43     }44     cout << endl;45 46 47     print(vec);48 49     Vector<string> vec2;50     vec2.push_back("beijing");51     vec2.push_back("shanghai");52     vec2.push_back("guangzhou");53     print(vec2);54 55     vec.swap(vec2);56     print(vec);57     print(vec2);58 59     return 0;60 }