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