OSDN Git Service

2011-05-26 Paolo Carlini <paolo.carlini@oracle.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_deque.h
1 // Deque implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation.  Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose.  It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation.  Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose.  It is provided "as is" without express or implied warranty.
50  */
51
52 /** @file bits/stl_deque.h
53  *  This is an internal header file, included by other library headers.
54  *  Do not attempt to use it directly. @headername{deque}
55  */
56
57 #ifndef _STL_DEQUE_H
58 #define _STL_DEQUE_H 1
59
60 #include <bits/concept_check.h>
61 #include <bits/stl_iterator_base_types.h>
62 #include <bits/stl_iterator_base_funcs.h>
63 #include <initializer_list>
64
65 namespace std _GLIBCXX_VISIBILITY(default)
66 {
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68
69   /**
70    *  @brief This function controls the size of memory nodes.
71    *  @param  size  The size of an element.
72    *  @return   The number (not byte size) of elements per node.
73    *
74    *  This function started off as a compiler kludge from SGI, but
75    *  seems to be a useful wrapper around a repeated constant
76    *  expression.  The @b 512 is tunable (and no other code needs to
77    *  change), but no investigation has been done since inheriting the
78    *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
79    *  you are doing, however: changing it breaks the binary
80    *  compatibility!!
81   */
82
83 #ifndef _GLIBCXX_DEQUE_BUF_SIZE
84 #define _GLIBCXX_DEQUE_BUF_SIZE 512
85 #endif
86
87   inline size_t
88   __deque_buf_size(size_t __size)
89   { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
90             ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
91
92
93   /**
94    *  @brief A deque::iterator.
95    *
96    *  Quite a bit of intelligence here.  Much of the functionality of
97    *  deque is actually passed off to this class.  A deque holds two
98    *  of these internally, marking its valid range.  Access to
99    *  elements is done as offsets of either of those two, relying on
100    *  operator overloading in this class.
101    *
102    *  All the functions are op overloads except for _M_set_node.
103   */
104   template<typename _Tp, typename _Ref, typename _Ptr>
105     struct _Deque_iterator
106     {
107       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
108       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
109
110       static size_t _S_buffer_size()
111       { return __deque_buf_size(sizeof(_Tp)); }
112
113       typedef std::random_access_iterator_tag iterator_category;
114       typedef _Tp                             value_type;
115       typedef _Ptr                            pointer;
116       typedef _Ref                            reference;
117       typedef size_t                          size_type;
118       typedef ptrdiff_t                       difference_type;
119       typedef _Tp**                           _Map_pointer;
120       typedef _Deque_iterator                 _Self;
121
122       _Tp* _M_cur;
123       _Tp* _M_first;
124       _Tp* _M_last;
125       _Map_pointer _M_node;
126
127       _Deque_iterator(_Tp* __x, _Map_pointer __y)
128       : _M_cur(__x), _M_first(*__y),
129         _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
130
131       _Deque_iterator()
132       : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }
133
134       _Deque_iterator(const iterator& __x)
135       : _M_cur(__x._M_cur), _M_first(__x._M_first),
136         _M_last(__x._M_last), _M_node(__x._M_node) { }
137
138       reference
139       operator*() const
140       { return *_M_cur; }
141
142       pointer
143       operator->() const
144       { return _M_cur; }
145
146       _Self&
147       operator++()
148       {
149         ++_M_cur;
150         if (_M_cur == _M_last)
151           {
152             _M_set_node(_M_node + 1);
153             _M_cur = _M_first;
154           }
155         return *this;
156       }
157
158       _Self
159       operator++(int)
160       {
161         _Self __tmp = *this;
162         ++*this;
163         return __tmp;
164       }
165
166       _Self&
167       operator--()
168       {
169         if (_M_cur == _M_first)
170           {
171             _M_set_node(_M_node - 1);
172             _M_cur = _M_last;
173           }
174         --_M_cur;
175         return *this;
176       }
177
178       _Self
179       operator--(int)
180       {
181         _Self __tmp = *this;
182         --*this;
183         return __tmp;
184       }
185
186       _Self&
187       operator+=(difference_type __n)
188       {
189         const difference_type __offset = __n + (_M_cur - _M_first);
190         if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
191           _M_cur += __n;
192         else
193           {
194             const difference_type __node_offset =
195               __offset > 0 ? __offset / difference_type(_S_buffer_size())
196                            : -difference_type((-__offset - 1)
197                                               / _S_buffer_size()) - 1;
198             _M_set_node(_M_node + __node_offset);
199             _M_cur = _M_first + (__offset - __node_offset
200                                  * difference_type(_S_buffer_size()));
201           }
202         return *this;
203       }
204
205       _Self
206       operator+(difference_type __n) const
207       {
208         _Self __tmp = *this;
209         return __tmp += __n;
210       }
211
212       _Self&
213       operator-=(difference_type __n)
214       { return *this += -__n; }
215
216       _Self
217       operator-(difference_type __n) const
218       {
219         _Self __tmp = *this;
220         return __tmp -= __n;
221       }
222
223       reference
224       operator[](difference_type __n) const
225       { return *(*this + __n); }
226
227       /** 
228        *  Prepares to traverse new_node.  Sets everything except
229        *  _M_cur, which should therefore be set by the caller
230        *  immediately afterwards, based on _M_first and _M_last.
231        */
232       void
233       _M_set_node(_Map_pointer __new_node)
234       {
235         _M_node = __new_node;
236         _M_first = *__new_node;
237         _M_last = _M_first + difference_type(_S_buffer_size());
238       }
239     };
240
241   // Note: we also provide overloads whose operands are of the same type in
242   // order to avoid ambiguous overload resolution when std::rel_ops operators
243   // are in scope (for additional details, see libstdc++/3628)
244   template<typename _Tp, typename _Ref, typename _Ptr>
245     inline bool
246     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
247                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
248     { return __x._M_cur == __y._M_cur; }
249
250   template<typename _Tp, typename _RefL, typename _PtrL,
251            typename _RefR, typename _PtrR>
252     inline bool
253     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
254                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
255     { return __x._M_cur == __y._M_cur; }
256
257   template<typename _Tp, typename _Ref, typename _Ptr>
258     inline bool
259     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
260                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
261     { return !(__x == __y); }
262
263   template<typename _Tp, typename _RefL, typename _PtrL,
264            typename _RefR, typename _PtrR>
265     inline bool
266     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
267                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
268     { return !(__x == __y); }
269
270   template<typename _Tp, typename _Ref, typename _Ptr>
271     inline bool
272     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
273               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
274     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
275                                           : (__x._M_node < __y._M_node); }
276
277   template<typename _Tp, typename _RefL, typename _PtrL,
278            typename _RefR, typename _PtrR>
279     inline bool
280     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
281               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
282     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
283                                           : (__x._M_node < __y._M_node); }
284
285   template<typename _Tp, typename _Ref, typename _Ptr>
286     inline bool
287     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
288               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
289     { return __y < __x; }
290
291   template<typename _Tp, typename _RefL, typename _PtrL,
292            typename _RefR, typename _PtrR>
293     inline bool
294     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
295               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
296     { return __y < __x; }
297
298   template<typename _Tp, typename _Ref, typename _Ptr>
299     inline bool
300     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
301                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
302     { return !(__y < __x); }
303
304   template<typename _Tp, typename _RefL, typename _PtrL,
305            typename _RefR, typename _PtrR>
306     inline bool
307     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
308                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
309     { return !(__y < __x); }
310
311   template<typename _Tp, typename _Ref, typename _Ptr>
312     inline bool
313     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
314                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
315     { return !(__x < __y); }
316
317   template<typename _Tp, typename _RefL, typename _PtrL,
318            typename _RefR, typename _PtrR>
319     inline bool
320     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
321                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
322     { return !(__x < __y); }
323
324   // _GLIBCXX_RESOLVE_LIB_DEFECTS
325   // According to the resolution of DR179 not only the various comparison
326   // operators but also operator- must accept mixed iterator/const_iterator
327   // parameters.
328   template<typename _Tp, typename _Ref, typename _Ptr>
329     inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
330     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
331               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
332     {
333       return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
334         (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
335         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
336         + (__y._M_last - __y._M_cur);
337     }
338
339   template<typename _Tp, typename _RefL, typename _PtrL,
340            typename _RefR, typename _PtrR>
341     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
342     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
343               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
344     {
345       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
346         (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
347         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
348         + (__y._M_last - __y._M_cur);
349     }
350
351   template<typename _Tp, typename _Ref, typename _Ptr>
352     inline _Deque_iterator<_Tp, _Ref, _Ptr>
353     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
354     { return __x + __n; }
355
356   template<typename _Tp>
357     void
358     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
359          const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
360
361   template<typename _Tp>
362     _Deque_iterator<_Tp, _Tp&, _Tp*>
363     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
364          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
365          _Deque_iterator<_Tp, _Tp&, _Tp*>);
366
367   template<typename _Tp>
368     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
369     copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
370          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
371          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
372     { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
373                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
374                        __result); }
375
376   template<typename _Tp>
377     _Deque_iterator<_Tp, _Tp&, _Tp*>
378     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
379                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
380                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
381
382   template<typename _Tp>
383     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
384     copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
385                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
386                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
387     { return std::copy_backward(_Deque_iterator<_Tp,
388                                 const _Tp&, const _Tp*>(__first),
389                                 _Deque_iterator<_Tp,
390                                 const _Tp&, const _Tp*>(__last),
391                                 __result); }
392
393 #ifdef __GXX_EXPERIMENTAL_CXX0X__
394   template<typename _Tp>
395     _Deque_iterator<_Tp, _Tp&, _Tp*>
396     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
397          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
398          _Deque_iterator<_Tp, _Tp&, _Tp*>);
399
400   template<typename _Tp>
401     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
402     move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
403          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
404          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
405     { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
406                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
407                        __result); }
408
409   template<typename _Tp>
410     _Deque_iterator<_Tp, _Tp&, _Tp*>
411     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
412                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
413                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
414
415   template<typename _Tp>
416     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
417     move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
418                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
419                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
420     { return std::move_backward(_Deque_iterator<_Tp,
421                                 const _Tp&, const _Tp*>(__first),
422                                 _Deque_iterator<_Tp,
423                                 const _Tp&, const _Tp*>(__last),
424                                 __result); }
425 #endif
426
427   /**
428    *  Deque base class.  This class provides the unified face for %deque's
429    *  allocation.  This class's constructor and destructor allocate and
430    *  deallocate (but do not initialize) storage.  This makes %exception
431    *  safety easier.
432    *
433    *  Nothing in this class ever constructs or destroys an actual Tp element.
434    *  (Deque handles that itself.)  Only/All memory management is performed
435    *  here.
436   */
437   template<typename _Tp, typename _Alloc>
438     class _Deque_base
439     {
440     public:
441       typedef _Alloc                  allocator_type;
442
443       allocator_type
444       get_allocator() const _GLIBCXX_NOEXCEPT
445       { return allocator_type(_M_get_Tp_allocator()); }
446
447       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
448       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
449
450       _Deque_base()
451       : _M_impl()
452       { _M_initialize_map(0); }
453
454       _Deque_base(size_t __num_elements)
455       : _M_impl()
456       { _M_initialize_map(__num_elements); }
457
458       _Deque_base(const allocator_type& __a, size_t __num_elements)
459       : _M_impl(__a)
460       { _M_initialize_map(__num_elements); }
461
462       _Deque_base(const allocator_type& __a)
463       : _M_impl(__a)
464       { }
465
466 #ifdef __GXX_EXPERIMENTAL_CXX0X__
467       _Deque_base(_Deque_base&& __x)
468       : _M_impl(__x._M_get_Tp_allocator())
469       {
470         _M_initialize_map(0);
471         if (__x._M_impl._M_map)
472           {
473             std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
474             std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
475             std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
476             std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
477           }
478       }
479 #endif
480
481       ~_Deque_base();
482
483     protected:
484       //This struct encapsulates the implementation of the std::deque
485       //standard container and at the same time makes use of the EBO
486       //for empty allocators.
487       typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
488
489       typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;
490
491       struct _Deque_impl
492       : public _Tp_alloc_type
493       {
494         _Tp** _M_map;
495         size_t _M_map_size;
496         iterator _M_start;
497         iterator _M_finish;
498
499         _Deque_impl()
500         : _Tp_alloc_type(), _M_map(0), _M_map_size(0),
501           _M_start(), _M_finish()
502         { }
503
504         _Deque_impl(const _Tp_alloc_type& __a)
505         : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
506           _M_start(), _M_finish()
507         { }
508       };
509
510       _Tp_alloc_type&
511       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
512       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
513
514       const _Tp_alloc_type&
515       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
516       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
517
518       _Map_alloc_type
519       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
520       { return _Map_alloc_type(_M_get_Tp_allocator()); }
521
522       _Tp*
523       _M_allocate_node()
524       { 
525         return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
526       }
527
528       void
529       _M_deallocate_node(_Tp* __p)
530       {
531         _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
532       }
533
534       _Tp**
535       _M_allocate_map(size_t __n)
536       { return _M_get_map_allocator().allocate(__n); }
537
538       void
539       _M_deallocate_map(_Tp** __p, size_t __n)
540       { _M_get_map_allocator().deallocate(__p, __n); }
541
542     protected:
543       void _M_initialize_map(size_t);
544       void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
545       void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
546       enum { _S_initial_map_size = 8 };
547
548       _Deque_impl _M_impl;
549     };
550
551   template<typename _Tp, typename _Alloc>
552     _Deque_base<_Tp, _Alloc>::
553     ~_Deque_base()
554     {
555       if (this->_M_impl._M_map)
556         {
557           _M_destroy_nodes(this->_M_impl._M_start._M_node,
558                            this->_M_impl._M_finish._M_node + 1);
559           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
560         }
561     }
562
563   /**
564    *  @brief Layout storage.
565    *  @param  num_elements  The count of T's for which to allocate space
566    *                        at first.
567    *  @return   Nothing.
568    *
569    *  The initial underlying memory layout is a bit complicated...
570   */
571   template<typename _Tp, typename _Alloc>
572     void
573     _Deque_base<_Tp, _Alloc>::
574     _M_initialize_map(size_t __num_elements)
575     {
576       const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
577                                   + 1);
578
579       this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
580                                            size_t(__num_nodes + 2));
581       this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
582
583       // For "small" maps (needing less than _M_map_size nodes), allocation
584       // starts in the middle elements and grows outwards.  So nstart may be
585       // the beginning of _M_map, but for small maps it may be as far in as
586       // _M_map+3.
587
588       _Tp** __nstart = (this->_M_impl._M_map
589                         + (this->_M_impl._M_map_size - __num_nodes) / 2);
590       _Tp** __nfinish = __nstart + __num_nodes;
591
592       __try
593         { _M_create_nodes(__nstart, __nfinish); }
594       __catch(...)
595         {
596           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
597           this->_M_impl._M_map = 0;
598           this->_M_impl._M_map_size = 0;
599           __throw_exception_again;
600         }
601
602       this->_M_impl._M_start._M_set_node(__nstart);
603       this->_M_impl._M_finish._M_set_node(__nfinish - 1);
604       this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
605       this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
606                                         + __num_elements
607                                         % __deque_buf_size(sizeof(_Tp)));
608     }
609
610   template<typename _Tp, typename _Alloc>
611     void
612     _Deque_base<_Tp, _Alloc>::
613     _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
614     {
615       _Tp** __cur;
616       __try
617         {
618           for (__cur = __nstart; __cur < __nfinish; ++__cur)
619             *__cur = this->_M_allocate_node();
620         }
621       __catch(...)
622         {
623           _M_destroy_nodes(__nstart, __cur);
624           __throw_exception_again;
625         }
626     }
627
628   template<typename _Tp, typename _Alloc>
629     void
630     _Deque_base<_Tp, _Alloc>::
631     _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
632     {
633       for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
634         _M_deallocate_node(*__n);
635     }
636
637   /**
638    *  @brief  A standard container using fixed-size memory allocation and
639    *  constant-time manipulation of elements at either end.
640    *
641    *  @ingroup sequences
642    *
643    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
644    *  <a href="tables.html#66">reversible container</a>, and a
645    *  <a href="tables.html#67">sequence</a>, including the
646    *  <a href="tables.html#68">optional sequence requirements</a>.
647    *
648    *  In previous HP/SGI versions of deque, there was an extra template
649    *  parameter so users could control the node size.  This extension turned
650    *  out to violate the C++ standard (it can be detected using template
651    *  template parameters), and it was removed.
652    *
653    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
654    *
655    *  - Tp**        _M_map
656    *  - size_t      _M_map_size
657    *  - iterator    _M_start, _M_finish
658    *
659    *  map_size is at least 8.  %map is an array of map_size
660    *  pointers-to-@anodes.  (The name %map has nothing to do with the
661    *  std::map class, and @b nodes should not be confused with
662    *  std::list's usage of @a node.)
663    *
664    *  A @a node has no specific type name as such, but it is referred
665    *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp
666    *  is very large, there will be one Tp element per node (i.e., an
667    *  @a array of one).  For non-huge Tp's, node size is inversely
668    *  related to Tp size: the larger the Tp, the fewer Tp's will fit
669    *  in a node.  The goal here is to keep the total size of a node
670    *  relatively small and constant over different Tp's, to improve
671    *  allocator efficiency.
672    *
673    *  Not every pointer in the %map array will point to a node.  If
674    *  the initial number of elements in the deque is small, the
675    *  /middle/ %map pointers will be valid, and the ones at the edges
676    *  will be unused.  This same situation will arise as the %map
677    *  grows: available %map pointers, if any, will be on the ends.  As
678    *  new nodes are created, only a subset of the %map's pointers need
679    *  to be copied @a outward.
680    *
681    *  Class invariants:
682    * - For any nonsingular iterator i:
683    *    - i.node points to a member of the %map array.  (Yes, you read that
684    *      correctly:  i.node does not actually point to a node.)  The member of
685    *      the %map array is what actually points to the node.
686    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
687    *    - i.last  == i.first + node_size
688    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
689    *      the implication of this is that i.cur is always a dereferenceable
690    *      pointer, even if i is a past-the-end iterator.
691    * - Start and Finish are always nonsingular iterators.  NOTE: this
692    * means that an empty deque must have one node, a deque with <N
693    * elements (where N is the node buffer size) must have one node, a
694    * deque with N through (2N-1) elements must have two nodes, etc.
695    * - For every node other than start.node and finish.node, every
696    * element in the node is an initialized object.  If start.node ==
697    * finish.node, then [start.cur, finish.cur) are initialized
698    * objects, and the elements outside that range are uninitialized
699    * storage.  Otherwise, [start.cur, start.last) and [finish.first,
700    * finish.cur) are initialized objects, and [start.first, start.cur)
701    * and [finish.cur, finish.last) are uninitialized storage.
702    * - [%map, %map + map_size) is a valid, non-empty range.
703    * - [start.node, finish.node] is a valid range contained within
704    *   [%map, %map + map_size).
705    * - A pointer in the range [%map, %map + map_size) points to an allocated
706    *   node if and only if the pointer is in the range
707    *   [start.node, finish.node].
708    *
709    *  Here's the magic:  nothing in deque is @b aware of the discontiguous
710    *  storage!
711    *
712    *  The memory setup and layout occurs in the parent, _Base, and the iterator
713    *  class is entirely responsible for @a leaping from one node to the next.
714    *  All the implementation routines for deque itself work only through the
715    *  start and finish iterators.  This keeps the routines simple and sane,
716    *  and we can use other standard algorithms as well.
717   */
718   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
719     class deque : protected _Deque_base<_Tp, _Alloc>
720     {
721       // concept requirements
722       typedef typename _Alloc::value_type        _Alloc_value_type;
723       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
724       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
725
726       typedef _Deque_base<_Tp, _Alloc>           _Base;
727       typedef typename _Base::_Tp_alloc_type     _Tp_alloc_type;
728
729     public:
730       typedef _Tp                                        value_type;
731       typedef typename _Tp_alloc_type::pointer           pointer;
732       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
733       typedef typename _Tp_alloc_type::reference         reference;
734       typedef typename _Tp_alloc_type::const_reference   const_reference;
735       typedef typename _Base::iterator                   iterator;
736       typedef typename _Base::const_iterator             const_iterator;
737       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
738       typedef std::reverse_iterator<iterator>            reverse_iterator;
739       typedef size_t                             size_type;
740       typedef ptrdiff_t                          difference_type;
741       typedef _Alloc                             allocator_type;
742
743     protected:
744       typedef pointer*                           _Map_pointer;
745
746       static size_t _S_buffer_size()
747       { return __deque_buf_size(sizeof(_Tp)); }
748
749       // Functions controlling memory layout, and nothing else.
750       using _Base::_M_initialize_map;
751       using _Base::_M_create_nodes;
752       using _Base::_M_destroy_nodes;
753       using _Base::_M_allocate_node;
754       using _Base::_M_deallocate_node;
755       using _Base::_M_allocate_map;
756       using _Base::_M_deallocate_map;
757       using _Base::_M_get_Tp_allocator;
758
759       /** 
760        *  A total of four data members accumulated down the hierarchy.
761        *  May be accessed via _M_impl.*
762        */
763       using _Base::_M_impl;
764
765     public:
766       // [23.2.1.1] construct/copy/destroy
767       // (assign() and get_allocator() are also listed in this section)
768       /**
769        *  @brief  Default constructor creates no elements.
770        */
771       deque()
772       : _Base() { }
773
774       /**
775        *  @brief  Creates a %deque with no elements.
776        *  @param  a  An allocator object.
777        */
778       explicit
779       deque(const allocator_type& __a)
780       : _Base(__a, 0) { }
781
782 #ifdef __GXX_EXPERIMENTAL_CXX0X__
783       /**
784        *  @brief  Creates a %deque with default constructed elements.
785        *  @param  n  The number of elements to initially create.
786        *
787        *  This constructor fills the %deque with @a n default
788        *  constructed elements.
789        */
790       explicit
791       deque(size_type __n)
792       : _Base(__n)
793       { _M_default_initialize(); }
794
795       /**
796        *  @brief  Creates a %deque with copies of an exemplar element.
797        *  @param  n  The number of elements to initially create.
798        *  @param  value  An element to copy.
799        *  @param  a  An allocator.
800        *
801        *  This constructor fills the %deque with @a n copies of @a value.
802        */
803       deque(size_type __n, const value_type& __value,
804             const allocator_type& __a = allocator_type())
805       : _Base(__a, __n)
806       { _M_fill_initialize(__value); }
807 #else
808       /**
809        *  @brief  Creates a %deque with copies of an exemplar element.
810        *  @param  n  The number of elements to initially create.
811        *  @param  value  An element to copy.
812        *  @param  a  An allocator.
813        *
814        *  This constructor fills the %deque with @a n copies of @a value.
815        */
816       explicit
817       deque(size_type __n, const value_type& __value = value_type(),
818             const allocator_type& __a = allocator_type())
819       : _Base(__a, __n)
820       { _M_fill_initialize(__value); }
821 #endif
822
823       /**
824        *  @brief  %Deque copy constructor.
825        *  @param  x  A %deque of identical element and allocator types.
826        *
827        *  The newly-created %deque uses a copy of the allocation object used
828        *  by @a x.
829        */
830       deque(const deque& __x)
831       : _Base(__x._M_get_Tp_allocator(), __x.size())
832       { std::__uninitialized_copy_a(__x.begin(), __x.end(), 
833                                     this->_M_impl._M_start,
834                                     _M_get_Tp_allocator()); }
835
836 #ifdef __GXX_EXPERIMENTAL_CXX0X__
837       /**
838        *  @brief  %Deque move constructor.
839        *  @param  x  A %deque of identical element and allocator types.
840        *
841        *  The newly-created %deque contains the exact contents of @a x.
842        *  The contents of @a x are a valid, but unspecified %deque.
843        */
844       deque(deque&& __x)
845       : _Base(std::move(__x)) { }
846
847       /**
848        *  @brief  Builds a %deque from an initializer list.
849        *  @param  l  An initializer_list.
850        *  @param  a  An allocator object.
851        *
852        *  Create a %deque consisting of copies of the elements in the
853        *  initializer_list @a l.
854        *
855        *  This will call the element type's copy constructor N times
856        *  (where N is l.size()) and do no memory reallocation.
857        */
858       deque(initializer_list<value_type> __l,
859             const allocator_type& __a = allocator_type())
860       : _Base(__a)
861       {
862         _M_range_initialize(__l.begin(), __l.end(),
863                             random_access_iterator_tag());
864       }
865 #endif
866
867       /**
868        *  @brief  Builds a %deque from a range.
869        *  @param  first  An input iterator.
870        *  @param  last  An input iterator.
871        *  @param  a  An allocator object.
872        *
873        *  Create a %deque consisting of copies of the elements from [first,
874        *  last).
875        *
876        *  If the iterators are forward, bidirectional, or random-access, then
877        *  this will call the elements' copy constructor N times (where N is
878        *  distance(first,last)) and do no memory reallocation.  But if only
879        *  input iterators are used, then this will do at most 2N calls to the
880        *  copy constructor, and logN memory reallocations.
881        */
882       template<typename _InputIterator>
883         deque(_InputIterator __first, _InputIterator __last,
884               const allocator_type& __a = allocator_type())
885         : _Base(__a)
886         {
887           // Check whether it's an integral type.  If so, it's not an iterator.
888           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
889           _M_initialize_dispatch(__first, __last, _Integral());
890         }
891
892       /**
893        *  The dtor only erases the elements, and note that if the elements
894        *  themselves are pointers, the pointed-to memory is not touched in any
895        *  way.  Managing the pointer is the user's responsibility.
896        */
897       ~deque()
898       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
899
900       /**
901        *  @brief  %Deque assignment operator.
902        *  @param  x  A %deque of identical element and allocator types.
903        *
904        *  All the elements of @a x are copied, but unlike the copy constructor,
905        *  the allocator object is not copied.
906        */
907       deque&
908       operator=(const deque& __x);
909
910 #ifdef __GXX_EXPERIMENTAL_CXX0X__
911       /**
912        *  @brief  %Deque move assignment operator.
913        *  @param  x  A %deque of identical element and allocator types.
914        *
915        *  The contents of @a x are moved into this deque (without copying).
916        *  @a x is a valid, but unspecified %deque.
917        */
918       deque&
919       operator=(deque&& __x)
920       {
921         // NB: DR 1204.
922         // NB: DR 675.
923         this->clear();
924         this->swap(__x);
925         return *this;
926       }
927
928       /**
929        *  @brief  Assigns an initializer list to a %deque.
930        *  @param  l  An initializer_list.
931        *
932        *  This function fills a %deque with copies of the elements in the
933        *  initializer_list @a l.
934        *
935        *  Note that the assignment completely changes the %deque and that the
936        *  resulting %deque's size is the same as the number of elements
937        *  assigned.  Old data may be lost.
938        */
939       deque&
940       operator=(initializer_list<value_type> __l)
941       {
942         this->assign(__l.begin(), __l.end());
943         return *this;
944       }
945 #endif
946
947       /**
948        *  @brief  Assigns a given value to a %deque.
949        *  @param  n  Number of elements to be assigned.
950        *  @param  val  Value to be assigned.
951        *
952        *  This function fills a %deque with @a n copies of the given
953        *  value.  Note that the assignment completely changes the
954        *  %deque and that the resulting %deque's size is the same as
955        *  the number of elements assigned.  Old data may be lost.
956        */
957       void
958       assign(size_type __n, const value_type& __val)
959       { _M_fill_assign(__n, __val); }
960
961       /**
962        *  @brief  Assigns a range to a %deque.
963        *  @param  first  An input iterator.
964        *  @param  last   An input iterator.
965        *
966        *  This function fills a %deque with copies of the elements in the
967        *  range [first,last).
968        *
969        *  Note that the assignment completely changes the %deque and that the
970        *  resulting %deque's size is the same as the number of elements
971        *  assigned.  Old data may be lost.
972        */
973       template<typename _InputIterator>
974         void
975         assign(_InputIterator __first, _InputIterator __last)
976         {
977           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
978           _M_assign_dispatch(__first, __last, _Integral());
979         }
980
981 #ifdef __GXX_EXPERIMENTAL_CXX0X__
982       /**
983        *  @brief  Assigns an initializer list to a %deque.
984        *  @param  l  An initializer_list.
985        *
986        *  This function fills a %deque with copies of the elements in the
987        *  initializer_list @a l.
988        *
989        *  Note that the assignment completely changes the %deque and that the
990        *  resulting %deque's size is the same as the number of elements
991        *  assigned.  Old data may be lost.
992        */
993       void
994       assign(initializer_list<value_type> __l)
995       { this->assign(__l.begin(), __l.end()); }
996 #endif
997
998       /// Get a copy of the memory allocation object.
999       allocator_type
1000       get_allocator() const _GLIBCXX_NOEXCEPT
1001       { return _Base::get_allocator(); }
1002
1003       // iterators
1004       /**
1005        *  Returns a read/write iterator that points to the first element in the
1006        *  %deque.  Iteration is done in ordinary element order.
1007        */
1008       iterator
1009       begin() _GLIBCXX_NOEXCEPT
1010       { return this->_M_impl._M_start; }
1011
1012       /**
1013        *  Returns a read-only (constant) iterator that points to the first
1014        *  element in the %deque.  Iteration is done in ordinary element order.
1015        */
1016       const_iterator
1017       begin() const _GLIBCXX_NOEXCEPT
1018       { return this->_M_impl._M_start; }
1019
1020       /**
1021        *  Returns a read/write iterator that points one past the last
1022        *  element in the %deque.  Iteration is done in ordinary
1023        *  element order.
1024        */
1025       iterator
1026       end() _GLIBCXX_NOEXCEPT
1027       { return this->_M_impl._M_finish; }
1028
1029       /**
1030        *  Returns a read-only (constant) iterator that points one past
1031        *  the last element in the %deque.  Iteration is done in
1032        *  ordinary element order.
1033        */
1034       const_iterator
1035       end() const _GLIBCXX_NOEXCEPT
1036       { return this->_M_impl._M_finish; }
1037
1038       /**
1039        *  Returns a read/write reverse iterator that points to the
1040        *  last element in the %deque.  Iteration is done in reverse
1041        *  element order.
1042        */
1043       reverse_iterator
1044       rbegin() _GLIBCXX_NOEXCEPT
1045       { return reverse_iterator(this->_M_impl._M_finish); }
1046
1047       /**
1048        *  Returns a read-only (constant) reverse iterator that points
1049        *  to the last element in the %deque.  Iteration is done in
1050        *  reverse element order.
1051        */
1052       const_reverse_iterator
1053       rbegin() const _GLIBCXX_NOEXCEPT
1054       { return const_reverse_iterator(this->_M_impl._M_finish); }
1055
1056       /**
1057        *  Returns a read/write reverse iterator that points to one
1058        *  before the first element in the %deque.  Iteration is done
1059        *  in reverse element order.
1060        */
1061       reverse_iterator
1062       rend() _GLIBCXX_NOEXCEPT
1063       { return reverse_iterator(this->_M_impl._M_start); }
1064
1065       /**
1066        *  Returns a read-only (constant) reverse iterator that points
1067        *  to one before the first element in the %deque.  Iteration is
1068        *  done in reverse element order.
1069        */
1070       const_reverse_iterator
1071       rend() const _GLIBCXX_NOEXCEPT
1072       { return const_reverse_iterator(this->_M_impl._M_start); }
1073
1074 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1075       /**
1076        *  Returns a read-only (constant) iterator that points to the first
1077        *  element in the %deque.  Iteration is done in ordinary element order.
1078        */
1079       const_iterator
1080       cbegin() const noexcept
1081       { return this->_M_impl._M_start; }
1082
1083       /**
1084        *  Returns a read-only (constant) iterator that points one past
1085        *  the last element in the %deque.  Iteration is done in
1086        *  ordinary element order.
1087        */
1088       const_iterator
1089       cend() const noexcept
1090       { return this->_M_impl._M_finish; }
1091
1092       /**
1093        *  Returns a read-only (constant) reverse iterator that points
1094        *  to the last element in the %deque.  Iteration is done in
1095        *  reverse element order.
1096        */
1097       const_reverse_iterator
1098       crbegin() const noexcept
1099       { return const_reverse_iterator(this->_M_impl._M_finish); }
1100
1101       /**
1102        *  Returns a read-only (constant) reverse iterator that points
1103        *  to one before the first element in the %deque.  Iteration is
1104        *  done in reverse element order.
1105        */
1106       const_reverse_iterator
1107       crend() const noexcept
1108       { return const_reverse_iterator(this->_M_impl._M_start); }
1109 #endif
1110
1111       // [23.2.1.2] capacity
1112       /**  Returns the number of elements in the %deque.  */
1113       size_type
1114       size() const _GLIBCXX_NOEXCEPT
1115       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
1116
1117       /**  Returns the size() of the largest possible %deque.  */
1118       size_type
1119       max_size() const _GLIBCXX_NOEXCEPT
1120       { return _M_get_Tp_allocator().max_size(); }
1121
1122 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1123       /**
1124        *  @brief  Resizes the %deque to the specified number of elements.
1125        *  @param  new_size  Number of elements the %deque should contain.
1126        *
1127        *  This function will %resize the %deque to the specified
1128        *  number of elements.  If the number is smaller than the
1129        *  %deque's current size the %deque is truncated, otherwise
1130        *  default constructed elements are appended.
1131        */
1132       void
1133       resize(size_type __new_size)
1134       {
1135         const size_type __len = size();
1136         if (__new_size > __len)
1137           _M_default_append(__new_size - __len);
1138         else if (__new_size < __len)
1139           _M_erase_at_end(this->_M_impl._M_start
1140                           + difference_type(__new_size));
1141       }
1142
1143       /**
1144        *  @brief  Resizes the %deque to the specified number of elements.
1145        *  @param  new_size  Number of elements the %deque should contain.
1146        *  @param  x  Data with which new elements should be populated.
1147        *
1148        *  This function will %resize the %deque to the specified
1149        *  number of elements.  If the number is smaller than the
1150        *  %deque's current size the %deque is truncated, otherwise the
1151        *  %deque is extended and new elements are populated with given
1152        *  data.
1153        */
1154       void
1155       resize(size_type __new_size, const value_type& __x)
1156       {
1157         const size_type __len = size();
1158         if (__new_size > __len)
1159           insert(this->_M_impl._M_finish, __new_size - __len, __x);
1160         else if (__new_size < __len)
1161           _M_erase_at_end(this->_M_impl._M_start
1162                           + difference_type(__new_size));
1163       }
1164 #else
1165       /**
1166        *  @brief  Resizes the %deque to the specified number of elements.
1167        *  @param  new_size  Number of elements the %deque should contain.
1168        *  @param  x  Data with which new elements should be populated.
1169        *
1170        *  This function will %resize the %deque to the specified
1171        *  number of elements.  If the number is smaller than the
1172        *  %deque's current size the %deque is truncated, otherwise the
1173        *  %deque is extended and new elements are populated with given
1174        *  data.
1175        */
1176       void
1177       resize(size_type __new_size, value_type __x = value_type())
1178       {
1179         const size_type __len = size();
1180         if (__new_size > __len)
1181           insert(this->_M_impl._M_finish, __new_size - __len, __x);
1182         else if (__new_size < __len)
1183           _M_erase_at_end(this->_M_impl._M_start
1184                           + difference_type(__new_size));
1185       }
1186 #endif
1187
1188 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1189       /**  A non-binding request to reduce memory use.  */
1190       void
1191       shrink_to_fit()
1192       { std::__shrink_to_fit<deque>::_S_do_it(*this); }
1193 #endif
1194
1195       /**
1196        *  Returns true if the %deque is empty.  (Thus begin() would
1197        *  equal end().)
1198        */
1199       bool
1200       empty() const _GLIBCXX_NOEXCEPT
1201       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
1202
1203       // element access
1204       /**
1205        *  @brief Subscript access to the data contained in the %deque.
1206        *  @param n The index of the element for which data should be
1207        *  accessed.
1208        *  @return  Read/write reference to data.
1209        *
1210        *  This operator allows for easy, array-style, data access.
1211        *  Note that data access with this operator is unchecked and
1212        *  out_of_range lookups are not defined. (For checked lookups
1213        *  see at().)
1214        */
1215       reference
1216       operator[](size_type __n)
1217       { return this->_M_impl._M_start[difference_type(__n)]; }
1218
1219       /**
1220        *  @brief Subscript access to the data contained in the %deque.
1221        *  @param n The index of the element for which data should be
1222        *  accessed.
1223        *  @return  Read-only (constant) reference to data.
1224        *
1225        *  This operator allows for easy, array-style, data access.
1226        *  Note that data access with this operator is unchecked and
1227        *  out_of_range lookups are not defined. (For checked lookups
1228        *  see at().)
1229        */
1230       const_reference
1231       operator[](size_type __n) const
1232       { return this->_M_impl._M_start[difference_type(__n)]; }
1233
1234     protected:
1235       /// Safety check used only from at().
1236       void
1237       _M_range_check(size_type __n) const
1238       {
1239         if (__n >= this->size())
1240           __throw_out_of_range(__N("deque::_M_range_check"));
1241       }
1242
1243     public:
1244       /**
1245        *  @brief  Provides access to the data contained in the %deque.
1246        *  @param n The index of the element for which data should be
1247        *  accessed.
1248        *  @return  Read/write reference to data.
1249        *  @throw  std::out_of_range  If @a n is an invalid index.
1250        *
1251        *  This function provides for safer data access.  The parameter
1252        *  is first checked that it is in the range of the deque.  The
1253        *  function throws out_of_range if the check fails.
1254        */
1255       reference
1256       at(size_type __n)
1257       {
1258         _M_range_check(__n);
1259         return (*this)[__n];
1260       }
1261
1262       /**
1263        *  @brief  Provides access to the data contained in the %deque.
1264        *  @param n The index of the element for which data should be
1265        *  accessed.
1266        *  @return  Read-only (constant) reference to data.
1267        *  @throw  std::out_of_range  If @a n is an invalid index.
1268        *
1269        *  This function provides for safer data access.  The parameter is first
1270        *  checked that it is in the range of the deque.  The function throws
1271        *  out_of_range if the check fails.
1272        */
1273       const_reference
1274       at(size_type __n) const
1275       {
1276         _M_range_check(__n);
1277         return (*this)[__n];
1278       }
1279
1280       /**
1281        *  Returns a read/write reference to the data at the first
1282        *  element of the %deque.
1283        */
1284       reference
1285       front()
1286       { return *begin(); }
1287
1288       /**
1289        *  Returns a read-only (constant) reference to the data at the first
1290        *  element of the %deque.
1291        */
1292       const_reference
1293       front() const
1294       { return *begin(); }
1295
1296       /**
1297        *  Returns a read/write reference to the data at the last element of the
1298        *  %deque.
1299        */
1300       reference
1301       back()
1302       {
1303         iterator __tmp = end();
1304         --__tmp;
1305         return *__tmp;
1306       }
1307
1308       /**
1309        *  Returns a read-only (constant) reference to the data at the last
1310        *  element of the %deque.
1311        */
1312       const_reference
1313       back() const
1314       {
1315         const_iterator __tmp = end();
1316         --__tmp;
1317         return *__tmp;
1318       }
1319
1320       // [23.2.1.2] modifiers
1321       /**
1322        *  @brief  Add data to the front of the %deque.
1323        *  @param  x  Data to be added.
1324        *
1325        *  This is a typical stack operation.  The function creates an
1326        *  element at the front of the %deque and assigns the given
1327        *  data to it.  Due to the nature of a %deque this operation
1328        *  can be done in constant time.
1329        */
1330       void
1331       push_front(const value_type& __x)
1332       {
1333         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1334           {
1335             this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
1336             --this->_M_impl._M_start._M_cur;
1337           }
1338         else
1339           _M_push_front_aux(__x);
1340       }
1341
1342 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1343       void
1344       push_front(value_type&& __x)
1345       { emplace_front(std::move(__x)); }
1346
1347       template<typename... _Args>
1348         void
1349         emplace_front(_Args&&... __args);
1350 #endif
1351
1352       /**
1353        *  @brief  Add data to the end of the %deque.
1354        *  @param  x  Data to be added.
1355        *
1356        *  This is a typical stack operation.  The function creates an
1357        *  element at the end of the %deque and assigns the given data
1358        *  to it.  Due to the nature of a %deque this operation can be
1359        *  done in constant time.
1360        */
1361       void
1362       push_back(const value_type& __x)
1363       {
1364         if (this->_M_impl._M_finish._M_cur
1365             != this->_M_impl._M_finish._M_last - 1)
1366           {
1367             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
1368             ++this->_M_impl._M_finish._M_cur;
1369           }
1370         else
1371           _M_push_back_aux(__x);
1372       }
1373
1374 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1375       void
1376       push_back(value_type&& __x)
1377       { emplace_back(std::move(__x)); }
1378
1379       template<typename... _Args>
1380         void
1381         emplace_back(_Args&&... __args);
1382 #endif
1383
1384       /**
1385        *  @brief  Removes first element.
1386        *
1387        *  This is a typical stack operation.  It shrinks the %deque by one.
1388        *
1389        *  Note that no data is returned, and if the first element's data is
1390        *  needed, it should be retrieved before pop_front() is called.
1391        */
1392       void
1393       pop_front()
1394       {
1395         if (this->_M_impl._M_start._M_cur
1396             != this->_M_impl._M_start._M_last - 1)
1397           {
1398             this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
1399             ++this->_M_impl._M_start._M_cur;
1400           }
1401         else
1402           _M_pop_front_aux();
1403       }
1404
1405       /**
1406        *  @brief  Removes last element.
1407        *
1408        *  This is a typical stack operation.  It shrinks the %deque by one.
1409        *
1410        *  Note that no data is returned, and if the last element's data is
1411        *  needed, it should be retrieved before pop_back() is called.
1412        */
1413       void
1414       pop_back()
1415       {
1416         if (this->_M_impl._M_finish._M_cur
1417             != this->_M_impl._M_finish._M_first)
1418           {
1419             --this->_M_impl._M_finish._M_cur;
1420             this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
1421           }
1422         else
1423           _M_pop_back_aux();
1424       }
1425
1426 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1427       /**
1428        *  @brief  Inserts an object in %deque before specified iterator.
1429        *  @param  position  An iterator into the %deque.
1430        *  @param  args  Arguments.
1431        *  @return  An iterator that points to the inserted data.
1432        *
1433        *  This function will insert an object of type T constructed
1434        *  with T(std::forward<Args>(args)...) before the specified location.
1435        */
1436       template<typename... _Args>
1437         iterator
1438         emplace(iterator __position, _Args&&... __args);
1439 #endif
1440
1441       /**
1442        *  @brief  Inserts given value into %deque before specified iterator.
1443        *  @param  position  An iterator into the %deque.
1444        *  @param  x  Data to be inserted.
1445        *  @return  An iterator that points to the inserted data.
1446        *
1447        *  This function will insert a copy of the given value before the
1448        *  specified location.
1449        */
1450       iterator
1451       insert(iterator __position, const value_type& __x);
1452
1453 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1454       /**
1455        *  @brief  Inserts given rvalue into %deque before specified iterator.
1456        *  @param  position  An iterator into the %deque.
1457        *  @param  x  Data to be inserted.
1458        *  @return  An iterator that points to the inserted data.
1459        *
1460        *  This function will insert a copy of the given rvalue before the
1461        *  specified location.
1462        */
1463       iterator
1464       insert(iterator __position, value_type&& __x)
1465       { return emplace(__position, std::move(__x)); }
1466
1467       /**
1468        *  @brief  Inserts an initializer list into the %deque.
1469        *  @param  p  An iterator into the %deque.
1470        *  @param  l  An initializer_list.
1471        *
1472        *  This function will insert copies of the data in the
1473        *  initializer_list @a l into the %deque before the location
1474        *  specified by @a p.  This is known as <em>list insert</em>.
1475        */
1476       void
1477       insert(iterator __p, initializer_list<value_type> __l)
1478       { this->insert(__p, __l.begin(), __l.end()); }
1479 #endif
1480
1481       /**
1482        *  @brief  Inserts a number of copies of given data into the %deque.
1483        *  @param  position  An iterator into the %deque.
1484        *  @param  n  Number of elements to be inserted.
1485        *  @param  x  Data to be inserted.
1486        *
1487        *  This function will insert a specified number of copies of the given
1488        *  data before the location specified by @a position.
1489        */
1490       void
1491       insert(iterator __position, size_type __n, const value_type& __x)
1492       { _M_fill_insert(__position, __n, __x); }
1493
1494       /**
1495        *  @brief  Inserts a range into the %deque.
1496        *  @param  position  An iterator into the %deque.
1497        *  @param  first  An input iterator.
1498        *  @param  last   An input iterator.
1499        *
1500        *  This function will insert copies of the data in the range
1501        *  [first,last) into the %deque before the location specified
1502        *  by @a pos.  This is known as <em>range insert</em>.
1503        */
1504       template<typename _InputIterator>
1505         void
1506         insert(iterator __position, _InputIterator __first,
1507                _InputIterator __last)
1508         {
1509           // Check whether it's an integral type.  If so, it's not an iterator.
1510           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1511           _M_insert_dispatch(__position, __first, __last, _Integral());
1512         }
1513
1514       /**
1515        *  @brief  Remove element at given position.
1516        *  @param  position  Iterator pointing to element to be erased.
1517        *  @return  An iterator pointing to the next element (or end()).
1518        *
1519        *  This function will erase the element at the given position and thus
1520        *  shorten the %deque by one.
1521        *
1522        *  The user is cautioned that
1523        *  this function only erases the element, and that if the element is
1524        *  itself a pointer, the pointed-to memory is not touched in any way.
1525        *  Managing the pointer is the user's responsibility.
1526        */
1527       iterator
1528       erase(iterator __position);
1529
1530       /**
1531        *  @brief  Remove a range of elements.
1532        *  @param  first  Iterator pointing to the first element to be erased.
1533        *  @param  last  Iterator pointing to one past the last element to be
1534        *                erased.
1535        *  @return  An iterator pointing to the element pointed to by @a last
1536        *           prior to erasing (or end()).
1537        *
1538        *  This function will erase the elements in the range [first,last) and
1539        *  shorten the %deque accordingly.
1540        *
1541        *  The user is cautioned that
1542        *  this function only erases the elements, and that if the elements
1543        *  themselves are pointers, the pointed-to memory is not touched in any
1544        *  way.  Managing the pointer is the user's responsibility.
1545        */
1546       iterator
1547       erase(iterator __first, iterator __last);
1548
1549       /**
1550        *  @brief  Swaps data with another %deque.
1551        *  @param  x  A %deque of the same element and allocator types.
1552        *
1553        *  This exchanges the elements between two deques in constant time.
1554        *  (Four pointers, so it should be quite fast.)
1555        *  Note that the global std::swap() function is specialized such that
1556        *  std::swap(d1,d2) will feed to this function.
1557        */
1558       void
1559       swap(deque& __x)
1560       {
1561         std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
1562         std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
1563         std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
1564         std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
1565
1566         // _GLIBCXX_RESOLVE_LIB_DEFECTS
1567         // 431. Swapping containers with unequal allocators.
1568         std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
1569                                                     __x._M_get_Tp_allocator());
1570       }
1571
1572       /**
1573        *  Erases all the elements.  Note that this function only erases the
1574        *  elements, and that if the elements themselves are pointers, the
1575        *  pointed-to memory is not touched in any way.  Managing the pointer is
1576        *  the user's responsibility.
1577        */
1578       void
1579       clear() _GLIBCXX_NOEXCEPT
1580       { _M_erase_at_end(begin()); }
1581
1582     protected:
1583       // Internal constructor functions follow.
1584
1585       // called by the range constructor to implement [23.1.1]/9
1586
1587       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1588       // 438. Ambiguity in the "do the right thing" clause
1589       template<typename _Integer>
1590         void
1591         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1592         {
1593           _M_initialize_map(static_cast<size_type>(__n));
1594           _M_fill_initialize(__x);
1595         }
1596
1597       // called by the range constructor to implement [23.1.1]/9
1598       template<typename _InputIterator>
1599         void
1600         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1601                                __false_type)
1602         {
1603           typedef typename std::iterator_traits<_InputIterator>::
1604             iterator_category _IterCategory;
1605           _M_range_initialize(__first, __last, _IterCategory());
1606         }
1607
1608       // called by the second initialize_dispatch above
1609       //@{
1610       /**
1611        *  @brief Fills the deque with whatever is in [first,last).
1612        *  @param  first  An input iterator.
1613        *  @param  last  An input iterator.
1614        *  @return   Nothing.
1615        *
1616        *  If the iterators are actually forward iterators (or better), then the
1617        *  memory layout can be done all at once.  Else we move forward using
1618        *  push_back on each value from the iterator.
1619        */
1620       template<typename _InputIterator>
1621         void
1622         _M_range_initialize(_InputIterator __first, _InputIterator __last,
1623                             std::input_iterator_tag);
1624
1625       // called by the second initialize_dispatch above
1626       template<typename _ForwardIterator>
1627         void
1628         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1629                             std::forward_iterator_tag);
1630       //@}
1631
1632       /**
1633        *  @brief Fills the %deque with copies of value.
1634        *  @param  value  Initial value.
1635        *  @return   Nothing.
1636        *  @pre _M_start and _M_finish have already been initialized,
1637        *  but none of the %deque's elements have yet been constructed.
1638        *
1639        *  This function is called only when the user provides an explicit size
1640        *  (with or without an explicit exemplar value).
1641        */
1642       void
1643       _M_fill_initialize(const value_type& __value);
1644
1645 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1646       // called by deque(n).
1647       void
1648       _M_default_initialize();
1649 #endif
1650
1651       // Internal assign functions follow.  The *_aux functions do the actual
1652       // assignment work for the range versions.
1653
1654       // called by the range assign to implement [23.1.1]/9
1655
1656       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1657       // 438. Ambiguity in the "do the right thing" clause
1658       template<typename _Integer>
1659         void
1660         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1661         { _M_fill_assign(__n, __val); }
1662
1663       // called by the range assign to implement [23.1.1]/9
1664       template<typename _InputIterator>
1665         void
1666         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1667                            __false_type)
1668         {
1669           typedef typename std::iterator_traits<_InputIterator>::
1670             iterator_category _IterCategory;
1671           _M_assign_aux(__first, __last, _IterCategory());
1672         }
1673
1674       // called by the second assign_dispatch above
1675       template<typename _InputIterator>
1676         void
1677         _M_assign_aux(_InputIterator __first, _InputIterator __last,
1678                       std::input_iterator_tag);
1679
1680       // called by the second assign_dispatch above
1681       template<typename _ForwardIterator>
1682         void
1683         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1684                       std::forward_iterator_tag)
1685         {
1686           const size_type __len = std::distance(__first, __last);
1687           if (__len > size())
1688             {
1689               _ForwardIterator __mid = __first;
1690               std::advance(__mid, size());
1691               std::copy(__first, __mid, begin());
1692               insert(end(), __mid, __last);
1693             }
1694           else
1695             _M_erase_at_end(std::copy(__first, __last, begin()));
1696         }
1697
1698       // Called by assign(n,t), and the range assign when it turns out
1699       // to be the same thing.
1700       void
1701       _M_fill_assign(size_type __n, const value_type& __val)
1702       {
1703         if (__n > size())
1704           {
1705             std::fill(begin(), end(), __val);
1706             insert(end(), __n - size(), __val);
1707           }
1708         else
1709           {
1710             _M_erase_at_end(begin() + difference_type(__n));
1711             std::fill(begin(), end(), __val);
1712           }
1713       }
1714
1715       //@{
1716       /// Helper functions for push_* and pop_*.
1717 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1718       void _M_push_back_aux(const value_type&);
1719
1720       void _M_push_front_aux(const value_type&);
1721 #else
1722       template<typename... _Args>
1723         void _M_push_back_aux(_Args&&... __args);
1724
1725       template<typename... _Args>
1726         void _M_push_front_aux(_Args&&... __args);
1727 #endif
1728
1729       void _M_pop_back_aux();
1730
1731       void _M_pop_front_aux();
1732       //@}
1733
1734       // Internal insert functions follow.  The *_aux functions do the actual
1735       // insertion work when all shortcuts fail.
1736
1737       // called by the range insert to implement [23.1.1]/9
1738
1739       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1740       // 438. Ambiguity in the "do the right thing" clause
1741       template<typename _Integer>
1742         void
1743         _M_insert_dispatch(iterator __pos,
1744                            _Integer __n, _Integer __x, __true_type)
1745         { _M_fill_insert(__pos, __n, __x); }
1746
1747       // called by the range insert to implement [23.1.1]/9
1748       template<typename _InputIterator>
1749         void
1750         _M_insert_dispatch(iterator __pos,
1751                            _InputIterator __first, _InputIterator __last,
1752                            __false_type)
1753         {
1754           typedef typename std::iterator_traits<_InputIterator>::
1755             iterator_category _IterCategory;
1756           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1757         }
1758
1759       // called by the second insert_dispatch above
1760       template<typename _InputIterator>
1761         void
1762         _M_range_insert_aux(iterator __pos, _InputIterator __first,
1763                             _InputIterator __last, std::input_iterator_tag);
1764
1765       // called by the second insert_dispatch above
1766       template<typename _ForwardIterator>
1767         void
1768         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1769                             _ForwardIterator __last, std::forward_iterator_tag);
1770
1771       // Called by insert(p,n,x), and the range insert when it turns out to be
1772       // the same thing.  Can use fill functions in optimal situations,
1773       // otherwise passes off to insert_aux(p,n,x).
1774       void
1775       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1776
1777       // called by insert(p,x)
1778 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1779       iterator
1780       _M_insert_aux(iterator __pos, const value_type& __x);
1781 #else
1782       template<typename... _Args>
1783         iterator
1784         _M_insert_aux(iterator __pos, _Args&&... __args);
1785 #endif
1786
1787       // called by insert(p,n,x) via fill_insert
1788       void
1789       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1790
1791       // called by range_insert_aux for forward iterators
1792       template<typename _ForwardIterator>
1793         void
1794         _M_insert_aux(iterator __pos,
1795                       _ForwardIterator __first, _ForwardIterator __last,
1796                       size_type __n);
1797
1798
1799       // Internal erase functions follow.
1800
1801       void
1802       _M_destroy_data_aux(iterator __first, iterator __last);
1803
1804       // Called by ~deque().
1805       // NB: Doesn't deallocate the nodes.
1806       template<typename _Alloc1>
1807         void
1808         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
1809         { _M_destroy_data_aux(__first, __last); }
1810
1811       void
1812       _M_destroy_data(iterator __first, iterator __last,
1813                       const std::allocator<_Tp>&)
1814       {
1815         if (!__has_trivial_destructor(value_type))
1816           _M_destroy_data_aux(__first, __last);
1817       }
1818
1819       // Called by erase(q1, q2).
1820       void
1821       _M_erase_at_begin(iterator __pos)
1822       {
1823         _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
1824         _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
1825         this->_M_impl._M_start = __pos;
1826       }
1827
1828       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
1829       // _M_fill_assign, operator=.
1830       void
1831       _M_erase_at_end(iterator __pos)
1832       {
1833         _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
1834         _M_destroy_nodes(__pos._M_node + 1,
1835                          this->_M_impl._M_finish._M_node + 1);
1836         this->_M_impl._M_finish = __pos;
1837       }
1838
1839 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1840       // Called by resize(sz).
1841       void
1842       _M_default_append(size_type __n);
1843 #endif
1844
1845       //@{
1846       /// Memory-handling helpers for the previous internal insert functions.
1847       iterator
1848       _M_reserve_elements_at_front(size_type __n)
1849       {
1850         const size_type __vacancies = this->_M_impl._M_start._M_cur
1851                                       - this->_M_impl._M_start._M_first;
1852         if (__n > __vacancies)
1853           _M_new_elements_at_front(__n - __vacancies);
1854         return this->_M_impl._M_start - difference_type(__n);
1855       }
1856
1857       iterator
1858       _M_reserve_elements_at_back(size_type __n)
1859       {
1860         const size_type __vacancies = (this->_M_impl._M_finish._M_last
1861                                        - this->_M_impl._M_finish._M_cur) - 1;
1862         if (__n > __vacancies)
1863           _M_new_elements_at_back(__n - __vacancies);
1864         return this->_M_impl._M_finish + difference_type(__n);
1865       }
1866
1867       void
1868       _M_new_elements_at_front(size_type __new_elements);
1869
1870       void
1871       _M_new_elements_at_back(size_type __new_elements);
1872       //@}
1873
1874
1875       //@{
1876       /**
1877        *  @brief Memory-handling helpers for the major %map.
1878        *
1879        *  Makes sure the _M_map has space for new nodes.  Does not
1880        *  actually add the nodes.  Can invalidate _M_map pointers.
1881        *  (And consequently, %deque iterators.)
1882        */
1883       void
1884       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
1885       {
1886         if (__nodes_to_add + 1 > this->_M_impl._M_map_size
1887             - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
1888           _M_reallocate_map(__nodes_to_add, false);
1889       }
1890
1891       void
1892       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
1893       {
1894         if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
1895                                        - this->_M_impl._M_map))
1896           _M_reallocate_map(__nodes_to_add, true);
1897       }
1898
1899       void
1900       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1901       //@}
1902     };
1903
1904
1905   /**
1906    *  @brief  Deque equality comparison.
1907    *  @param  x  A %deque.
1908    *  @param  y  A %deque of the same type as @a x.
1909    *  @return  True iff the size and elements of the deques are equal.
1910    *
1911    *  This is an equivalence relation.  It is linear in the size of the
1912    *  deques.  Deques are considered equivalent if their sizes are equal,
1913    *  and if corresponding elements compare equal.
1914   */
1915   template<typename _Tp, typename _Alloc>
1916     inline bool
1917     operator==(const deque<_Tp, _Alloc>& __x,
1918                          const deque<_Tp, _Alloc>& __y)
1919     { return __x.size() == __y.size()
1920              && std::equal(__x.begin(), __x.end(), __y.begin()); }
1921
1922   /**
1923    *  @brief  Deque ordering relation.
1924    *  @param  x  A %deque.
1925    *  @param  y  A %deque of the same type as @a x.
1926    *  @return  True iff @a x is lexicographically less than @a y.
1927    *
1928    *  This is a total ordering relation.  It is linear in the size of the
1929    *  deques.  The elements must be comparable with @c <.
1930    *
1931    *  See std::lexicographical_compare() for how the determination is made.
1932   */
1933   template<typename _Tp, typename _Alloc>
1934     inline bool
1935     operator<(const deque<_Tp, _Alloc>& __x,
1936               const deque<_Tp, _Alloc>& __y)
1937     { return std::lexicographical_compare(__x.begin(), __x.end(),
1938                                           __y.begin(), __y.end()); }
1939
1940   /// Based on operator==
1941   template<typename _Tp, typename _Alloc>
1942     inline bool
1943     operator!=(const deque<_Tp, _Alloc>& __x,
1944                const deque<_Tp, _Alloc>& __y)
1945     { return !(__x == __y); }
1946
1947   /// Based on operator<
1948   template<typename _Tp, typename _Alloc>
1949     inline bool
1950     operator>(const deque<_Tp, _Alloc>& __x,
1951               const deque<_Tp, _Alloc>& __y)
1952     { return __y < __x; }
1953
1954   /// Based on operator<
1955   template<typename _Tp, typename _Alloc>
1956     inline bool
1957     operator<=(const deque<_Tp, _Alloc>& __x,
1958                const deque<_Tp, _Alloc>& __y)
1959     { return !(__y < __x); }
1960
1961   /// Based on operator<
1962   template<typename _Tp, typename _Alloc>
1963     inline bool
1964     operator>=(const deque<_Tp, _Alloc>& __x,
1965                const deque<_Tp, _Alloc>& __y)
1966     { return !(__x < __y); }
1967
1968   /// See std::deque::swap().
1969   template<typename _Tp, typename _Alloc>
1970     inline void
1971     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
1972     { __x.swap(__y); }
1973
1974 #undef _GLIBCXX_DEQUE_BUF_SIZE
1975
1976 _GLIBCXX_END_NAMESPACE_CONTAINER
1977 } // namespace std
1978
1979 #endif /* _STL_DEQUE_H */