libstdc++/stl/vector.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 #ifndef __SGI_STL_VECTOR_H
  28 #define __SGI_STL_VECTOR_H
  29
  30 #include <stddef.h>
  31 #include <algobase.h>
  32 #include <alloc.h>
  33
  34 template <class T, class Alloc = alloc>
  35 class vector {
  36 public:
  37     typedef T value_type;
  38     typedef value_type* pointer;
  39     typedef value_type* iterator;
  40     typedef const value_type* const_iterator;
  41     typedef value_type& reference;
  42     typedef const value_type& const_reference;
  43     typedef size_t size_type;
  44     typedef ptrdiff_t difference_type;
  45     typedef reverse_iterator<const_iterator, value_type, const_reference,
  46                              difference_type>  const_reverse_iterator;
  47     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  48         reverse_iterator;
  49 protected:
  50     typedef simple_alloc<value_type, Alloc> data_allocator;
  51     iterator start;
  52     iterator finish;
  53     iterator end_of_storage;
  54     void insert_aux(iterator position, const T& x);
  55     void deallocate() {
  56       if (start) data_allocator::deallocate(start, end_of_storage - start);
  57     }
  58 public:
  59     iterator begin() { return start; }
  60     const_iterator begin() const { return start; }
  61     iterator end() { return finish; }
  62     const_iterator end() const { return finish; }
  63     reverse_iterator rbegin() { return reverse_iterator(end()); }
  64     const_reverse_iterator rbegin() const {
  65         return const_reverse_iterator(end());
  66     }
  67     reverse_iterator rend() { return reverse_iterator(begin()); }
  68     const_reverse_iterator rend() const {
  69         return const_reverse_iterator(begin());
  70     }
  71     size_type size() const { return size_type(end() - begin()); }
  72     size_type max_size() const { return size_type(-1); }
  73     size_type capacity() const { return size_type(end_of_storage - begin()); }
  74     bool empty() const { return begin() == end(); }
  75     reference operator[](size_type n) { return *(begin() + n); }
  76     const_reference operator[](size_type n) const { return *(begin() + n); }
  77     vector() : start(0), finish(0), end_of_storage(0) {}
  78     vector(size_type n, const T& value) {
  79       start = allocate_and_fill(n, value);
  80       finish = start + n;
  81       end_of_storage = finish;
  82     }
  83     explicit vector(size_type n) {
  84       start = allocate_and_fill(n, T());
  85       finish = start + n;
  86       end_of_storage = finish;
  87     }
  88     vector(const vector<T, Alloc>& x) {
  89       start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
  90       finish = start + (x.end() - x.begin());
  91       end_of_storage = finish;
  92     }
  93 #ifdef __STL_MEMBER_TEMPLATES
  94     template <class InputIterator>
  95     vector(InputIterator first, InputIterator last) :
  96       start(0), finish(0), end_of_storage(0) {
  97         range_initialize(first, last, iterator_category(first));
  98     }
  99 #else /* __STL_MEMBER_TEMPLATES */
 100     vector(const_iterator first, const_iterator last) {
 101       size_type n = 0;
 102       distance(first, last, n);
 103       start = allocate_and_copy(n, first, last);
 104       finish = start + n;
 105       end_of_storage = finish;
 106     }
 107 #endif /* __STL_MEMBER_TEMPLATES */
 108     ~vector() {
 109         destroy(start, finish);
 110         deallocate();
 111     }
 112     vector<T, Alloc>& operator=(const vector<T, Alloc>& x);
 113     void reserve(size_type n) {
 114       if (capacity() < n) {
 115         const size_type old_size = size();
 116         const iterator tmp = allocate_and_copy(n, start, finish);
 117         destroy(start, finish);
 118         deallocate();
 119         start = tmp;
 120         finish = tmp + old_size;
 121         end_of_storage = start + n;
 122       }
 123     }
 124     reference front() { return *begin(); }
 125     const_reference front() const { return *begin(); }
 126     reference back() { return *(end() - 1); }
 127     const_reference back() const { return *(end() - 1); }
 128     void push_back(const T& x) {
 129         if (finish != end_of_storage) {
 130             construct(finish, x);
 131             ++finish;
 132         } else
 133             insert_aux(end(), x);
 134     }
 135     void swap(vector<T, Alloc>& x) {
 136         ::swap(start, x.start);
 137         ::swap(finish, x.finish);
 138         ::swap(end_of_storage, x.end_of_storage);
 139     }
 140     iterator insert(iterator position, const T& x) {
 141         size_type n = position - begin();
 142         if (finish != end_of_storage && position == end()) {
 143             construct(finish, x);
 144             ++finish;
 145         } else
 146             insert_aux(position, x);
 147         return begin() + n;
 148     }
 149     iterator insert(iterator position) { return insert(position, T()); }
 150 #ifdef __STL_MEMBER_TEMPLATES
 151     template <class InputIterator>
 152     void insert(iterator position, InputIterator first, InputIterator last) {
 153       range_insert(position, first, last, iterator_category(first));
 154     }
 155 #else /* __STL_MEMBER_TEMPLATES */
 156     void insert(iterator position,
 157                 const_iterator first, const_iterator last);
 158 #endif /* __STL_MEMBER_TEMPLATES */
 159     void insert (iterator position, size_type n, const T& x);
 160     void pop_back() {
 161         --finish;
 162         destroy(finish);
 163     }
 164     void erase(iterator position) {
 165         if (position + 1 != end())
 166             copy(position + 1, finish, position);
 167         --finish;
 168         destroy(finish);
 169     }
 170     void erase(iterator first, iterator last) {
 171         iterator i = copy(last, finish, first);
 172         destroy(i, finish);
 173         finish = finish - (last - first);
 174     }
 175     void resize(size_type new_size, const T& x) {
 176       if (new_size < size())
 177         erase(begin() + new_size, end());
 178       else
 179         insert(end(), new_size - size(), x);
 180     }
 181     void resize(size_type new_size) { resize(new_size, T()); }
 182     void clear() { erase(begin(), end()); }
 183
 184 protected:
 185     iterator allocate_and_fill(size_type n, const T& x) {
 186       iterator result = data_allocator::allocate(n);
 187 #         ifdef __STL_USE_EXCEPTIONS
 188       try {
 189 #         endif /* __STL_USE_EXCEPTIONS */
 190         uninitialized_fill_n(result, n, x);
 191         return result;
 192 #         ifdef __STL_USE_EXCEPTIONS
 193       }
 194       catch(...) {
 195         data_allocator::deallocate(result, n);
 196         throw;
 197       }
 198 #         endif /* __STL_USE_EXCEPTIONS */
 199     }
 200
 201 #ifdef __STL_MEMBER_TEMPLATES
 202     template <class ForwardIterator>
 203     iterator allocate_and_copy(size_type n,
 204                                ForwardIterator first, ForwardIterator last) {
 205       iterator result = data_allocator::allocate(n);
 206 #         ifdef __STL_USE_EXCEPTIONS
 207       try {
 208 #         endif /* __STL_USE_EXCEPTIONS */
 209         uninitialized_copy(first, last, result);
 210         return result;
 211 #         ifdef __STL_USE_EXCEPTIONS
 212       }
 213       catch(...) {
 214         data_allocator::deallocate(result, n);
 215         throw;
 216       }
 217 #         endif /* __STL_USE_EXCEPTIONS */
 218     }
 219 #else /* __STL_MEMBER_TEMPLATES */
 220     iterator allocate_and_copy(size_type n,
 221                                const_iterator first, const_iterator last) {
 222       iterator result = data_allocator::allocate(n);
 223 #         ifdef __STL_USE_EXCEPTIONS
 224       try {
 225 #         endif /* __STL_USE_EXCEPTIONS */
 226         uninitialized_copy(first, last, result);
 227         return result;
 228 #         ifdef __STL_USE_EXCEPTIONS
 229       }
 230       catch(...) {
 231         data_allocator::deallocate(result, n);
 232         throw;
 233       }
 234 #         endif /* __STL_USE_EXCEPTIONS */
 235     }
 236 #endif /* __STL_MEMBER_TEMPLATES */
 237
 238
 239 #ifdef __STL_MEMBER_TEMPLATES
 240     template <class InputIterator>
 241     void range_initialize(InputIterator first, InputIterator last,
 242                           input_iterator_tag) {
 243       for ( ; first != last; ++first)
 244         push_back(*first);
 245     }
 246
 247     // This function is only called by the constructor.  We have to worry
 248     //  about resource leaks, but not about maintaining invariants.
 249     template <class ForwardIterator>
 250     void range_initialize(ForwardIterator first, ForwardIterator last,
 251                           forward_iterator_tag) {
 252       size_type n = 0;
 253       distance(first, last, n);
 254       start = allocate_and_copy(n, first, last);
 255       finish = start + n;
 256       end_of_storage = finish;
 257     }
 258
 259     template <class BidirectionalIterator>
 260     void range_initialize(BidirectionalIterator first,
 261                           BidirectionalIterator last,
 262                           bidirectional_iterator_tag) {
 263       range_initialize(first, last, forward_iterator_tag());
 264     }
 265
 266     template <class RandomAccessIterator>
 267     void range_initialize(RandomAccessIterator first,
 268                           RandomAccessIterator last,
 269                           random_access_iterator_tag) {
 270       range_initialize(first, last, forward_iterator_tag());
 271     }
 272
 273     template <class InputIterator>
 274     void range_insert(iterator pos,
 275                       InputIterator first, InputIterator last,
 276                       input_iterator_tag);
 277
 278     template <class ForwardIterator>
 279     void range_insert(iterator pos,
 280                       ForwardIterator first, ForwardIterator last,
 281                       forward_iterator_tag);
 282
 283     template <class BidirectionalIterator>
 284     void range_insert(iterator pos,
 285                       BidirectionalIterator first, BidirectionalIterator last,
 286                       bidirectional_iterator_tag) {
 287       range_insert(pos, first, last, forward_iterator_tag());
 288     }
 289
 290     template <class RandomAccessIterator>
 291     void range_insert(iterator pos,
 292                       RandomAccessIterator first, RandomAccessIterator last,
 293                       random_access_iterator_tag) {
 294       range_insert(pos, first, last, forward_iterator_tag());
 295     }
 296 #endif /* __STL_MEMBER_TEMPLATES */
 297 };
 298
 299 template <class T, class Alloc>
 300 inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
 301     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
 302 }
 303
 304 template <class T, class Alloc>
 305 inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
 306     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
 307 }
 308
 309
 310
 311 template <class T, class Alloc>
 312 vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
 313   if (&x != this) {
 314     if (x.size() > capacity()) {
 315       const iterator tmp = allocate_and_copy(x.end() - x.begin(),
 316                                              x.begin(), x.end());
 317       destroy(start, finish);
 318       deallocate();
 319       start = tmp;
 320       end_of_storage = start + (x.end() - x.begin());
 321     }
 322     else if (size() >= x.size()) {
 323       iterator i = copy(x.begin(), x.end(), begin());
 324       destroy(i, finish);
 325     }
 326     else {
 327       copy(x.begin(), x.begin() + size(), start);
 328       uninitialized_copy(x.begin() + size(), x.end(), finish);
 329     }
 330     finish = start + x.size();
 331   }
 332   return *this;
 333 }
 334
 335 template <class T, class Alloc>
 336 void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
 337   if (finish != end_of_storage) {
 338     construct(finish, *(finish - 1));
 339     ++finish;
 340     T x_copy = x;
 341     copy_backward(position, finish - 2, finish - 1);
 342     *position = x_copy;
 343   }
 344   else {
 345     const size_type old_size = size();
 346     const size_type len = old_size != 0 ? 2 * old_size : 1;
 347     const iterator new_start = data_allocator::allocate(len);
 348     iterator new_finish = new_start;
 349 #       ifdef __STL_USE_EXCEPTIONS
 350     try {
 351 #       endif /* __STL_USE_EXCEPTIONS */
 352       new_finish = uninitialized_copy(start, position, new_start);
 353       construct(new_finish, x);
 354       ++new_finish;
 355       new_finish = uninitialized_copy(position, finish, new_finish);
 356 #       ifdef __STL_USE_EXCEPTIONS
 357     }
 358     catch(...) {
 359       destroy(new_start, new_finish);
 360       data_allocator::deallocate(new_start, len);
 361       throw;
 362     }
 363 #       endif /* __STL_USE_EXCEPTIONS */
 364     destroy(begin(), end());
 365     deallocate();
 366     start = new_start;
 367     finish = new_finish;
 368     end_of_storage = new_start + len;
 369   }
 370 }
 371
 372 template <class T, class Alloc>
 373 void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
 374   if (n != 0) {
 375     if (size_type (end_of_storage - finish) >= n) {
 376       T x_copy = x;
 377       const size_type elems_after = finish - position;
 378       const iterator old_finish = finish;
 379       if (elems_after > n) {
 380         uninitialized_copy(finish - n, finish, finish);
 381         finish += n;
 382         copy_backward(position, old_finish - n, old_finish);
 383         fill(position, position + n, x_copy);
 384       }
 385       else {
 386         uninitialized_fill_n(finish, n - elems_after, x_copy);
 387         finish += n - elems_after;
 388         uninitialized_copy(position, old_finish, finish);
 389         finish += elems_after;
 390         fill(position, old_finish, x_copy);
 391       }
 392     }
 393     else {
 394       const size_type old_size = size();
 395       const size_type len = old_size + max(old_size, n);
 396       const iterator new_start = data_allocator::allocate(len);
 397       iterator new_finish = new_start;
 398 #         ifdef __STL_USE_EXCEPTIONS
 399       try {
 400 #         endif /* __STL_USE_EXCEPTIONS */
 401         new_finish = uninitialized_copy(start, position, new_start);
 402         new_finish = uninitialized_fill_n(new_finish, n, x);
 403         new_finish = uninitialized_copy(position, finish, new_finish);
 404 #         ifdef __STL_USE_EXCEPTIONS
 405       }
 406       catch(...) {
 407         destroy(new_start, new_finish);
 408         data_allocator::deallocate(new_start, len);
 409         throw;
 410       }
 411 #         endif /* __STL_USE_EXCEPTIONS */
 412       destroy(start, finish);
 413       deallocate();
 414       start = new_start;
 415       finish = new_finish;
 416       end_of_storage = new_start + len;
 417     }
 418   }
 419 }
 420
 421 #ifdef __STL_MEMBER_TEMPLATES
 422
 423 template <class T, class Alloc> template <class InputIterator>
 424 void vector<T, Alloc>::range_insert(iterator pos,
 425                                     InputIterator first, InputIterator last,
 426                                     input_iterator_tag) {
 427   for ( ; first != last; ++first) {
 428     pos = insert(pos, *first);
 429     ++pos;
 430   }
 431 }
 432
 433 template <class T, class Alloc> template <class ForwardIterator>
 434 void vector<T, Alloc>::range_insert(iterator position,
 435                                     ForwardIterator first,
 436                                     ForwardIterator last,
 437                                     forward_iterator_tag) {
 438   if (first != last) {
 439     size_type n = 0;
 440     distance(first, last, n);
 441     if (size_type (end_of_storage - finish) >= n) {
 442       const size_type elems_after = finish - position;
 443       const iterator old_finish = finish;
 444       if (elems_after > n) {
 445         uninitialized_copy(finish - n, finish, finish);
 446         finish += n;
 447         copy_backward(position, old_finish - n, old_finish);
 448         copy(first, last, position);
 449       }
 450       else {
 451         ForwardIterator mid = first;
 452         advance(mid, elems_after);
 453         uninitialized_copy(mid, last, finish);
 454         finish += n - elems_after;
 455         uninitialized_copy(position, old_finish, finish);
 456         finish += elems_after;
 457         copy(first, mid, position);
 458       }
 459     }
 460     else {
 461       const size_type old_size = size();
 462       const size_type len = old_size + max(old_size, n);
 463       const iterator new_start = data_allocator::allocate(len);
 464       iterator new_finish = new_start;
 465 #         ifdef __STL_USE_EXCEPTIONS
 466       try {
 467 #         endif /* __STL_USE_EXCEPTIONS */
 468         new_finish = uninitialized_copy(start, position, new_start);
 469         new_finish = uninitialized_copy(first, last, new_finish);
 470         new_finish = uninitialized_copy(position, finish, new_finish);
 471 #         ifdef __STL_USE_EXCEPTIONS
 472       }
 473       catch(...) {
 474         destroy(new_start, new_finish);
 475         data_allocator::deallocate(new_start, len);
 476         throw;
 477       }
 478 #         endif /* __STL_USE_EXCEPTIONS */
 479       destroy(start, finish);
 480       deallocate();
 481       start = new_start;
 482       finish = new_finish;
 483       end_of_storage = new_start + len;
 484     }
 485   }
 486 }
 487
 488 #else /* __STL_MEMBER_TEMPLATES */
 489
 490 template <class T, class Alloc>
 491 void vector<T, Alloc>::insert(iterator position,
 492                               const_iterator first,
 493                               const_iterator last) {
 494   if (first != last) {
 495     size_type n = 0;
 496     distance(first, last, n);
 497     if (end_of_storage - finish >= n) {
 498       const size_type elems_after = finish - position;
 499       const iterator old_finish = finish;
 500       if (elems_after > n) {
 501         uninitialized_copy(finish - n, finish, finish);
 502         finish += n;
 503         copy_backward(position, old_finish - n, old_finish);
 504         copy(first, last, position);
 505       }
 506       else {
 507         uninitialized_copy(first + elems_after, last, finish);
 508         finish += n - elems_after;
 509         uninitialized_copy(position, old_finish, finish);
 510         finish += elems_after;
 511         copy(first, first + elems_after, position);
 512       }
 513     }
 514     else {
 515       const size_type old_size = size();
 516       const size_type len = old_size + max(old_size, n);
 517       const iterator new_start = data_allocator::allocate(len);
 518       iterator new_finish = new_start;
 519 #         ifdef __STL_USE_EXCEPTIONS
 520       try {
 521 #         endif /* __STL_USE_EXCEPTIONS */
 522         new_finish = uninitialized_copy(start, position, new_start);
 523         new_finish = uninitialized_copy(first, last, new_finish);
 524         new_finish = uninitialized_copy(position, finish, new_finish);
 525 #         ifdef __STL_USE_EXCEPTIONS
 526       }
 527       catch(...) {
 528         destroy(new_start, new_finish);
 529         data_allocator::deallocate(new_start, len);
 530         throw;
 531       }
 532 #         endif /* __STL_USE_EXCEPTIONS */
 533       destroy(start, finish);
 534       deallocate();
 535       start = new_start;
 536       finish = new_finish;
 537       end_of_storage = new_start + len;
 538     }
 539   }
 540 }
 541
 542 #endif /* __STL_MEMBER_TEMPLATES */
 543
 544 #endif /* __SGI_STL_VECTOR_H */