home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1997 May / Pcwk0597.iso / borland / cb / setup / cbuilder / data.z / VECTOR.H < prev    next >
C/C++ Source or Header  |  1997-02-28  |  33KB  |  1,091 lines
  1. #ifndef __STD_VECTOR__
  2. #define __STD_VECTOR__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * vector - declarations for the Standard Library vector class
  8.  *
  9.  * $Id: vector,v 1.41 1995/09/14 23:53:38 lijewski Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED
  29.  *
  30.  * The software and information contained herein are proprietary to, and
  31.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  32.  * intends to preserve as trade secrets such software and information.
  33.  * This software is furnished pursuant to a written license agreement and
  34.  * may be used, copied, transmitted, and stored only in accordance with
  35.  * the terms of such license and with the inclusion of the above copyright
  36.  * notice.  This software and information or any other copies thereof may
  37.  * not be provided or otherwise made available to any other person.
  38.  *
  39.  * Notwithstanding any other lease or license that may pertain to, or
  40.  * accompany the delivery of, this computer software and information, the
  41.  * rights of the Government regarding its use, reproduction and disclosure
  42.  * are as set forth in Section 52.227-19 of the FARS Computer
  43.  * Software-Restricted Rights clause.
  44.  *
  45.  * Use, duplication, or disclosure by the Government is subject to
  46.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  47.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  48.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  49.  * P.O. Box 2328, Corvallis, Oregon 97339.
  50.  *
  51.  * This computer software and information is distributed with "restricted
  52.  * rights."  Use, duplication or disclosure is subject to restrictions as
  53.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  54.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  55.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  56.  * then the "Alternate III" clause applies.
  57.  *
  58.  **************************************************************************/
  59.  
  60. #include <stdcomp.h>
  61.  
  62. #include <function>
  63. #include <iterator>
  64. #include <algorith>
  65.  
  66. #ifndef Allocator
  67. #define Allocator allocator
  68. #include <memory>
  69. #endif
  70.  
  71. #ifndef vector
  72. #define vector vector
  73. #endif
  74.  
  75. #ifndef RWSTD_NO_NAMESPACE
  76. namespace std {
  77. #endif
  78.  
  79. template <class T>
  80. class vector
  81. {
  82.   public:
  83.     //
  84.     // Types.
  85.     //
  86.     typedef Allocator<T>                               vector_allocator;
  87.     typedef typename vector_allocator::reference       reference;
  88.     typedef typename vector_allocator::const_reference const_reference;
  89.     typedef typename vector_allocator::pointer         iterator;
  90.     typedef typename vector_allocator::const_pointer   const_iterator;
  91.     typedef typename vector_allocator::size_type       size_type;
  92.     typedef typename vector_allocator::difference_type difference_type;
  93.     typedef          T                                 value_type;
  94.     typedef reverse_iterator<const_iterator, value_type,
  95.                              const_reference, difference_type>
  96.                                                        const_reverse_iterator;
  97.     typedef reverse_iterator<iterator, value_type,
  98.                              reference, difference_type>
  99.                                                        reverse_iterator;
  100.   protected:
  101.  
  102.     Allocator<T> the_allocator;
  103.  
  104.     iterator start;
  105.     iterator finish;
  106.     iterator end_of_storage;
  107.  
  108.     void insert_aux (iterator position, const T& x);
  109.  
  110.   public:
  111.     //
  112.     // construct/copy/destroy
  113.     //
  114.     vector () : start(0), finish(0), end_of_storage(0) {}
  115.     //
  116.     // Build a vector of size n with each element set to default for type T.
  117.     // This requires that T have a default constructor.
  118.     //
  119.     explicit vector (size_type n)
  120.     {
  121.         start = the_allocator.allocate(n);
  122.         T value;
  123.         uninitialized_fill_n(start, n, value);
  124.         finish = start + n;
  125.         end_of_storage = finish;
  126.     }
  127.     //
  128.     // Build a vector of size n with each element set to copy of value.
  129.     //
  130.     explicit vector (size_type n, const T& value)
  131.     {
  132.         start = the_allocator.allocate(n);
  133.         uninitialized_fill_n(start, n, value);
  134.         finish = start + n;
  135.         end_of_storage = finish;
  136.     }
  137.     vector (const vector<T>& x)
  138.     {
  139.         start = the_allocator.allocate(x.end() - x.begin());
  140.         finish = uninitialized_copy(x.begin(), x.end(), start);
  141.         end_of_storage = finish;
  142.     }
  143.  
  144. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  145. template<class InputIterator>
  146.     vector (InputIterator first, InputIterator last)
  147. #else
  148.     vector (const_iterator first, const_iterator last)
  149. #endif
  150.      {
  151.         size_type n;
  152.         __initialize(n, size_type(0));
  153.         distance(first, last, n);
  154.         start = the_allocator.allocate(n);
  155.         finish = uninitialized_copy(first, last, start);
  156.         end_of_storage = finish;
  157.     }
  158.  
  159.     ~vector ()
  160.     {
  161.         destroy(start, finish); the_allocator.deallocate(start);
  162.     }
  163.     vector<T>& operator= (const vector<T>& x);
  164.  
  165. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  166.     template<class InputIterator>
  167.     void assign (InputIterator first, InputIterator last)
  168. #else
  169.     void assign (const_iterator first, const_iterator last)
  170. #endif
  171.     {
  172.         erase(begin(), end()); insert(begin(), first, last);
  173.     }
  174.     //
  175.     // Assign n copies of default value of type T to vector.
  176.     // This requires that T have a default constructor.
  177.     //
  178. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  179.     template<class Size, class T>
  180.     void assign (Size n)
  181. #else
  182.     void assign (size_type n)
  183. #endif
  184.     {
  185.         erase(begin(), end()); insert(begin(), n, T());
  186.     }
  187.     //
  188.     // Assign n copies of t to this vector.
  189.     //
  190. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  191.     template<class Size, class T>
  192.     void assign (Size n, const T& t)
  193. #else
  194.     void assign (size_type n, const T& t)
  195. #endif
  196.     {
  197.         erase(begin(), end()); insert(begin(), n, t);
  198.     }
  199.     //
  200.     // Iterators.
  201.     //
  202.     iterator       begin ()       { return start;  }
  203.     const_iterator begin () const { return start;  }
  204.     iterator       end ()         { return finish; }
  205.     const_iterator end ()   const { return finish; }
  206.  
  207.     reverse_iterator rbegin ()
  208.     {
  209.         reverse_iterator tmp(end()); return tmp;
  210.     }
  211.     const_reverse_iterator rbegin () const
  212.     {
  213.         const_reverse_iterator tmp(end()); return tmp;
  214.     }
  215.     reverse_iterator rend ()
  216.     {
  217.         reverse_iterator tmp(begin()); return tmp;
  218.     }
  219.     const_reverse_iterator rend () const
  220.     {
  221.         const_reverse_iterator tmp(begin()); return tmp;
  222.     }
  223.  
  224.     //
  225.     // Capacity.
  226.     //
  227.     size_type size ()     const { return size_type(end() - begin()); }
  228.     size_type max_size () const { return the_allocator.max_size();   }
  229.     void resize (size_type new_size);
  230.     void resize (size_type new_size, T value);
  231.  
  232.     size_type capacity () const { return size_type(end_of_storage - begin()); }
  233.     bool      empty ()    const { return begin() == end();                    }
  234.     void reserve (size_type n)
  235.     {
  236.         if (capacity() < n)
  237.         {
  238.             iterator tmp = the_allocator.allocate(n);
  239.             uninitialized_copy(begin(), end(), tmp);
  240.             destroy(start, finish);
  241.             the_allocator.deallocate(start);
  242.             finish = tmp + size();
  243.             start = tmp;
  244.             end_of_storage = begin() + n;
  245.         }
  246.     }
  247.  
  248.     //
  249.     // Element access.
  250.     //
  251.     reference       operator[] (size_type n)       { return *(begin() + n); }
  252.     const_reference operator[] (size_type n) const { return *(begin() + n); }
  253.     reference       at (size_type n)               { return *(begin() + n); }
  254.     const_reference at (size_type n)         const { return *(begin() + n); }
  255.     reference       front ()                       { return *begin();       }
  256.     const_reference front ()                 const { return *begin();       }
  257.     reference       back ()                        { return *(end() - 1);   }
  258.     const_reference back ()                  const { return *(end() - 1);   }
  259.  
  260.     //
  261.     // Modifiers.
  262.     //
  263.     void push_back (const T& x)
  264.     {
  265.         if (finish != end_of_storage)
  266.         {
  267.             construct(finish, x); finish++;
  268.         }
  269.         else
  270.             insert_aux(end(), x);
  271.     }
  272.     void pop_back()
  273.     {
  274.         --finish; destroy(finish);
  275.     }
  276.     //
  277.     // Insert default value of type T at position.
  278.     // Requires that T have a default constructor.
  279.     //
  280.     iterator insert (iterator position)
  281.     {
  282.         size_type n = position - begin();
  283.         T x;
  284.         if (finish != end_of_storage && position == end())
  285.         {
  286.             construct(finish, x); finish++;
  287.         }
  288.         else
  289.             insert_aux(position, x);
  290.         return begin() + n;
  291.     }
  292.     //
  293.     // Insert x at position.
  294.     //
  295.     iterator insert (iterator position, const T& x)
  296.     {
  297.         size_type n = position - begin();
  298.         if (finish != end_of_storage && position == end())
  299.         {
  300.             construct(finish, x); finish++;
  301.         }
  302.         else
  303.             insert_aux(position, x);
  304.         return begin() + n;
  305.     }
  306.     void insert (iterator position, size_type n, const T& x);
  307.  
  308. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  309.     template<class InputIterator>
  310.     void insert (iterator position, InputIterator first, InputIterator last);
  311. #else
  312.     void insert (iterator position, const_iterator first, const_iterator last);
  313. #endif
  314.  
  315.     void swap (vector<T>& x)
  316.     {
  317. #ifndef RWSTD_NO_NAMESPACE
  318.         std::swap(start, x.start);
  319.         std::swap(finish, x.finish);
  320.         std::swap(end_of_storage, x.end_of_storage);
  321.         std::swap(the_allocator,x.the_allocator);
  322. #else
  323.         ::swap(start, x.start);
  324.         ::swap(finish, x.finish);
  325.         ::swap(end_of_storage, x.end_of_storage);
  326.         ::swap(the_allocator,x.the_allocator);
  327. #endif
  328.     }
  329.     void erase (iterator position)
  330.     {
  331.         if (position + 1 != end()) copy(position + 1, end(), position);
  332.         --finish;
  333.         destroy(finish);
  334.     }
  335.     void erase (iterator first, iterator last)
  336.     {
  337.         iterator i = copy(last, end(), first);
  338.         destroy(i, finish);
  339.         finish = finish - (last - first);
  340.     }
  341. };
  342.  
  343. template <class T>
  344. inline bool operator== (const vector<T>& x, const vector<T>& y)
  345. {
  346.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  347. }
  348.  
  349. template <class T>
  350. inline bool operator< (const vector<T>& x, const vector<T>& y)
  351. {
  352.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  353. }
  354.  
  355. //
  356. // This requires that T have a default constructor.
  357. //
  358.  
  359. template <class T>
  360. void vector<T>::resize (size_type new_size)
  361. {
  362.     T value;
  363.     if (new_size > size())
  364.         insert(end(), new_size - size(), value);
  365.     else if (new_size < size())
  366.         erase(begin() + new_size, end());
  367. }
  368.  
  369. template <class T>
  370. void vector<T>::resize (size_type new_size, T value)
  371. {
  372.     if (new_size > size())
  373.         insert(end(), new_size - size(), value);
  374.     else if (new_size < size())
  375.         erase(begin() + new_size, end());
  376. }
  377.  
  378. template <class T>
  379. vector<T>& vector<T>::operator= (const vector<T>& x)
  380. {
  381.     if (&x == this) return *this;
  382.     if (x.size() > capacity())
  383.     {
  384.         destroy(start, finish);
  385.         the_allocator.deallocate(start);
  386.         start = the_allocator.allocate(x.end() - x.begin());
  387.         end_of_storage = uninitialized_copy(x.begin(), x.end(), start);
  388.     }
  389.     else if (size() >= x.size())
  390.     {
  391.         iterator i = copy(x.begin(), x.end(), begin());
  392.         destroy(i, finish);
  393.     }
  394.     else
  395.     {
  396.         copy(x.begin(), x.begin() + size(), begin());
  397.         uninitialized_copy(x.begin() + size(), x.end(), begin() + size());
  398.     }
  399.     finish = begin() + x.size();
  400.     return *this;
  401. }
  402.  
  403. template <class T>
  404. void vector<T>::insert_aux (iterator position, const T& x)
  405. {
  406.     if (finish != end_of_storage)
  407.     {
  408.         construct(finish, *(finish - 1));
  409.         copy_backward(position, finish - 1, finish);
  410.         *position = x;
  411.         ++finish;
  412.     }
  413.     else
  414.     {
  415.         //
  416.         // We always allocate enough space for a number of additional
  417.         // elements in the vector, unless the size of each element is
  418.         // very large.
  419.         //
  420.         const size_type CHUNKSIZE = sizeof(T) >= 1024 ? 1 : 1024 / sizeof(T);
  421.         size_type len = size() ? 2 * size() : CHUNKSIZE;
  422.         iterator tmp = the_allocator.allocate(len);
  423.         uninitialized_copy(begin(), position, tmp);
  424.         construct((tmp + (position - begin())), x);
  425.         uninitialized_copy(position, end(), tmp + (position - begin()) + 1);
  426.         destroy(begin(), end());
  427.         the_allocator.deallocate(begin());
  428.         end_of_storage = tmp + len;
  429.         finish = tmp + size() + 1;
  430.         start = tmp;
  431.     }
  432. }
  433.  
  434. template <class T>
  435. void vector<T>::insert (iterator position, size_type n, const T& x)
  436. {
  437.     if (n == 0) return;
  438.     if (end_of_storage - finish >= n)
  439.     {
  440.         if (end() - position > n)
  441.         {
  442.             uninitialized_copy(end() - n, end(), end());
  443.             copy_backward(position, end() - n, end());
  444.             fill(position, position + n, x);
  445.         }
  446.         else
  447.         {
  448.             uninitialized_copy(position, end(), position + n);
  449.             fill(position, end(), x);
  450.             uninitialized_fill_n(end(), n - (end() - position), x);
  451.         }
  452.         finish += n;
  453.     }
  454.     else
  455.     {
  456.         size_type len = size() + max(size(), n);
  457.         iterator tmp = the_allocator.allocate(len);
  458.         uninitialized_copy(begin(), position, tmp);
  459.         uninitialized_fill_n(tmp + (position - begin()), n, x);
  460.         uninitialized_copy(position, end(), tmp + (position - begin() + n));
  461.         destroy(begin(), end());
  462.         the_allocator.deallocate(begin());
  463.         end_of_storage = tmp + len;
  464.         finish = tmp + size() + n;
  465.         start = tmp;
  466.     }
  467. }
  468.  
  469. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  470. template<class T>
  471. template<class InputIterator>
  472. void vector<T>::insert (iterator position, InputIterator first,
  473.                         InputIterator last)
  474. #else
  475. template<class T>
  476. void vector<T>::insert (iterator position, const_iterator first,
  477.                         const_iterator last)
  478. #endif
  479. {
  480.     if (first == last) return;
  481.     size_type n;
  482.     __initialize(n, size_type(0));
  483.     distance(first, last, n);
  484.     if (end_of_storage - finish >= n)
  485.     {
  486.         if (end() - position > n)
  487.         {
  488.             uninitialized_copy(end() - n, end(), end());
  489.             copy_backward(position, end() - n, end());
  490.             copy(first, last, position);
  491.         }
  492.         else
  493.         {
  494.             uninitialized_copy(position, end(), position + n);
  495.             copy(first, first + (end() - position), position);
  496.             uninitialized_copy(first + (end() - position), last, end());
  497.         }
  498.         finish += n;
  499.     }
  500.     else
  501.     {
  502.         size_type len = size() + max(size(), n);
  503.         iterator tmp = the_allocator.allocate(len);
  504.         uninitialized_copy(begin(), position, tmp);
  505.         uninitialized_copy(first, last, tmp + (position - begin()));
  506.         uninitialized_copy(position, end(), tmp + (position - begin() + n));
  507.         destroy(begin(), end());
  508.         the_allocator.deallocate(begin());
  509.         end_of_storage = tmp + len;
  510.         finish = tmp + size() + n;
  511.         start = tmp;
  512.     }
  513. }
  514.  
  515. //
  516. // If bool is a builtin type, we provide a vector<bool> specialization.
  517. //
  518. #ifndef RWSTD_NO_BOOL
  519.  
  520. #define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int)))
  521.  
  522. class vector<bool>
  523. {
  524.   public:
  525.     //
  526.     // types
  527.     //
  528.     typedef Allocator<unsigned int>                     vector_allocator;
  529.     typedef bool                                        value_type;
  530.     typedef typename vector_allocator::size_type        size_type;
  531.     typedef typename vector_allocator::difference_type  difference_type;
  532.     //
  533.     // forward declarations
  534.     //
  535.     class iterator;
  536.     class const_iterator;
  537.     //
  538.     // bit reference
  539.     //
  540.     class reference
  541.     {
  542.         friend class iterator;
  543.         friend class const_iterator;
  544.       protected:
  545.         unsigned int* p;
  546.         unsigned int mask;
  547.         reference (unsigned int* x, unsigned int y) : p(x), mask(y) {}
  548.       public:
  549.         reference () : p(0), mask(0) {}
  550.         operator bool () const { return !(!(*p & mask)); }
  551.         reference& operator= (bool x)
  552.         {
  553.             if (x)
  554.                 *p |= mask;
  555.             else
  556.                 *p &= ~mask;
  557.             return *this;
  558.         }
  559.         reference& operator= (const reference& x) { return *this = bool(x); }
  560.         bool operator== (const reference& x) const
  561.         {
  562.             return bool(*this) == bool(x);
  563.         }
  564.         bool operator< (const reference& x) const
  565.         {
  566.             return bool(*this) < bool(x);
  567.         }
  568.         void flip () { *p ^= mask; }
  569.     };
  570.  
  571.     typedef bool const_reference;
  572.     //
  573.     // Definition of our iterator.
  574.     //
  575.     class iterator : public random_access_iterator<bool, difference_type>
  576.     {
  577.         friend class vector<bool>;
  578.         friend class const_iterator;
  579.  
  580.       protected:
  581.  
  582.         unsigned int* p;
  583.         unsigned int  offset;
  584.  
  585.         void bump_up ()
  586.         {
  587.             if (offset++ == __WORD_BIT - 1)
  588.             {
  589.                 offset = 0; ++p;
  590.             }
  591.         }
  592.         void bump_down ()
  593.         {
  594.             if (offset-- == 0)
  595.             {
  596.                 offset = __WORD_BIT - 1; --p;
  597.             }
  598.         }
  599.  
  600.       public:
  601.  
  602.         iterator () : p(0), offset(0) {}
  603.         iterator (unsigned int* x, unsigned int y) : p(x), offset(y) {}
  604.  
  605.         reference operator* () const { return reference(p, 1U << offset); }
  606.         iterator& operator++ ()
  607.         {
  608.             bump_up(); return *this;
  609.         }
  610.         iterator operator++ (int)
  611.         {
  612.             iterator tmp = *this; bump_up(); return tmp;
  613.         }
  614.         iterator& operator-- ()
  615.         {
  616.             bump_down(); return *this;
  617.         }
  618.         iterator operator-- (int)
  619.         {
  620.             iterator tmp = *this; bump_down(); return tmp;
  621.         }
  622.         iterator& operator+= (difference_type i)
  623.         {
  624.             difference_type n = i + offset;
  625.             p += n / __WORD_BIT;
  626.             n = n % __WORD_BIT;
  627.             if (n < 0)
  628.             {
  629.                 offset = n + __WORD_BIT; --p;
  630.             }
  631.             else
  632.                 offset = n;
  633.             return *this;
  634.         }
  635.         iterator& operator-= (difference_type i)
  636.         {
  637.             *this += -i; return *this;
  638.         }
  639.         iterator operator+ (difference_type i) const
  640.         {
  641.             iterator tmp = *this; return tmp += i;
  642.         }
  643.         iterator operator- (difference_type i) const
  644.         {
  645.             iterator tmp = *this; return tmp -= i;
  646.         }
  647.         difference_type operator- (iterator x) const
  648.         {
  649.             return __WORD_BIT * (p - x.p) + offset - x.offset;
  650.         }
  651.         reference operator[] (difference_type i)
  652.         {
  653.             return *(*this + i);
  654.         }
  655.         bool operator== (const iterator& x) const
  656.         {
  657.             return p == x.p && offset == x.offset;
  658.         }
  659.         bool operator< (iterator x) const
  660.         {
  661.             return p < x.p || (p == x.p && offset < x.offset);
  662.         }
  663.     };
  664.     //
  665.     // Definition of our const_iterator.
  666.     //
  667.     class const_iterator
  668.         : public random_access_iterator<bool, difference_type>
  669.     {
  670.         friend class vector<bool>;
  671.  
  672.       protected:
  673.  
  674.         unsigned int* p;
  675.         unsigned int offset;
  676.         void bump_up ()
  677.         {
  678.             if (offset++ == __WORD_BIT - 1)
  679.             {
  680.                 offset = 0; ++p;
  681.             }
  682.         }
  683.         void bump_down()
  684.         {
  685.             if (offset-- == 0)
  686.             {
  687.                 offset = __WORD_BIT - 1; --p;
  688.             }
  689.         }
  690.  
  691.       public:
  692.  
  693.         const_iterator () : p(0), offset(0) {}
  694.         const_iterator (unsigned int* x, unsigned int y) : p(x), offset(y) {}
  695.         const_iterator (const iterator& x) : p(x.p), offset(x.offset) {}
  696.  
  697.         const_reference operator* () const
  698.         {
  699.             return reference(p, 1U << offset);
  700.         }
  701.         const_iterator& operator++ ()
  702.         {
  703.             bump_up(); return *this;
  704.         }
  705.         const_iterator operator++ (int)
  706.         {
  707.             const_iterator tmp = *this; bump_up(); return tmp;
  708.         }
  709.         const_iterator& operator-- ()
  710.         {
  711.             bump_down(); return *this;
  712.         }
  713.         const_iterator operator-- (int)
  714.         {
  715.             const_iterator tmp = *this; bump_down(); return tmp;
  716.         }
  717.         const_iterator& operator+= (difference_type i)
  718.         {
  719.             difference_type n = i + offset;
  720.             p += n / __WORD_BIT;
  721.             n = n % __WORD_BIT;
  722.             if (n < 0)
  723.             {
  724.                 offset = n + __WORD_BIT; --p;
  725.             }
  726.             else
  727.                 offset = n;
  728.             return *this;
  729.         }
  730.         const_iterator& operator-= (difference_type i)
  731.         {
  732.             *this += -i; return *this;
  733.         }
  734.         const_iterator operator+ (difference_type i) const
  735.         {
  736.             const_iterator tmp = *this; return tmp += i;
  737.         }
  738.         const_iterator operator- (difference_type i) const
  739.         {
  740.             const_iterator tmp = *this; return tmp -= i;
  741.         }
  742.         difference_type operator- (const_iterator x) const
  743.         {
  744.             return __WORD_BIT * (p - x.p) + offset - x.offset;
  745.         }
  746.         const_reference operator[] (difference_type i)
  747.         {
  748.             return *(*this + i);
  749.         }
  750.         bool operator== (const const_iterator& x) const
  751.         {
  752.             return p == x.p && offset == x.offset;
  753.         }
  754.         bool operator< (const_iterator x) const
  755.         {
  756.             return p < x.p || (p == x.p && offset < x.offset);
  757.         }
  758.     };
  759.     //
  760.     // types
  761.     //
  762.     typedef reverse_iterator<const_iterator,
  763.                              value_type,
  764.                              const_reference,
  765.                              difference_type> const_reverse_iterator;
  766.     typedef reverse_iterator<iterator,
  767.                              value_type,
  768.                              reference,
  769.                              difference_type> reverse_iterator;
  770.   protected:
  771.  
  772.     Allocator<unsigned int> the_allocator;
  773.     iterator                start;
  774.     iterator                finish;
  775.     unsigned int*           end_of_storage;
  776.  
  777.     unsigned int* bit_alloc (size_type n)
  778.     {
  779.         return the_allocator.allocate((n + __WORD_BIT - 1)/__WORD_BIT);
  780.     }
  781.     void initialize (size_type n)
  782.     {
  783.         unsigned int* q = bit_alloc(n);
  784.         end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  785.         start = iterator(q, 0);
  786.         finish = start + n;
  787.     }
  788.     void insert_aux (iterator position, bool x);
  789.  
  790.   public:
  791.  
  792.     //
  793.     // construct/copy/destroy
  794.     //
  795.     explicit vector ()
  796.         : start(iterator()), finish(iterator()), end_of_storage(0) {}
  797.     explicit vector (size_type n, bool value = bool())
  798.     {
  799.         initialize(n); fill(start.p, end_of_storage, value ? ~0 : 0);
  800.     }
  801.     vector (const vector<bool>& x)
  802.     {
  803.         initialize(x.size()); copy(x.begin(), x.end(), start);
  804.     }
  805.  
  806. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  807. template<class InputIterator>
  808.     vector (InputIterator first, InputIterator last)
  809.     {
  810.         size_type n;
  811.         __initialize(n, size_type(0));
  812.         distance(first, last, n);
  813.         initialize(n);
  814.         copy(first, last, start);
  815.     }
  816. #else
  817.     vector (const_iterator first, const_iterator last)
  818.     {
  819.         size_type n;
  820.         __initialize(n, size_type(0));
  821.         distance(first, last, n);
  822.         initialize(n);
  823.         copy(first, last, start);
  824.     }
  825.     vector (const bool* first, const bool* last)
  826.     {
  827.         size_type n;
  828.         __initialize(n, size_type(0));
  829.         distance(first, last, n);
  830.         initialize(n);
  831.         copy(first, last, start);
  832.     }
  833. #endif
  834.     ~vector () { the_allocator.deallocate(start.p); }
  835.     vector& operator= (const vector<bool>& x)
  836.     {
  837.         if (&x == this) return *this;
  838.         if (x.size() > capacity())
  839.         {
  840.             the_allocator.deallocate(start.p);
  841.             initialize(x.size());
  842.         }
  843.         copy(x.begin(), x.end(), begin());
  844.         finish = begin() + x.size();
  845.         return *this;
  846.     }
  847. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  848.     template<class InputIterator>
  849.     void assign (InputIterator first, InputIterator last)
  850. #else
  851.     void assign (const_iterator first, const_iterator last)
  852. #endif
  853.     {
  854.         erase(begin(), end()); insert(begin(), first, last);
  855.     }
  856.  
  857. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  858.     template<class Size, class T>
  859.     void assign (Size n, const bool& t = bool())
  860. #else
  861.     void assign (size_type n, const bool& t = bool())
  862. #endif
  863.     {
  864.         erase(begin(), end()); insert(begin(), n, t);
  865.     }
  866.     //
  867.     // iterators
  868.     //
  869.     iterator       begin ()       { return start; }
  870.     const_iterator begin () const { return start; }
  871.     iterator       end   ()       { return finish; }
  872.     const_iterator end   () const { return finish; }
  873.  
  874.     reverse_iterator       rbegin () { return reverse_iterator(end()); }
  875.     const_reverse_iterator rbegin () const
  876.     {
  877.         return const_reverse_iterator(end());
  878.     }
  879.     reverse_iterator       rend () { return reverse_iterator(begin()); }
  880.     const_reverse_iterator rend () const
  881.     {
  882.         return const_reverse_iterator(begin());
  883.     }
  884.     //
  885.     // capacity
  886.     //
  887.     size_type size     () const { return size_type(end() - begin());  }
  888.     size_type max_size () const { return the_allocator.max_size(); }
  889.     void resize (size_type new_size, bool c = false);
  890.     size_type capacity () const
  891.     {
  892.         return size_type(const_iterator(end_of_storage, 0) - begin());
  893.     }
  894.     bool empty () const { return begin() == end(); }
  895.     void reserve (size_type n)
  896.     {
  897.         if (capacity() < n)
  898.         {
  899.             unsigned int* q = bit_alloc(n);
  900.             finish = copy(begin(), end(), iterator(q, 0));
  901.             the_allocator.deallocate(start.p);
  902.             start = iterator(q, 0);
  903.             end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  904.         }
  905.     }
  906.     //
  907.     // element access
  908.     //
  909.     reference       operator[] (size_type n)       { return *(begin() + n); }
  910.     const_reference operator[] (size_type n) const { return *(begin() + n); }
  911.     reference       at (size_type n)               { return *(begin() + n); }
  912.     const_reference at (size_type n)         const { return *(begin() + n); }
  913.     reference       front ()       { return *begin();     }
  914.     const_reference front () const { return *begin();     }
  915.     reference       back  ()       { return *(end() - 1); }
  916.     const_reference back  () const { return *(end() - 1); }
  917.     //
  918.     // modifiers
  919.     //
  920.     void push_back (bool x)
  921.     {
  922.         if (finish.p != end_of_storage)
  923.             *finish++ = x;
  924.         else
  925.             insert_aux(end(), x);
  926.     }
  927.     void pop_back () { --finish; }
  928.     iterator insert (iterator position, const bool& x = bool())
  929.     {
  930.         size_type n = position - begin();
  931.         if (finish.p != end_of_storage && position == end())
  932.             *finish++ = x;
  933.         else
  934.             insert_aux(position, x);
  935.         return begin() + n;
  936.     }
  937.     void insert (iterator position, size_type n, const bool& x = bool());
  938.  
  939. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  940.     template<class InputIterator>
  941.     void insert (iterator position, InputIterator first, InputIterator last);
  942. #else
  943.     void insert (iterator position, const_iterator first,
  944.                  const_iterator last);
  945. #endif
  946.  
  947.     void erase (iterator position)
  948.     {
  949.         if (position + 1 != end())
  950.             copy(position + 1, end(), position);
  951.         --finish;
  952.     }
  953.     void erase(iterator first, iterator last)
  954.     {
  955.         finish = copy(last, end(), first);
  956.     }
  957.     void swap (vector<bool>& x)
  958.     {
  959. #ifndef RWSTD_NO_NAMESPACE
  960.         std::swap(start,          x.start);
  961.         std::swap(finish,         x.finish);
  962.         std::swap(the_allocator,  x.the_allocator);
  963.         std::swap(end_of_storage, x.end_of_storage);
  964. #else
  965.         ::swap(start,          x.start);
  966.         ::swap(finish,         x.finish);
  967.         ::swap(the_allocator,  x.the_allocator);
  968.         ::swap(end_of_storage, x.end_of_storage);
  969. #endif
  970.     }
  971.     void flip ();
  972. };
  973.  
  974. inline bool operator== (const vector<bool>& x, const vector<bool>& y)
  975. {
  976.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  977. }
  978.  
  979. inline bool operator< (const vector<bool>& x, const vector<bool>& y)
  980. {
  981.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  982. }
  983.  
  984. void vector<bool>::flip ()
  985. {
  986.     for (iterator i = begin(); i != end(); i++)
  987.         *i = !(*i);
  988. }
  989.  
  990. void swap (typename vector<bool>::reference x,
  991.            typename vector<bool>::reference y)
  992. {
  993.     bool tmp = x; x = y; y = tmp;
  994. }
  995.  
  996. void vector<bool>::insert_aux (iterator position, bool x)
  997. {
  998.     if (finish.p != end_of_storage)
  999.     {
  1000.         copy_backward(position, finish - 1, finish);
  1001.         *position = x;
  1002.         ++finish;
  1003.     }
  1004.     else
  1005.     {
  1006.         size_type len = size() ? 2 * size() : __WORD_BIT;
  1007.         unsigned int* q = bit_alloc(len);
  1008.         iterator i = copy(begin(), position, iterator(q, 0));
  1009.         *i++ = x;
  1010.         finish = copy(position, end(), i);
  1011.         the_allocator.deallocate(start.p);
  1012.         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  1013.         start = iterator(q, 0);
  1014.     }
  1015. }
  1016.  
  1017. void vector<bool>::insert (iterator position, size_type n, const bool& x)
  1018. {
  1019.     if (n == 0) return;
  1020.     if (capacity() - size() >= n)
  1021.     {
  1022.         copy_backward(position, end(), finish + n);
  1023.         fill(position, position + n, x);
  1024.         finish += n;
  1025.     }
  1026.     else
  1027.     {
  1028.         size_type len = size() + max(size(), n);
  1029.         unsigned int* q = bit_alloc(len);
  1030.         iterator i = copy(begin(), position, iterator(q, 0));
  1031.         fill_n(i, n, x);
  1032.         finish = copy(position, end(), i + n);
  1033.         the_allocator.deallocate(start.p);
  1034.         end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  1035.         start = iterator(q, 0);
  1036.     }
  1037. }
  1038.  
  1039. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  1040. template<class InputIterator>
  1041. void vector<bool>::insert (iterator position, InputIterator first,
  1042.                            InputIterator last)
  1043. #else
  1044. void vector<bool>::insert (iterator position, const_iterator first,
  1045.                            const_iterator last)
  1046. #endif
  1047. {
  1048.     if (first == last) return;
  1049.     size_type n;
  1050.     __initialize(n, size_type(0));
  1051.     distance(first, last, n);
  1052.     if (capacity() - size() >= n)
  1053.     {
  1054.         copy_backward(position, end(), finish + n);
  1055.         copy(first, last, position);
  1056.         finish += n;
  1057.     }
  1058.     else
  1059.     {
  1060.         size_type len = size() + max(size(), n);
  1061.         unsigned int* q = bit_alloc(len);
  1062.         iterator i = copy(begin(), position, iterator(q, 0));
  1063.         i = copy(first, last, i);
  1064.         finish = copy(position, end(), i);
  1065.         the_allocator.deallocate(start.p);
  1066.         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  1067.         start = iterator(q, 0);
  1068.     }
  1069. }
  1070.  
  1071. void vector<bool>::resize (size_type new_size, bool c)
  1072. {
  1073.   if (new_size > size())
  1074.       insert(end(), new_size - size(), c);
  1075.   else if (new_size < size())
  1076.       erase(begin() + new_size, end());
  1077. }
  1078.  
  1079. #undef __WORD_BIT
  1080.  
  1081. #endif /*RWSTD_NO_BOOL*/
  1082.  
  1083. #ifndef RWSTD_NO_NAMESPACE
  1084. }
  1085. #endif
  1086.  
  1087. #undef Allocator
  1088. #undef vector
  1089.  
  1090. #endif /*__STD_VECTOR__*/
  1091.