stl_dequ.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:52k
源码类别:

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