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