OSDN Git Service

31126775ad034d5d4909215a2ca7131f3343d8cc
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_deque.h
1 // Deque implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004 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 #ifndef _DEQUE_H
62 #define _DEQUE_H 1
63
64 #include <bits/concept_check.h>
65 #include <bits/stl_iterator_base_types.h>
66 #include <bits/stl_iterator_base_funcs.h>
67
68 namespace __gnu_norm
69 {
70   /**
71    *  @if maint
72    *  @brief This function controls the size of memory nodes.
73    *  @param  size  The size of an element.
74    *  @return   The number (not byte size) of elements per node.
75    *
76    *  This function started off as a compiler kludge from SGI, but seems to
77    *  be a useful wrapper around a repeated constant expression.  The '512' is
78    *  tuneable (and no other code needs to change), but no investigation has
79    *  been done since inheriting the SGI code.
80    *  @endif
81   */
82   inline size_t
83   __deque_buf_size(size_t __size)
84   { return __size < 512 ? size_t(512 / __size) : size_t(1); }
85
86
87   /**
88    *  @brief A deque::iterator.
89    *
90    *  Quite a bit of intelligence here.  Much of the functionality of deque is
91    *  actually passed off to this class.  A deque holds two of these internally,
92    *  marking its valid range.  Access to elements is done as offsets of either
93    *  of those two, relying on operator overloading in this class.
94    *
95    *  @if maint
96    *  All the functions are op overloads except for _M_set_node.
97    *  @endif
98   */
99   template<typename _Tp, typename _Ref, typename _Ptr>
100     struct _Deque_iterator
101     {
102       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
103       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
104
105       static size_t _S_buffer_size()
106       { 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
126       _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
127
128       _Deque_iterator(const iterator& __x)
129       : _M_cur(__x._M_cur), _M_first(__x._M_first),
130         _M_last(__x._M_last), _M_node(__x._M_node) {}
131
132       reference
133       operator*() const
134       { return *_M_cur; }
135
136       pointer
137       operator->() const
138       { return _M_cur; }
139
140       _Self&
141       operator++()
142       {
143         ++_M_cur;
144         if (_M_cur == _M_last)
145           {
146             _M_set_node(_M_node + 1);
147             _M_cur = _M_first;
148           }
149         return *this;
150       }
151
152       _Self
153       operator++(int)
154       {
155         _Self __tmp = *this;
156         ++*this;
157         return __tmp;
158       }
159
160       _Self&
161       operator--()
162       {
163         if (_M_cur == _M_first)
164           {
165             _M_set_node(_M_node - 1);
166             _M_cur = _M_last;
167           }
168         --_M_cur;
169         return *this;
170       }
171
172       _Self
173       operator--(int)
174       {
175         _Self __tmp = *this;
176         --*this;
177         return __tmp;
178       }
179
180       _Self&
181       operator+=(difference_type __n)
182       {
183         const difference_type __offset = __n + (_M_cur - _M_first);
184         if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
185           _M_cur += __n;
186         else
187           {
188             const difference_type __node_offset =
189               __offset > 0 ? __offset / difference_type(_S_buffer_size())
190                            : -difference_type((-__offset - 1)
191                                               / _S_buffer_size()) - 1;
192             _M_set_node(_M_node + __node_offset);
193             _M_cur = _M_first + (__offset - __node_offset
194                                  * difference_type(_S_buffer_size()));
195           }
196         return *this;
197       }
198
199       _Self
200       operator+(difference_type __n) const
201       {
202         _Self __tmp = *this;
203         return __tmp += __n;
204       }
205
206       _Self&
207       operator-=(difference_type __n)
208       { return *this += -__n; }
209
210       _Self
211       operator-(difference_type __n) const
212       {
213         _Self __tmp = *this;
214         return __tmp -= __n;
215       }
216
217       reference
218       operator[](difference_type __n) const
219       { return *(*this + __n); }
220
221       /** @if maint
222        *  Prepares to traverse new_node.  Sets everything except _M_cur, which
223        *  should therefore be set by the caller immediately afterwards, based on
224        *  _M_first and _M_last.
225        *  @endif
226        */
227       void
228       _M_set_node(_Map_pointer __new_node)
229       {
230         _M_node = __new_node;
231         _M_first = *__new_node;
232         _M_last = _M_first + difference_type(_S_buffer_size());
233       }
234     };
235
236   // Note: we also provide overloads whose operands are of the same type in
237   // order to avoid ambiguous overload resolution when std::rel_ops operators
238   // are in scope (for additional details, see libstdc++/3628)
239   template<typename _Tp, typename _Ref, typename _Ptr>
240     inline bool
241     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
242                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
243     { return __x._M_cur == __y._M_cur; }
244
245   template<typename _Tp, typename _RefL, typename _PtrL,
246            typename _RefR, typename _PtrR>
247     inline bool
248     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
249                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
250     { return __x._M_cur == __y._M_cur; }
251
252   template<typename _Tp, typename _Ref, typename _Ptr>
253     inline bool
254     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
255                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
256     { return !(__x == __y); }
257
258   template<typename _Tp, typename _RefL, typename _PtrL,
259            typename _RefR, typename _PtrR>
260     inline bool
261     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
262                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
263     { return !(__x == __y); }
264
265   template<typename _Tp, typename _Ref, typename _Ptr>
266     inline bool
267     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
268               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
269     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
270                                           : (__x._M_node < __y._M_node); }
271
272   template<typename _Tp, typename _RefL, typename _PtrL,
273            typename _RefR, typename _PtrR>
274     inline bool
275     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
276               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
277     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
278                                           : (__x._M_node < __y._M_node); }
279
280   template<typename _Tp, typename _Ref, typename _Ptr>
281     inline bool
282     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
283               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
284     { return __y < __x; }
285
286   template<typename _Tp, typename _RefL, typename _PtrL,
287            typename _RefR, typename _PtrR>
288     inline bool
289     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
290               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
291     { return __y < __x; }
292
293   template<typename _Tp, typename _Ref, typename _Ptr>
294     inline bool
295     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
296                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
297     { return !(__y < __x); }
298
299   template<typename _Tp, typename _RefL, typename _PtrL,
300            typename _RefR, typename _PtrR>
301     inline bool
302     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
303                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
304     { return !(__y < __x); }
305
306   template<typename _Tp, typename _Ref, typename _Ptr>
307     inline bool
308     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
309                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
310     { return !(__x < __y); }
311
312   template<typename _Tp, typename _RefL, typename _PtrL,
313            typename _RefR, typename _PtrR>
314     inline bool
315     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
316                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
317     { return !(__x < __y); }
318
319   // _GLIBCXX_RESOLVE_LIB_DEFECTS
320   // According to the resolution of DR179 not only the various comparison
321   // operators but also operator- must accept mixed iterator/const_iterator
322   // parameters.
323   template<typename _Tp, typename _RefL, typename _PtrL,
324            typename _RefR, typename _PtrR>
325     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
326     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
327               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
328     {
329       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
330         (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
331         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
332         + (__y._M_last - __y._M_cur);
333     }
334
335   template<typename _Tp, typename _Ref, typename _Ptr>
336     inline _Deque_iterator<_Tp, _Ref, _Ptr>
337     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
338     { return __x + __n; }
339
340   /**
341    *  @if maint
342    *  Deque base class.  This class provides the unified face for %deque's
343    *  allocation.  This class's constructor and destructor allocate and
344    *  deallocate (but do not initialize) storage.  This makes %exception
345    *  safety easier.
346    *
347    *  Nothing in this class ever constructs or destroys an actual Tp element.
348    *  (Deque handles that itself.)  Only/All memory management is performed
349    *  here.
350    *  @endif
351   */
352   template<typename _Tp, typename _Alloc>
353     class _Deque_base
354     : public _Alloc
355     {
356     public:
357       typedef _Alloc                  allocator_type;
358
359       allocator_type
360       get_allocator() const
361       { return *static_cast<const _Alloc*>(this); }
362
363       typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
364       typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
365
366       _Deque_base(const allocator_type& __a, size_t __num_elements)
367       : _Alloc(__a), _M_start(), _M_finish()
368       { _M_initialize_map(__num_elements); }
369
370       _Deque_base(const allocator_type& __a)
371       : _Alloc(__a), _M_start(), _M_finish() { }
372
373       ~_Deque_base();
374
375     protected:
376       typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
377       _Map_alloc_type _M_get_map_allocator() const
378       { return _Map_alloc_type(this->get_allocator()); }
379
380       _Tp*
381       _M_allocate_node()
382       { return _Alloc::allocate(__deque_buf_size(sizeof(_Tp))); }
383
384       void
385       _M_deallocate_node(_Tp* __p)
386       { _Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
387
388       _Tp**
389       _M_allocate_map(size_t __n)
390       { return _M_get_map_allocator().allocate(__n); }
391
392       void
393       _M_deallocate_map(_Tp** __p, size_t __n)
394       { _M_get_map_allocator().deallocate(__p, __n); }
395
396     protected:
397       void _M_initialize_map(size_t);
398       void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
399       void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
400       enum { _S_initial_map_size = 8 };
401
402       _Tp** _M_map;
403       size_t _M_map_size;
404       iterator _M_start;
405       iterator _M_finish;
406     };
407
408   template<typename _Tp, typename _Alloc>
409   _Deque_base<_Tp,_Alloc>::~_Deque_base()
410   {
411     if (this->_M_map)
412     {
413       _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
414       _M_deallocate_map(this->_M_map, this->_M_map_size);
415     }
416   }
417
418   /**
419    *  @if maint
420    *  @brief Layout storage.
421    *  @param  num_elements  The count of T's for which to allocate space
422    *                        at first.
423    *  @return   Nothing.
424    *
425    *  The initial underlying memory layout is a bit complicated...
426    *  @endif
427   */
428   template<typename _Tp, typename _Alloc>
429     void
430     _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
431     {
432       size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
433
434       this->_M_map_size = std::max((size_t) _S_initial_map_size,
435                                    __num_nodes + 2);
436       this->_M_map = _M_allocate_map(this->_M_map_size);
437
438       // For "small" maps (needing less than _M_map_size nodes), allocation
439       // starts in the middle elements and grows outwards.  So nstart may be
440       // the beginning of _M_map, but for small maps it may be as far in as
441       // _M_map+3.
442
443       _Tp** __nstart = this->_M_map + (this->_M_map_size - __num_nodes) / 2;
444       _Tp** __nfinish = __nstart + __num_nodes;
445
446       try
447         { _M_create_nodes(__nstart, __nfinish); }
448       catch(...)
449         {
450           _M_deallocate_map(this->_M_map, this->_M_map_size);
451           this->_M_map = 0;
452           this->_M_map_size = 0;
453           __throw_exception_again;
454         }
455
456       _M_start._M_set_node(__nstart);
457       _M_finish._M_set_node(__nfinish - 1);
458       _M_start._M_cur = _M_start._M_first;
459       _M_finish._M_cur = _M_finish._M_first + __num_elements
460                          % __deque_buf_size(sizeof(_Tp));
461     }
462
463   template<typename _Tp, typename _Alloc>
464     void
465     _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
466     {
467       _Tp** __cur;
468       try
469         {
470           for (__cur = __nstart; __cur < __nfinish; ++__cur)
471             *__cur = this->_M_allocate_node();
472         }
473       catch(...)
474         {
475           _M_destroy_nodes(__nstart, __cur);
476           __throw_exception_again;
477         }
478     }
479
480   template<typename _Tp, typename _Alloc>
481     void
482     _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
483     {
484       for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
485         _M_deallocate_node(*__n);
486     }
487
488   /**
489    *  @brief  A standard container using fixed-size memory allocation and
490    *  constant-time manipulation of elements at either end.
491    *
492    *  @ingroup Containers
493    *  @ingroup Sequences
494    *
495    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
496    *  <a href="tables.html#66">reversible container</a>, and a
497    *  <a href="tables.html#67">sequence</a>, including the
498    *  <a href="tables.html#68">optional sequence requirements</a>.
499    *
500    *  In previous HP/SGI versions of deque, there was an extra template
501    *  parameter so users could control the node size.  This extension turned
502    *  out to violate the C++ standard (it can be detected using template
503    *  template parameters), and it was removed.
504    *
505    *  @if maint
506    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
507    *
508    *  - Tp**        _M_map
509    *  - size_t      _M_map_size
510    *  - iterator    _M_start, _M_finish
511    *
512    *  map_size is at least 8.  %map is an array of map_size pointers-to-"nodes".
513    *  (The name %map has nothing to do with the std::map class, and "nodes"
514    *  should not be confused with std::list's usage of "node".)
515    *
516    *  A "node" has no specific type name as such, but it is referred to as
517    *  "node" in this file.  It is a simple array-of-Tp.  If Tp is very large,
518    *  there will be one Tp element per node (i.e., an "array" of one).
519    *  For non-huge Tp's, node size is inversely related to Tp size:  the
520    *  larger the Tp, the fewer Tp's will fit in a node.  The goal here is to
521    *  keep the total size of a node relatively small and constant over different
522    *  Tp's, to improve allocator efficiency.
523    *
524    *  **** As I write this, the nodes are /not/ allocated using the high-speed
525    *  memory pool.  There are 20 hours left in the year; perhaps I can fix
526    *  this before 2002.
527    *
528    *  Not every pointer in the %map array will point to a node.  If the initial
529    *  number of elements in the deque is small, the /middle/ %map pointers will
530    *  be valid, and the ones at the edges will be unused.  This same situation
531    *  will arise as the %map grows:  available %map pointers, if any, will be on
532    *  the ends.  As new nodes are created, only a subset of the %map's pointers
533    *  need to be copied "outward".
534    *
535    *  Class invariants:
536    * - For any nonsingular iterator i:
537    *    - i.node points to a member of the %map array.  (Yes, you read that
538    *      correctly:  i.node does not actually point to a node.)  The member of
539    *      the %map array is what actually points to the node.
540    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
541    *    - i.last  == i.first + node_size
542    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
543    *      the implication of this is that i.cur is always a dereferenceable
544    *      pointer, even if i is a past-the-end iterator.
545    * - Start and Finish are always nonsingular iterators.  NOTE: this means that
546    *   an empty deque must have one node, a deque with <N elements (where N is
547    *   the node buffer size) must have one node, a deque with N through (2N-1)
548    *   elements must have two nodes, etc.
549    * - For every node other than start.node and finish.node, every element in
550    *   the node is an initialized object.  If start.node == finish.node, then
551    *   [start.cur, finish.cur) are initialized objects, and the elements outside
552    *   that range are uninitialized storage.  Otherwise, [start.cur, start.last)
553    *   and [finish.first, finish.cur) are initialized objects, and [start.first,
554    *   start.cur) and [finish.cur, finish.last) are uninitialized storage.
555    * - [%map, %map + map_size) is a valid, non-empty range.
556    * - [start.node, finish.node] is a valid range contained within
557    *   [%map, %map + map_size).
558    * - A pointer in the range [%map, %map + map_size) points to an allocated
559    *   node if and only if the pointer is in the range
560    *   [start.node, finish.node].
561    *
562    *  Here's the magic:  nothing in deque is "aware" of the discontiguous
563    *  storage!
564    *
565    *  The memory setup and layout occurs in the parent, _Base, and the iterator
566    *  class is entirely responsible for "leaping" from one node to the next.
567    *  All the implementation routines for deque itself work only through the
568    *  start and finish iterators.  This keeps the routines simple and sane,
569    *  and we can use other standard algorithms as well.
570    *  @endif
571   */
572   template<typename _Tp, typename _Alloc = allocator<_Tp> >
573     class deque : protected _Deque_base<_Tp, _Alloc>
574     {
575       // concept requirements
576       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
577
578       typedef _Deque_base<_Tp, _Alloc>           _Base;
579
580     public:
581       typedef _Tp                                value_type;
582       typedef value_type*                        pointer;
583       typedef const value_type*                  const_pointer;
584       typedef typename _Base::iterator           iterator;
585       typedef typename _Base::const_iterator     const_iterator;
586       typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
587       typedef std::reverse_iterator<iterator>         reverse_iterator;
588       typedef value_type&                        reference;
589       typedef const value_type&                  const_reference;
590       typedef size_t                             size_type;
591       typedef ptrdiff_t                          difference_type;
592       typedef typename _Base::allocator_type     allocator_type;
593
594     protected:
595       typedef pointer*                           _Map_pointer;
596
597       static size_t _S_buffer_size()
598       { return __deque_buf_size(sizeof(_Tp)); }
599
600       // Functions controlling memory layout, and nothing else.
601       using _Base::_M_initialize_map;
602       using _Base::_M_create_nodes;
603       using _Base::_M_destroy_nodes;
604       using _Base::_M_allocate_node;
605       using _Base::_M_deallocate_node;
606       using _Base::_M_allocate_map;
607       using _Base::_M_deallocate_map;
608
609       /** @if maint
610        *  A total of four data members accumulated down the heirarchy.
611        *  @endif
612        */
613       using _Base::_M_map;
614       using _Base::_M_map_size;
615       using _Base::_M_start;
616       using _Base::_M_finish;
617
618     public:
619       // [23.2.1.1] construct/copy/destroy
620       // (assign() and get_allocator() are also listed in this section)
621       /**
622        *  @brief  Default constructor creates no elements.
623        */
624       explicit
625       deque(const allocator_type& __a = allocator_type())
626       : _Base(__a, 0) {}
627
628       /**
629        *  @brief  Create a %deque with copies of an exemplar element.
630        *  @param  n  The number of elements to initially create.
631        *  @param  value  An element to copy.
632        *
633        *  This constructor fills the %deque with @a n copies of @a value.
634        */
635       deque(size_type __n, const value_type& __value,
636             const allocator_type& __a = allocator_type())
637       : _Base(__a, __n)
638       { _M_fill_initialize(__value); }
639
640       /**
641        *  @brief  Create a %deque with default elements.
642        *  @param  n  The number of elements to initially create.
643        *
644        *  This constructor fills the %deque with @a n copies of a
645        *  default-constructed element.
646        */
647       explicit
648       deque(size_type __n)
649       : _Base(allocator_type(), __n)
650       { _M_fill_initialize(value_type()); }
651
652       /**
653        *  @brief  %Deque copy constructor.
654        *  @param  x  A %deque of identical element and allocator types.
655        *
656        *  The newly-created %deque uses a copy of the allocation object used
657        *  by @a x.
658        */
659       deque(const deque& __x)
660       : _Base(__x.get_allocator(), __x.size())
661       { std::uninitialized_copy(__x.begin(), __x.end(), this->_M_start); }
662
663       /**
664        *  @brief  Builds a %deque from a range.
665        *  @param  first  An input iterator.
666        *  @param  last  An input iterator.
667        *
668        *  Create a %deque consisting of copies of the elements from [first,
669        *  last).
670        *
671        *  If the iterators are forward, bidirectional, or random-access, then
672        *  this will call the elements' copy constructor N times (where N is
673        *  distance(first,last)) and do no memory reallocation.  But if only
674        *  input iterators are used, then this will do at most 2N calls to the
675        *  copy constructor, and logN memory reallocations.
676        */
677       template<typename _InputIterator>
678         deque(_InputIterator __first, _InputIterator __last,
679               const allocator_type& __a = allocator_type())
680         : _Base(__a)
681         {
682           // Check whether it's an integral type.  If so, it's not an iterator.
683           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
684           _M_initialize_dispatch(__first, __last, _Integral());
685         }
686
687       /**
688        *  The dtor only erases the elements, and note that if the elements
689        *  themselves are pointers, the pointed-to memory is not touched in any
690        *  way.  Managing the pointer is the user's responsibilty.
691        */
692       ~deque()
693       { std::_Destroy(this->_M_start, this->_M_finish); }
694
695       /**
696        *  @brief  %Deque assignment operator.
697        *  @param  x  A %deque of identical element and allocator types.
698        *
699        *  All the elements of @a x are copied, but unlike the copy constructor,
700        *  the allocator object is not copied.
701        */
702       deque&
703       operator=(const deque& __x);
704
705       /**
706        *  @brief  Assigns a given value to a %deque.
707        *  @param  n  Number of elements to be assigned.
708        *  @param  val  Value to be assigned.
709        *
710        *  This function fills a %deque with @a n copies of the given value.
711        *  Note that the assignment completely changes the %deque and that the
712        *  resulting %deque's size is the same as the number of elements assigned.
713        *  Old data may be lost.
714        */
715       void
716       assign(size_type __n, const value_type& __val)
717       { _M_fill_assign(__n, __val); }
718
719       /**
720        *  @brief  Assigns a range to a %deque.
721        *  @param  first  An input iterator.
722        *  @param  last   An input iterator.
723        *
724        *  This function fills a %deque with copies of the elements in the
725        *  range [first,last).
726        *
727        *  Note that the assignment completely changes the %deque and that the
728        *  resulting %deque's size is the same as the number of elements
729        *  assigned.  Old data may be lost.
730        */
731       template<typename _InputIterator>
732         void
733         assign(_InputIterator __first, _InputIterator __last)
734         {
735           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
736           _M_assign_dispatch(__first, __last, _Integral());
737         }
738
739       /// Get a copy of the memory allocation object.
740       allocator_type
741       get_allocator() const
742       { return _Base::get_allocator(); }
743
744       // iterators
745       /**
746        *  Returns a read/write iterator that points to the first element in the
747        *  %deque.  Iteration is done in ordinary element order.
748        */
749       iterator
750       begin()
751       { return this->_M_start; }
752
753       /**
754        *  Returns a read-only (constant) iterator that points to the first
755        *  element in the %deque.  Iteration is done in ordinary element order.
756        */
757       const_iterator
758       begin() const
759       { return this->_M_start; }
760
761       /**
762        *  Returns a read/write iterator that points one past the last element in
763        *  the %deque.  Iteration is done in ordinary element order.
764        */
765       iterator
766       end()
767       { return this->_M_finish; }
768
769       /**
770        *  Returns a read-only (constant) iterator that points one past the last
771        *  element in the %deque.  Iteration is done in ordinary element order.
772        */
773       const_iterator
774       end() const
775       { return this->_M_finish; }
776
777       /**
778        *  Returns a read/write reverse iterator that points to the last element
779        *  in the %deque.  Iteration is done in reverse element order.
780        */
781       reverse_iterator
782       rbegin()
783       { return reverse_iterator(this->_M_finish); }
784
785       /**
786        *  Returns a read-only (constant) reverse iterator that points to the
787        *  last element in the %deque.  Iteration is done in reverse element
788        *  order.
789        */
790       const_reverse_iterator
791       rbegin() const
792       { return const_reverse_iterator(this->_M_finish); }
793
794       /**
795        *  Returns a read/write reverse iterator that points to one before the
796        *  first element in the %deque.  Iteration is done in reverse element
797        *  order.
798        */
799       reverse_iterator
800       rend() { return reverse_iterator(this->_M_start); }
801
802       /**
803        *  Returns a read-only (constant) reverse iterator that points to one
804        *  before the first element in the %deque.  Iteration is done in reverse
805        *  element order.
806        */
807       const_reverse_iterator
808       rend() const
809       { return const_reverse_iterator(this->_M_start); }
810
811       // [23.2.1.2] capacity
812       /**  Returns the number of elements in the %deque.  */
813       size_type
814       size() const
815       { return this->_M_finish - this->_M_start; }
816
817       /**  Returns the size() of the largest possible %deque.  */
818       size_type
819       max_size() const
820       { return size_type(-1); }
821
822       /**
823        *  @brief  Resizes the %deque to the specified number of elements.
824        *  @param  new_size  Number of elements the %deque should contain.
825        *  @param  x  Data with which new elements should be populated.
826        *
827        *  This function will %resize the %deque to the specified number of
828        *  elements.  If the number is smaller than the %deque's current size the
829        *  %deque is truncated, otherwise the %deque is extended and new elements
830        *  are populated with given data.
831        */
832       void
833       resize(size_type __new_size, const value_type& __x)
834       {
835         const size_type __len = size();
836         if (__new_size < __len)
837           erase(this->_M_start + __new_size, this->_M_finish);
838         else
839           insert(this->_M_finish, __new_size - __len, __x);
840       }
841
842       /**
843        *  @brief  Resizes the %deque to the specified number of elements.
844        *  @param  new_size  Number of elements the %deque should contain.
845        *
846        *  This function will resize the %deque to the specified number of
847        *  elements.  If the number is smaller than the %deque's current size the
848        *  %deque is truncated, otherwise the %deque is extended and new elements
849        *  are default-constructed.
850        */
851       void
852       resize(size_type new_size)
853       { resize(new_size, value_type()); }
854
855       /**
856        *  Returns true if the %deque is empty.  (Thus begin() would equal end().)
857        */
858       bool
859       empty() const
860       { return this->_M_finish == this->_M_start; }
861
862       // element access
863       /**
864        *  @brief  Subscript access to the data contained in the %deque.
865        *  @param  n  The index of the element for which data should be accessed.
866        *  @return  Read/write reference to data.
867        *
868        *  This operator allows for easy, array-style, data access.
869        *  Note that data access with this operator is unchecked and out_of_range
870        *  lookups are not defined. (For checked lookups see at().)
871        */
872       reference
873       operator[](size_type __n)
874       { return this->_M_start[difference_type(__n)]; }
875
876       /**
877        *  @brief  Subscript access to the data contained in the %deque.
878        *  @param  n  The index of the element for which data should be accessed.
879        *  @return  Read-only (constant) reference to data.
880        *
881        *  This operator allows for easy, array-style, data access.
882        *  Note that data access with this operator is unchecked and out_of_range
883        *  lookups are not defined. (For checked lookups see at().)
884        */
885       const_reference
886       operator[](size_type __n) const
887       { return this->_M_start[difference_type(__n)]; }
888
889     protected:
890       /// @if maint Safety check used only from at().  @endif
891       void
892       _M_range_check(size_type __n) const
893       {
894         if (__n >= this->size())
895           __throw_out_of_range(__N("deque::_M_range_check"));
896       }
897
898     public:
899       /**
900        *  @brief  Provides access to the data contained in the %deque.
901        *  @param  n  The index of the element for which data should be accessed.
902        *  @return  Read/write reference to data.
903        *  @throw  std::out_of_range  If @a n is an invalid index.
904        *
905        *  This function provides for safer data access.  The parameter is first
906        *  checked that it is in the range of the deque.  The function throws
907        *  out_of_range if the check fails.
908        */
909       reference
910       at(size_type __n)
911       { _M_range_check(__n); return (*this)[__n]; }
912
913       /**
914        *  @brief  Provides access to the data contained in the %deque.
915        *  @param  n  The index of the element for which data should be accessed.
916        *  @return  Read-only (constant) reference to data.
917        *  @throw  std::out_of_range  If @a n is an invalid index.
918        *
919        *  This function provides for safer data access.  The parameter is first
920        *  checked that it is in the range of the deque.  The function throws
921        *  out_of_range if the check fails.
922        */
923       const_reference
924       at(size_type __n) const
925       {
926         _M_range_check(__n);
927         return (*this)[__n];
928       }
929
930       /**
931        *  Returns a read/write reference to the data at the first element of the
932        *  %deque.
933        */
934       reference
935       front()
936       { return *this->_M_start; }
937
938       /**
939        *  Returns a read-only (constant) reference to the data at the first
940        *  element of the %deque.
941        */
942       const_reference
943       front() const
944       { return *this->_M_start; }
945
946       /**
947        *  Returns a read/write reference to the data at the last element of the
948        *  %deque.
949        */
950       reference
951       back()
952       {
953         iterator __tmp = this->_M_finish;
954         --__tmp;
955         return *__tmp;
956       }
957
958       /**
959        *  Returns a read-only (constant) reference to the data at the last
960        *  element of the %deque.
961        */
962       const_reference
963       back() const
964       {
965         const_iterator __tmp = this->_M_finish;
966         --__tmp;
967         return *__tmp;
968       }
969
970       // [23.2.1.2] modifiers
971       /**
972        *  @brief  Add data to the front of the %deque.
973        *  @param  x  Data to be added.
974        *
975        *  This is a typical stack operation.  The function creates an element at
976        *  the front of the %deque and assigns the given data to it.  Due to the
977        *  nature of a %deque this operation can be done in constant time.
978        */
979       void
980       push_front(const value_type& __x)
981       {
982         if (this->_M_start._M_cur != this->_M_start._M_first)
983           {
984             std::_Construct(this->_M_start._M_cur - 1, __x);
985             --this->_M_start._M_cur;
986           }
987         else
988           _M_push_front_aux(__x);
989       }
990
991       /**
992        *  @brief  Add data to the end of the %deque.
993        *  @param  x  Data to be added.
994        *
995        *  This is a typical stack operation.  The function creates an element at
996        *  the end of the %deque and assigns the given data to it.  Due to the
997        *  nature of a %deque this operation can be done in constant time.
998        */
999       void
1000       push_back(const value_type& __x)
1001       {
1002         if (this->_M_finish._M_cur != this->_M_finish._M_last - 1)
1003           {
1004             std::_Construct(this->_M_finish._M_cur, __x);
1005             ++this->_M_finish._M_cur;
1006           }
1007         else
1008           _M_push_back_aux(__x);
1009       }
1010
1011       /**
1012        *  @brief  Removes first element.
1013        *
1014        *  This is a typical stack operation.  It shrinks the %deque by one.
1015        *
1016        *  Note that no data is returned, and if the first element's data is
1017        *  needed, it should be retrieved before pop_front() is called.
1018        */
1019       void
1020       pop_front()
1021       {
1022         if (this->_M_start._M_cur != this->_M_start._M_last - 1)
1023           {
1024             std::_Destroy(this->_M_start._M_cur);
1025             ++this->_M_start._M_cur;
1026           }
1027         else
1028           _M_pop_front_aux();
1029       }
1030
1031       /**
1032        *  @brief  Removes last element.
1033        *
1034        *  This is a typical stack operation.  It shrinks the %deque by one.
1035        *
1036        *  Note that no data is returned, and if the last element's data is
1037        *  needed, it should be retrieved before pop_back() is called.
1038        */
1039       void
1040       pop_back()
1041       {
1042         if (this->_M_finish._M_cur != this->_M_finish._M_first)
1043           {
1044             --this->_M_finish._M_cur;
1045             std::_Destroy(this->_M_finish._M_cur);
1046           }
1047         else
1048           _M_pop_back_aux();
1049       }
1050
1051       /**
1052        *  @brief  Inserts given value into %deque before specified iterator.
1053        *  @param  position  An iterator into the %deque.
1054        *  @param  x  Data to be inserted.
1055        *  @return  An iterator that points to the inserted data.
1056        *
1057        *  This function will insert a copy of the given value before the
1058        *  specified location.
1059        */
1060       iterator
1061       insert(iterator position, const value_type& __x);
1062
1063       /**
1064        *  @brief  Inserts a number of copies of given data into the %deque.
1065        *  @param  position  An iterator into the %deque.
1066        *  @param  n  Number of elements to be inserted.
1067        *  @param  x  Data to be inserted.
1068        *
1069        *  This function will insert a specified number of copies of the given
1070        *  data before the location specified by @a position.
1071        */
1072       void
1073       insert(iterator __position, size_type __n, const value_type& __x)
1074       { _M_fill_insert(__position, __n, __x); }
1075
1076       /**
1077        *  @brief  Inserts a range into the %deque.
1078        *  @param  position  An iterator into the %deque.
1079        *  @param  first  An input iterator.
1080        *  @param  last   An input iterator.
1081        *
1082        *  This function will insert copies of the data in the range [first,last)
1083        *  into the %deque before the location specified by @a pos.  This is
1084        *  known as "range insert."
1085        */
1086       template<typename _InputIterator>
1087         void
1088         insert(iterator __position, _InputIterator __first,
1089                _InputIterator __last)
1090         {
1091           // Check whether it's an integral type.  If so, it's not an iterator.
1092           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1093           _M_insert_dispatch(__position, __first, __last, _Integral());
1094         }
1095
1096       /**
1097        *  @brief  Remove element at given position.
1098        *  @param  position  Iterator pointing to element to be erased.
1099        *  @return  An iterator pointing to the next element (or end()).
1100        *
1101        *  This function will erase the element at the given position and thus
1102        *  shorten the %deque by one.
1103        *
1104        *  The user is cautioned that
1105        *  this function only erases the element, and that if the element is
1106        *  itself a pointer, the pointed-to memory is not touched in any way.
1107        *  Managing the pointer is the user's responsibilty.
1108        */
1109       iterator
1110       erase(iterator __position);
1111
1112       /**
1113        *  @brief  Remove a range of elements.
1114        *  @param  first  Iterator pointing to the first element to be erased.
1115        *  @param  last  Iterator pointing to one past the last element to be
1116        *                erased.
1117        *  @return  An iterator pointing to the element pointed to by @a last
1118        *           prior to erasing (or end()).
1119        *
1120        *  This function will erase the elements in the range [first,last) and
1121        *  shorten the %deque accordingly.
1122        *
1123        *  The user is cautioned that
1124        *  this function only erases the elements, and that if the elements
1125        *  themselves are pointers, the pointed-to memory is not touched in any
1126        *  way.  Managing the pointer is the user's responsibilty.
1127        */
1128       iterator
1129       erase(iterator __first, iterator __last);
1130
1131       /**
1132        *  @brief  Swaps data with another %deque.
1133        *  @param  x  A %deque of the same element and allocator types.
1134        *
1135        *  This exchanges the elements between two deques in constant time.
1136        *  (Four pointers, so it should be quite fast.)
1137        *  Note that the global std::swap() function is specialized such that
1138        *  std::swap(d1,d2) will feed to this function.
1139        */
1140       void
1141       swap(deque& __x)
1142       {
1143         std::swap(this->_M_start, __x._M_start);
1144         std::swap(this->_M_finish, __x._M_finish);
1145         std::swap(this->_M_map, __x._M_map);
1146         std::swap(this->_M_map_size, __x._M_map_size);
1147       }
1148
1149       /**
1150        *  Erases all the elements.  Note that this function only erases the
1151        *  elements, and that if the elements themselves are pointers, the
1152        *  pointed-to memory is not touched in any way.  Managing the pointer is
1153        *  the user's responsibilty.
1154        */
1155       void clear();
1156
1157     protected:
1158       // Internal constructor functions follow.
1159
1160       // called by the range constructor to implement [23.1.1]/9
1161       template<typename _Integer>
1162         void
1163         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1164         {
1165           _M_initialize_map(__n);
1166           _M_fill_initialize(__x);
1167         }
1168
1169       // called by the range constructor to implement [23.1.1]/9
1170       template<typename _InputIterator>
1171         void
1172         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1173                                __false_type)
1174         {
1175           typedef typename iterator_traits<_InputIterator>::iterator_category
1176             _IterCategory;
1177           _M_range_initialize(__first, __last, _IterCategory());
1178         }
1179
1180       // called by the second initialize_dispatch above
1181       //@{
1182       /**
1183        *  @if maint
1184        *  @brief Fills the deque with whatever is in [first,last).
1185        *  @param  first  An input iterator.
1186        *  @param  last  An input iterator.
1187        *  @return   Nothing.
1188        *
1189        *  If the iterators are actually forward iterators (or better), then the
1190        *  memory layout can be done all at once.  Else we move forward using
1191        *  push_back on each value from the iterator.
1192        *  @endif
1193        */
1194       template<typename _InputIterator>
1195         void
1196         _M_range_initialize(_InputIterator __first, _InputIterator __last,
1197                             input_iterator_tag);
1198
1199       // called by the second initialize_dispatch above
1200       template<typename _ForwardIterator>
1201         void
1202         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1203                             forward_iterator_tag);
1204       //@}
1205
1206       /**
1207        *  @if maint
1208        *  @brief Fills the %deque with copies of value.
1209        *  @param  value  Initial value.
1210        *  @return   Nothing.
1211        *  @pre _M_start and _M_finish have already been initialized, but none of
1212        *       the %deque's elements have yet been constructed.
1213        *
1214        *  This function is called only when the user provides an explicit size
1215        *  (with or without an explicit exemplar value).
1216        *  @endif
1217        */
1218       void
1219       _M_fill_initialize(const value_type& __value);
1220
1221       // Internal assign functions follow.  The *_aux functions do the actual
1222       // assignment work for the range versions.
1223
1224       // called by the range assign to implement [23.1.1]/9
1225       template<typename _Integer>
1226         void
1227         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1228         {
1229           _M_fill_assign(static_cast<size_type>(__n),
1230                          static_cast<value_type>(__val));
1231         }
1232
1233       // called by the range assign to implement [23.1.1]/9
1234       template<typename _InputIterator>
1235         void
1236         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1237                            __false_type)
1238         {
1239           typedef typename iterator_traits<_InputIterator>::iterator_category
1240             _IterCategory;
1241           _M_assign_aux(__first, __last, _IterCategory());
1242         }
1243
1244       // called by the second assign_dispatch above
1245       template<typename _InputIterator>
1246         void
1247         _M_assign_aux(_InputIterator __first, _InputIterator __last,
1248                       input_iterator_tag);
1249
1250       // called by the second assign_dispatch above
1251       template<typename _ForwardIterator>
1252         void
1253         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1254                       forward_iterator_tag)
1255         {
1256           const size_type __len = std::distance(__first, __last);
1257           if (__len > size())
1258             {
1259               _ForwardIterator __mid = __first;
1260               std::advance(__mid, size());
1261               std::copy(__first, __mid, begin());
1262               insert(end(), __mid, __last);
1263             }
1264           else
1265             erase(std::copy(__first, __last, begin()), end());
1266         }
1267
1268       // Called by assign(n,t), and the range assign when it turns out to be the
1269       // same thing.
1270       void
1271       _M_fill_assign(size_type __n, const value_type& __val)
1272       {
1273         if (__n > size())
1274           {
1275             std::fill(begin(), end(), __val);
1276             insert(end(), __n - size(), __val);
1277           }
1278         else
1279           {
1280             erase(begin() + __n, end());
1281             std::fill(begin(), end(), __val);
1282           }
1283       }
1284
1285       //@{
1286       /**
1287        *  @if maint
1288        *  @brief Helper functions for push_* and pop_*.
1289        *  @endif
1290        */
1291       void _M_push_back_aux(const value_type&);
1292       void _M_push_front_aux(const value_type&);
1293       void _M_pop_back_aux();
1294       void _M_pop_front_aux();
1295       //@}
1296
1297       // Internal insert functions follow.  The *_aux functions do the actual
1298       // insertion work when all shortcuts fail.
1299
1300       // called by the range insert to implement [23.1.1]/9
1301       template<typename _Integer>
1302         void
1303         _M_insert_dispatch(iterator __pos,
1304                            _Integer __n, _Integer __x, __true_type)
1305         {
1306           _M_fill_insert(__pos, static_cast<size_type>(__n),
1307                          static_cast<value_type>(__x));
1308         }
1309
1310       // called by the range insert to implement [23.1.1]/9
1311       template<typename _InputIterator>
1312         void
1313         _M_insert_dispatch(iterator __pos,
1314                            _InputIterator __first, _InputIterator __last,
1315                            __false_type)
1316         {
1317           typedef typename iterator_traits<_InputIterator>::iterator_category
1318             _IterCategory;
1319           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1320         }
1321
1322       // called by the second insert_dispatch above
1323       template<typename _InputIterator>
1324         void
1325         _M_range_insert_aux(iterator __pos, _InputIterator __first,
1326                             _InputIterator __last, input_iterator_tag);
1327
1328       // called by the second insert_dispatch above
1329       template<typename _ForwardIterator>
1330         void
1331         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1332                             _ForwardIterator __last, forward_iterator_tag);
1333
1334       // Called by insert(p,n,x), and the range insert when it turns out to be
1335       // the same thing.  Can use fill functions in optimal situations,
1336       // otherwise passes off to insert_aux(p,n,x).
1337       void
1338       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1339
1340       // called by insert(p,x)
1341       iterator
1342       _M_insert_aux(iterator __pos, const value_type& __x);
1343
1344       // called by insert(p,n,x) via fill_insert
1345       void
1346       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1347
1348       // called by range_insert_aux for forward iterators
1349       template<typename _ForwardIterator>
1350         void
1351         _M_insert_aux(iterator __pos,
1352                       _ForwardIterator __first, _ForwardIterator __last,
1353                       size_type __n);
1354
1355       //@{
1356       /**
1357        *  @if maint
1358        *  @brief Memory-handling helpers for the previous internal insert
1359        *         functions.
1360        *  @endif
1361        */
1362       iterator
1363       _M_reserve_elements_at_front(size_type __n)
1364       {
1365         const size_type __vacancies = this->_M_start._M_cur
1366                                       - this->_M_start._M_first;
1367         if (__n > __vacancies)
1368           _M_new_elements_at_front(__n - __vacancies);
1369         return this->_M_start - difference_type(__n);
1370       }
1371
1372       iterator
1373       _M_reserve_elements_at_back(size_type __n)
1374       {
1375         const size_type __vacancies = (this->_M_finish._M_last
1376                                        - this->_M_finish._M_cur) - 1;
1377         if (__n > __vacancies)
1378           _M_new_elements_at_back(__n - __vacancies);
1379         return this->_M_finish + difference_type(__n);
1380       }
1381
1382       void
1383       _M_new_elements_at_front(size_type __new_elements);
1384
1385       void
1386       _M_new_elements_at_back(size_type __new_elements);
1387       //@}
1388
1389
1390       //@{
1391       /**
1392        *  @if maint
1393        *  @brief Memory-handling helpers for the major %map.
1394        *
1395        *  Makes sure the _M_map has space for new nodes.  Does not actually add
1396        *  the nodes.  Can invalidate _M_map pointers.  (And consequently, %deque
1397        *  iterators.)
1398        *  @endif
1399        */
1400       void
1401       _M_reserve_map_at_back (size_type __nodes_to_add = 1)
1402       {
1403         if (__nodes_to_add + 1 > this->_M_map_size
1404             - (this->_M_finish._M_node - this->_M_map))
1405           _M_reallocate_map(__nodes_to_add, false);
1406       }
1407
1408       void
1409       _M_reserve_map_at_front (size_type __nodes_to_add = 1)
1410       {
1411         if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map))
1412           _M_reallocate_map(__nodes_to_add, true);
1413       }
1414
1415       void
1416       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1417       //@}
1418     };
1419
1420
1421   /**
1422    *  @brief  Deque equality comparison.
1423    *  @param  x  A %deque.
1424    *  @param  y  A %deque of the same type as @a x.
1425    *  @return  True iff the size and elements of the deques are equal.
1426    *
1427    *  This is an equivalence relation.  It is linear in the size of the
1428    *  deques.  Deques are considered equivalent if their sizes are equal,
1429    *  and if corresponding elements compare equal.
1430   */
1431   template<typename _Tp, typename _Alloc>
1432     inline bool
1433     operator==(const deque<_Tp, _Alloc>& __x,
1434                          const deque<_Tp, _Alloc>& __y)
1435     { return __x.size() == __y.size()
1436              && std::equal(__x.begin(), __x.end(), __y.begin()); }
1437
1438   /**
1439    *  @brief  Deque ordering relation.
1440    *  @param  x  A %deque.
1441    *  @param  y  A %deque of the same type as @a x.
1442    *  @return  True iff @a x is lexicographically less than @a y.
1443    *
1444    *  This is a total ordering relation.  It is linear in the size of the
1445    *  deques.  The elements must be comparable with @c <.
1446    *
1447    *  See std::lexicographical_compare() for how the determination is made.
1448   */
1449   template<typename _Tp, typename _Alloc>
1450     inline bool
1451     operator<(const deque<_Tp, _Alloc>& __x,
1452               const deque<_Tp, _Alloc>& __y)
1453     { return lexicographical_compare(__x.begin(), __x.end(),
1454                                      __y.begin(), __y.end()); }
1455
1456   /// Based on operator==
1457   template<typename _Tp, typename _Alloc>
1458     inline bool
1459     operator!=(const deque<_Tp, _Alloc>& __x,
1460                const deque<_Tp, _Alloc>& __y)
1461     { return !(__x == __y); }
1462
1463   /// Based on operator<
1464   template<typename _Tp, typename _Alloc>
1465     inline bool
1466     operator>(const deque<_Tp, _Alloc>& __x,
1467               const deque<_Tp, _Alloc>& __y)
1468     { return __y < __x; }
1469
1470   /// Based on operator<
1471   template<typename _Tp, typename _Alloc>
1472     inline bool
1473     operator<=(const deque<_Tp, _Alloc>& __x,
1474                const deque<_Tp, _Alloc>& __y)
1475     { return !(__y < __x); }
1476
1477   /// Based on operator<
1478   template<typename _Tp, typename _Alloc>
1479     inline bool
1480     operator>=(const deque<_Tp, _Alloc>& __x,
1481                const deque<_Tp, _Alloc>& __y)
1482     { return !(__x < __y); }
1483
1484   /// See std::deque::swap().
1485   template<typename _Tp, typename _Alloc>
1486     inline void
1487     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
1488     { __x.swap(__y); }
1489 } // namespace __gnu_norm
1490
1491 #endif /* _DEQUE_H */