stl_deque.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:41k
源码类别:

STL

开发平台:

Visual C++

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