home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / vector.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  11KB  |  356 lines
  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.  
  16. #ifndef VECTOR_H
  17. #define VECTOR_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #ifndef __GNUG__
  22. #include <bool.h>
  23. #endif
  24.  
  25. #ifndef Allocator
  26. #define Allocator allocator
  27. #include <defalloc.h>
  28. #endif
  29.  
  30. #ifndef vector
  31. #define vector vector
  32. #endif
  33.  
  34. template <class T>
  35. class vector {
  36. public:
  37.     
  38.     typedef Allocator<T> vector_allocator;
  39.     typedef T value_type;
  40.     typedef vector_allocator::pointer pointer;
  41.     typedef vector_allocator::pointer iterator;
  42.     typedef vector_allocator::const_pointer const_iterator;
  43.     typedef vector_allocator::reference reference;
  44.     typedef vector_allocator::const_reference const_reference;
  45.     typedef vector_allocator::size_type size_type;
  46.     typedef vector_allocator::difference_type difference_type;
  47.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  48.                              difference_type>  const_reverse_iterator;
  49.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  50.         reverse_iterator;
  51. protected:
  52.     static Allocator<T> static_allocator;
  53.     iterator start;
  54.     iterator finish;
  55.     iterator end_of_storage;
  56. #ifdef __GNUG__
  57.     void insert_aux(iterator position, const T& x) {
  58.     insert_aux(vector_iterator<T>(position), x);
  59.     }
  60.     void insert_aux(vector_iterator<T> position, const T& x);
  61. #else
  62.     void insert_aux(iterator position, const T& x);
  63. #endif
  64. public:
  65.     iterator begin() { return start; }
  66.     const_iterator begin() const { return start; }
  67.     iterator end() { return finish; }
  68.     const_iterator end() const { return finish; }
  69.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  70.     const_reverse_iterator rbegin() const { 
  71.         return const_reverse_iterator(end()); 
  72.     }
  73.     reverse_iterator rend() { return reverse_iterator(begin()); }
  74.     const_reverse_iterator rend() const { 
  75.         return const_reverse_iterator(begin()); 
  76.     }
  77.     size_type size() const { return size_type(end() - begin()); }
  78.     size_type max_size() const { return static_allocator.max_size(); }
  79.     size_type capacity() const { return size_type(end_of_storage - begin()); }
  80.     bool empty() const { return begin() == end(); }
  81.     reference operator[](size_type n) { return *(begin() + n); }
  82.     const_reference operator[](size_type n) const { return *(begin() + n); }
  83.     vector() : start(0), finish(0), end_of_storage(0) {}
  84.     vector(size_type n, const T& value = T()) {
  85.     start = static_allocator.allocate(n);
  86.     uninitialized_fill_n(start, n, value);
  87.     finish = start + n;
  88.     end_of_storage = finish;
  89.     }
  90.     vector(const vector<T>& x) {
  91.     start = static_allocator.allocate(x.end() - x.begin());
  92.     finish = uninitialized_copy(x.begin(), x.end(), start);
  93.     end_of_storage = finish;
  94.     }
  95.     vector(const_iterator first, const_iterator last) {
  96.     size_type n = 0;
  97.     distance(first, last, n);
  98.     start = static_allocator.allocate(n);
  99.     finish = uninitialized_copy(first, last, start);
  100.     end_of_storage = finish;
  101.     }
  102.     ~vector() { 
  103.     destroy(start, finish);
  104.     static_allocator.deallocate(start);
  105.     }
  106.     vector<T>& operator=(const vector<T>& x);
  107.     void reserve(size_type n) {
  108.     if (capacity() < n) {
  109.         iterator tmp = static_allocator.allocate(n);
  110.         uninitialized_copy(begin(), end(), tmp);
  111.         destroy(start, finish);
  112.         static_allocator.deallocate(start);
  113.         finish = tmp + size();
  114.         start = tmp;
  115.         end_of_storage = begin() + n;
  116.     }
  117.     }
  118.     reference front() { return *begin(); }
  119.     const_reference front() const { return *begin(); }
  120.     reference back() { return *(end() - 1); }
  121.     const_reference back() const { return *(end() - 1); }
  122.     void push_back(const T& x) {
  123.     if (finish != end_of_storage) {
  124.         /* Borland bug */
  125.         construct(finish, x);
  126.         finish++;
  127.     } else
  128.         insert_aux(end(), x);
  129.     }
  130.     void swap(vector<T>& x) {
  131.     ::swap(start, x.start);
  132.     ::swap(finish, x.finish);
  133.     ::swap(end_of_storage, x.end_of_storage);
  134.     }
  135.     iterator insert(iterator position, const T& x) {
  136.     size_type n = position - begin();
  137.     if (finish != end_of_storage && position == end()) {
  138.         /* Borland bug */
  139.         construct(finish, x);
  140.         finish++;
  141.     } else
  142.         insert_aux(position, x);
  143.     return begin() + n;
  144.     }
  145. #ifdef __GNUG__
  146.     void insert (iterator position, const_iterator first, 
  147.          const_iterator last) {
  148.         insert(vector_iterator<T>(position),
  149.            vector_const_iterator<T>(first),
  150.            vector_const_iterator<T>(last));
  151.     }
  152.     void insert (vector_iterator<T> position, vector_const_iterator<T> first, 
  153.          vector_const_iterator<T> last);
  154.     void insert (iterator position, size_type n, const T& x) {
  155.     insert(vector_iterator<T>(position), n, x);
  156.     }
  157.     void insert (vector_iterator<T> position, size_type n, const T& x);
  158. #else
  159.     void insert (iterator position, const_iterator first, 
  160.          const_iterator last);
  161.     void insert (iterator position, size_type n, const T& x);
  162. #endif
  163.     void pop_back() {
  164.     /* Borland bug */
  165.         --finish;
  166.         destroy(finish);
  167.     }
  168.     void erase(iterator position) {
  169.     if (position + 1 != end())
  170.         copy(position + 1, end(), position);
  171.     /* Borland bug */
  172.     --finish;
  173.     destroy(finish);
  174.     }
  175.     void erase(iterator first, iterator last) {
  176.     vector<T>::iterator i = copy(last, end(), first);
  177.     destroy(i, finish);
  178.     // work around for destroy(copy(last, end(), first), finish);
  179.     finish = finish - (last - first); 
  180.     }
  181. };
  182.  
  183. #ifdef __GNUG__
  184. template <class T>
  185. struct vector_iterator {
  186.     vector<T>::iterator it;
  187.     vector_iterator(vector<T>::iterator i) : it(i) {}
  188.     operator vector<T>::iterator() {
  189.     return it;
  190.     }
  191. };
  192.  
  193. template <class T>
  194. inline T* value_type(const vector_iterator<T>&) {
  195.     return (T*)(0);
  196. }
  197.  
  198.  
  199. template <class T>
  200. struct vector_const_iterator {
  201.     vector<T>::const_iterator it;
  202.     vector_const_iterator(vector<T>::const_iterator i) : it(i) {}
  203.     operator vector<T>::const_iterator() {
  204.     return it;
  205.     }
  206. };
  207. #endif
  208.  
  209. template <class T>
  210. inline bool operator==(const vector<T>& x, const vector<T>& y) {
  211.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  212. }
  213.  
  214. template <class T>
  215. inline bool operator<(const vector<T>& x, const vector<T>& y) {
  216.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  217. }
  218.  
  219. #ifndef __GNUG__
  220. template <class T>
  221. vector<T>::vector_allocator vector<T>::static_allocator;
  222. #endif
  223.  
  224. template <class T>
  225. vector<T>& vector<T>::operator=(const vector<T>& x) {
  226.     if (&x == this) return *this;
  227.     if (x.size() > capacity()) {
  228.     destroy(start, finish);
  229.     static_allocator.deallocate(start);
  230.     start = static_allocator.allocate(x.end() - x.begin());
  231.     end_of_storage = uninitialized_copy(x.begin(), x.end(), start);
  232.     } else if (size() >= x.size()) {
  233.     vector<T>::iterator i = copy(x.begin(), x.end(), begin());
  234.     destroy(i, finish);
  235.     // work around for destroy(copy(x.begin(), x.end(), begin()), finish);
  236.     } else {
  237.     copy(x.begin(), x.begin() + size(), begin());
  238.     uninitialized_copy(x.begin() + size(), x.end(), begin() + size());
  239.     }
  240.     finish = begin() + x.size();
  241.     return *this;
  242. }
  243.  
  244. template <class T>
  245. #ifdef __GNUG__
  246. void vector<T>::insert_aux(vector_iterator<T> posn, const T& x) {
  247.     iterator position = posn;
  248. #else
  249. void vector<T>::insert_aux(iterator position, const T& x) {
  250. #endif
  251.     if (finish != end_of_storage) {
  252.     construct(finish, *(finish - 1));
  253.     copy_backward(position, finish - 1, finish);
  254.     *position = x;
  255.     ++finish;
  256.     } else {
  257.     size_type len = size() ? 2 * size() 
  258.         : static_allocator.init_page_size();
  259.     iterator tmp = static_allocator.allocate(len);
  260.     uninitialized_copy(begin(), position, tmp);
  261.     construct(tmp + (position - begin()), x);
  262.     uninitialized_copy(position, end(), tmp + (position - begin()) + 1); 
  263.     destroy(begin(), end());
  264.     static_allocator.deallocate(begin());
  265.     end_of_storage = tmp + len;
  266.     finish = tmp + size() + 1;
  267.     start = tmp;
  268.     }
  269. }
  270.  
  271. template <class T>
  272. #ifdef __GNUG__
  273. void vector<T>::insert(vector_iterator<T> posn,
  274.                size_t n,
  275.                const T& x) {
  276.     iterator position = posn;
  277. #else
  278. void vector<T>::insert(iterator position, size_type n, const T& x) {
  279. #endif
  280.     if (n == 0) return;
  281.     if ((size_type) (end_of_storage - finish) >= n) {
  282.     if ((size_type) (end() - position) > n) {
  283.         uninitialized_copy(end() - n, end(), end());
  284.         copy_backward(position, end() - n, end());
  285.         fill(position, position + n, x);
  286.     } else {
  287.         uninitialized_copy(position, end(), position + n);
  288.         fill(position, end(), x);
  289.         uninitialized_fill_n(end(), n - (end() - position), x);
  290.     }
  291.     finish += n;
  292.     } else {
  293.     size_type len = size() + max(size(), n);
  294.     iterator tmp = static_allocator.allocate(len);
  295.     uninitialized_copy(begin(), position, tmp);
  296.     uninitialized_fill_n(tmp + (position - begin()), n, x);
  297.     uninitialized_copy(position, end(), tmp + (position - begin() + n));
  298.     destroy(begin(), end());
  299.     static_allocator.deallocate(begin());
  300.     end_of_storage = tmp + len;
  301.     finish = tmp + size() + n;
  302.     start = tmp;
  303.     }
  304. }
  305.  
  306. template <class T>
  307. #ifdef __GNUG__
  308. void vector<T>::insert(vector_iterator<T> posn, 
  309.                vector_const_iterator<T> fi, 
  310.                vector_const_iterator<T> la) {
  311.     iterator position = posn;
  312.     const_iterator first = fi;
  313.     const_iterator last = la;
  314. #else
  315. void vector<T>::insert(iterator position, 
  316.                const_iterator first, 
  317.                const_iterator last) {
  318. #endif
  319.     if (first == last) return;
  320.     size_type n = 0;
  321.     distance(first, last, n);
  322.     if ((size_type) (end_of_storage - finish) >= n) {
  323.     if ((size_type) (end() - position) > n) {
  324.         uninitialized_copy(end() - n, end(), end());
  325.         copy_backward(position, end() - n, end());
  326.         copy(first, last, position);
  327.     } else {
  328.         uninitialized_copy(position, end(), position + n);
  329.         copy(first, first + (end() - position), position);
  330.         uninitialized_copy(first + (end() - position), last, end());
  331.     }
  332.     finish += n;
  333.     } else {
  334.     size_type len = size() + max(size(), n);
  335.     iterator tmp = static_allocator.allocate(len);
  336.     uninitialized_copy(begin(), position, tmp);
  337.     uninitialized_copy(first, last, tmp + (position - begin()));
  338.     uninitialized_copy(position, end(), tmp + (position - begin() + n));
  339.     destroy(begin(), end());
  340.     static_allocator.deallocate(begin());
  341.     end_of_storage = tmp + len;
  342.     finish = tmp + size() + n;
  343.     start = tmp;
  344.     }
  345. }
  346.  
  347. #undef Allocator
  348. #undef vector
  349.  
  350. #endif
  351.  
  352.  
  353.  
  354.  
  355.  
  356.