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