vector

   1 // vi:ft=cpp
   2 #ifndef _STL_VECTOR_H
   3 #define _STL_VECTOR_H
   4
   5 #include "memory"
   6 #include "iterator"
   7 #include "stdexcept"
   8 #include "type_traits"
   9
  10 namespace std {
  11
  12 /* Forward declarations of vector and __vector_iterator */
  13
  14 template <class T, class Allocator = allocator<T>, bool BCheck = false>
  15 class vector;
  16
  17 template <class T, bool BCheck>
  18 class __vector_iterator;
  19
  20 /* Normal vector iterator (not checked) */
  21
  22 template <class T>
  23 class __vector_iterator<T, false>: public std::iterator<random_access_iterator_tag, T> {
  24     public:
  25         __vector_iterator(){ ptr_ = NULL; }
  26         __vector_iterator(const __vector_iterator &b){ ptr_ = b.ptr_; }
  27         __vector_iterator &operator = (const __vector_iterator &b){ ptr_ = b.ptr_; return *this; }
  28         __vector_iterator &operator ++ () { ++ptr_; return *this; }
  29         __vector_iterator operator ++ (int) { __vector_iterator copy = *this; ++*this; return copy; }
  30         __vector_iterator &operator -- () { --ptr_; return *this; }
  31         __vector_iterator operator -- (int) { __vector_iterator copy = *this; --*this; return copy; }
  32         __vector_iterator &operator += (ptrdiff_t n) { ptr_ += n; return *this; }
  33         __vector_iterator &operator -= (ptrdiff_t n) { ptr_ -= n; return *this; }
  34         __vector_iterator operator + (ptrdiff_t n) const { __vector_iterator copy = *this; copy += n; return copy; }
  35         __vector_iterator operator - (ptrdiff_t n) const { __vector_iterator copy = *this; copy -= n; return copy; }
  36         T &operator [] (ptrdiff_t n) const { return ptr_[n]; }
  37         T &operator * () const { return *ptr_; }
  38     private:
  39         T *ptr_;
  40
  41         // constructor used internally
  42         __vector_iterator(const T *init_array, size_t init_size, T *init_p){ ptr_ = init_p; }
  43
  44         bool get_base_pointer() const { return false; }
  45
  46         void check() const {};
  47         void invalidate(){};
  48
  49     template <class, class, bool>
  50     friend class vector;
  51
  52     template <class T1, bool B1, class T2, bool B2>
  53     friend bool operator == (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  54     template <class T1, bool B1, class T2, bool B2>
  55     friend bool operator != (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  56     template <class T1, bool B1, class T2, bool B2>
  57     friend bool operator < (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  58     template <class T1, bool B1, class T2, bool B2>
  59     friend bool operator > (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  60     template <class T1, bool B1, class T2, bool B2>
  61     friend bool operator <= (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  62     template <class T1, bool B1, class T2, bool B2>
  63     friend bool operator >= (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  64     template <class T1, bool B1, class T2, bool B2>
  65     friend ptrdiff_t operator - (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
  66
  67 };
  68
  69 /* Bounds-checked vector iterator */
  70
  71 template <class T>
  72 class __vector_iterator<T, true>: public std::iterator<random_access_iterator_tag, T> {
  73     public:
  74         __vector_iterator(){ }
  75         __vector_iterator(const __vector_iterator &b){ init_ = true; array_ = b.array_; size_ = b.size_; ptr_ = b.ptr_; }
  76         __vector_iterator &operator = (const __vector_iterator &b)
  77           { init_ = true; invalidated_ = false; array_ = b.array_; size_ = b.size_; ptr_ = b.ptr_; return *this; }
  78         __vector_iterator &operator ++ () { return *this += 1; }
  79         __vector_iterator &operator -- () { return *this -= 1; }
  80         __vector_iterator operator ++ (int) { __vector_iterator copy = *this; ++*this; return copy; }
  81         __vector_iterator operator -- (int) { __vector_iterator copy = *this; --*this; return copy; }
  82         __vector_iterator operator + (ptrdiff_t n) const { __vector_iterator copy = *this; copy += n; return copy; }
  83         __vector_iterator operator - (ptrdiff_t n) const { __vector_iterator copy = *this; copy -= n; return copy; }
  84         __vector_iterator &operator -= (ptrdiff_t n) { return *this += -n; }
  85         T &operator [] (ptrdiff_t n) const { return *(*this + n); }
  86
  87         /* these are the only bounds-checking functions */
  88         __vector_iterator &operator += (ptrdiff_t n)
  89         {
  90             check();
  91             T *new_ptr = ptr_ + n;
  92             if (new_ptr < array_ || new_ptr > (array_ + size_)){
  93                 if (n > 0){
  94                     throw out_of_range("increment of vector iterator would exceed vector bounds");
  95                 } else {
  96                     throw out_of_range("decrement of vector iterator would exceed vector bounds");
  97                 }
  98             }
  99             ptr_ = new_ptr;
 100             return *this;
 101         }
 102
 103         T &operator * () const
 104         {
 105             check();
 106             if (ptr_ == array_ + size_){
 107                 throw out_of_range("attempt to dereference vector::end()");
 108             }
 109             return *ptr_;
 110         }
 111
 112     private:
 113         T *ptr_;
 114         bool invalidated_ : 1; // marked true when iterator is invalidated
 115         bool init_ : 1;        // initialised?
 116         const T *array_;
 117         size_t size_;
 118
 119         // constructor used internally
 120         __vector_iterator(const T *init_array, size_t init_size, T *init_p)
 121         { invalidated_ = false; init_ = true; array_ = init_array; size_ = init_size; ptr_ = init_p; }
 122
 123         /* throw an exception if the iterator is invalid */
 124         void check() const
 125         {
 126             if (!init_){
 127                 throw logic_error("attempt to use uninitialised vector iterator");
 128             } else if (invalidated_){
 129                 throw logic_error("attempt to use invalidated vector iterator");
 130             }
 131         }
 132
 133         /* mark the iterator as invalid */
 134         void invalidate(){ invalidated_ = true; }
 135
 136         const T *get_base_pointer() const { return array_; }
 137
 138     template <class, class, bool>
 139     friend class vector;
 140
 141     template <class T1, bool B1, class T2, bool B2>
 142     friend bool operator == (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 143     template <class T1, bool B1, class T2, bool B2>
 144     friend bool operator != (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 145     template <class T1, bool B1, class T2, bool B2>
 146     friend bool operator < (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 147     template <class T1, bool B1, class T2, bool B2>
 148     friend bool operator > (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 149     template <class T1, bool B1, class T2, bool B2>
 150     friend bool operator <= (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 151     template <class T1, bool B1, class T2, bool B2>
 152     friend bool operator >= (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 153     template <class T1, bool B1, class T2, bool B2>
 154     friend ptrdiff_t operator - (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b);
 155
 156 };
 157
 158 /* Comparisons and other operators on iterators */
 159
 160 template <class T1, bool B1, class T2, bool B2>
 161 bool operator == (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 162 {
 163     a.check();
 164     b.check();
 165     return a.ptr_ == b.ptr_;
 166 }
 167
 168 template <class T1, bool B1, class T2, bool B2>
 169 bool operator != (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 170 {
 171     a.check();
 172     b.check();
 173     return a.ptr_ != b.ptr_;
 174 }
 175
 176 template <class T1, bool B1, class T2, bool B2>
 177 bool operator < (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 178 {
 179     a.check();
 180     b.check();
 181     if (B1 && B2 && a.get_base_pointer() != b.get_base_pointer()){
 182         throw out_of_range("attempt to compare vector iterators of different vectors");
 183     }
 184     return a.ptr_ < b.ptr_;
 185 }
 186
 187 template <class T1, bool B1, class T2, bool B2>
 188 bool operator > (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 189 {
 190     a.check();
 191     b.check();
 192     if (B1 && B2 && a.get_base_pointer() != b.get_base_pointer()){
 193         throw out_of_range("attempt to compare vector iterators of different vectors");
 194     }
 195     return a.ptr_ > b.ptr_;
 196 }
 197
 198 template <class T1, bool B1, class T2, bool B2>
 199 bool operator <= (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 200 {
 201     a.check();
 202     b.check();
 203     if (B1 && B2 && a.get_base_pointer() != b.get_base_pointer()){
 204         throw out_of_range("attempt to compare vector iterators of different vectors");
 205     }
 206     return a.ptr_ <= b.ptr_;
 207 }
 208
 209 template <class T1, bool B1, class T2, bool B2>
 210 bool operator >= (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 211 {
 212     a.check();
 213     b.check();
 214     if (B1 && B2 && a.get_base_pointer() != b.get_base_pointer()){
 215         throw out_of_range("attempt to compare vector iterators of different vectors");
 216     }
 217     return a.ptr_ >= b.ptr_;
 218 }
 219
 220 template <class T1, bool B1, class T2, bool B2>
 221 ptrdiff_t operator - (const __vector_iterator<T1, B1> &a, const __vector_iterator<T2, B2> &b)
 222 {
 223     a.check();
 224     b.check();
 225     if (B1 && B2 && a.get_base_pointer() != b.get_base_pointer()){
 226         throw out_of_range("attempt to subtract vector iterators of different vectors");
 227     }
 228     return a.ptr_ - b.ptr_;
 229 }
 230
 231 /* Vector implementation */
 232
 233 template <class T, class Allocator, bool BCheck>
 234 class vector {
 235 public:
 236     typedef typename Allocator::reference reference;
 237     typedef typename Allocator::const_reference const_reference;
 238     typedef size_t size_type;
 239     typedef ptrdiff_t difference_type;
 240     typedef T value_type;
 241     typedef Allocator allocator_type;
 242     typedef typename Allocator::pointer pointer;
 243     typedef typename Allocator::const_pointer const_pointer;
 244
 245     typedef __vector_iterator<T, BCheck> iterator;
 246     typedef __vector_iterator<const T, BCheck> const_iterator;
 247     typedef std::reverse_iterator<iterator> reverse_iterator;
 248     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 249
 250     explicit vector(const Allocator &new_allocator = Allocator()):
 251         allocator_(new_allocator)
 252     {
 253         init();
 254     }
 255
 256     explicit vector(size_type n, const T &value = T(), const Allocator &new_allocator = Allocator()):
 257         allocator_(new_allocator)
 258     {
 259         init();
 260         assign(n, value);
 261     }
 262
 263     template <class InputIterator>
 264       vector(InputIterator first, InputIterator last, const Allocator &new_allocator = Allocator()):
 265         allocator_(new_allocator)
 266     {
 267         init();
 268         assign(first, last);
 269     }
 270
 271     vector(const vector &x):
 272         allocator_(x.get_allocator())
 273     {
 274         init();
 275         *this = x;
 276     }
 277
 278     vector(vector &&x):
 279         allocator_(x.get_allocator())
 280     {
 281         init();
 282         *this = move(x);
 283     }
 284
 285     ~vector()
 286     {
 287         finit();
 288     }
 289
 290     vector &operator = (const vector &x)
 291     {
 292         clear();
 293         reserve(x.size());
 294         for (const_iterator i=x.begin(); i!=x.end(); ++i){
 295             push_back(*i);
 296         }
 297         return *this;
 298     }
 299
 300     vector &operator = (vector &&x)
 301     {
 302         finit();
 303         // nick x's resources
 304         array_ = x.array_;
 305         size_ = x.size_;
 306         capacity_ = x.capacity_;
 307         x.init();
 308     }
 309
 310     iterator begin(){ return iterator(array_, size_, array_); }
 311     iterator end() { return iterator(array_, size_, array_ + size_); }
 312     reverse_iterator rbegin(){ return reverse_iterator(end()); }
 313     reverse_iterator rend(){ return reverse_iterator(begin()); }
 314
 315     const_iterator begin() const { return const_iterator(array_, size_, array_); }
 316     const_iterator end() const { return const_iterator(array_, size_, array_ + size_); }
 317     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
 318     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
 319
 320     size_type size() const { return size_; }
 321     size_type max_size() const { return allocator_.max_size(); }
 322     size_type capacity() const { return capacity_; }
 323     bool empty() const { return size_ == 0; }
 324
 325     void reserve(size_type n)
 326     {
 327         if (capacity_ < n){
 328             // allocate new array
 329             T *new_array = allocator_.allocate(n, array_);
 330             // copy all existing elements and destroy old ones
 331             for (size_type i=0; i<size_; ++i){
 332                 allocator_.construct(new_array + i, move(array_[i]));
 333                 allocator_.destroy(array_ + i);
 334             }
 335             // free old array
 336             allocator_.deallocate(array_, capacity_);
 337
 338             array_ = new_array;
 339             capacity_ = n;
 340         }
 341     }
 342
 343     void resize(size_type n, T c = T())
 344     {
 345         if (n > size_){
 346             // expand
 347             reserve(n);
 348             for (size_type i=size_; i<n; ++i){
 349                 allocator_.construct(array_ + i, c);
 350             }
 351         } else {
 352             // contract
 353             for (size_type i=n-1; i>=size_; --i){
 354                 allocator_.destroy(array_ + i);
 355             }
 356         }
 357         size_ = n;
 358     }
 359
 360     reference operator [] (size_type n){ return *(begin() + n); }
 361     const_reference operator [] (size_type n) const { return *(begin() + n); }
 362
 363     reference at(size_type n)
 364     {
 365         if (n >= 0 && n < size_){
 366             return array_[n];
 367         } else {
 368             throw out_of_range("vector index out of range");
 369         }
 370     }
 371
 372     const_reference at(size_type n) const
 373     {
 374         if (n >= 0 && n < size_){
 375             return array_[n];
 376         } else {
 377             throw out_of_range("vector index out of range");
 378         }
 379     }
 380
 381     reference front(){ return *begin(); }
 382     const_reference front() const { return *begin(); }
 383     reference back(){ return end()[-1]; }
 384     const_reference back() const { return end()[-1]; }
 385
 386 private:
 387     /* Hack to fix vector::assign<int, int> ambiguity */
 388     template <bool is_integer, class SuspiciousType>
 389     struct __assign;
 390
 391     /* version for iterator, iterator */
 392     template <class InputIterator>
 393     struct __assign<false, InputIterator> {
 394         static void run(vector *__this, InputIterator first, InputIterator last)
 395         {
 396             size_t n = distance(first, last);
 397             size_type i;
 398             __this->clear();
 399             __this->reserve(n);
 400             i = 0;
 401             while (first != last){
 402                 __this->allocator_.construct(__this->array_ + i++, *first++);
 403             }
 404             __this->size_ = n;
 405         }
 406     };
 407
 408     /* version for int, int */
 409     template <class INT>
 410     struct __assign<true, INT> {
 411         static void run(vector *__this, INT n, INT u)
 412         {
 413             __this->assign(value_iterator<T>(u, 0), value_iterator<T>(u, n));
 414         }
 415     };
 416
 417 public:
 418     template <class SuspectType>
 419     void assign(SuspectType first, SuspectType last)
 420     {
 421         // If InputIterator is actually an integral type, it's not an iterator.
 422         // Furthermore, the call should have been to the following (size_type n, const T &u)
 423         // overload, so invoke the correct specialisation of __assign (defined further down).
 424         __assign<is_integral<SuspectType>::value, SuspectType>::run(this, first, last);
 425     }
 426
 427     void assign(size_type n, const T &u)
 428     {
 429         assign(value_iterator<T>(u, 0), value_iterator<T>(u, n));
 430     }
 431
 432     void push_back(const T &x)
 433     {
 434         reserve(size_ + 1);
 435         allocator_.construct(array_ + size_, x);
 436         ++size_;
 437     }
 438
 439     void pop_back()
 440     {
 441         if (size_ > 0){
 442             allocator_.destroy(array_ + size_ - 1);
 443             --size_;
 444         } else if (BCheck){
 445             throw out_of_range("attempt to pop empty vector");
 446         }
 447     }
 448
 449 private:
 450     template <bool is_integer, class SuspectType> struct __insert;
 451     template  <class InputIterator> struct __insert<false, InputIterator> {
 452         static void run(vector *__this, iterator position, InputIterator first, InputIterator last)
 453         {
 454             size_t off = position - __this->begin(),
 455                    distance = std::distance(first, last);
 456             __this->shift(off, distance);
 457             std::copy(first, last, __this->array_ + off);
 458         }
 459     };
 460     template <class IntType> struct __insert<true, IntType> {
 461         static void run(vector *__this, iterator position, IntType n, IntType x)
 462         {
 463             __insert<false, value_iterator<T> >::run(__this, position, value_iterator<T>(x, 0), value_iterator<T>(x, n));
 464         }
 465     };
 466
 467 public:
 468     iterator insert(iterator position, const T &x)
 469     {
 470         size_t off = position - begin();
 471         shift(off, 1);
 472         allocator_.construct(array_ + off, x);
 473         return begin() + off;
 474     }
 475
 476     void insert(iterator position, size_type n, const T &x)
 477     {
 478         __insert<false, value_iterator<T> >::run(this, position, value_iterator<T>(x, 0), value_iterator<T>(x, n));
 479     }
 480
 481     template <class SuspectType>
 482     void insert(iterator position, SuspectType first, SuspectType last)
 483     {
 484         __insert<is_integral<SuspectType>::value, SuspectType>::run(this, position, first, last);
 485     }
 486
 487     iterator erase(iterator position)
 488     {
 489         size_t off = position - begin();
 490         unshift(off, 1);
 491         return begin() + off;
 492     }
 493
 494     iterator erase(iterator first, iterator last)
 495     {
 496         size_t off = first - begin();
 497         unshift(off, last - first);
 498         return begin() + off;
 499     }
 500
 501     void swap(vector &vec)
 502     {
 503         std::swap(*this, vec);
 504     }
 505
 506     void clear()
 507     {
 508         size_type i;
 509         for (i=0; i<size_; ++i){
 510             allocator_.destroy(array_ + i);
 511         }
 512         size_ = 0;
 513     }
 514
 515     allocator_type get_allocator() const { return allocator_; }
 516
 517 private:
 518     T *array_;
 519     size_type size_;
 520     size_type capacity_;
 521     Allocator allocator_;
 522
 523     // Initialise vector
 524     void init()
 525     {
 526         array_ = NULL;
 527         size_ = NULL;
 528         capacity_ = NULL;
 529     }
 530
 531     // Free all resources
 532     void finit()
 533     {
 534         clear();
 535         allocator_.deallocate(array_, capacity_);
 536     }
 537
 538     // Increase size, and move [pos .. end] n elements to the right
 539     void shift(size_t pos, size_t n)
 540     {
 541         if (BCheck && pos > size_){
 542             throw out_of_range("attempt to insert beyond end of vector");
 543         }
 544         reserve(size_ + n);
 545         std::move_backward(array_ + pos, array_ + size_, array_ + size_ + n);
 546         size_ += n;
 547     }
 548
 549     // Move [pos+n .. end] n elements to the left, and reduce size
 550     void unshift(size_t pos, size_t n)
 551     {
 552         if (BCheck && (pos + n > size_)){
 553             throw out_of_range("attempt to erase beyond end of vector");
 554         }
 555         std::move(array_ + pos + n, array_ + size_, array_ + pos);
 556         size_ -= n;
 557     }
 558 };
 559
 560
 561 }
 562
 563 #endif