1 // deque implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
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)
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.
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,
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.
33 * Hewlett-Packard Company
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.
45 * Silicon Graphics Computer Systems, Inc.
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.
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
61 #include <bits/concept_check.h>
62 #include <bits/stl_iterator_base_types.h>
63 #include <bits/stl_iterator_base_funcs.h>
65 #ifndef __GLIBCPP_INTERNAL_DEQUE_H
66 #define __GLIBCPP_INTERNAL_DEQUE_H
69 // Since this entire file is within namespace std, there's no reason to
70 // waste two spaces along the left column. Thus the leading indentation is
71 // slightly violated from here on.
77 * @brief This function controls the size of memory nodes.
78 * @param size The size of an element.
79 * @return The number (not bytesize) of elements per node.
81 * This function started off as a compiler kludge from SGI, but seems to
82 * be a useful wrapper around a repeated constant expression.
86 __deque_buf_size(size_t __size)
87 { return __size < 512 ? size_t(512 / __size) : size_t(1); }
90 /// A deque::iterator.
92 * Quite a bit of intelligence here. Much of the functionality of deque is
93 * actually passed off to this class. A deque holds two of these internally,
94 * marking its valid range. Access to elements is done as offsets of either
95 * of those two, relying on operator overloading in this class.
98 * All the functions are op overloads except for _M_set_node.
101 template <class _Tp, class _Ref, class _Ptr>
102 struct _Deque_iterator
104 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
105 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
106 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
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;
120 _Map_pointer _M_node;
122 _Deque_iterator(_Tp* __x, _Map_pointer __y)
123 : _M_cur(__x), _M_first(*__y),
124 _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
125 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
126 _Deque_iterator(const iterator& __x)
127 : _M_cur(__x._M_cur), _M_first(__x._M_first),
128 _M_last(__x._M_last), _M_node(__x._M_node) {}
130 reference operator*() const { return *_M_cur; }
131 pointer operator->() const { return _M_cur; }
133 _Self& operator++() {
135 if (_M_cur == _M_last) {
136 _M_set_node(_M_node + 1);
141 _Self operator++(int) {
147 _Self& operator--() {
148 if (_M_cur == _M_first) {
149 _M_set_node(_M_node - 1);
155 _Self operator--(int) {
161 _Self& operator+=(difference_type __n)
163 difference_type __offset = __n + (_M_cur - _M_first);
164 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
167 difference_type __node_offset =
168 __offset > 0 ? __offset / difference_type(_S_buffer_size())
169 : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
170 _M_set_node(_M_node + __node_offset);
172 (__offset - __node_offset * difference_type(_S_buffer_size()));
177 _Self operator+(difference_type __n) const
183 _Self& operator-=(difference_type __n) { return *this += -__n; }
185 _Self operator-(difference_type __n) const {
190 reference operator[](difference_type __n) const { return *(*this + __n); }
193 * Prepares to traverse new_node. Sets everything except _M_cur, which
194 * should therefore be set by the caller immediately afterwards, based on
195 * _M_first and _M_last.
198 void _M_set_node(_Map_pointer __new_node) {
199 _M_node = __new_node;
200 _M_first = *__new_node;
201 _M_last = _M_first + difference_type(_S_buffer_size());
205 // Note: we also provide overloads whose operands are of the same type in
206 // order to avoid ambiguos overload resolution when std::rel_ops operators
207 // are in scope (for additional details, see libstdc++/3628)
208 template <class _Tp, class _Ref, class _Ptr>
210 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
211 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
213 return __x._M_cur == __y._M_cur;
216 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
218 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
219 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
221 return __x._M_cur == __y._M_cur;
224 template <class _Tp, class _Ref, class _Ptr>
226 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
227 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
229 return !(__x == __y);
232 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
234 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
235 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
237 return !(__x == __y);
240 template <class _Tp, class _Ref, class _Ptr>
242 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
243 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
245 return (__x._M_node == __y._M_node) ?
246 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
249 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
251 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
252 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
254 return (__x._M_node == __y._M_node) ?
255 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
258 template <class _Tp, class _Ref, class _Ptr>
260 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
261 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
266 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
268 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
269 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
274 template <class _Tp, class _Ref, class _Ptr>
276 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
277 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
282 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
284 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
285 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
290 template <class _Tp, class _Ref, class _Ptr>
292 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
293 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
298 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
300 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
301 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
306 // _GLIBCPP_RESOLVE_LIB_DEFECTS
307 // According to the resolution of DR179 not only the various comparison
308 // operators but also operator- must accept mixed iterator/const_iterator
310 template <typename _Tp, typename _RefL, typename _PtrL,
311 typename _RefR, typename _PtrR>
312 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
313 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
314 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
316 return _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
317 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) *
318 (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) +
319 (__y._M_last - __y._M_cur);
322 template <class _Tp, class _Ref, class _Ptr>
323 inline _Deque_iterator<_Tp, _Ref, _Ptr>
324 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
330 /// @if maint Primary default version. @endif
333 * Deque base class. It has two purposes. First, its constructor
334 * and destructor allocate (but don't initialize) storage. This makes
335 * exception safety easier. Second, the base class encapsulates all of
336 * the differences between SGI-style allocators and standard-conforming
337 * allocators. There are two versions: this ordinary one, and the
338 * space-saving specialization for instanceless allocators.
341 template <class _Tp, class _Alloc, bool __is_static>
342 class _Deque_alloc_base
345 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
346 allocator_type get_allocator() const { return _M_node_allocator; }
348 _Deque_alloc_base(const allocator_type& __a)
349 : _M_node_allocator(__a), _M_map_allocator(__a),
350 _M_map(0), _M_map_size(0)
354 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
357 allocator_type _M_node_allocator;
358 _Map_allocator_type _M_map_allocator;
360 _Tp* _M_allocate_node() {
361 return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
363 void _M_deallocate_node(_Tp* __p) {
364 _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
366 _Tp** _M_allocate_map(size_t __n)
367 { return _M_map_allocator.allocate(__n); }
368 void _M_deallocate_map(_Tp** __p, size_t __n)
369 { _M_map_allocator.deallocate(__p, __n); }
375 /// @if maint Specialization for instanceless allocators. @endif
376 template <class _Tp, class _Alloc>
377 class _Deque_alloc_base<_Tp, _Alloc, true>
380 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
381 allocator_type get_allocator() const { return allocator_type(); }
383 _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
386 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
387 typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
389 _Tp* _M_allocate_node() {
390 return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
392 void _M_deallocate_node(_Tp* __p) {
393 _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
395 _Tp** _M_allocate_map(size_t __n)
396 { return _Map_alloc_type::allocate(__n); }
397 void _M_deallocate_map(_Tp** __p, size_t __n)
398 { _Map_alloc_type::deallocate(__p, __n); }
407 * Deque base class. Using _Alloc_traits in the instantiation of the parent
408 * class provides the compile-time dispatching mentioned in the parent's docs.
409 * This class provides the unified face for deque's allocation.
411 * Nothing in this class ever constructs or destroys an actual Tp element.
412 * (Deque handles that itself.) Only/All memory management is performed here.
415 template <class _Tp, class _Alloc>
417 : public _Deque_alloc_base<_Tp,_Alloc,
418 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
421 typedef _Deque_alloc_base<_Tp,_Alloc,
422 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
424 typedef typename _Base::allocator_type allocator_type;
425 typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
426 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
428 _Deque_base(const allocator_type& __a, size_t __num_elements)
429 : _Base(__a), _M_start(), _M_finish()
430 { _M_initialize_map(__num_elements); }
431 _Deque_base(const allocator_type& __a)
432 : _Base(__a), _M_start(), _M_finish() {}
436 void _M_initialize_map(size_t);
437 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
438 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
439 enum { _S_initial_map_size = 8 };
447 template <class _Tp, class _Alloc>
448 _Deque_base<_Tp,_Alloc>::~_Deque_base()
451 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
452 _M_deallocate_map(_M_map, _M_map_size);
458 * @brief Layout storage.
459 * @param num_elements The count of T's for which to allocate space at first.
462 * The initial underlying memory layout is a bit complicated...
465 template <class _Tp, class _Alloc>
467 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
470 __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
472 _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
473 _M_map = _M_allocate_map(_M_map_size);
475 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
476 _Tp** __nfinish = __nstart + __num_nodes;
479 { _M_create_nodes(__nstart, __nfinish); }
482 _M_deallocate_map(_M_map, _M_map_size);
485 __throw_exception_again;
488 _M_start._M_set_node(__nstart);
489 _M_finish._M_set_node(__nfinish - 1);
490 _M_start._M_cur = _M_start._M_first;
491 _M_finish._M_cur = _M_finish._M_first +
492 __num_elements % __deque_buf_size(sizeof(_Tp));
495 template <class _Tp, class _Alloc>
496 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
500 for (__cur = __nstart; __cur < __nfinish; ++__cur)
501 *__cur = _M_allocate_node();
505 _M_destroy_nodes(__nstart, __cur);
506 __throw_exception_again;
510 template <class _Tp, class _Alloc>
512 _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
514 for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
515 _M_deallocate_node(*__n);
520 * @ingroup Containers
523 * Meets the requirements of a <a href="tables.html#65">container</a>, a
524 * <a href="tables.html#66">reversible container</a>, and a
525 * <a href="tables.html#67">sequence</a>, including the
526 * <a href="tables.html#68">optional sequence requirements</a>.
528 * Placeholder: see http://www.sgi.com/tech/stl/Deque.html for now.
530 * In previous HP/SGI versions of deque, there was an extra template parameter
531 * so users could control the node size. This extension turned out to violate
532 * the C++ standard (it can be detected using template template parameters),
533 * and it was removed.
536 * Here's how a deque<Tp> manages memory. Each deque has 4 members:
539 * - size_t _M_map_size
540 * - iterator _M_start, _M_finish
542 * map_size is at least 8. %map is an array of map_size pointers-to-"nodes".
543 * (The name has nothing to do with the std::map class.)
545 * A "node" has no specific type name as such, but it is referred to as
546 * "node" in this file. It is a simple array-of-Tp. If Tp is very large,
547 * there will be one Tp element per node (i.e., an "array" of one).
548 * For non-huge Tp's, node size is inversely related to Tp size: the
549 * larger the Tp, the fewer Tp's will fit in a node. The goal here is to
550 * keep the total size of a node relatively small and constant over different
551 * Tp's, to improve allocator efficiency.
553 * **** As I write this, the nodes are /not/ allocated using the high-speed
554 * memory pool. There are 20 hours left in the year; perhaps I can fix
557 * Not every pointer in the %map array will point to a node. If the initial
558 * number of elements in the deque is small, the /middle/ %map pointers will
559 * be valid, and the ones at the edges will be unused. This same situation
560 * will arise as the %map grows: available %map pointers, if any, will be on
561 * the ends. As new nodes are created, only a subset of the %map's pointers
562 * need to be copied "outward".
565 * - For any nonsingular iterator i:
566 * - i.node points to a member of the %map array. (Yes, you read that
567 * correctly: i.node does not actually point to a node.) The member of
568 * the %map array is what actually points to the node.
569 * - i.first == *(i.node) (This points to the node (first Tp element).)
570 * - i.last == i.first + node_size
571 * - i.cur is a pointer in the range [i.first, i.last). NOTE:
572 * the implication of this is that i.cur is always a dereferenceable
573 * pointer, even if i is a past-the-end iterator.
574 * - Start and Finish are always nonsingular iterators. NOTE: this means that
575 * an empty deque must have one node, a deque with <N elements (where N is
576 * the node buffer size) must have one node, a deque with N through (2N-1)
577 * elements must have two nodes, etc.
578 * - For every node other than start.node and finish.node, every element in the
579 * node is an initialized object. If start.node == finish.node, then
580 * [start.cur, finish.cur) are initialized objects, and the elements outside
581 * that range are uninitialized storage. Otherwise, [start.cur, start.last)
582 * and [finish.first, finish.cur) are initialized objects, and [start.first,
583 * start.cur) and [finish.cur, finish.last) are uninitialized storage.
584 * - [%map, %map + map_size) is a valid, non-empty range.
585 * - [start.node, finish.node] is a valid range contained within
586 * [%map, %map + map_size).
587 * - A pointer in the range [%map, %map + map_size) points to an allocated node
588 * if and only if the pointer is in the range [start.node, finish.node].
590 * Here's the magic: nothing in deque is "aware" of the discontiguous storage!
592 * The memory setup and layout occurs in the parent, _Base, and the iterator
593 * class is entirely responsible for "leaping" from one node to the next. All
594 * the implementation routines for deque itself work only through the start
595 * and finish iterators. This keeps the routines simple and sane, and we can
596 * use other standard algorithms as well.
599 template <class _Tp, class _Alloc = allocator<_Tp> >
600 class deque : protected _Deque_base<_Tp, _Alloc>
602 // concept requirements
603 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
605 typedef _Deque_base<_Tp, _Alloc> _Base;
608 typedef _Tp value_type;
609 typedef value_type* pointer;
610 typedef const value_type* const_pointer;
611 typedef value_type& reference;
612 typedef const value_type& const_reference;
613 typedef size_t size_type;
614 typedef ptrdiff_t difference_type;
616 typedef typename _Base::allocator_type allocator_type;
617 allocator_type get_allocator() const { return _Base::get_allocator(); }
619 typedef typename _Base::iterator iterator;
620 typedef typename _Base::const_iterator const_iterator;
621 typedef reverse_iterator<const_iterator> const_reverse_iterator;
622 typedef reverse_iterator<iterator> reverse_iterator;
625 typedef pointer* _Map_pointer;
626 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
628 // Functions controlling memory layout, and nothing else.
629 using _Base::_M_initialize_map;
630 using _Base::_M_create_nodes;
631 using _Base::_M_destroy_nodes;
632 using _Base::_M_allocate_node;
633 using _Base::_M_deallocate_node;
634 using _Base::_M_allocate_map;
635 using _Base::_M_deallocate_map;
638 * A total of four data members accumulated down the heirarchy. If the
639 * _Alloc type requires separate instances, then two of them will also be
640 * included in each deque.
644 using _Base::_M_map_size;
645 using _Base::_M_start;
646 using _Base::_M_finish;
648 public: // Basic accessors
649 iterator begin() { return _M_start; }
650 iterator end() { return _M_finish; }
651 const_iterator begin() const { return _M_start; }
652 const_iterator end() const { return _M_finish; }
654 reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
655 reverse_iterator rend() { return reverse_iterator(_M_start); }
656 const_reverse_iterator rbegin() const
657 { return const_reverse_iterator(_M_finish); }
658 const_reverse_iterator rend() const
659 { return const_reverse_iterator(_M_start); }
661 reference operator[](size_type __n)
662 { return _M_start[difference_type(__n)]; }
663 const_reference operator[](size_type __n) const
664 { return _M_start[difference_type(__n)]; }
666 void _M_range_check(size_type __n) const {
667 if (__n >= this->size())
668 __throw_range_error("deque");
671 reference at(size_type __n)
672 { _M_range_check(__n); return (*this)[__n]; }
673 const_reference at(size_type __n) const
674 { _M_range_check(__n); return (*this)[__n]; }
676 reference front() { return *_M_start; }
678 iterator __tmp = _M_finish;
682 const_reference front() const { return *_M_start; }
683 const_reference back() const {
684 const_iterator __tmp = _M_finish;
689 size_type size() const { return _M_finish - _M_start; }
690 size_type max_size() const { return size_type(-1); }
691 bool empty() const { return _M_finish == _M_start; }
693 public: // Constructor, destructor.
694 explicit deque(const allocator_type& __a = allocator_type())
696 deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
697 { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
698 deque(size_type __n, const value_type& __value,
699 const allocator_type& __a = allocator_type()) : _Base(__a, __n)
700 { _M_fill_initialize(__value); }
704 : _Base(allocator_type(), __n)
705 { _M_fill_initialize(value_type()); }
707 // Check whether it's an integral type. If so, it's not an iterator.
708 template<class _InputIterator>
709 deque(_InputIterator __first, _InputIterator __last,
710 const allocator_type& __a = allocator_type())
713 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
714 _M_initialize_dispatch(__first, __last, _Integral());
717 template<class _Integer>
719 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
721 _M_initialize_map(__n);
722 _M_fill_initialize(__x);
725 template<class _InputIter>
727 _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
729 typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
730 _M_range_initialize(__first, __last, _IterCategory());
734 { _Destroy(_M_start, _M_finish); }
736 deque& operator= (const deque& __x) {
737 const size_type __len = size();
739 if (__len >= __x.size())
740 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
742 const_iterator __mid = __x.begin() + difference_type(__len);
743 copy(__x.begin(), __mid, _M_start);
744 insert(_M_finish, __mid, __x.end());
750 void swap(deque& __x) {
751 std::swap(_M_start, __x._M_start);
752 std::swap(_M_finish, __x._M_finish);
753 std::swap(_M_map, __x._M_map);
754 std::swap(_M_map_size, __x._M_map_size);
758 // assign(), a generalized assignment member function. Two
759 // versions: one that takes a count, and one that takes a range.
760 // The range version is a member template, so we dispatch on whether
761 // or not the type is an integer.
763 void _M_fill_assign(size_type __n, const _Tp& __val) {
765 fill(begin(), end(), __val);
766 insert(end(), __n - size(), __val);
769 erase(begin() + __n, end());
770 fill(begin(), end(), __val);
775 assign(size_type __n, const _Tp& __val)
776 { _M_fill_assign(__n, __val); }
778 template<class _InputIterator>
780 assign(_InputIterator __first, _InputIterator __last)
782 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
783 _M_assign_dispatch(__first, __last, _Integral());
786 private: // helper functions for assign()
788 template<class _Integer>
790 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
791 { _M_fill_assign(static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
793 template<class _InputIterator>
795 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
797 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
798 _M_assign_aux(__first, __last, _IterCategory());
801 template <class _InputIterator>
802 void _M_assign_aux(_InputIterator __first, _InputIterator __last,
805 template <class _ForwardIterator>
806 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
807 forward_iterator_tag) {
808 size_type __len = distance(__first, __last);
809 if (__len > size()) {
810 _ForwardIterator __mid = __first;
811 advance(__mid, size());
812 copy(__first, __mid, begin());
813 insert(end(), __mid, __last);
816 erase(copy(__first, __last, begin()), end());
819 public: // push_* and pop_*
822 push_back(const value_type& __t)
824 if (_M_finish._M_cur != _M_finish._M_last - 1) {
825 _Construct(_M_finish._M_cur, __t);
829 _M_push_back_aux(__t);
835 if (_M_finish._M_cur != _M_finish._M_last - 1) {
836 _Construct(_M_finish._M_cur);
844 push_front(const value_type& __t)
846 if (_M_start._M_cur != _M_start._M_first) {
847 _Construct(_M_start._M_cur - 1, __t);
851 _M_push_front_aux(__t);
857 if (_M_start._M_cur != _M_start._M_first) {
858 _Construct(_M_start._M_cur - 1);
869 if (_M_finish._M_cur != _M_finish._M_first) {
871 _Destroy(_M_finish._M_cur);
880 if (_M_start._M_cur != _M_start._M_last - 1) {
881 _Destroy(_M_start._M_cur);
891 insert(iterator position, const value_type& __x)
893 if (position._M_cur == _M_start._M_cur) {
897 else if (position._M_cur == _M_finish._M_cur) {
899 iterator __tmp = _M_finish;
904 return _M_insert_aux(position, __x);
909 insert(iterator __position)
910 { return insert(__position, value_type()); }
913 insert(iterator __pos, size_type __n, const value_type& __x)
914 { _M_fill_insert(__pos, __n, __x); }
917 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
919 // Check whether it's an integral type. If so, it's not an iterator.
920 template<class _InputIterator>
922 insert(iterator __pos, _InputIterator __first, _InputIterator __last)
924 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
925 _M_insert_dispatch(__pos, __first, __last, _Integral());
928 template<class _Integer>
930 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
931 { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<value_type>(__x)); }
933 template<class _InputIterator>
935 _M_insert_dispatch(iterator __pos,
936 _InputIterator __first, _InputIterator __last,
939 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
940 insert(__pos, __first, __last, _IterCategory());
943 void resize(size_type __new_size, const value_type& __x) {
944 const size_type __len = size();
945 if (__new_size < __len)
946 erase(_M_start + __new_size, _M_finish);
948 insert(_M_finish, __new_size - __len, __x);
951 void resize(size_type new_size) { resize(new_size, value_type()); }
954 iterator erase(iterator __pos) {
955 iterator __next = __pos;
957 size_type __index = __pos - _M_start;
958 if (__index < (size() >> 1)) {
959 copy_backward(_M_start, __pos, __next);
963 copy(__next, _M_finish, __pos);
966 return _M_start + __index;
969 iterator erase(iterator __first, iterator __last);
972 protected: // Internal construction/destruction
974 void _M_fill_initialize(const value_type& __value);
976 template <class _InputIterator>
977 void _M_range_initialize(_InputIterator __first, _InputIterator __last,
980 template <class _ForwardIterator>
981 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
982 forward_iterator_tag);
984 protected: // Internal push_* and pop_*
986 void _M_push_back_aux(const value_type&);
987 void _M_push_back_aux();
988 void _M_push_front_aux(const value_type&);
989 void _M_push_front_aux();
990 void _M_pop_back_aux();
991 void _M_pop_front_aux();
993 protected: // Internal insert functions
995 template <class _InputIterator>
996 void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
999 template <class _ForwardIterator>
1000 void insert(iterator __pos,
1001 _ForwardIterator __first, _ForwardIterator __last,
1002 forward_iterator_tag);
1004 iterator _M_insert_aux(iterator __pos, const value_type& __x);
1005 iterator _M_insert_aux(iterator __pos);
1006 void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1008 template <class _ForwardIterator>
1009 void _M_insert_aux(iterator __pos,
1010 _ForwardIterator __first, _ForwardIterator __last,
1013 iterator _M_reserve_elements_at_front(size_type __n) {
1014 size_type __vacancies = _M_start._M_cur - _M_start._M_first;
1015 if (__n > __vacancies)
1016 _M_new_elements_at_front(__n - __vacancies);
1017 return _M_start - difference_type(__n);
1020 iterator _M_reserve_elements_at_back(size_type __n) {
1021 size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
1022 if (__n > __vacancies)
1023 _M_new_elements_at_back(__n - __vacancies);
1024 return _M_finish + difference_type(__n);
1027 void _M_new_elements_at_front(size_type __new_elements);
1028 void _M_new_elements_at_back(size_type __new_elements);
1030 protected: // Allocation of _M_map and nodes
1032 // Makes sure the _M_map has space for new nodes. Does not actually
1033 // add the nodes. Can invalidate _M_map pointers. (And consequently,
1034 // deque iterators.)
1036 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
1037 if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
1038 _M_reallocate_map(__nodes_to_add, false);
1041 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
1042 if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
1043 _M_reallocate_map(__nodes_to_add, true);
1046 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1049 // Non-inline member functions
1051 template <class _Tp, class _Alloc>
1052 template <class _InputIter>
1053 void deque<_Tp, _Alloc>
1054 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
1056 iterator __cur = begin();
1057 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
1059 if (__first == __last)
1060 erase(__cur, end());
1062 insert(end(), __first, __last);
1065 template <class _Tp, class _Alloc>
1066 void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
1067 size_type __n, const value_type& __x)
1069 if (__pos._M_cur == _M_start._M_cur) {
1070 iterator __new_start = _M_reserve_elements_at_front(__n);
1072 uninitialized_fill(__new_start, _M_start, __x);
1073 _M_start = __new_start;
1077 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
1078 __throw_exception_again;
1081 else if (__pos._M_cur == _M_finish._M_cur) {
1082 iterator __new_finish = _M_reserve_elements_at_back(__n);
1084 uninitialized_fill(_M_finish, __new_finish, __x);
1085 _M_finish = __new_finish;
1089 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
1090 __throw_exception_again;
1094 _M_insert_aux(__pos, __n, __x);
1097 template <class _Tp, class _Alloc>
1098 typename deque<_Tp,_Alloc>::iterator
1099 deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
1101 if (__first == _M_start && __last == _M_finish) {
1106 difference_type __n = __last - __first;
1107 difference_type __elems_before = __first - _M_start;
1108 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
1109 copy_backward(_M_start, __first, __last);
1110 iterator __new_start = _M_start + __n;
1111 _Destroy(_M_start, __new_start);
1112 _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
1113 _M_start = __new_start;
1116 copy(__last, _M_finish, __first);
1117 iterator __new_finish = _M_finish - __n;
1118 _Destroy(__new_finish, _M_finish);
1119 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
1120 _M_finish = __new_finish;
1122 return _M_start + __elems_before;
1126 template <class _Tp, class _Alloc>
1127 void deque<_Tp,_Alloc>::clear()
1129 for (_Map_pointer __node = _M_start._M_node + 1;
1130 __node < _M_finish._M_node;
1132 _Destroy(*__node, *__node + _S_buffer_size());
1133 _M_deallocate_node(*__node);
1136 if (_M_start._M_node != _M_finish._M_node) {
1137 _Destroy(_M_start._M_cur, _M_start._M_last);
1138 _Destroy(_M_finish._M_first, _M_finish._M_cur);
1139 _M_deallocate_node(_M_finish._M_first);
1142 _Destroy(_M_start._M_cur, _M_finish._M_cur);
1144 _M_finish = _M_start;
1149 * @brief Fills the deque with copies of value.
1150 * @param value Initial value.
1152 * @pre _M_start and _M_finish have already been initialized, but none of the
1153 * deque's elements have yet been constructed.
1155 * This function is called only when the user provides an explicit size (with
1156 * or without an explicit exemplar value).
1159 template <class _Tp, class _Alloc>
1160 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value)
1164 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
1165 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
1166 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
1170 _Destroy(_M_start, iterator(*__cur, __cur));
1171 __throw_exception_again;
1177 * @brief Fills the deque with whatever is in [first,last).
1178 * @param first An input iterator.
1179 * @param last An input iterator.
1182 * If the iterators are actually forward iterators (or better), then the
1183 * memory layout can be done all at once. Else we move forward using
1184 * push_back on each value from the iterator.
1187 template <class _Tp, class _Alloc> template <class _InputIterator>
1188 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
1189 _InputIterator __last,
1192 _M_initialize_map(0);
1194 for ( ; __first != __last; ++__first)
1195 push_back(*__first);
1200 __throw_exception_again;
1204 template <class _Tp, class _Alloc> template <class _ForwardIterator>
1205 void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
1206 _ForwardIterator __last,
1207 forward_iterator_tag)
1209 size_type __n = distance(__first, __last);
1210 _M_initialize_map(__n);
1212 _Map_pointer __cur_node;
1214 for (__cur_node = _M_start._M_node;
1215 __cur_node < _M_finish._M_node;
1217 _ForwardIterator __mid = __first;
1218 advance(__mid, _S_buffer_size());
1219 uninitialized_copy(__first, __mid, *__cur_node);
1222 uninitialized_copy(__first, __last, _M_finish._M_first);
1226 _Destroy(_M_start, iterator(*__cur_node, __cur_node));
1227 __throw_exception_again;
1232 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1233 template <class _Tp, class _Alloc>
1235 deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
1237 value_type __t_copy = __t;
1238 _M_reserve_map_at_back();
1239 *(_M_finish._M_node + 1) = _M_allocate_node();
1241 _Construct(_M_finish._M_cur, __t_copy);
1242 _M_finish._M_set_node(_M_finish._M_node + 1);
1243 _M_finish._M_cur = _M_finish._M_first;
1247 _M_deallocate_node(*(_M_finish._M_node + 1));
1248 __throw_exception_again;
1252 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1253 template <class _Tp, class _Alloc>
1255 deque<_Tp,_Alloc>::_M_push_back_aux()
1257 _M_reserve_map_at_back();
1258 *(_M_finish._M_node + 1) = _M_allocate_node();
1260 _Construct(_M_finish._M_cur);
1261 _M_finish._M_set_node(_M_finish._M_node + 1);
1262 _M_finish._M_cur = _M_finish._M_first;
1266 _M_deallocate_node(*(_M_finish._M_node + 1));
1267 __throw_exception_again;
1271 // Called only if _M_start._M_cur == _M_start._M_first.
1272 template <class _Tp, class _Alloc>
1274 deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
1276 value_type __t_copy = __t;
1277 _M_reserve_map_at_front();
1278 *(_M_start._M_node - 1) = _M_allocate_node();
1280 _M_start._M_set_node(_M_start._M_node - 1);
1281 _M_start._M_cur = _M_start._M_last - 1;
1282 _Construct(_M_start._M_cur, __t_copy);
1287 _M_deallocate_node(*(_M_start._M_node - 1));
1288 __throw_exception_again;
1292 // Called only if _M_start._M_cur == _M_start._M_first.
1293 template <class _Tp, class _Alloc>
1295 deque<_Tp,_Alloc>::_M_push_front_aux()
1297 _M_reserve_map_at_front();
1298 *(_M_start._M_node - 1) = _M_allocate_node();
1300 _M_start._M_set_node(_M_start._M_node - 1);
1301 _M_start._M_cur = _M_start._M_last - 1;
1302 _Construct(_M_start._M_cur);
1307 _M_deallocate_node(*(_M_start._M_node - 1));
1308 __throw_exception_again;
1312 // Called only if _M_finish._M_cur == _M_finish._M_first.
1313 template <class _Tp, class _Alloc>
1314 void deque<_Tp,_Alloc>::_M_pop_back_aux()
1316 _M_deallocate_node(_M_finish._M_first);
1317 _M_finish._M_set_node(_M_finish._M_node - 1);
1318 _M_finish._M_cur = _M_finish._M_last - 1;
1319 _Destroy(_M_finish._M_cur);
1322 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
1323 // if the deque has at least one element (a precondition for this member
1324 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
1325 // must have at least two nodes.
1326 template <class _Tp, class _Alloc>
1327 void deque<_Tp,_Alloc>::_M_pop_front_aux()
1329 _Destroy(_M_start._M_cur);
1330 _M_deallocate_node(_M_start._M_first);
1331 _M_start._M_set_node(_M_start._M_node + 1);
1332 _M_start._M_cur = _M_start._M_first;
1335 template <class _Tp, class _Alloc> template <class _InputIterator>
1336 void deque<_Tp,_Alloc>::insert(iterator __pos,
1337 _InputIterator __first, _InputIterator __last,
1340 copy(__first, __last, inserter(*this, __pos));
1343 template <class _Tp, class _Alloc> template <class _ForwardIterator>
1345 deque<_Tp,_Alloc>::insert(iterator __pos,
1346 _ForwardIterator __first, _ForwardIterator __last,
1347 forward_iterator_tag) {
1348 size_type __n = distance(__first, __last);
1349 if (__pos._M_cur == _M_start._M_cur) {
1350 iterator __new_start = _M_reserve_elements_at_front(__n);
1352 uninitialized_copy(__first, __last, __new_start);
1353 _M_start = __new_start;
1357 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
1358 __throw_exception_again;
1361 else if (__pos._M_cur == _M_finish._M_cur) {
1362 iterator __new_finish = _M_reserve_elements_at_back(__n);
1364 uninitialized_copy(__first, __last, _M_finish);
1365 _M_finish = __new_finish;
1369 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
1370 __throw_exception_again;
1374 _M_insert_aux(__pos, __first, __last, __n);
1377 template <class _Tp, class _Alloc>
1378 typename deque<_Tp, _Alloc>::iterator
1379 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
1381 difference_type __index = __pos - _M_start;
1382 value_type __x_copy = __x;
1383 if (static_cast<size_type>(__index) < size() / 2) {
1384 push_front(front());
1385 iterator __front1 = _M_start;
1387 iterator __front2 = __front1;
1389 __pos = _M_start + __index;
1390 iterator __pos1 = __pos;
1392 copy(__front2, __pos1, __front1);
1396 iterator __back1 = _M_finish;
1398 iterator __back2 = __back1;
1400 __pos = _M_start + __index;
1401 copy_backward(__pos, __back2, __back1);
1407 template <class _Tp, class _Alloc>
1408 typename deque<_Tp,_Alloc>::iterator
1409 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
1411 difference_type __index = __pos - _M_start;
1412 if (static_cast<size_type>(__index) < size() / 2) {
1413 push_front(front());
1414 iterator __front1 = _M_start;
1416 iterator __front2 = __front1;
1418 __pos = _M_start + __index;
1419 iterator __pos1 = __pos;
1421 copy(__front2, __pos1, __front1);
1425 iterator __back1 = _M_finish;
1427 iterator __back2 = __back1;
1429 __pos = _M_start + __index;
1430 copy_backward(__pos, __back2, __back1);
1432 *__pos = value_type();
1436 template <class _Tp, class _Alloc>
1437 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1439 const value_type& __x)
1441 const difference_type __elems_before = __pos - _M_start;
1442 size_type __length = this->size();
1443 value_type __x_copy = __x;
1444 if (__elems_before < difference_type(__length / 2)) {
1445 iterator __new_start = _M_reserve_elements_at_front(__n);
1446 iterator __old_start = _M_start;
1447 __pos = _M_start + __elems_before;
1449 if (__elems_before >= difference_type(__n)) {
1450 iterator __start_n = _M_start + difference_type(__n);
1451 uninitialized_copy(_M_start, __start_n, __new_start);
1452 _M_start = __new_start;
1453 copy(__start_n, __pos, __old_start);
1454 fill(__pos - difference_type(__n), __pos, __x_copy);
1457 __uninitialized_copy_fill(_M_start, __pos, __new_start,
1458 _M_start, __x_copy);
1459 _M_start = __new_start;
1460 fill(__old_start, __pos, __x_copy);
1465 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
1466 __throw_exception_again;
1470 iterator __new_finish = _M_reserve_elements_at_back(__n);
1471 iterator __old_finish = _M_finish;
1472 const difference_type __elems_after =
1473 difference_type(__length) - __elems_before;
1474 __pos = _M_finish - __elems_after;
1476 if (__elems_after > difference_type(__n)) {
1477 iterator __finish_n = _M_finish - difference_type(__n);
1478 uninitialized_copy(__finish_n, _M_finish, _M_finish);
1479 _M_finish = __new_finish;
1480 copy_backward(__pos, __finish_n, __old_finish);
1481 fill(__pos, __pos + difference_type(__n), __x_copy);
1484 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
1485 __x_copy, __pos, _M_finish);
1486 _M_finish = __new_finish;
1487 fill(__pos, __old_finish, __x_copy);
1492 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
1493 __throw_exception_again;
1498 template <class _Tp, class _Alloc> template <class _ForwardIterator>
1499 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1500 _ForwardIterator __first,
1501 _ForwardIterator __last,
1504 const difference_type __elemsbefore = __pos - _M_start;
1505 size_type __length = size();
1506 if (static_cast<size_type>(__elemsbefore) < __length / 2) {
1507 iterator __new_start = _M_reserve_elements_at_front(__n);
1508 iterator __old_start = _M_start;
1509 __pos = _M_start + __elemsbefore;
1511 if (__elemsbefore >= difference_type(__n)) {
1512 iterator __start_n = _M_start + difference_type(__n);
1513 uninitialized_copy(_M_start, __start_n, __new_start);
1514 _M_start = __new_start;
1515 copy(__start_n, __pos, __old_start);
1516 copy(__first, __last, __pos - difference_type(__n));
1519 _ForwardIterator __mid = __first;
1520 advance(__mid, difference_type(__n) - __elemsbefore);
1521 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
1523 _M_start = __new_start;
1524 copy(__mid, __last, __old_start);
1529 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
1530 __throw_exception_again;
1534 iterator __new_finish = _M_reserve_elements_at_back(__n);
1535 iterator __old_finish = _M_finish;
1536 const difference_type __elemsafter =
1537 difference_type(__length) - __elemsbefore;
1538 __pos = _M_finish - __elemsafter;
1540 if (__elemsafter > difference_type(__n)) {
1541 iterator __finish_n = _M_finish - difference_type(__n);
1542 uninitialized_copy(__finish_n, _M_finish, _M_finish);
1543 _M_finish = __new_finish;
1544 copy_backward(__pos, __finish_n, __old_finish);
1545 copy(__first, __last, __pos);
1548 _ForwardIterator __mid = __first;
1549 advance(__mid, __elemsafter);
1550 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
1551 _M_finish = __new_finish;
1552 copy(__first, __mid, __pos);
1557 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
1558 __throw_exception_again;
1563 template <class _Tp, class _Alloc>
1564 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
1566 size_type __new_nodes
1567 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1568 _M_reserve_map_at_front(__new_nodes);
1571 for (__i = 1; __i <= __new_nodes; ++__i)
1572 *(_M_start._M_node - __i) = _M_allocate_node();
1575 for (size_type __j = 1; __j < __i; ++__j)
1576 _M_deallocate_node(*(_M_start._M_node - __j));
1577 __throw_exception_again;
1581 template <class _Tp, class _Alloc>
1582 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
1584 size_type __new_nodes
1585 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
1586 _M_reserve_map_at_back(__new_nodes);
1589 for (__i = 1; __i <= __new_nodes; ++__i)
1590 *(_M_finish._M_node + __i) = _M_allocate_node();
1593 for (size_type __j = 1; __j < __i; ++__j)
1594 _M_deallocate_node(*(_M_finish._M_node + __j));
1595 __throw_exception_again;
1599 template <class _Tp, class _Alloc>
1600 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
1601 bool __add_at_front)
1603 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
1604 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1606 _Map_pointer __new_nstart;
1607 if (_M_map_size > 2 * __new_num_nodes) {
1608 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
1609 + (__add_at_front ? __nodes_to_add : 0);
1610 if (__new_nstart < _M_start._M_node)
1611 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1613 copy_backward(_M_start._M_node, _M_finish._M_node + 1,
1614 __new_nstart + __old_num_nodes);
1617 size_type __new_map_size =
1618 _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
1620 _Map_pointer __new_map = _M_allocate_map(__new_map_size);
1621 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1622 + (__add_at_front ? __nodes_to_add : 0);
1623 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
1624 _M_deallocate_map(_M_map, _M_map_size);
1627 _M_map_size = __new_map_size;
1630 _M_start._M_set_node(__new_nstart);
1631 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1635 // Nonmember functions.
1637 template <class _Tp, class _Alloc>
1638 inline bool operator==(const deque<_Tp, _Alloc>& __x,
1639 const deque<_Tp, _Alloc>& __y) {
1640 return __x.size() == __y.size() &&
1641 equal(__x.begin(), __x.end(), __y.begin());
1644 template <class _Tp, class _Alloc>
1645 inline bool operator<(const deque<_Tp, _Alloc>& __x,
1646 const deque<_Tp, _Alloc>& __y) {
1647 return lexicographical_compare(__x.begin(), __x.end(),
1648 __y.begin(), __y.end());
1651 template <class _Tp, class _Alloc>
1652 inline bool operator!=(const deque<_Tp, _Alloc>& __x,
1653 const deque<_Tp, _Alloc>& __y) {
1654 return !(__x == __y);
1657 template <class _Tp, class _Alloc>
1658 inline bool operator>(const deque<_Tp, _Alloc>& __x,
1659 const deque<_Tp, _Alloc>& __y) {
1663 template <class _Tp, class _Alloc>
1664 inline bool operator<=(const deque<_Tp, _Alloc>& __x,
1665 const deque<_Tp, _Alloc>& __y) {
1666 return !(__y < __x);
1668 template <class _Tp, class _Alloc>
1669 inline bool operator>=(const deque<_Tp, _Alloc>& __x,
1670 const deque<_Tp, _Alloc>& __y) {
1671 return !(__x < __y);
1674 template <class _Tp, class _Alloc>
1675 inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
1681 #endif /* __GLIBCPP_INTERNAL_DEQUE_H */