home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / stl_deque.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-08  |  52.3 KB  |  1,653 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * 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. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #include <concept_checks.h>
  32.  
  33. #ifndef __SGI_STL_INTERNAL_DEQUE_H
  34. #define __SGI_STL_INTERNAL_DEQUE_H
  35.  
  36. /* Class invariants:
  37.  *  For any nonsingular iterator i:
  38.  *    i.node is the address of an element in the map array.  The
  39.  *      contents of i.node is a pointer to the beginning of a node.
  40.  *    i.first == *(i.node) 
  41.  *    i.last  == i.first + node_size
  42.  *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
  43.  *      the implication of this is that i.cur is always a dereferenceable
  44.  *      pointer, even if i is a past-the-end iterator.
  45.  *  Start and Finish are always nonsingular iterators.  NOTE: this means
  46.  *    that an empty deque must have one node, and that a deque
  47.  *    with N elements, where N is the buffer size, must have two nodes.
  48.  *  For every node other than start.node and finish.node, every element
  49.  *    in the node is an initialized object.  If start.node == finish.node,
  50.  *    then [start.cur, finish.cur) are initialized objects, and
  51.  *    the elements outside that range are uninitialized storage.  Otherwise,
  52.  *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
  53.  *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
  54.  *    are uninitialized storage.
  55.  *  [map, map + map_size) is a valid, non-empty range.  
  56.  *  [start.node, finish.node] is a valid range contained within 
  57.  *    [map, map + map_size).  
  58.  *  A pointer in the range [map, map + map_size) points to an allocated node
  59.  *    if and only if the pointer is in the range [start.node, finish.node].
  60.  */
  61.  
  62.  
  63. /*
  64.  * In previous versions of deque, there was an extra template 
  65.  * parameter so users could control the node size.  This extension
  66.  * turns out to violate the C++ standard (it can be detected using
  67.  * template template parameters), and it has been removed.
  68.  */
  69.  
  70. __STL_BEGIN_NAMESPACE 
  71.  
  72. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  73. #pragma set woff 1174
  74. #pragma set woff 1375
  75. #endif
  76.  
  77. // Note: this function is simply a kludge to work around several compilers'
  78. //  bugs in handling constant expressions.
  79. inline size_t __deque_buf_size(size_t __size) {
  80.   return __size < 512 ? size_t(512 / __size) : size_t(1);
  81. }
  82.  
  83. template <class _Tp, class _Ref, class _Ptr>
  84. struct _Deque_iterator {
  85.   typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
  86.   typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  87.   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
  88.  
  89.   typedef random_access_iterator_tag iterator_category;
  90.   typedef _Tp value_type;
  91.   typedef _Ptr pointer;
  92.   typedef _Ref reference;
  93.   typedef size_t size_type;
  94.   typedef ptrdiff_t difference_type;
  95.   typedef _Tp** _Map_pointer;
  96.  
  97.   typedef _Deque_iterator _Self;
  98.  
  99.   _Tp* _M_cur;
  100.   _Tp* _M_first;
  101.   _Tp* _M_last;
  102.   _Map_pointer _M_node;
  103.  
  104.   _Deque_iterator(_Tp* __x, _Map_pointer __y) 
  105.     : _M_cur(__x), _M_first(*__y),
  106.       _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
  107.   _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
  108.   _Deque_iterator(const iterator& __x)
  109.     : _M_cur(__x._M_cur), _M_first(__x._M_first), 
  110.       _M_last(__x._M_last), _M_node(__x._M_node) {}
  111.  
  112.   reference operator*() const { return *_M_cur; }
  113. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  114.   pointer operator->() const { return _M_cur; }
  115. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  116.  
  117.   difference_type operator-(const _Self& __x) const {
  118.     return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
  119.       (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
  120.   }
  121.  
  122.   _Self& operator++() {
  123.     ++_M_cur;
  124.     if (_M_cur == _M_last) {
  125.       _M_set_node(_M_node + 1);
  126.       _M_cur = _M_first;
  127.     }
  128.     return *this; 
  129.   }
  130.   _Self operator++(int)  {
  131.     _Self __tmp = *this;
  132.     ++*this;
  133.     return __tmp;
  134.   }
  135.  
  136.   _Self& operator--() {
  137.     if (_M_cur == _M_first) {
  138.       _M_set_node(_M_node - 1);
  139.       _M_cur = _M_last;
  140.     }
  141.     --_M_cur;
  142.     return *this;
  143.   }
  144.   _Self operator--(int) {
  145.     _Self __tmp = *this;
  146.     --*this;
  147.     return __tmp;
  148.   }
  149.  
  150.   _Self& operator+=(difference_type __n)
  151.   {
  152.     difference_type __offset = __n + (_M_cur - _M_first);
  153.     if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
  154.       _M_cur += __n;
  155.     else {
  156.       difference_type __node_offset =
  157.         __offset > 0 ? __offset / difference_type(_S_buffer_size())
  158.                    : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
  159.       _M_set_node(_M_node + __node_offset);
  160.       _M_cur = _M_first + 
  161.         (__offset - __node_offset * difference_type(_S_buffer_size()));
  162.     }
  163.     return *this;
  164.   }
  165.  
  166.   _Self operator+(difference_type __n) const
  167.   {
  168.     _Self __tmp = *this;
  169.     return __tmp += __n;
  170.   }
  171.  
  172.   _Self& operator-=(difference_type __n) { return *this += -__n; }
  173.  
  174.   _Self operator-(difference_type __n) const {
  175.     _Self __tmp = *this;
  176.     return __tmp -= __n;
  177.   }
  178.  
  179.   reference operator[](difference_type __n) const { return *(*this + __n); }
  180.  
  181.   bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
  182.   bool operator!=(const _Self& __x) const { return !(*this == __x); }
  183.   bool operator<(const _Self& __x) const {
  184.     return (_M_node == __x._M_node) ? 
  185.       (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
  186.   }
  187.   bool operator>(const _Self& __x) const  { return __x < *this; }
  188.   bool operator<=(const _Self& __x) const { return !(__x < *this); }
  189.   bool operator>=(const _Self& __x) const { return !(*this < __x); }
  190.  
  191.   void _M_set_node(_Map_pointer __new_node) {
  192.     _M_node = __new_node;
  193.     _M_first = *__new_node;
  194.     _M_last = _M_first + difference_type(_S_buffer_size());
  195.   }
  196. };
  197.  
  198. template <class _Tp, class _Ref, class _Ptr>
  199. inline _Deque_iterator<_Tp, _Ref, _Ptr>
  200. operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
  201. {
  202.   return __x + __n;
  203. }
  204.  
  205. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  206.  
  207. template <class _Tp, class _Ref, class _Ptr>
  208. inline random_access_iterator_tag
  209. iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&)
  210. {
  211.   return random_access_iterator_tag();
  212. }
  213.  
  214. template <class _Tp, class _Ref, class _Ptr>
  215. inline _Tp* value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; }
  216.  
  217. template <class _Tp, class _Ref, class _Ptr>
  218. inline ptrdiff_t* distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) {
  219.   return 0;
  220. }
  221.  
  222. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  223.  
  224. // Deque base class.  It has two purposes.  First, its constructor
  225. //  and destructor allocate (but don't initialize) storage.  This makes
  226. //  exception safety easier.  Second, the base class encapsulates all of
  227. //  the differences between SGI-style allocators and standard-conforming
  228. //  allocators.
  229.  
  230. #ifdef __STL_USE_STD_ALLOCATORS
  231.  
  232. // Base class for ordinary allocators.
  233. template <class _Tp, class _Alloc, bool __is_static>
  234. class _Deque_alloc_base {
  235. public:
  236.   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
  237.   allocator_type get_allocator() const { return _M_node_allocator; }
  238.  
  239.   _Deque_alloc_base(const allocator_type& __a)
  240.     : _M_node_allocator(__a), _M_map_allocator(__a),
  241.       _M_map(0), _M_map_size(0)
  242.   {}
  243.   
  244. protected:
  245.   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
  246.           _Map_allocator_type;
  247.  
  248.   allocator_type      _M_node_allocator;
  249.   _Map_allocator_type _M_map_allocator;
  250.  
  251.   _Tp* _M_allocate_node() {
  252.     return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
  253.   }
  254.   void _M_deallocate_node(_Tp* __p) {
  255.     _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
  256.   }
  257.   _Tp** _M_allocate_map(size_t __n) 
  258.     { return _M_map_allocator.allocate(__n); }
  259.   void _M_deallocate_map(_Tp** __p, size_t __n) 
  260.     { _M_map_allocator.deallocate(__p, __n); }
  261.  
  262.   _Tp** _M_map;
  263.   size_t _M_map_size;
  264. };
  265.  
  266. // Specialization for instanceless allocators.
  267. template <class _Tp, class _Alloc>
  268. class _Deque_alloc_base<_Tp, _Alloc, true>
  269. {
  270. public:
  271.   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
  272.   allocator_type get_allocator() const { return allocator_type(); }
  273.  
  274.   _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
  275.   
  276. protected:
  277.   typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
  278.   typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
  279.  
  280.   _Tp* _M_allocate_node() {
  281.     return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
  282.   }
  283.   void _M_deallocate_node(_Tp* __p) {
  284.     _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
  285.   }
  286.   _Tp** _M_allocate_map(size_t __n) 
  287.     { return _Map_alloc_type::allocate(__n); }
  288.   void _M_deallocate_map(_Tp** __p, size_t __n) 
  289.     { _Map_alloc_type::deallocate(__p, __n); }
  290.  
  291.   _Tp** _M_map;
  292.   size_t _M_map_size;
  293. };
  294.  
  295. template <class _Tp, class _Alloc>
  296. class _Deque_base
  297.   : public _Deque_alloc_base<_Tp,_Alloc,
  298.                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  299. {
  300. public:
  301.   typedef _Deque_alloc_base<_Tp,_Alloc,
  302.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  303.           _Base;
  304.   typedef typename _Base::allocator_type allocator_type;
  305.   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
  306.   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  307.  
  308.   _Deque_base(const allocator_type& __a, size_t __num_elements)
  309.     : _Base(__a), _M_start(), _M_finish()
  310.     { _M_initialize_map(__num_elements); }
  311.   _Deque_base(const allocator_type& __a) 
  312.     : _Base(__a), _M_start(), _M_finish() {}
  313.   ~_Deque_base();    
  314.  
  315. protected:
  316.   void _M_initialize_map(size_t);
  317.   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
  318.   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
  319.   enum { _S_initial_map_size = 8 };
  320.  
  321. protected:
  322.   iterator _M_start;
  323.   iterator _M_finish;
  324. };
  325.  
  326. #else /* __STL_USE_STD_ALLOCATORS */
  327.  
  328. template <class _Tp, class _Alloc>
  329. class _Deque_base {
  330. public:
  331.   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
  332.   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  333.  
  334.   typedef _Alloc allocator_type;
  335.   allocator_type get_allocator() const { return allocator_type(); }
  336.  
  337.   _Deque_base(const allocator_type&, size_t __num_elements)
  338.     : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {
  339.     _M_initialize_map(__num_elements);
  340.   }
  341.   _Deque_base(const allocator_type&)
  342.     : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {}
  343.   ~_Deque_base();    
  344.  
  345. protected:
  346.   void _M_initialize_map(size_t);
  347.   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
  348.   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
  349.   enum { _S_initial_map_size = 8 };
  350.  
  351. protected:
  352.   _Tp** _M_map;
  353.   size_t _M_map_size;  
  354.   iterator _M_start;
  355.   iterator _M_finish;
  356.  
  357.   typedef simple_alloc<_Tp, _Alloc>  _Node_alloc_type;
  358.   typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
  359.  
  360.   _Tp* _M_allocate_node()
  361.     { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
  362.   void _M_deallocate_node(_Tp* __p)
  363.     { _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
  364.   _Tp** _M_allocate_map(size_t __n) 
  365.     { return _Map_alloc_type::allocate(__n); }
  366.   void _M_deallocate_map(_Tp** __p, size_t __n) 
  367.     { _Map_alloc_type::deallocate(__p, __n); }
  368. };
  369.  
  370. #endif /* __STL_USE_STD_ALLOCATORS */
  371.  
  372. // Non-inline member functions from _Deque_base.
  373.  
  374. template <class _Tp, class _Alloc>
  375. _Deque_base<_Tp,_Alloc>::~_Deque_base() {
  376.   if (_M_map) {
  377.     _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
  378.     _M_deallocate_map(_M_map, _M_map_size);
  379.   }
  380. }
  381.  
  382. template <class _Tp, class _Alloc>
  383. void
  384. _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
  385. {
  386.   size_t __num_nodes = 
  387.     __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
  388.  
  389.   _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
  390.   _M_map = _M_allocate_map(_M_map_size);
  391.  
  392.   _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
  393.   _Tp** __nfinish = __nstart + __num_nodes;
  394.     
  395.   __STL_TRY {
  396.     _M_create_nodes(__nstart, __nfinish);
  397.   }
  398.   __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), 
  399.                 _M_map = 0, _M_map_size = 0));
  400.   _M_start._M_set_node(__nstart);
  401.   _M_finish._M_set_node(__nfinish - 1);
  402.   _M_start._M_cur = _M_start._M_first;
  403.   _M_finish._M_cur = _M_finish._M_first +
  404.                __num_elements % __deque_buf_size(sizeof(_Tp));
  405. }
  406.  
  407. template <class _Tp, class _Alloc>
  408. void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
  409. {
  410.   _Tp** __cur;
  411.   __STL_TRY {
  412.     for (__cur = __nstart; __cur < __nfinish; ++__cur)
  413.       *__cur = _M_allocate_node();
  414.   }
  415.   __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
  416. }
  417.  
  418. template <class _Tp, class _Alloc>
  419. void
  420. _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
  421. {
  422.   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
  423.     _M_deallocate_node(*__n);
  424. }
  425.  
  426. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  427. class deque : protected _Deque_base<_Tp, _Alloc> {
  428.  
  429.   // requirements:
  430.  
  431.   __STL_CLASS_REQUIRES(_Tp, _Assignable);
  432.  
  433.   typedef _Deque_base<_Tp, _Alloc> _Base;
  434. public:                         // Basic types
  435.   typedef _Tp value_type;
  436.   typedef value_type* pointer;
  437.   typedef const value_type* const_pointer;
  438.   typedef value_type& reference;
  439.   typedef const value_type& const_reference;
  440.   typedef size_t size_type;
  441.   typedef ptrdiff_t difference_type;
  442.  
  443.   typedef typename _Base::allocator_type allocator_type;
  444.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  445.  
  446. public:                         // Iterators
  447.   typedef typename _Base::iterator       iterator;
  448.   typedef typename _Base::const_iterator const_iterator;
  449.  
  450. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  451.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  452.   typedef reverse_iterator<iterator> reverse_iterator;
  453. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  454.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  455.                            difference_type>  
  456.           const_reverse_iterator;
  457.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  458.           reverse_iterator; 
  459. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  460.  
  461. protected:                      // Internal typedefs
  462.   typedef pointer* _Map_pointer;
  463.   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
  464.  
  465. protected:
  466. #ifdef __STL_USE_NAMESPACES
  467.   using _Base::_M_initialize_map;
  468.   using _Base::_M_create_nodes;
  469.   using _Base::_M_destroy_nodes;
  470.   using _Base::_M_allocate_node;
  471.   using _Base::_M_deallocate_node;
  472.   using _Base::_M_allocate_map;
  473.   using _Base::_M_deallocate_map;
  474.  
  475.   using _Base::_M_map;
  476.   using _Base::_M_map_size;
  477.   using _Base::_M_start;
  478.   using _Base::_M_finish;
  479. #endif /* __STL_USE_NAMESPACES */
  480.  
  481. public:                         // Basic accessors
  482.   iterator begin() { return _M_start; }
  483.   iterator end() { return _M_finish; }
  484.   const_iterator begin() const { return _M_start; }
  485.   const_iterator end() const { return _M_finish; }
  486.  
  487.   reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
  488.   reverse_iterator rend() { return reverse_iterator(_M_start); }
  489.   const_reverse_iterator rbegin() const 
  490.     { return const_reverse_iterator(_M_finish); }
  491.   const_reverse_iterator rend() const 
  492.     { return const_reverse_iterator(_M_start); }
  493.  
  494.   reference operator[](size_type __n)
  495.     { return _M_start[difference_type(__n)]; }
  496.   const_reference operator[](size_type __n) const 
  497.     { return _M_start[difference_type(__n)]; }
  498.  
  499. #ifdef __STL_THROW_RANGE_ERRORS
  500.   void _M_range_check(size_type __n) const {
  501.     if (__n >= this->size())
  502.       __stl_throw_range_error("deque");
  503.   }
  504.  
  505.   reference at(size_type __n)
  506.     { _M_range_check(__n); return (*this)[__n]; }
  507.   const_reference at(size_type __n) const
  508.     { _M_range_check(__n); return (*this)[__n]; }
  509. #endif /* __STL_THROW_RANGE_ERRORS */
  510.  
  511.   reference front() { return *_M_start; }
  512.   reference back() {
  513.     iterator __tmp = _M_finish;
  514.     --__tmp;
  515.     return *__tmp;
  516.   }
  517.   const_reference front() const { return *_M_start; }
  518.   const_reference back() const {
  519.     const_iterator __tmp = _M_finish;
  520.     --__tmp;
  521.     return *__tmp;
  522.   }
  523.  
  524.   size_type size() const { return _M_finish - _M_start; }
  525.   size_type max_size() const { return size_type(-1); }
  526.   bool empty() const { return _M_finish == _M_start; }
  527.  
  528. public:                         // Constructor, destructor.
  529.   explicit deque(const allocator_type& __a = allocator_type()) 
  530.     : _Base(__a, 0) {}
  531.   deque(const deque& __x) : _Base(__x.get_allocator(), __x.size()) 
  532.     { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
  533.   deque(size_type __n, const value_type& __value,
  534.         const allocator_type& __a = allocator_type()) : _Base(__a, __n)
  535.     { _M_fill_initialize(__value); }
  536.   explicit deque(size_type __n) : _Base(allocator_type(), __n)
  537.     { _M_fill_initialize(value_type()); }
  538.  
  539. #ifdef __STL_MEMBER_TEMPLATES
  540.  
  541.   // Check whether it's an integral type.  If so, it's not an iterator.
  542.   template <class _InputIterator>
  543.   deque(_InputIterator __first, _InputIterator __last,
  544.         const allocator_type& __a = allocator_type()) : _Base(__a) {
  545.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  546.     _M_initialize_dispatch(__first, __last, _Integral());
  547.   }
  548.  
  549.   template <class _Integer>
  550.   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
  551.     _M_initialize_map(__n);
  552.     _M_fill_initialize(__x);
  553.   }
  554.  
  555.   template <class _InputIter>
  556.   void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
  557.                               __false_type) {
  558.     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
  559.   }
  560.  
  561. #else /* __STL_MEMBER_TEMPLATES */
  562.  
  563.   deque(const value_type* __first, const value_type* __last,
  564.         const allocator_type& __a = allocator_type()) 
  565.     : _Base(__a, __last - __first)
  566.     { uninitialized_copy(__first, __last, _M_start); }
  567.   deque(const_iterator __first, const_iterator __last,
  568.         const allocator_type& __a = allocator_type()) 
  569.     : _Base(__a, __last - __first)
  570.     { uninitialized_copy(__first, __last, _M_start); }
  571.  
  572. #endif /* __STL_MEMBER_TEMPLATES */
  573.  
  574.   ~deque() { destroy(_M_start, _M_finish); }
  575.  
  576.   deque& operator= (const deque& __x) {
  577.     const size_type __len = size();
  578.     if (&__x != this) {
  579.       if (__len >= __x.size())
  580.         erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
  581.       else {
  582.         const_iterator __mid = __x.begin() + difference_type(__len);
  583.         copy(__x.begin(), __mid, _M_start);
  584.         insert(_M_finish, __mid, __x.end());
  585.       }
  586.     }
  587.     return *this;
  588.   }        
  589.  
  590.   void swap(deque& __x) {
  591.     __STD::swap(_M_start, __x._M_start);
  592.     __STD::swap(_M_finish, __x._M_finish);
  593.     __STD::swap(_M_map, __x._M_map);
  594.     __STD::swap(_M_map_size, __x._M_map_size);
  595.   }
  596.  
  597. public: 
  598.   // assign(), a generalized assignment member function.  Two
  599.   // versions: one that takes a count, and one that takes a range.
  600.   // The range version is a member template, so we dispatch on whether
  601.   // or not the type is an integer.
  602.  
  603.   void _M_fill_assign(size_type __n, const _Tp& __val) {
  604.     if (__n > size()) {
  605.       fill(begin(), end(), __val);
  606.       insert(end(), __n - size(), __val);
  607.     }
  608.     else {
  609.       erase(begin() + __n, end());
  610.       fill(begin(), end(), __val);
  611.     }
  612.   }
  613.  
  614.   void assign(size_type __n, const _Tp& __val) {
  615.     _M_fill_assign(__n, __val);
  616.   }
  617.  
  618. #ifdef __STL_MEMBER_TEMPLATES
  619.  
  620.   template <class _InputIterator>
  621.   void assign(_InputIterator __first, _InputIterator __last) {
  622.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  623.     _M_assign_dispatch(__first, __last, _Integral());
  624.   }
  625.  
  626. private:                        // helper functions for assign() 
  627.  
  628.   template <class _Integer>
  629.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  630.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  631.  
  632.   template <class _InputIterator>
  633.   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  634.                           __false_type) {
  635.     _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
  636.   }
  637.  
  638.   template <class _InputIterator>
  639.   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
  640.                      input_iterator_tag);
  641.  
  642.   template <class _ForwardIterator>
  643.   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  644.                      forward_iterator_tag) {
  645.     size_type __len = 0;
  646.     distance(__first, __last, __len);
  647.     if (__len > size()) {
  648.       _ForwardIterator __mid = __first;
  649.       advance(__mid, size());
  650.       copy(__first, __mid, begin());
  651.       insert(end(), __mid, __last);
  652.     }
  653.     else
  654.       erase(copy(__first, __last, begin()), end());
  655.   }
  656.  
  657. #endif /* __STL_MEMBER_TEMPLATES */
  658.  
  659. public:                         // push_* and pop_*
  660.   
  661.   void push_back(const value_type& __t) {
  662.     if (_M_finish._M_cur != _M_finish._M_last - 1) {
  663.       construct(_M_finish._M_cur, __t);
  664.       ++_M_finish._M_cur;
  665.     }
  666.     else
  667.       _M_push_back_aux(__t);
  668.   }
  669.  
  670.   void push_back() {
  671.     if (_M_finish._M_cur != _M_finish._M_last - 1) {
  672.       construct(_M_finish._M_cur);
  673.       ++_M_finish._M_cur;
  674.     }
  675.     else
  676.       _M_push_back_aux();
  677.   }
  678.  
  679.   void push_front(const value_type& __t) {
  680.     if (_M_start._M_cur != _M_start._M_first) {
  681.       construct(_M_start._M_cur - 1, __t);
  682.       --_M_start._M_cur;
  683.     }
  684.     else
  685.       _M_push_front_aux(__t);
  686.   }
  687.  
  688.   void push_front() {
  689.     if (_M_start._M_cur != _M_start._M_first) {
  690.       construct(_M_start._M_cur - 1);
  691.       --_M_start._M_cur;
  692.     }
  693.     else
  694.       _M_push_front_aux();
  695.   }
  696.  
  697.  
  698.   void pop_back() {
  699.     if (_M_finish._M_cur != _M_finish._M_first) {
  700.       --_M_finish._M_cur;
  701.       destroy(_M_finish._M_cur);
  702.     }
  703.     else
  704.       _M_pop_back_aux();
  705.   }
  706.  
  707.   void pop_front() {
  708.     if (_M_start._M_cur != _M_start._M_last - 1) {
  709.       destroy(_M_start._M_cur);
  710.       ++_M_start._M_cur;
  711.     }
  712.     else 
  713.       _M_pop_front_aux();
  714.   }
  715.  
  716. public:                         // Insert
  717.  
  718.   iterator insert(iterator position, const value_type& __x) {
  719.     if (position._M_cur == _M_start._M_cur) {
  720.       push_front(__x);
  721.       return _M_start;
  722.     }
  723.     else if (position._M_cur == _M_finish._M_cur) {
  724.       push_back(__x);
  725.       iterator __tmp = _M_finish;
  726.       --__tmp;
  727.       return __tmp;
  728.     }
  729.     else {
  730.       return _M_insert_aux(position, __x);
  731.     }
  732.   }
  733.  
  734.   iterator insert(iterator __position)
  735.     { return insert(__position, value_type()); }
  736.  
  737.   void insert(iterator __pos, size_type __n, const value_type& __x)
  738.     { _M_fill_insert(__pos, __n, __x); }
  739.  
  740.   void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 
  741.  
  742. #ifdef __STL_MEMBER_TEMPLATES  
  743.  
  744.   // Check whether it's an integral type.  If so, it's not an iterator.
  745.   template <class _InputIterator>
  746.   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
  747.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  748.     _M_insert_dispatch(__pos, __first, __last, _Integral());
  749.   }
  750.  
  751.   template <class _Integer>
  752.   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
  753.                           __true_type) {
  754.     _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
  755.   }
  756.  
  757.   template <class _InputIterator>
  758.   void _M_insert_dispatch(iterator __pos,
  759.                           _InputIterator __first, _InputIterator __last,
  760.                           __false_type) {
  761.     insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
  762.   }
  763.  
  764. #else /* __STL_MEMBER_TEMPLATES */
  765.  
  766.   void insert(iterator __pos,
  767.               const value_type* __first, const value_type* __last);
  768.   void insert(iterator __pos,
  769.               const_iterator __first, const_iterator __last);
  770.  
  771. #endif /* __STL_MEMBER_TEMPLATES */
  772.  
  773.   void resize(size_type __new_size, const value_type& __x) {
  774.     const size_type __len = size();
  775.     if (__new_size < __len) 
  776.       erase(_M_start + __new_size, _M_finish);
  777.     else
  778.       insert(_M_finish, __new_size - __len, __x);
  779.   }
  780.  
  781.   void resize(size_type new_size) { resize(new_size, value_type()); }
  782.  
  783. public:                         // Erase
  784.   iterator erase(iterator __pos) {
  785.     iterator __next = __pos;
  786.     ++__next;
  787.     difference_type __index = __pos - _M_start;
  788.     if (size_type(__index) < (this->size() >> 1)) {
  789.       copy_backward(_M_start, __pos, __next);
  790.       pop_front();
  791.     }
  792.     else {
  793.       copy(__next, _M_finish, __pos);
  794.       pop_back();
  795.     }
  796.     return _M_start + __index;
  797.   }
  798.  
  799.   iterator erase(iterator __first, iterator __last);
  800.   void clear(); 
  801.  
  802. protected:                        // Internal construction/destruction
  803.  
  804.   void _M_fill_initialize(const value_type& __value);
  805.  
  806. #ifdef __STL_MEMBER_TEMPLATES  
  807.  
  808.   template <class _InputIterator>
  809.   void _M_range_initialize(_InputIterator __first, _InputIterator __last,
  810.                         input_iterator_tag);
  811.  
  812.   template <class _ForwardIterator>
  813.   void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
  814.                         forward_iterator_tag);
  815.  
  816. #endif /* __STL_MEMBER_TEMPLATES */
  817.  
  818. protected:                        // Internal push_* and pop_*
  819.  
  820.   void _M_push_back_aux(const value_type&);
  821.   void _M_push_back_aux();
  822.   void _M_push_front_aux(const value_type&);
  823.   void _M_push_front_aux();
  824.   void _M_pop_back_aux();
  825.   void _M_pop_front_aux();
  826.  
  827. protected:                        // Internal insert functions
  828.  
  829. #ifdef __STL_MEMBER_TEMPLATES  
  830.  
  831.   template <class _InputIterator>
  832.   void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
  833.               input_iterator_tag);
  834.  
  835.   template <class _ForwardIterator>
  836.   void insert(iterator __pos,
  837.               _ForwardIterator __first, _ForwardIterator __last,
  838.               forward_iterator_tag);
  839.  
  840. #endif /* __STL_MEMBER_TEMPLATES */
  841.  
  842.   iterator _M_insert_aux(iterator __pos, const value_type& __x);
  843.   iterator _M_insert_aux(iterator __pos);
  844.   void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
  845.  
  846. #ifdef __STL_MEMBER_TEMPLATES  
  847.  
  848.   template <class _ForwardIterator>
  849.   void _M_insert_aux(iterator __pos, 
  850.                      _ForwardIterator __first, _ForwardIterator __last,
  851.                      size_type __n);
  852.  
  853. #else /* __STL_MEMBER_TEMPLATES */
  854.   
  855.   void _M_insert_aux(iterator __pos,
  856.                      const value_type* __first, const value_type* __last,
  857.                      size_type __n);
  858.  
  859.   void _M_insert_aux(iterator __pos, 
  860.                      const_iterator __first, const_iterator __last,
  861.                      size_type __n);
  862.  
  863. #endif /* __STL_MEMBER_TEMPLATES */
  864.  
  865.   iterator _M_reserve_elements_at_front(size_type __n) {
  866.     size_type __vacancies = _M_start._M_cur - _M_start._M_first;
  867.     if (__n > __vacancies) 
  868.       _M_new_elements_at_front(__n - __vacancies);
  869.     return _M_start - difference_type(__n);
  870.   }
  871.  
  872.   iterator _M_reserve_elements_at_back(size_type __n) {
  873.     size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
  874.     if (__n > __vacancies)
  875.       _M_new_elements_at_back(__n - __vacancies);
  876.     return _M_finish + difference_type(__n);
  877.   }
  878.  
  879.   void _M_new_elements_at_front(size_type __new_elements);
  880.   void _M_new_elements_at_back(size_type __new_elements);
  881.  
  882. protected:                      // Allocation of _M_map and nodes
  883.  
  884.   // Makes sure the _M_map has space for new nodes.  Does not actually
  885.   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently, 
  886.   //  deque iterators.)
  887.  
  888.   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
  889.     if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
  890.       _M_reallocate_map(__nodes_to_add, false);
  891.   }
  892.  
  893.   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
  894.     if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
  895.       _M_reallocate_map(__nodes_to_add, true);
  896.   }
  897.  
  898.   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
  899. };
  900.  
  901. // Non-inline member functions
  902.  
  903. #ifdef __STL_MEMBER_TEMPLATES
  904.  
  905. template <class _Tp, class _Alloc>
  906. template <class _InputIter>
  907. void deque<_Tp, _Alloc>
  908.   ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
  909. {
  910.   iterator __cur = begin();
  911.   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  912.     *__cur = *__first;
  913.   if (__first == __last)
  914.     erase(__cur, end());
  915.   else
  916.     insert(end(), __first, __last);
  917. }
  918.  
  919. #endif /* __STL_MEMBER_TEMPLATES */
  920.  
  921. template <class _Tp, class _Alloc>
  922. void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
  923.                                         size_type __n, const value_type& __x)
  924. {
  925.   if (__pos._M_cur == _M_start._M_cur) {
  926.     iterator __new_start = _M_reserve_elements_at_front(__n);
  927.     __STL_TRY {
  928.       uninitialized_fill(__new_start, _M_start, __x);
  929.       _M_start = __new_start;
  930.     }
  931.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  932.   }
  933.   else if (__pos._M_cur == _M_finish._M_cur) {
  934.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  935.     __STL_TRY {
  936.       uninitialized_fill(_M_finish, __new_finish, __x);
  937.       _M_finish = __new_finish;
  938.     }
  939.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  940.                                   __new_finish._M_node + 1));    
  941.   }
  942.   else 
  943.     _M_insert_aux(__pos, __n, __x);
  944. }
  945.  
  946. #ifndef __STL_MEMBER_TEMPLATES  
  947.  
  948. template <class _Tp, class _Alloc>
  949. void deque<_Tp, _Alloc>::insert(iterator __pos,
  950.                                 const value_type* __first,
  951.                                 const value_type* __last) {
  952.   size_type __n = __last - __first;
  953.   if (__pos._M_cur == _M_start._M_cur) {
  954.     iterator __new_start = _M_reserve_elements_at_front(__n);
  955.     __STL_TRY {
  956.       uninitialized_copy(__first, __last, __new_start);
  957.       _M_start = __new_start;
  958.     }
  959.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  960.   }
  961.   else if (__pos._M_cur == _M_finish._M_cur) {
  962.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  963.     __STL_TRY {
  964.       uninitialized_copy(__first, __last, _M_finish);
  965.       _M_finish = __new_finish;
  966.     }
  967.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  968.                                   __new_finish._M_node + 1));
  969.   }
  970.   else
  971.     _M_insert_aux(__pos, __first, __last, __n);
  972. }
  973.  
  974. template <class _Tp, class _Alloc>
  975. void deque<_Tp,_Alloc>::insert(iterator __pos,
  976.                                const_iterator __first, const_iterator __last)
  977. {
  978.   size_type __n = __last - __first;
  979.   if (__pos._M_cur == _M_start._M_cur) {
  980.     iterator __new_start = _M_reserve_elements_at_front(__n);
  981.     __STL_TRY {
  982.       uninitialized_copy(__first, __last, __new_start);
  983.       _M_start = __new_start;
  984.     }
  985.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  986.   }
  987.   else if (__pos._M_cur == _M_finish._M_cur) {
  988.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  989.     __STL_TRY {
  990.       uninitialized_copy(__first, __last, _M_finish);
  991.       _M_finish = __new_finish;
  992.     }
  993.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  994.                  __new_finish._M_node + 1));
  995.   }
  996.   else
  997.     _M_insert_aux(__pos, __first, __last, __n);
  998. }
  999.  
  1000. #endif /* __STL_MEMBER_TEMPLATES */
  1001.  
  1002. template <class _Tp, class _Alloc>
  1003. typename deque<_Tp,_Alloc>::iterator 
  1004. deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
  1005. {
  1006.   if (__first == _M_start && __last == _M_finish) {
  1007.     clear();
  1008.     return _M_finish;
  1009.   }
  1010.   else {
  1011.     difference_type __n = __last - __first;
  1012.     difference_type __elems_before = __first - _M_start;
  1013.     if (__elems_before < difference_type((this->size() - __n) / 2)) {
  1014.       copy_backward(_M_start, __first, __last);
  1015.       iterator __new_start = _M_start + __n;
  1016.       destroy(_M_start, __new_start);
  1017.       _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
  1018.       _M_start = __new_start;
  1019.     }
  1020.     else {
  1021.       copy(__last, _M_finish, __first);
  1022.       iterator __new_finish = _M_finish - __n;
  1023.       destroy(__new_finish, _M_finish);
  1024.       _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
  1025.       _M_finish = __new_finish;
  1026.     }
  1027.     return _M_start + __elems_before;
  1028.   }
  1029. }
  1030.  
  1031. template <class _Tp, class _Alloc> 
  1032. void deque<_Tp,_Alloc>::clear()
  1033. {
  1034.   for (_Map_pointer __node = _M_start._M_node + 1;
  1035.        __node < _M_finish._M_node;
  1036.        ++__node) {
  1037.     destroy(*__node, *__node + _S_buffer_size());
  1038.     _M_deallocate_node(*__node);
  1039.   }
  1040.  
  1041.   if (_M_start._M_node != _M_finish._M_node) {
  1042.     destroy(_M_start._M_cur, _M_start._M_last);
  1043.     destroy(_M_finish._M_first, _M_finish._M_cur);
  1044.     _M_deallocate_node(_M_finish._M_first);
  1045.   }
  1046.   else
  1047.     destroy(_M_start._M_cur, _M_finish._M_cur);
  1048.  
  1049.   _M_finish = _M_start;
  1050. }
  1051.  
  1052. // Precondition: _M_start and _M_finish have already been initialized,
  1053. // but none of the deque's elements have yet been constructed.
  1054. template <class _Tp, class _Alloc>
  1055. void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) {
  1056.   _Map_pointer __cur;
  1057.   __STL_TRY {
  1058.     for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
  1059.       uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
  1060.     uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
  1061.   }
  1062.   __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
  1063. }
  1064.  
  1065. #ifdef __STL_MEMBER_TEMPLATES  
  1066.  
  1067. template <class _Tp, class _Alloc> template <class _InputIterator>
  1068. void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
  1069.                                             _InputIterator __last,
  1070.                                             input_iterator_tag)
  1071. {
  1072.   _M_initialize_map(0);
  1073.   __STL_TRY {
  1074.     for ( ; __first != __last; ++__first)
  1075.       push_back(*__first);
  1076.   }
  1077.   __STL_UNWIND(clear());
  1078. }
  1079.  
  1080. template <class _Tp, class _Alloc> template <class _ForwardIterator>
  1081. void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
  1082.                                             _ForwardIterator __last,
  1083.                                             forward_iterator_tag)
  1084. {
  1085.   size_type __n = 0;
  1086.   distance(__first, __last, __n);
  1087.   _M_initialize_map(__n);
  1088.  
  1089.   _Map_pointer __cur_node;
  1090.   __STL_TRY {
  1091.     for (__cur_node = _M_start._M_node; 
  1092.          __cur_node < _M_finish._M_node; 
  1093.          ++__cur_node) {
  1094.       _ForwardIterator __mid = __first;
  1095.       advance(__mid, _S_buffer_size());
  1096.       uninitialized_copy(__first, __mid, *__cur_node);
  1097.       __first = __mid;
  1098.     }
  1099.     uninitialized_copy(__first, __last, _M_finish._M_first);
  1100.   }
  1101.   __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
  1102. }
  1103.  
  1104. #endif /* __STL_MEMBER_TEMPLATES */
  1105.  
  1106. // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
  1107. template <class _Tp, class _Alloc>
  1108. void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
  1109. {
  1110.   value_type __t_copy = __t;
  1111.   _M_reserve_map_at_back();
  1112.   *(_M_finish._M_node + 1) = _M_allocate_node();
  1113.   __STL_TRY {
  1114.     construct(_M_finish._M_cur, __t_copy);
  1115.     _M_finish._M_set_node(_M_finish._M_node + 1);
  1116.     _M_finish._M_cur = _M_finish._M_first;
  1117.   }
  1118.   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
  1119. }
  1120.  
  1121. // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
  1122. template <class _Tp, class _Alloc>
  1123. void deque<_Tp,_Alloc>::_M_push_back_aux()
  1124. {
  1125.   _M_reserve_map_at_back();
  1126.   *(_M_finish._M_node + 1) = _M_allocate_node();
  1127.   __STL_TRY {
  1128.     construct(_M_finish._M_cur);
  1129.     _M_finish._M_set_node(_M_finish._M_node + 1);
  1130.     _M_finish._M_cur = _M_finish._M_first;
  1131.   }
  1132.   __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
  1133. }
  1134.  
  1135. // Called only if _M_start._M_cur == _M_start._M_first.
  1136. template <class _Tp, class _Alloc>
  1137. void  deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
  1138. {
  1139.   value_type __t_copy = __t;
  1140.   _M_reserve_map_at_front();
  1141.   *(_M_start._M_node - 1) = _M_allocate_node();
  1142.   __STL_TRY {
  1143.     _M_start._M_set_node(_M_start._M_node - 1);
  1144.     _M_start._M_cur = _M_start._M_last - 1;
  1145.     construct(_M_start._M_cur, __t_copy);
  1146.   }
  1147.   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
  1148. } 
  1149.  
  1150. // Called only if _M_start._M_cur == _M_start._M_first.
  1151. template <class _Tp, class _Alloc>
  1152. void deque<_Tp,_Alloc>::_M_push_front_aux()
  1153. {
  1154.   _M_reserve_map_at_front();
  1155.   *(_M_start._M_node - 1) = _M_allocate_node();
  1156.   __STL_TRY {
  1157.     _M_start._M_set_node(_M_start._M_node - 1);
  1158.     _M_start._M_cur = _M_start._M_last - 1;
  1159.     construct(_M_start._M_cur);
  1160.   }
  1161.   __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
  1162. } 
  1163.  
  1164. // Called only if _M_finish._M_cur == _M_finish._M_first.
  1165. template <class _Tp, class _Alloc>
  1166. void deque<_Tp,_Alloc>::_M_pop_back_aux()
  1167. {
  1168.   _M_deallocate_node(_M_finish._M_first);
  1169.   _M_finish._M_set_node(_M_finish._M_node - 1);
  1170.   _M_finish._M_cur = _M_finish._M_last - 1;
  1171.   destroy(_M_finish._M_cur);
  1172. }
  1173.  
  1174. // Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that 
  1175. // if the deque has at least one element (a precondition for this member 
  1176. // function), and if _M_start._M_cur == _M_start._M_last, then the deque 
  1177. // must have at least two nodes.
  1178. template <class _Tp, class _Alloc>
  1179. void deque<_Tp,_Alloc>::_M_pop_front_aux()
  1180. {
  1181.   destroy(_M_start._M_cur);
  1182.   _M_deallocate_node(_M_start._M_first);
  1183.   _M_start._M_set_node(_M_start._M_node + 1);
  1184.   _M_start._M_cur = _M_start._M_first;
  1185. }      
  1186.  
  1187. #ifdef __STL_MEMBER_TEMPLATES  
  1188.  
  1189. template <class _Tp, class _Alloc> template <class _InputIterator>
  1190. void deque<_Tp,_Alloc>::insert(iterator __pos,
  1191.                                _InputIterator __first, _InputIterator __last,
  1192.                                input_iterator_tag)
  1193. {
  1194.   copy(__first, __last, inserter(*this, __pos));
  1195. }
  1196.  
  1197. template <class _Tp, class _Alloc> template <class _ForwardIterator>
  1198. void
  1199. deque<_Tp,_Alloc>::insert(iterator __pos,
  1200.                           _ForwardIterator __first, _ForwardIterator __last,
  1201.                           forward_iterator_tag) {
  1202.   size_type __n = 0;
  1203.   distance(__first, __last, __n);
  1204.   if (__pos._M_cur == _M_start._M_cur) {
  1205.     iterator __new_start = _M_reserve_elements_at_front(__n);
  1206.     __STL_TRY {
  1207.       uninitialized_copy(__first, __last, __new_start);
  1208.       _M_start = __new_start;
  1209.     }
  1210.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  1211.   }
  1212.   else if (__pos._M_cur == _M_finish._M_cur) {
  1213.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  1214.     __STL_TRY {
  1215.       uninitialized_copy(__first, __last, _M_finish);
  1216.       _M_finish = __new_finish;
  1217.     }
  1218.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  1219.                                   __new_finish._M_node + 1));
  1220.   }
  1221.   else
  1222.     _M_insert_aux(__pos, __first, __last, __n);
  1223. }
  1224.  
  1225. #endif /* __STL_MEMBER_TEMPLATES */
  1226.  
  1227. template <class _Tp, class _Alloc>
  1228. typename deque<_Tp, _Alloc>::iterator
  1229. deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
  1230. {
  1231.   difference_type __index = __pos - _M_start;
  1232.   value_type __x_copy = __x;
  1233.   if (size_type(__index) < this->size() / 2) {
  1234.     push_front(front());
  1235.     iterator __front1 = _M_start;
  1236.     ++__front1;
  1237.     iterator __front2 = __front1;
  1238.     ++__front2;
  1239.     __pos = _M_start + __index;
  1240.     iterator __pos1 = __pos;
  1241.     ++__pos1;
  1242.     copy(__front2, __pos1, __front1);
  1243.   }
  1244.   else {
  1245.     push_back(back());
  1246.     iterator __back1 = _M_finish;
  1247.     --__back1;
  1248.     iterator __back2 = __back1;
  1249.     --__back2;
  1250.     __pos = _M_start + __index;
  1251.     copy_backward(__pos, __back2, __back1);
  1252.   }
  1253.   *__pos = __x_copy;
  1254.   return __pos;
  1255. }
  1256.  
  1257. template <class _Tp, class _Alloc>
  1258. typename deque<_Tp,_Alloc>::iterator 
  1259. deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
  1260. {
  1261.   difference_type __index = __pos - _M_start;
  1262.   if (__index < size() / 2) {
  1263.     push_front(front());
  1264.     iterator __front1 = _M_start;
  1265.     ++__front1;
  1266.     iterator __front2 = __front1;
  1267.     ++__front2;
  1268.     __pos = _M_start + __index;
  1269.     iterator __pos1 = __pos;
  1270.     ++__pos1;
  1271.     copy(__front2, __pos1, __front1);
  1272.   }
  1273.   else {
  1274.     push_back(back());
  1275.     iterator __back1 = _M_finish;
  1276.     --__back1;
  1277.     iterator __back2 = __back1;
  1278.     --__back2;
  1279.     __pos = _M_start + __index;
  1280.     copy_backward(__pos, __back2, __back1);
  1281.   }
  1282.   *__pos = value_type();
  1283.   return __pos;
  1284. }
  1285.  
  1286. template <class _Tp, class _Alloc>
  1287. void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  1288.                                       size_type __n,
  1289.                                       const value_type& __x)
  1290. {
  1291.   const difference_type __elems_before = __pos - _M_start;
  1292.   size_type __length = this->size();
  1293.   value_type __x_copy = __x;
  1294.   if (__elems_before < difference_type(__length / 2)) {
  1295.     iterator __new_start = _M_reserve_elements_at_front(__n);
  1296.     iterator __old_start = _M_start;
  1297.     __pos = _M_start + __elems_before;
  1298.     __STL_TRY {
  1299.       if (__elems_before >= difference_type(__n)) {
  1300.         iterator __start_n = _M_start + difference_type(__n);
  1301.         uninitialized_copy(_M_start, __start_n, __new_start);
  1302.         _M_start = __new_start;
  1303.         copy(__start_n, __pos, __old_start);
  1304.         fill(__pos - difference_type(__n), __pos, __x_copy);
  1305.       }
  1306.       else {
  1307.         __uninitialized_copy_fill(_M_start, __pos, __new_start, 
  1308.                                   _M_start, __x_copy);
  1309.         _M_start = __new_start;
  1310.         fill(__old_start, __pos, __x_copy);
  1311.       }
  1312.     }
  1313.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  1314.   }
  1315.   else {
  1316.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  1317.     iterator __old_finish = _M_finish;
  1318.     const difference_type __elems_after = 
  1319.       difference_type(__length) - __elems_before;
  1320.     __pos = _M_finish - __elems_after;
  1321.     __STL_TRY {
  1322.       if (__elems_after > difference_type(__n)) {
  1323.         iterator __finish_n = _M_finish - difference_type(__n);
  1324.         uninitialized_copy(__finish_n, _M_finish, _M_finish);
  1325.         _M_finish = __new_finish;
  1326.         copy_backward(__pos, __finish_n, __old_finish);
  1327.         fill(__pos, __pos + difference_type(__n), __x_copy);
  1328.       }
  1329.       else {
  1330.         __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
  1331.                                   __x_copy, __pos, _M_finish);
  1332.         _M_finish = __new_finish;
  1333.         fill(__pos, __old_finish, __x_copy);
  1334.       }
  1335.     }
  1336.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  1337.                                   __new_finish._M_node + 1));
  1338.   }
  1339. }
  1340.  
  1341. #ifdef __STL_MEMBER_TEMPLATES  
  1342.  
  1343. template <class _Tp, class _Alloc> template <class _ForwardIterator>
  1344. void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  1345.                                       _ForwardIterator __first,
  1346.                                       _ForwardIterator __last,
  1347.                                       size_type __n)
  1348. {
  1349.   const difference_type __elemsbefore = __pos - _M_start;
  1350.   size_type __length = size();
  1351.   if (__elemsbefore < __length / 2) {
  1352.     iterator __new_start = _M_reserve_elements_at_front(__n);
  1353.     iterator __old_start = _M_start;
  1354.     __pos = _M_start + __elemsbefore;
  1355.     __STL_TRY {
  1356.       if (__elemsbefore >= difference_type(__n)) {
  1357.         iterator __start_n = _M_start + difference_type(__n); 
  1358.         uninitialized_copy(_M_start, __start_n, __new_start);
  1359.         _M_start = __new_start;
  1360.         copy(__start_n, __pos, __old_start);
  1361.         copy(__first, __last, __pos - difference_type(__n));
  1362.       }
  1363.       else {
  1364.         _ForwardIterator __mid = __first;
  1365.         advance(__mid, difference_type(__n) - __elemsbefore);
  1366.         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
  1367.                                   __new_start);
  1368.         _M_start = __new_start;
  1369.         copy(__mid, __last, __old_start);
  1370.       }
  1371.     }
  1372.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  1373.   }
  1374.   else {
  1375.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  1376.     iterator __old_finish = _M_finish;
  1377.     const difference_type __elemsafter = 
  1378.       difference_type(__length) - __elemsbefore;
  1379.     __pos = _M_finish - __elemsafter;
  1380.     __STL_TRY {
  1381.       if (__elemsafter > difference_type(__n)) {
  1382.         iterator __finish_n = _M_finish - difference_type(__n);
  1383.         uninitialized_copy(__finish_n, _M_finish, _M_finish);
  1384.         _M_finish = __new_finish;
  1385.         copy_backward(__pos, __finish_n, __old_finish);
  1386.         copy(__first, __last, __pos);
  1387.       }
  1388.       else {
  1389.         _ForwardIterator __mid = __first;
  1390.         advance(__mid, __elemsafter);
  1391.         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
  1392.         _M_finish = __new_finish;
  1393.         copy(__first, __mid, __pos);
  1394.       }
  1395.     }
  1396.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  1397.                                   __new_finish._M_node + 1));
  1398.   }
  1399. }
  1400.  
  1401. #else /* __STL_MEMBER_TEMPLATES */
  1402.  
  1403. template <class _Tp, class _Alloc>
  1404. void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  1405.                                       const value_type* __first,
  1406.                                       const value_type* __last,
  1407.                                       size_type __n)
  1408. {
  1409.   const difference_type __elemsbefore = __pos - _M_start;
  1410.   size_type __length = size();
  1411.   if (__elemsbefore < __length / 2) {
  1412.     iterator __new_start = _M_reserve_elements_at_front(__n);
  1413.     iterator __old_start = _M_start;
  1414.     __pos = _M_start + __elemsbefore;
  1415.     __STL_TRY {
  1416.       if (__elemsbefore >= difference_type(__n)) {
  1417.         iterator __start_n = _M_start + difference_type(__n);
  1418.         uninitialized_copy(_M_start, __start_n, __new_start);
  1419.         _M_start = __new_start;
  1420.         copy(__start_n, __pos, __old_start);
  1421.         copy(__first, __last, __pos - difference_type(__n));
  1422.       }
  1423.       else {
  1424.         const value_type* __mid = 
  1425.           __first + (difference_type(__n) - __elemsbefore);
  1426.         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
  1427.                                   __new_start);
  1428.         _M_start = __new_start;
  1429.         copy(__mid, __last, __old_start);
  1430.       }
  1431.     }
  1432.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  1433.   }
  1434.   else {
  1435.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  1436.     iterator __old_finish = _M_finish;
  1437.     const difference_type __elemsafter = 
  1438.       difference_type(__length) - __elemsbefore;
  1439.     __pos = _M_finish - __elemsafter;
  1440.     __STL_TRY {
  1441.       if (__elemsafter > difference_type(__n)) {
  1442.         iterator __finish_n = _M_finish - difference_type(__n);
  1443.         uninitialized_copy(__finish_n, _M_finish, _M_finish);
  1444.         _M_finish = __new_finish;
  1445.         copy_backward(__pos, __finish_n, __old_finish);
  1446.         copy(__first, __last, __pos);
  1447.       }
  1448.       else {
  1449.         const value_type* __mid = __first + __elemsafter;
  1450.         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
  1451.         _M_finish = __new_finish;
  1452.         copy(__first, __mid, __pos);
  1453.       }
  1454.     }
  1455.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  1456.                                   __new_finish._M_node + 1));
  1457.   }
  1458. }
  1459.  
  1460. template <class _Tp, class _Alloc>
  1461. void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  1462.                                       const_iterator __first,
  1463.                                       const_iterator __last,
  1464.                                       size_type __n)
  1465. {
  1466.   const difference_type __elemsbefore = __pos - _M_start;
  1467.   size_type __length = size();
  1468.   if (__elemsbefore < __length / 2) {
  1469.     iterator __new_start = _M_reserve_elements_at_front(__n);
  1470.     iterator __old_start = _M_start;
  1471.     __pos = _M_start + __elemsbefore;
  1472.     __STL_TRY {
  1473.       if (__elemsbefore >= __n) {
  1474.         iterator __start_n = _M_start + __n;
  1475.         uninitialized_copy(_M_start, __start_n, __new_start);
  1476.         _M_start = __new_start;
  1477.         copy(__start_n, __pos, __old_start);
  1478.         copy(__first, __last, __pos - difference_type(__n));
  1479.       }
  1480.       else {
  1481.         const_iterator __mid = __first + (__n - __elemsbefore);
  1482.         __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
  1483.                                   __new_start);
  1484.         _M_start = __new_start;
  1485.         copy(__mid, __last, __old_start);
  1486.       }
  1487.     }
  1488.     __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
  1489.   }
  1490.   else {
  1491.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  1492.     iterator __old_finish = _M_finish;
  1493.     const difference_type __elemsafter = __length - __elemsbefore;
  1494.     __pos = _M_finish - __elemsafter;
  1495.     __STL_TRY {
  1496.       if (__elemsafter > __n) {
  1497.         iterator __finish_n = _M_finish - difference_type(__n);
  1498.         uninitialized_copy(__finish_n, _M_finish, _M_finish);
  1499.         _M_finish = __new_finish;
  1500.         copy_backward(__pos, __finish_n, __old_finish);
  1501.         copy(__first, __last, __pos);
  1502.       }
  1503.       else {
  1504.         const_iterator __mid = __first + __elemsafter;
  1505.         __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
  1506.         _M_finish = __new_finish;
  1507.         copy(__first, __mid, __pos);
  1508.       }
  1509.     }
  1510.     __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 
  1511.                  __new_finish._M_node + 1));
  1512.   }
  1513. }
  1514.  
  1515. #endif /* __STL_MEMBER_TEMPLATES */
  1516.  
  1517. template <class _Tp, class _Alloc>
  1518. void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
  1519. {
  1520.   size_type __new_nodes
  1521.       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
  1522.   _M_reserve_map_at_front(__new_nodes);
  1523.   size_type __i;
  1524.   __STL_TRY {
  1525.     for (__i = 1; __i <= __new_nodes; ++__i)
  1526.       *(_M_start._M_node - __i) = _M_allocate_node();
  1527.   }
  1528. #       ifdef __STL_USE_EXCEPTIONS
  1529.   catch(...) {
  1530.     for (size_type __j = 1; __j < __i; ++__j)
  1531.       _M_deallocate_node(*(_M_start._M_node - __j));      
  1532.     throw;
  1533.   }
  1534. #       endif /* __STL_USE_EXCEPTIONS */
  1535. }
  1536.  
  1537. template <class _Tp, class _Alloc>
  1538. void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
  1539. {
  1540.   size_type __new_nodes
  1541.       = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
  1542.   _M_reserve_map_at_back(__new_nodes);
  1543.   size_type __i;
  1544.   __STL_TRY {
  1545.     for (__i = 1; __i <= __new_nodes; ++__i)
  1546.       *(_M_finish._M_node + __i) = _M_allocate_node();
  1547.   }
  1548. #       ifdef __STL_USE_EXCEPTIONS
  1549.   catch(...) {
  1550.     for (size_type __j = 1; __j < __i; ++__j)
  1551.       _M_deallocate_node(*(_M_finish._M_node + __j));      
  1552.     throw;
  1553.   }
  1554. #       endif /* __STL_USE_EXCEPTIONS */
  1555. }
  1556.  
  1557. template <class _Tp, class _Alloc>
  1558. void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
  1559.                                           bool __add_at_front)
  1560. {
  1561.   size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
  1562.   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
  1563.  
  1564.   _Map_pointer __new_nstart;
  1565.   if (_M_map_size > 2 * __new_num_nodes) {
  1566.     __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 
  1567.                      + (__add_at_front ? __nodes_to_add : 0);
  1568.     if (__new_nstart < _M_start._M_node)
  1569.       copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
  1570.     else
  1571.       copy_backward(_M_start._M_node, _M_finish._M_node + 1, 
  1572.                     __new_nstart + __old_num_nodes);
  1573.   }
  1574.   else {
  1575.     size_type __new_map_size = 
  1576.       _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
  1577.  
  1578.     _Map_pointer __new_map = _M_allocate_map(__new_map_size);
  1579.     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
  1580.                          + (__add_at_front ? __nodes_to_add : 0);
  1581.     copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
  1582.     _M_deallocate_map(_M_map, _M_map_size);
  1583.  
  1584.     _M_map = __new_map;
  1585.     _M_map_size = __new_map_size;
  1586.   }
  1587.  
  1588.   _M_start._M_set_node(__new_nstart);
  1589.   _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
  1590. }
  1591.  
  1592.  
  1593. // Nonmember functions.
  1594.  
  1595. template <class _Tp, class _Alloc>
  1596. inline bool operator==(const deque<_Tp, _Alloc>& __x,
  1597.                        const deque<_Tp, _Alloc>& __y) {
  1598.   return __x.size() == __y.size() &&
  1599.          equal(__x.begin(), __x.end(), __y.begin());
  1600. }
  1601.  
  1602. template <class _Tp, class _Alloc>
  1603. inline bool operator<(const deque<_Tp, _Alloc>& __x,
  1604.                       const deque<_Tp, _Alloc>& __y) {
  1605.   return lexicographical_compare(__x.begin(), __x.end(), 
  1606.                                  __y.begin(), __y.end());
  1607. }
  1608.  
  1609. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  1610.  
  1611. template <class _Tp, class _Alloc>
  1612. inline bool operator!=(const deque<_Tp, _Alloc>& __x,
  1613.                        const deque<_Tp, _Alloc>& __y) {
  1614.   return !(__x == __y);
  1615. }
  1616.  
  1617. template <class _Tp, class _Alloc>
  1618. inline bool operator>(const deque<_Tp, _Alloc>& __x,
  1619.                       const deque<_Tp, _Alloc>& __y) {
  1620.   return __y < __x;
  1621. }
  1622.  
  1623. template <class _Tp, class _Alloc>
  1624. inline bool operator<=(const deque<_Tp, _Alloc>& __x,
  1625.                        const deque<_Tp, _Alloc>& __y) {
  1626.   return !(__y < __x);
  1627. }
  1628. template <class _Tp, class _Alloc>
  1629. inline bool operator>=(const deque<_Tp, _Alloc>& __x,
  1630.                        const deque<_Tp, _Alloc>& __y) {
  1631.   return !(__x < __y);
  1632. }
  1633.  
  1634. template <class _Tp, class _Alloc>
  1635. inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
  1636.   __x.swap(__y);
  1637. }
  1638.  
  1639. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  1640.  
  1641. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  1642. #pragma reset woff 1174
  1643. #pragma reset woff 1375
  1644. #endif
  1645.           
  1646. __STL_END_NAMESPACE 
  1647.   
  1648. #endif /* __SGI_STL_INTERNAL_DEQUE_H */
  1649.  
  1650. // Local Variables:
  1651. // mode:C++
  1652. // End:
  1653.