"Fossies" - the Fresh Open Source Software Archive

Member "erltools/stl/deque.h" (25 Jul 1999, 42199 Bytes) of package /linux/misc/old/erltools-4.0.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "deque.h" see the Fossies "Dox" file reference documentation.

    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) 1997
   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_DEQUE_H
   28 #define __SGI_STL_DEQUE_H
   29 
   30 /* Class invariants:
   31  *  For any nonsingular iterator i:
   32  *    i.node is the address of an element in the map array.  The
   33  *      contents of i.node is a pointer to the beginning of a node.
   34  *    i.first == *(i.node) 
   35  *    i.last  == i.first + node_size
   36  *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
   37  *      the implication of this is that i.cur is always a dereferenceable
   38  *      pointer, even if i is a past-the-end iterator.
   39  *  Start and Finish are always nonsingular iterators.  NOTE: this means
   40  *    that an empty deque must have one node, and that a deque
   41  *    with N elements, where N is the buffer size, must have two nodes.
   42  *  For every node other than start.node and finish.node, every element
   43  *    in the node is an initialized object.  If start.node == finish.node,
   44  *    then [start.cur, finish.cur) are initialized objects, and
   45  *    the elements outside that range are uninitialized storage.  Otherwise,
   46  *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
   47  *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
   48  *    are uninitialized storage.
   49  *  [map, map + map_size) is a valid, non-empty range.  
   50  *  [start.node, finish.node] is a valid range contained within 
   51  *    [map, map + map_size).  
   52  *  A pointer in the range [map, map + map_size) points to an allocated
   53  *    node if and only if the pointer is in the range [start.node, finish.node].
   54  */
   55 
   56 
   57 /*
   58  * In previous versions of deque, node_size was fixed by the 
   59  * implementation.  In this version, however, users can select
   60  * the node size.  Deque has three template parameters; the third,
   61  * a number of type size_t, is the number of elements per node.
   62  * If the third template parameter is 0 (which is the default), 
   63  * then deque will use a default node size.
   64  *
   65  * The only reason for using an alternate node size is if your application
   66  * requires a different performance tradeoff than the default.  If,
   67  * for example, your program contains many deques each of which contains
   68  * only a few elements, then you might want to save memory (possibly
   69  * by sacrificing some speed) by using smaller nodes.
   70  *
   71  * Unfortunately, some compilers have trouble with non-type template 
   72  * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if
   73  * that is the case.  If your compiler is one of them, then you will
   74  * not be able to use alternate node sizes; you will have to use the
   75  * default value.
   76  */
   77 
   78 #include <stddef.h>
   79 #include <algobase.h>
   80 #include <alloc.h>
   81 
   82 // Note: this function is simply a kludge to work around several compilers'
   83 //  bugs in handling constant expressions.
   84 inline size_t __deque_buf_size(size_t n, size_t sz)
   85 {
   86   return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
   87 }
   88 
   89 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
   90 template <class T, class Ref, size_t BufSiz>
   91 struct __deque_iterator {
   92   typedef __deque_iterator<T, T&, BufSiz> iterator;
   93   typedef __deque_iterator<T, const T&, BufSiz> const_iterator;
   94   static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
   95 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
   96 template <class T, class Ref>
   97 struct __deque_iterator {
   98   typedef __deque_iterator<T, T&> iterator;
   99   typedef __deque_iterator<T, const T&> const_iterator;
  100   static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }
  101 #endif
  102 
  103   typedef random_access_iterator_tag iterator_category;
  104   typedef T value_type;
  105   typedef value_type* pointer;
  106   typedef value_type& reference;
  107   typedef const value_type& const_reference;
  108   typedef size_t size_type;
  109   typedef ptrdiff_t difference_type;
  110   typedef pointer* map_pointer;
  111 
  112   typedef __deque_iterator self;
  113 
  114   pointer cur;
  115   pointer first;
  116   pointer last;
  117   map_pointer node;
  118 
  119   __deque_iterator(pointer x, map_pointer y) 
  120     : cur(x), first(*y), last(*y + buffer_size()), node(y) {}
  121   __deque_iterator() : cur(0), first(0), last(0), node(0) {}
  122   __deque_iterator(const iterator& x)
  123     : cur(x.cur), first(x.first), last(x.last), node(x.node) {}
  124 
  125   Ref operator*() const { return *cur; }
  126 
  127   difference_type operator-(const self& x) const {
  128     return buffer_size() * (node - x.node - 1) +
  129       (cur - first) + (x.last - x.cur);
  130   }
  131 
  132   self& operator++() {
  133     ++cur;
  134     if (cur == last) {
  135       set_node(node + 1);
  136       cur = first;
  137     }
  138     return *this; 
  139   }
  140   self operator++(int)  {
  141     self tmp = *this;
  142     ++*this;
  143     return tmp;
  144   }
  145 
  146   self& operator--() {
  147     if (cur == first) {
  148       set_node(node - 1);
  149       cur = last;
  150     }
  151     --cur;
  152     return *this;
  153   }
  154   self operator--(int) {
  155     self tmp = *this;
  156     --*this;
  157     return tmp;
  158   }
  159 
  160   self& operator+=(difference_type n) {
  161     difference_type offset = n + (cur - first);
  162     if (offset >= 0 && offset < buffer_size())
  163       cur += n;
  164     else {
  165       difference_type node_offset =
  166         offset > 0 ? offset / buffer_size()
  167                    : -difference_type((-offset - 1) / buffer_size()) - 1;
  168       set_node(node + node_offset);
  169       cur = first + (offset - node_offset * buffer_size());
  170     }
  171     return *this;
  172   }
  173 
  174   self operator+(difference_type n) const {
  175     self tmp = *this;
  176     return tmp += n;
  177   }
  178 
  179   self& operator-=(difference_type n) { return *this += -n; }
  180  
  181   self operator-(difference_type n) const {
  182     self tmp = *this;
  183     return tmp -= n;
  184   }
  185 
  186   Ref operator[](difference_type n) const { return *(*this + n); }
  187 
  188   bool operator==(const self& x) const { return cur == x.cur; }
  189   bool operator!=(const self& x) const { return !(*this == x); }
  190   bool operator<(const self& x) const {
  191     return (node == x.node) ? (cur < x.cur) : (node < x.node);
  192   }
  193 
  194   void set_node(map_pointer new_node) {
  195     node = new_node;
  196     first = *new_node;
  197     last = first + buffer_size();
  198   }
  199 };
  200 
  201 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
  202 
  203 template <class T, class Ref, size_t BufSiz>
  204 inline random_access_iterator_tag
  205 iterator_category(const __deque_iterator<T, Ref, BufSiz>&) {
  206   return random_access_iterator_tag();
  207 }
  208 
  209 template <class T, class Ref, size_t BufSiz>
  210 inline T* value_type(const __deque_iterator<T, Ref, BufSiz>&) { return 0; }
  211 
  212 template <class T, class Ref, size_t BufSiz>
  213 inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, BufSiz>&) {
  214   return 0;
  215 }
  216 
  217 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  218 
  219 template <class T, class Ref>
  220 inline random_access_iterator_tag
  221 iterator_category(const __deque_iterator<T, Ref>&) {
  222   return random_access_iterator_tag();
  223 }
  224 
  225 template <class T, class Ref>
  226 inline T* value_type(const __deque_iterator<T, Ref>&) { return 0; }
  227 
  228 template <class T, class Ref>
  229 inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref>&) {
  230   return 0;
  231 }
  232 
  233 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  234 
  235 
  236 // See __deque_buf_size().  The only reason that the default value is 0
  237 //  is as a workaround for bugs in the way that some compilers handle
  238 //  constant expressions.
  239 template <class T, class Alloc = alloc, size_t BufSiz = 0> 
  240 class deque {
  241 public:                         // Basic types
  242   typedef T value_type;
  243   typedef value_type* pointer;
  244   typedef value_type& reference;
  245   typedef const value_type& const_reference;
  246   typedef size_t size_type;
  247   typedef ptrdiff_t difference_type;
  248 
  249 public:                         // Iterators
  250 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
  251   typedef __deque_iterator<value_type, reference, BufSiz> iterator;
  252   typedef __deque_iterator<value_type, const_reference, BufSiz> const_iterator;
  253 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  254   typedef __deque_iterator<value_type, reference> iterator;
  255   typedef __deque_iterator<value_type, const_reference> const_iterator;
  256 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  257   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  258                            difference_type>  
  259           const_reverse_iterator;
  260   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  261           reverse_iterator; 
  262 
  263 protected:                      // Internal typedefs
  264   typedef pointer* map_pointer;
  265   typedef simple_alloc<value_type, Alloc> data_allocator;
  266   typedef simple_alloc<pointer, Alloc> map_allocator;
  267 
  268   static size_type buffer_size() {
  269     return __deque_buf_size(BufSiz, sizeof(value_type));
  270   }
  271   static size_type initial_map_size() { return 8; }
  272 
  273 protected:                      // Data members
  274   iterator start;
  275   iterator finish;
  276 
  277   map_pointer map;
  278   size_type map_size;
  279 
  280 public:                         // Basic accessors
  281   iterator begin() { return start; }
  282   iterator end() { return finish; }
  283   const_iterator begin() const { return start; }
  284   const_iterator end() const { return finish; }
  285 
  286   reverse_iterator rbegin() { return reverse_iterator(finish); }
  287   reverse_iterator rend() { return reverse_iterator(start); }
  288   const_reverse_iterator rbegin() const {
  289     return const_reverse_iterator(finish);
  290   }
  291   const_reverse_iterator rend() const {
  292     return const_reverse_iterator(start);
  293   }
  294 
  295   reference operator[](size_type n) { return start[n]; }
  296   const_reference operator[](size_type n) const { return start[n]; }
  297 
  298   reference front() { return *start; }
  299   reference back() {
  300     iterator tmp = finish;
  301     --tmp;
  302     return *tmp;
  303   }
  304   const_reference front() const { return *start; }
  305   const_reference back() const {
  306     const_iterator tmp = finish;
  307     --tmp;
  308     return *tmp;
  309   }
  310 
  311   size_type size() const { return finish - start;; }
  312   size_type max_size() const { return size_type(-1); }
  313   bool empty() const { return finish == start; }
  314 
  315 public:                         // Constructor, destructor.
  316   deque()
  317     : start(), finish(), map(0), map_size(0)
  318   {
  319     create_map_and_nodes(0);
  320   }
  321 
  322   deque(const deque& x)
  323     : start(), finish(), map(0), map_size(0)
  324   {
  325     create_map_and_nodes(x.size());
  326 #       ifdef __STL_USE_EXCEPTIONS
  327     try {
  328 #       endif /* __STL_USE_EXCEPTIONS */
  329       uninitialized_copy(x.begin(), x.end(), start);
  330 #       ifdef __STL_USE_EXCEPTIONS
  331     }
  332     catch(...) {
  333       destroy_map_and_nodes();
  334       throw;
  335     }
  336 #       endif /* __STL_USE_EXCEPTIONS */
  337   }
  338 
  339   deque(size_type n, const value_type& value)
  340     : start(), finish(), map(0), map_size(0) {
  341       fill_initialize(n, value);
  342   }
  343 
  344   deque(int n, const value_type& value)
  345     : start(), finish(), map(0), map_size(0) {
  346       fill_initialize(n, value);
  347   }
  348  
  349   deque(long n, const value_type& value)
  350     : start(), finish(), map(0), map_size(0) {
  351       fill_initialize(n, value);
  352   }
  353 
  354   explicit deque(size_type n)
  355     : start(), finish(), map(0), map_size(0) {
  356     fill_initialize(n, value_type());
  357   }
  358 
  359 #ifdef __STL_MEMBER_TEMPLATES
  360 
  361   template <class InputIterator>
  362   deque(InputIterator first, InputIterator last)
  363     : start(), finish(), map(0), map_size(0)
  364   {
  365     range_initialize(first, last, iterator_category(first));
  366   }
  367 
  368 #else /* __STL_MEMBER_TEMPLATES */
  369 
  370   deque(const value_type* first, const value_type* last)
  371     : start(), finish(), map(0), map_size(0)
  372   {
  373     create_map_and_nodes(last - first);
  374 #       ifdef __STL_USE_EXCEPTIONS
  375     try {
  376 #       endif /* __STL_USE_EXCEPTIONS */
  377       uninitialized_copy(first, last, start);
  378 #       ifdef __STL_USE_EXCEPTIONS
  379     }
  380     catch(...) {
  381       destroy_map_and_nodes();
  382       throw;
  383     }
  384 #       endif /* __STL_USE_EXCEPTIONS */
  385   }
  386 
  387   deque(const_iterator first, const_iterator last)
  388     : start(), finish(), map(0), map_size(0)
  389   {
  390     create_map_and_nodes(last - first);
  391 #       ifdef __STL_USE_EXCEPTIONS
  392     try {
  393 #       endif /* __STL_USE_EXCEPTIONS */
  394       uninitialized_copy(first, last, start);
  395 #       ifdef __STL_USE_EXCEPTIONS
  396     }
  397     catch(...) {
  398       destroy_map_and_nodes();
  399       throw;
  400     }
  401 #       endif /* __STL_USE_EXCEPTIONS */
  402   }
  403 
  404 #endif /* __STL_MEMBER_TEMPLATES */
  405 
  406   ~deque() {
  407     destroy(start, finish);
  408     destroy_map_and_nodes();
  409   }
  410 
  411   deque& operator= (const deque& x) {
  412     const size_type len = size();
  413     if (&x != this) {
  414       if (len >= x.size())
  415         erase(copy(x.begin(), x.end(), start), finish);
  416       else {
  417         const_iterator mid = x.begin() + len;
  418         copy(x.begin(), mid, start);
  419         insert(finish, mid, x.end());
  420       }
  421     }
  422     return *this;
  423   }        
  424 
  425   void swap(deque& x) {
  426     ::swap(start, x.start);
  427     ::swap(finish, x.finish);
  428     ::swap(map, x.map);
  429     ::swap(map_size, x.map_size);
  430   }
  431 
  432 public:                         // push_* and pop_*
  433   
  434   void push_back(const value_type& t) {
  435     if (finish.cur != finish.last - 1) {
  436       construct(finish.cur, t);
  437       ++finish.cur;
  438     }
  439     else
  440       push_back_aux(t);
  441   }
  442 
  443   void push_front(const value_type& t) {
  444     if (start.cur != start.first) {
  445       construct(start.cur - 1, t);
  446       --start.cur;
  447     }
  448     else
  449       push_front_aux(t);
  450   }
  451 
  452   void pop_back() {
  453     if (finish.cur != finish.first) {
  454       --finish.cur;
  455       destroy(finish.cur);
  456     }
  457     else
  458       pop_back_aux();
  459   }
  460 
  461   void pop_front() {
  462     if (start.cur != start.last - 1) {
  463       destroy(start.cur);
  464       ++start.cur;
  465     }
  466     else 
  467       pop_front_aux();
  468   }
  469 
  470 public:                         // Insert
  471 
  472   iterator insert(iterator position, const value_type& x) {
  473     if (position.cur == start.cur) {
  474       push_front(x);
  475       return start;
  476     }
  477     else if (position.cur == finish.cur) {
  478       push_back(x);
  479       iterator tmp = finish;
  480       --tmp;
  481       return tmp;
  482     }
  483     else {
  484       return insert_aux(position, x);
  485     }
  486   }
  487 
  488   iterator insert(iterator position) { return insert(position, value_type()); }
  489 
  490   void insert(iterator pos, size_type n, const value_type& x); 
  491 
  492   void insert(iterator pos, int n, const value_type& x) {
  493     insert(pos, (size_type) n, x);
  494   }
  495   void insert(iterator pos, long n, const value_type& x) {
  496     insert(pos, (size_type) n, x);
  497   }
  498 
  499 #ifdef __STL_MEMBER_TEMPLATES  
  500 
  501   template <class InputIterator>
  502   void insert(iterator pos, InputIterator first, InputIterator last) {
  503     insert(pos, first, last, iterator_category(first));
  504   }
  505 
  506 #else /* __STL_MEMBER_TEMPLATES */
  507 
  508   void insert(iterator pos, const value_type* first, const value_type* last);
  509   void insert(iterator pos, const_iterator first, const_iterator last);
  510 
  511 #endif /* __STL_MEMBER_TEMPLATES */
  512 
  513   void resize(size_type new_size, const value_type& x) {
  514     const size_type len = size();
  515     if (new_size < len) 
  516       erase(start + new_size, finish);
  517     else
  518       insert(finish, new_size - len, x);
  519   }
  520 
  521   void resize(size_type new_size) { resize(new_size, value_type()); }
  522 
  523 public:                         // Erase
  524   void erase(iterator pos) {
  525     iterator next = pos;
  526     ++next;
  527     if (pos - start < size() / 2) {
  528       copy_backward(start, pos, next);
  529       pop_front();
  530     }
  531     else {
  532       copy(next, finish, pos);
  533       pop_back();
  534     }
  535   }
  536 
  537   void erase(iterator first, iterator last);
  538   void clear(); 
  539 
  540 protected:                        // Internal construction/destruction
  541 
  542   void create_map_and_nodes(size_type num_elements);
  543   void destroy_map_and_nodes();
  544   void fill_initialize(size_type n, const value_type& value);
  545 
  546 #ifdef __STL_MEMBER_TEMPLATES  
  547 
  548   template <class InputIterator>
  549   void range_initialize(InputIterator first, InputIterator last,
  550                         input_iterator_tag);
  551 
  552   template <class ForwardIterator>
  553   void range_initialize(ForwardIterator first, ForwardIterator last,
  554                         forward_iterator_tag);
  555 
  556   template <class BidirectionalIterator>
  557   void range_initialize(BidirectionalIterator first,
  558                         BidirectionalIterator last,
  559                         bidirectional_iterator_tag) {
  560     range_initialize(first, last, forward_iterator_tag());
  561   }
  562 
  563   template <class RandomAccessIterator>
  564   void range_initialize(RandomAccessIterator first, RandomAccessIterator last,
  565                         random_access_iterator_tag) {
  566     range_initialize(first, last, forward_iterator_tag());
  567   }
  568 
  569 #endif /* __STL_MEMBER_TEMPLATES */
  570 
  571 protected:                        // Internal push_* and pop_*
  572 
  573   void push_back_aux(const value_type& t);
  574   void push_front_aux(const value_type& t);
  575   void pop_back_aux();
  576   void pop_front_aux();
  577 
  578 protected:                        // Internal insert functions
  579 
  580 #ifdef __STL_MEMBER_TEMPLATES  
  581 
  582   template <class InputIterator>
  583   void insert(iterator pos, InputIterator first, InputIterator last,
  584               input_iterator_tag);
  585 
  586   template <class ForwardIterator>
  587   void insert(iterator pos, ForwardIterator first, ForwardIterator last,
  588               forward_iterator_tag);
  589 
  590   template <class BidirectionalIterator>
  591   void insert(iterator pos,
  592               BidirectionalIterator first, BidirectionalIterator last,
  593               bidirectional_iterator_tag) {
  594     insert(pos, first, last, forward_iterator_tag());
  595   }
  596 
  597   template <class RandomAccessIterator>
  598   void insert(iterator pos,
  599               RandomAccessIterator first, RandomAccessIterator last,
  600               random_access_iterator_tag) {
  601     insert(pos, first, last, forward_iterator_tag());
  602   }
  603 #endif /* __STL_MEMBER_TEMPLATES */
  604 
  605   iterator insert_aux(iterator pos, const value_type& x);
  606   void insert_aux(iterator pos, size_type n, const value_type& x);
  607 
  608 #ifdef __STL_MEMBER_TEMPLATES  
  609 
  610   template <class ForwardIterator>
  611   void insert_aux(iterator pos, ForwardIterator first, ForwardIterator last,
  612                   size_type n);
  613 
  614 #else /* __STL_MEMBER_TEMPLATES */
  615   
  616   void insert_aux(iterator pos,
  617                   const value_type* first, const value_type* last,
  618                   size_type n);
  619 
  620   void insert_aux(iterator pos, const_iterator first, const_iterator last,
  621                   size_type n);
  622  
  623 #endif /* __STL_MEMBER_TEMPLATES */
  624 
  625   iterator reserve_elements_at_front(size_type n) {
  626     size_type vacancies = start.cur - start.first;
  627     if (n > vacancies) 
  628       new_elements_at_front(n - vacancies);
  629     return start - n;
  630   }
  631 
  632   iterator reserve_elements_at_back(size_type n) {
  633     size_type vacancies = (finish.last - finish.cur) - 1;
  634     if (n > vacancies)
  635       new_elements_at_back(n - vacancies);
  636     return finish + n;
  637   }
  638 
  639   void new_elements_at_front(size_type new_elements);
  640   void new_elements_at_back(size_type new_elements);
  641 
  642   void destroy_nodes_at_front(iterator before_start);
  643   void destroy_nodes_at_back(iterator after_finish);
  644 
  645 protected:                      // Allocation of map and nodes
  646 
  647   // Makes sure the map has space for new nodes.  Does not actually
  648   //  add the nodes.  Can invalidate map pointers.  (And consequently, 
  649   //  deque iterators.)
  650 
  651   void reserve_map_at_back (size_type nodes_to_add = 1) {
  652     if (nodes_to_add + 1 > map_size - (finish.node - map))
  653       reallocate_map(nodes_to_add);
  654   }
  655 
  656   void reserve_map_at_front (size_type nodes_to_add = 1) {
  657     if (nodes_to_add > start.node - map)
  658       reallocate_map(nodes_to_add);
  659   }
  660 
  661   void reallocate_map(size_type nodes_to_add);
  662 
  663   pointer allocate_node() { return data_allocator::allocate(buffer_size()); }
  664   void deallocate_node(pointer n) {
  665     data_allocator::deallocate(n, buffer_size());
  666   }
  667 
  668 #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG
  669 public:
  670   bool operator==(const deque<T, Alloc, 0>& x) const {
  671     return size() == x.size() && equal(begin(), end(), x.begin());
  672   }
  673   bool operator!=(const deque<T, Alloc, 0>& x) const {
  674     return size() != x.size() || !equal(begin(), end(), x.begin());
  675   }
  676   bool operator<(const deque<T, Alloc, 0>& x) const {
  677     return lexicographical_compare(begin(), end(), x.begin(), x.end());
  678   }
  679 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  680 };
  681 
  682 // Non-inline member functions
  683 
  684 template <class T, class Alloc, size_t BufSize>
  685 void deque<T, Alloc, BufSize>::insert(iterator pos,
  686                                       size_type n, const value_type& x) {
  687   if (pos.cur == start.cur) {
  688     iterator new_start = reserve_elements_at_front(n);
  689     uninitialized_fill(new_start, start, x);
  690     start = new_start;
  691   }
  692   else if (pos.cur == finish.cur) {
  693     iterator new_finish = reserve_elements_at_back(n);
  694     uninitialized_fill(finish, new_finish, x);
  695     finish = new_finish;
  696   }
  697   else 
  698     insert_aux(pos, n, x);
  699 }
  700 
  701 #ifndef __STL_MEMBER_TEMPLATES  
  702 
  703 template <class T, class Alloc, size_t BufSize>
  704 void deque<T, Alloc, BufSize>::insert(iterator pos,
  705                                       const value_type* first,
  706                                       const value_type* last) {
  707   size_type n = last - first;
  708   if (pos.cur == start.cur) {
  709     iterator new_start = reserve_elements_at_front(n);
  710     uninitialized_copy(first, last, new_start);
  711     start = new_start;
  712   }
  713   else if (pos.cur == finish.cur) {
  714     iterator new_finish = reserve_elements_at_back(n);
  715     uninitialized_copy(first, last, finish);
  716     finish = new_finish;
  717   }
  718   else
  719     insert_aux(pos, first, last, n);
  720 }
  721 
  722 template <class T, class Alloc, size_t BufSize>
  723 void deque<T, Alloc, BufSize>::insert(iterator pos,
  724                                       const_iterator first,
  725                                       const_iterator last)
  726 {
  727   size_type n = last - first;
  728   if (pos.cur == start.cur) {
  729     iterator new_start = reserve_elements_at_front(n);
  730     uninitialized_copy(first, last, new_start);
  731     start = new_start;
  732   }
  733   else if (pos.cur == finish.cur) {
  734     iterator new_finish = reserve_elements_at_back(n);
  735     uninitialized_copy(first, last, finish);
  736     finish = new_finish;
  737   }
  738   else
  739     insert_aux(pos, first, last, n);
  740 }
  741 
  742 #endif /* __STL_MEMBER_TEMPLATES */
  743 
  744 template <class T, class Alloc, size_t BufSize>
  745 void deque<T, Alloc, BufSize>::erase(iterator first, iterator last) {
  746   if (first == start && last == finish)
  747     clear();
  748   else {
  749     difference_type n = last - first;
  750     difference_type elems_before = first - start;
  751     if (elems_before < (size() - n) / 2) {
  752       copy_backward(start, first, last);
  753       iterator new_start = start + n;
  754       destroy(start, new_start);
  755       for (map_pointer cur = start.node; cur < new_start.node; ++cur)
  756         data_allocator::deallocate(*cur, buffer_size());
  757       start = new_start;
  758     }
  759     else {
  760       copy(last, finish, first);
  761       iterator new_finish = finish - n;
  762       destroy(new_finish, finish);
  763       for (map_pointer cur = new_finish.node + 1; cur < finish.node; ++cur)
  764         data_allocator::deallocate(*cur, buffer_size());
  765       finish = new_finish;
  766     }
  767   }
  768 }
  769 
  770 template <class T, class Alloc, size_t BufSize>
  771 void deque<T, Alloc, BufSize>::clear() {
  772   for (map_pointer node = start.node + 1; node < finish.node; ++node) {
  773     destroy(*node, *node + buffer_size());
  774     data_allocator::deallocate(*node, buffer_size());
  775   }
  776 
  777   if (start.node != finish.node) {
  778     destroy(start.cur, start.last);
  779     destroy(finish.first, finish.cur);
  780     data_allocator::deallocate(finish.first, buffer_size());
  781   }
  782   else
  783     destroy(start.cur, finish.cur);
  784 
  785   finish = start;
  786 }
  787 
  788 template <class T, class Alloc, size_t BufSize>
  789 void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {
  790   size_type num_nodes = num_elements / buffer_size() + 1;
  791 
  792   map_size = max(initial_map_size(), num_nodes + 2);
  793   map = map_allocator::allocate(map_size);
  794 
  795   map_pointer nstart = map + (map_size - num_nodes) / 2;
  796   map_pointer nfinish = nstart + num_nodes - 1;
  797     
  798   map_pointer cur;
  799 #     ifdef __STL_USE_EXCEPTIONS
  800   try {
  801 #     endif /* __STL_USE_EXCEPTIONS */
  802     for (cur = nstart; cur <= nfinish; ++cur)
  803       *cur = allocate_node();
  804 #     ifdef __STL_USE_EXCEPTIONS
  805   }
  806   catch(...) {
  807     for (map_pointer n = nstart; n < cur; ++n)
  808       deallocate_node(*n);
  809     map_allocator::deallocate(map, map_size);
  810     throw;
  811   }
  812 #     endif /* __STL_USE_EXCEPTIONS */
  813 
  814   start.set_node(nstart);
  815   finish.set_node(nfinish);
  816   start.cur = start.first;
  817   finish.cur = finish.first + num_elements % buffer_size();
  818 }
  819 
  820 // This is only used as a cleanup function in catch clauses.
  821 template <class T, class Alloc, size_t BufSize>
  822 void deque<T, Alloc, BufSize>::destroy_map_and_nodes() {
  823   for (map_pointer cur = start.node; cur <= finish.node; ++cur)
  824     deallocate_node(*cur);
  825   map_allocator::deallocate(map, map_size);
  826 }
  827   
  828 
  829 template <class T, class Alloc, size_t BufSize>
  830 void deque<T, Alloc, BufSize>::fill_initialize(size_type n,
  831                                                const value_type& value) {
  832   create_map_and_nodes(n);
  833   map_pointer cur;
  834 #     ifdef __STL_USE_EXCEPTIONS
  835   try {
  836 #     endif /* __STL_USE_EXCEPTIONS */
  837     for (cur = start.node; cur < finish.node; ++cur)
  838       uninitialized_fill(*cur, *cur + buffer_size(), value);
  839     uninitialized_fill(finish.first, finish.cur, value);
  840 #       ifdef __STL_USE_EXCEPTIONS
  841   }
  842   catch(...) {
  843     for (map_pointer n = start.node; n < cur; ++n)
  844       destroy(*cur, *cur + buffer_size());
  845     destroy_map_and_nodes();
  846     throw;
  847   }
  848 #       endif /* __STL_USE_EXCEPTIONS */
  849 }
  850 
  851 #ifdef __STL_MEMBER_TEMPLATES  
  852 
  853 template <class T, class Alloc, size_t BufSize>
  854 template <class InputIterator>
  855 void deque<T, Alloc, BufSize>::range_initialize(InputIterator first,
  856                                                 InputIterator last,
  857                                                 input_iterator_tag) {
  858   create_map_and_nodes(0);
  859   for ( ; first != last; ++first)
  860     push_back(*first);
  861 }
  862 
  863 template <class T, class Alloc, size_t BufSize>
  864 template <class ForwardIterator>
  865 void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first,
  866                                                 ForwardIterator last,
  867                                                 forward_iterator_tag) {
  868   size_type n = 0;
  869   distance(first, last, n);
  870   create_map_and_nodes(n);
  871 #     ifdef __STL_USE_EXCEPTIONS
  872   try {
  873 #     endif /* __STL_USE_EXCEPTIONS */
  874     uninitialized_copy(first, last, start);
  875 #     ifdef __STL_USE_EXCEPTIONS
  876   }
  877   catch(...) {
  878     destroy_map_and_nodes();
  879     throw;
  880   }
  881 #     endif /* __STL_USE_EXCEPTIONS */
  882 }
  883 
  884 #endif /* __STL_MEMBER_TEMPLATES */
  885 
  886 // Called only if finish.cur == finish.last - 1.
  887 template <class T, class Alloc, size_t BufSize>
  888 void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {
  889   value_type t_copy = t;
  890   reserve_map_at_back();
  891   *(finish.node + 1) = allocate_node();
  892 #     ifdef __STL_USE_EXCEPTIONS
  893   try {
  894 #     endif /* __STL_USE_EXCEPTIONS */
  895     construct(finish.cur, t_copy);
  896     finish.set_node(finish.node + 1);
  897     finish.cur = finish.first;
  898 #     ifdef __STL_USE_EXCEPTIONS
  899   }
  900   catch(...) {
  901     deallocate_node(*(finish.node + 1));
  902     throw;
  903   }
  904 #     endif /* __STL_USE_EXCEPTIONS */
  905 }
  906 
  907 // Called only if start.cur == start.first.
  908 template <class T, class Alloc, size_t BufSize>
  909 void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
  910   value_type t_copy = t;
  911   reserve_map_at_front();
  912   *(start.node - 1) = allocate_node();
  913 #     ifdef __STL_USE_EXCEPTIONS
  914   try {
  915 #     endif /* __STL_USE_EXCEPTIONS */
  916     start.set_node(start.node - 1);
  917     start.cur = start.last - 1;
  918     construct(start.cur, t_copy);
  919 #     ifdef __STL_USE_EXCEPTIONS
  920   }
  921   catch(...) {
  922     start.set_node(start.node + 1);
  923     deallocate_node(*(start.node - 1));
  924     throw;
  925   }
  926 #     endif /* __STL_USE_EXCEPTIONS */
  927 } 
  928 
  929 // Called only if finish.cur == finish.first.
  930 template <class T, class Alloc, size_t BufSize>
  931 void deque<T, Alloc, BufSize>:: pop_back_aux() {
  932   deallocate_node(finish.first);
  933   finish.set_node(finish.node - 1);
  934   finish.cur = finish.last - 1;
  935   destroy(finish.cur);
  936 }
  937 
  938 // Called only if start.cur == start.last - 1.  Note that if the deque
  939 //  has at least one element (a necessary precondition for this member
  940 //  function), and if start.cur == start.last, then the deque must have
  941 //  at least two nodes.
  942 template <class T, class Alloc, size_t BufSize>
  943 void deque<T, Alloc, BufSize>::pop_front_aux() {
  944   destroy(start.cur);
  945   deallocate_node(start.first);
  946   start.set_node(start.node + 1);
  947   start.cur = start.first;
  948 }      
  949 
  950 #ifdef __STL_MEMBER_TEMPLATES  
  951 
  952 template <class T, class Alloc, size_t BufSize>
  953 template <class InputIterator>
  954 void deque<T, Alloc, BufSize>::insert(iterator pos,
  955                                       InputIterator first, InputIterator last,
  956                                       input_iterator_tag) {
  957   copy(first, last, inserter(*this, pos));
  958 }
  959 
  960 template <class T, class Alloc, size_t BufSize>
  961 template <class ForwardIterator>
  962 void deque<T, Alloc, BufSize>::insert(iterator pos,
  963                                       ForwardIterator first,
  964                                       ForwardIterator last,
  965                                       forward_iterator_tag) {
  966   size_type n = 0;
  967   distance(first, last, n);
  968   if (pos.cur == start.cur) {
  969     iterator new_start = reserve_elements_at_front(n);
  970     uninitialized_copy(first, last, new_start);
  971     start = new_start;
  972   }
  973   else if (pos.cur == finish.cur) {
  974     iterator new_finish = reserve_elements_at_back(n);
  975     uninitialized_copy(first, last, finish);
  976     finish = new_finish;
  977   }
  978   else
  979     insert_aux(pos, first, last, n);
  980 }
  981 
  982 #endif /* __STL_MEMBER_TEMPLATES */
  983 
  984 template <class T, class Alloc, size_t BufSize>
  985 deque<T, Alloc, BufSize>::iterator
  986 deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {
  987   difference_type index = pos - start;
  988   value_type x_copy = x;
  989   if (index < size() / 2) {
  990     push_front(front());
  991     iterator front1 = start;
  992     ++front1;
  993     iterator front2 = front1;
  994     ++front2;
  995     pos = start + index;
  996     iterator pos1 = pos;
  997     ++pos1;
  998     copy(front2, pos1, front1);
  999   }
 1000   else {
 1001     push_back(back());
 1002     iterator back1 = finish;
 1003     --back1;
 1004     iterator back2 = back1;
 1005     --back2;
 1006     pos = start + index;
 1007     copy_backward(pos, back2, back1);
 1008   }
 1009   *pos = x_copy;
 1010   return pos;
 1011 }
 1012 
 1013 template <class T, class Alloc, size_t BufSize>
 1014 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
 1015                                           size_type n, const value_type& x) {
 1016   const difference_type elems_before = pos - start;
 1017   size_type length = size();
 1018   value_type x_copy = x;
 1019   if (elems_before < length / 2) {
 1020     iterator new_start = reserve_elements_at_front(n);
 1021     iterator old_start = start;
 1022     pos = start + elems_before;
 1023 #       ifdef __STL_USE_EXCEPTIONS
 1024     try {
 1025 #       endif /* __STL_USE_EXCEPTIONS */
 1026       if (elems_before >= n) {
 1027         iterator start_n = start + n;
 1028         uninitialized_copy(start, start_n, new_start);
 1029         start = new_start;
 1030         copy(start_n, pos, old_start);
 1031         fill(pos - n, pos, x_copy);
 1032       }
 1033       else {
 1034         __uninitialized_copy_fill(start, pos, new_start, start, x_copy);
 1035         start = new_start;
 1036         fill(old_start, pos, x_copy);
 1037       }
 1038 #       ifdef __STL_USE_EXCEPTIONS
 1039     }
 1040     catch(...) {
 1041       destroy_nodes_at_front(new_start);
 1042       throw;
 1043     }
 1044 #       endif /* __STL_USE_EXCEPTIONS */
 1045   }
 1046   else {
 1047     iterator new_finish = reserve_elements_at_back(n);
 1048     iterator old_finish = finish;
 1049     const difference_type elems_after = length - elems_before;
 1050     pos = finish - elems_after;
 1051 #       ifdef __STL_USE_EXCEPTIONS
 1052     try {
 1053 #       endif /* __STL_USE_EXCEPTIONS */
 1054       if (elems_after > n) {
 1055         iterator finish_n = finish - n;
 1056         uninitialized_copy(finish_n, finish, finish);
 1057         finish = new_finish;
 1058         copy_backward(pos, finish_n, old_finish);
 1059         fill(pos, pos + n, x_copy);
 1060       }
 1061       else {
 1062         __uninitialized_fill_copy(finish, pos + n, x_copy, pos, finish);
 1063         finish = new_finish;
 1064         fill(pos, old_finish, x_copy);
 1065       }
 1066 #       ifdef __STL_USE_EXCEPTIONS
 1067     }
 1068     catch(...) {
 1069       destroy_nodes_at_back(new_finish);
 1070       throw;
 1071     }
 1072 #       endif /* __STL_USE_EXCEPTIONS */    
 1073   }
 1074 }
 1075 
 1076 #ifdef __STL_MEMBER_TEMPLATES  
 1077 
 1078 template <class T, class Alloc, size_t BufSize>
 1079 template <class ForwardIterator>
 1080 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
 1081                                           ForwardIterator first,
 1082                                           ForwardIterator last,
 1083                                           size_type n)
 1084 {
 1085   const difference_type elems_before = pos - start;
 1086   size_type length = size();
 1087   if (elems_before < length / 2) {
 1088     iterator new_start = reserve_elements_at_front(n);
 1089     iterator old_start = start;
 1090     pos = start + elems_before;
 1091 #       ifdef __STL_USE_EXCEPTIONS
 1092     try {
 1093 #       endif /* __STL_USE_EXCEPTIONS */
 1094       if (elems_before >= n) {
 1095         iterator start_n = start + n;      
 1096         uninitialized_copy(start, start_n, new_start);
 1097         start = new_start;
 1098         copy(start_n, pos, old_start);
 1099         copy(first, last, pos - n);
 1100       }
 1101       else {
 1102         ForwardIterator mid = first;
 1103         advance(mid, n - elems_before);
 1104         __uninitialized_copy_copy(start, pos, first, mid, new_start);
 1105         start = new_start;
 1106         copy(mid, last, old_start);
 1107       }
 1108 #       ifdef __STL_USE_EXCEPTIONS
 1109     }
 1110     catch(...) {
 1111       destroy_nodes_at_front(new_start);
 1112       throw;
 1113     }
 1114 #       endif /* __STL_USE_EXCEPTIONS */
 1115   }
 1116   else {
 1117     iterator new_finish = reserve_elements_at_back(n);
 1118     iterator old_finish = finish;
 1119     const difference_type elems_after = length - elems_before;
 1120     pos = finish - elems_after;
 1121 #       ifdef __STL_USE_EXCEPTIONS
 1122     try {
 1123 #       endif /* __STL_USE_EXCEPTIONS */
 1124       if (elems_after > n) {
 1125         iterator finish_n = finish - n;
 1126         uninitialized_copy(finish_n, finish, finish);
 1127         finish = new_finish;
 1128         copy_backward(pos, finish_n, old_finish);
 1129         copy(first, last, pos);
 1130       }
 1131       else {
 1132         ForwardIterator mid = first;
 1133         advance(mid, elems_after);
 1134         __uninitialized_copy_copy(mid, last, pos, finish, finish);
 1135         finish = new_finish;
 1136         copy(first, mid, pos);
 1137       }
 1138 #       ifdef __STL_USE_EXCEPTIONS
 1139     }
 1140     catch(...) {
 1141       destroy_nodes_at_back(new_finish);
 1142       throw;
 1143     }
 1144 #       endif /* __STL_USE_EXCEPTIONS */
 1145   }
 1146 }
 1147 
 1148 #else /* __STL_MEMBER_TEMPLATES */
 1149 
 1150 template <class T, class Alloc, size_t BufSize>
 1151 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
 1152                                           const value_type* first,
 1153                                           const value_type* last,
 1154                                           size_type n)
 1155 {
 1156   const difference_type elems_before = pos - start;
 1157   size_type length = size();
 1158   if (elems_before < length / 2) {
 1159     iterator new_start = reserve_elements_at_front(n);
 1160     iterator old_start = start;
 1161     pos = start + elems_before;
 1162 #       ifdef __STL_USE_EXCEPTIONS
 1163     try {
 1164 #       endif /* __STL_USE_EXCEPTIONS */
 1165       if (elems_before >= n) {
 1166         iterator start_n = start + n;
 1167         uninitialized_copy(start, start_n, new_start);
 1168         start = new_start;
 1169         copy(start_n, pos, old_start);
 1170         copy(first, last, pos - n);
 1171       }
 1172       else {
 1173         const value_type* mid = first + (n - elems_before);
 1174         __uninitialized_copy_copy(start, pos, first, mid, new_start);
 1175         start = new_start;
 1176         copy(mid, last, old_start);
 1177       }
 1178 #       ifdef __STL_USE_EXCEPTIONS
 1179     }
 1180     catch(...) {
 1181       destroy_nodes_at_front(new_start);
 1182       throw;
 1183     }
 1184 #       endif /* __STL_USE_EXCEPTIONS */
 1185   }
 1186   else {
 1187     iterator new_finish = reserve_elements_at_back(n);
 1188     iterator old_finish = finish;
 1189     const difference_type elems_after = length - elems_before;
 1190     pos = finish - elems_after;
 1191 #       ifdef __STL_USE_EXCEPTIONS
 1192     try {
 1193 #       endif /* __STL_USE_EXCEPTIONS */
 1194       if (elems_after > n) {
 1195         iterator finish_n = finish - n;
 1196         uninitialized_copy(finish_n, finish, finish);
 1197         finish = new_finish;
 1198         copy_backward(pos, finish_n, old_finish);
 1199         copy(first, last, pos);
 1200       }
 1201       else {
 1202         const value_type* mid = first + elems_after;
 1203         __uninitialized_copy_copy(mid, last, pos, finish, finish);
 1204         finish = new_finish;
 1205         copy(first, mid, pos);
 1206       }
 1207 #       ifdef __STL_USE_EXCEPTIONS
 1208     }
 1209     catch(...) {
 1210       destroy_nodes_at_back(new_finish);
 1211       throw;
 1212     }
 1213 #       endif /* __STL_USE_EXCEPTIONS */
 1214   }
 1215 }
 1216 
 1217 template <class T, class Alloc, size_t BufSize>
 1218 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
 1219                                           const_iterator first,
 1220                                           const_iterator last,
 1221                                           size_type n)
 1222 {
 1223   const difference_type elems_before = pos - start;
 1224   size_type length = size();
 1225   if (elems_before < length / 2) {
 1226     iterator new_start = reserve_elements_at_front(n);
 1227     iterator old_start = start;
 1228     pos = start + elems_before;
 1229 #       ifdef __STL_USE_EXCEPTIONS
 1230     try {
 1231 #       endif /* __STL_USE_EXCEPTIONS */
 1232       if (elems_before >= n) {
 1233         iterator start_n = start + n;
 1234         uninitialized_copy(start, start_n, new_start);
 1235         start = new_start;
 1236         copy(start_n, pos, old_start);
 1237         copy(first, last, pos - n);
 1238       }
 1239       else {
 1240         const_iterator mid = first + (n - elems_before);
 1241         __uninitialized_copy_copy(start, pos, first, mid, new_start);
 1242         start = new_start;
 1243         copy(mid, last, old_start);
 1244       }
 1245 #       ifdef __STL_USE_EXCEPTIONS
 1246     }
 1247     catch(...) {
 1248       destroy_nodes_at_front(new_start);
 1249       throw;
 1250     }
 1251 #       endif /* __STL_USE_EXCEPTIONS */
 1252   }
 1253   else {
 1254     iterator new_finish = reserve_elements_at_back(n);
 1255     iterator old_finish = finish;
 1256     const difference_type elems_after = length - elems_before;
 1257     pos = finish - elems_after;
 1258 #       ifdef __STL_USE_EXCEPTIONS
 1259     try {
 1260 #       endif /* __STL_USE_EXCEPTIONS */
 1261       if (elems_after > n) {
 1262         iterator finish_n = finish - n;
 1263         uninitialized_copy(finish_n, finish, finish);
 1264         finish = new_finish;
 1265         copy_backward(pos, finish_n, old_finish);
 1266         copy(first, last, pos);
 1267       }
 1268       else {
 1269         const_iterator mid = first + elems_after;
 1270         __uninitialized_copy_copy(mid, last, pos, finish, finish);
 1271         finish = new_finish;
 1272         copy(first, mid, pos);
 1273       }
 1274 #       ifdef __STL_USE_EXCEPTIONS
 1275     }
 1276     catch(...) {
 1277       destroy_nodes_at_back(new_finish);
 1278       throw;
 1279     }
 1280 #       endif /* __STL_USE_EXCEPTIONS */
 1281   }
 1282 }
 1283 
 1284 #endif /* __STL_MEMBER_TEMPLATES */
 1285 
 1286 template <class T, class Alloc, size_t BufSize>
 1287 void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) {
 1288   size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
 1289   reserve_map_at_front(new_nodes);
 1290   size_type i;
 1291 #       ifdef __STL_USE_EXCEPTIONS
 1292   try {
 1293 #       endif /* __STL_USE_EXCEPTIONS */
 1294     for (i = 1; i <= new_nodes; ++i)
 1295       *(start.node - i) = allocate_node();
 1296 #       ifdef __STL_USE_EXCEPTIONS
 1297   }
 1298   catch(...) {
 1299     for (size_type j = 1; j < i; ++j)
 1300       deallocate_node(*(start.node - j));      
 1301     throw;
 1302   }
 1303 #       endif /* __STL_USE_EXCEPTIONS */
 1304 }
 1305 
 1306 template <class T, class Alloc, size_t BufSize>
 1307 void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) {
 1308   size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
 1309   reserve_map_at_back(new_nodes);
 1310   size_type i;
 1311 #       ifdef __STL_USE_EXCEPTIONS
 1312   try {
 1313 #       endif /* __STL_USE_EXCEPTIONS */
 1314     for (i = 1; i <= new_nodes; ++i)
 1315       *(finish.node + i) = allocate_node();
 1316 #       ifdef __STL_USE_EXCEPTIONS
 1317   }
 1318   catch(...) {
 1319     for (size_type j = 1; j < i; ++j)
 1320       deallocate_node(*(finish.node + j));      
 1321     throw;
 1322   }
 1323 #       endif /* __STL_USE_EXCEPTIONS */
 1324 }
 1325 
 1326 template <class T, class Alloc, size_t BufSize>
 1327 void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) {
 1328   for (map_pointer n = before_start.node; n < start.node; ++n)
 1329     deallocate_node(*n);
 1330 }
 1331 
 1332 template <class T, class Alloc, size_t BufSize>
 1333 void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) {
 1334   for (map_pointer n = after_finish.node; n > finish.node; --n)
 1335     deallocate_node(*n);
 1336 }
 1337 
 1338 template <class T, class Alloc, size_t BufSize>
 1339 void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add) {
 1340   size_type old_num_nodes = finish.node - start.node + 1;
 1341   size_type new_num_nodes = old_num_nodes + nodes_to_add;
 1342 
 1343   map_pointer new_nstart;
 1344   if (new_num_nodes > map_size / 2) {
 1345     size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
 1346 
 1347     map_pointer new_map = map_allocator::allocate(new_map_size);
 1348     new_nstart = new_map + (new_map_size - new_num_nodes) / 2;
 1349     copy(start.node, finish.node + 1, new_nstart);
 1350     map_allocator::deallocate(map, map_size);
 1351 
 1352     map = new_map;
 1353     map_size = new_map_size;
 1354   }
 1355   else {
 1356     new_nstart = map + (map_size - new_num_nodes) / 2;
 1357     if (new_nstart < start.node)
 1358       copy(start.node, finish.node + 1, new_nstart);
 1359     else
 1360       copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
 1361   }
 1362   start.set_node(new_nstart);
 1363   finish.set_node(new_nstart + old_num_nodes - 1);
 1364 }
 1365 
 1366 
 1367 // Nonmember functions.
 1368 
 1369 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
 1370 
 1371 template <class T, class Alloc, size_t BufSiz>
 1372 bool operator==(const deque<T, Alloc, BufSiz>& x,
 1373                 const deque<T, Alloc, BufSiz>& y) {
 1374   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
 1375 }
 1376 
 1377 template <class T, class Alloc, size_t BufSiz>
 1378 bool operator<(const deque<T, Alloc, BufSiz>& x,
 1379                const deque<T, Alloc, BufSiz>& y) {
 1380   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
 1381 }
 1382 
 1383 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
 1384            
 1385   
 1386 #endif /* __SGI_STL_DEQUE_H */
 1387