4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
16 * Silicon Graphics Computer Systems, Inc.
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
31 #include <bits/concept_checks.h>
33 #ifndef __SGI_STL_INTERNAL_DEQUE_H
34 #define __SGI_STL_INTERNAL_DEQUE_H
37 * For any nonsingular iterator i:
38 * i.node is the address of an element in the map array. The
39 * contents of i.node is a pointer to the beginning of a node.
40 * i.first == *(i.node)
41 * i.last == i.first + node_size
42 * i.cur is a pointer in the range [i.first, i.last). NOTE:
43 * the implication of this is that i.cur is always a dereferenceable
44 * pointer, even if i is a past-the-end iterator.
45 * Start and Finish are always nonsingular iterators. NOTE: this means
46 * that an empty deque must have one node, and that a deque
47 * with N elements, where N is the buffer size, must have two nodes.
48 * For every node other than start.node and finish.node, every element
49 * in the node is an initialized object. If start.node == finish.node,
50 * then [start.cur, finish.cur) are initialized objects, and
51 * the elements outside that range are uninitialized storage. Otherwise,
52 * [start.cur, start.last) and [finish.first, finish.cur) are initialized
53 * objects, and [start.first, start.cur) and [finish.cur, finish.last)
54 * are uninitialized storage.
55 * [map, map + map_size) is a valid, non-empty range.
56 * [start.node, finish.node] is a valid range contained within
57 * [map, map + map_size).
58 * A pointer in the range [map, map + map_size) points to an allocated node
59 * if and only if the pointer is in the range [start.node, finish.node].
64 * In previous versions of deque, there was an extra template
65 * parameter so users could control the node size. This extension
66 * turns out to violate the C++ standard (it can be detected using
67 * template template parameters), and it has been removed.
72 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
77 // Note: this function is simply a kludge to work around several compilers'
78 // bugs in handling constant expressions.
79 inline size_t __deque_buf_size(size_t __size
) {
80 return __size
< 512 ? size_t(512 / __size
) : size_t(1);
83 template <class _Tp
, class _Ref
, class _Ptr
>
84 struct _Deque_iterator
{
85 typedef _Deque_iterator
<_Tp
, _Tp
&, _Tp
*> iterator
;
86 typedef _Deque_iterator
<_Tp
, const _Tp
&, const _Tp
*> const_iterator
;
87 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp
)); }
89 typedef random_access_iterator_tag iterator_category
;
90 typedef _Tp value_type
;
92 typedef _Ref reference
;
93 typedef size_t size_type
;
94 typedef ptrdiff_t difference_type
;
95 typedef _Tp
** _Map_pointer
;
97 typedef _Deque_iterator _Self
;
102 _Map_pointer _M_node
;
104 _Deque_iterator(_Tp
* __x
, _Map_pointer __y
)
105 : _M_cur(__x
), _M_first(*__y
),
106 _M_last(*__y
+ _S_buffer_size()), _M_node(__y
) {}
107 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
108 _Deque_iterator(const iterator
& __x
)
109 : _M_cur(__x
._M_cur
), _M_first(__x
._M_first
),
110 _M_last(__x
._M_last
), _M_node(__x
._M_node
) {}
112 reference
operator*() const { return *_M_cur
; }
113 #ifndef __SGI_STL_NO_ARROW_OPERATOR
114 pointer
operator->() const { return _M_cur
; }
115 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
117 difference_type
operator-(const _Self
& __x
) const {
118 return difference_type(_S_buffer_size()) * (_M_node
- __x
._M_node
- 1) +
119 (_M_cur
- _M_first
) + (__x
._M_last
- __x
._M_cur
);
122 _Self
& operator++() {
124 if (_M_cur
== _M_last
) {
125 _M_set_node(_M_node
+ 1);
130 _Self
operator++(int) {
136 _Self
& operator--() {
137 if (_M_cur
== _M_first
) {
138 _M_set_node(_M_node
- 1);
144 _Self
operator--(int) {
150 _Self
& operator+=(difference_type __n
)
152 difference_type __offset
= __n
+ (_M_cur
- _M_first
);
153 if (__offset
>= 0 && __offset
< difference_type(_S_buffer_size()))
156 difference_type __node_offset
=
157 __offset
> 0 ? __offset
/ difference_type(_S_buffer_size())
158 : -difference_type((-__offset
- 1) / _S_buffer_size()) - 1;
159 _M_set_node(_M_node
+ __node_offset
);
161 (__offset
- __node_offset
* difference_type(_S_buffer_size()));
166 _Self
operator+(difference_type __n
) const
172 _Self
& operator-=(difference_type __n
) { return *this += -__n
; }
174 _Self
operator-(difference_type __n
) const {
179 reference
operator[](difference_type __n
) const { return *(*this + __n
); }
181 bool operator==(const _Self
& __x
) const { return _M_cur
== __x
._M_cur
; }
182 bool operator!=(const _Self
& __x
) const { return !(*this == __x
); }
183 bool operator<(const _Self
& __x
) const {
184 return (_M_node
== __x
._M_node
) ?
185 (_M_cur
< __x
._M_cur
) : (_M_node
< __x
._M_node
);
187 bool operator>(const _Self
& __x
) const { return __x
< *this; }
188 bool operator<=(const _Self
& __x
) const { return !(__x
< *this); }
189 bool operator>=(const _Self
& __x
) const { return !(*this < __x
); }
191 void _M_set_node(_Map_pointer __new_node
) {
192 _M_node
= __new_node
;
193 _M_first
= *__new_node
;
194 _M_last
= _M_first
+ difference_type(_S_buffer_size());
198 template <class _Tp
, class _Ref
, class _Ptr
>
199 inline _Deque_iterator
<_Tp
, _Ref
, _Ptr
>
200 operator+(ptrdiff_t __n
, const _Deque_iterator
<_Tp
, _Ref
, _Ptr
>& __x
)
205 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
207 template <class _Tp
, class _Ref
, class _Ptr
>
208 inline random_access_iterator_tag
209 iterator_category(const _Deque_iterator
<_Tp
,_Ref
,_Ptr
>&)
211 return random_access_iterator_tag();
214 template <class _Tp
, class _Ref
, class _Ptr
>
215 inline _Tp
* value_type(const _Deque_iterator
<_Tp
,_Ref
,_Ptr
>&) { return 0; }
217 template <class _Tp
, class _Ref
, class _Ptr
>
218 inline ptrdiff_t* distance_type(const _Deque_iterator
<_Tp
,_Ref
,_Ptr
>&) {
222 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
224 // Deque base class. It has two purposes. First, its constructor
225 // and destructor allocate (but don't initialize) storage. This makes
226 // exception safety easier. Second, the base class encapsulates all of
227 // the differences between SGI-style allocators and standard-conforming
230 #ifdef __STL_USE_STD_ALLOCATORS
232 // Base class for ordinary allocators.
233 template <class _Tp
, class _Alloc
, bool __is_static
>
234 class _Deque_alloc_base
{
236 typedef typename _Alloc_traits
<_Tp
,_Alloc
>::allocator_type allocator_type
;
237 allocator_type
get_allocator() const { return _M_node_allocator
; }
239 _Deque_alloc_base(const allocator_type
& __a
)
240 : _M_node_allocator(__a
), _M_map_allocator(__a
),
241 _M_map(0), _M_map_size(0)
245 typedef typename _Alloc_traits
<_Tp
*, _Alloc
>::allocator_type
248 allocator_type _M_node_allocator
;
249 _Map_allocator_type _M_map_allocator
;
251 _Tp
* _M_allocate_node() {
252 return _M_node_allocator
.allocate(__deque_buf_size(sizeof(_Tp
)));
254 void _M_deallocate_node(_Tp
* __p
) {
255 _M_node_allocator
.deallocate(__p
, __deque_buf_size(sizeof(_Tp
)));
257 _Tp
** _M_allocate_map(size_t __n
)
258 { return _M_map_allocator
.allocate(__n
); }
259 void _M_deallocate_map(_Tp
** __p
, size_t __n
)
260 { _M_map_allocator
.deallocate(__p
, __n
); }
266 // Specialization for instanceless allocators.
267 template <class _Tp
, class _Alloc
>
268 class _Deque_alloc_base
<_Tp
, _Alloc
, true>
271 typedef typename _Alloc_traits
<_Tp
,_Alloc
>::allocator_type allocator_type
;
272 allocator_type
get_allocator() const { return allocator_type(); }
274 _Deque_alloc_base(const allocator_type
&) : _M_map(0), _M_map_size(0) {}
277 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::_Alloc_type _Node_alloc_type
;
278 typedef typename _Alloc_traits
<_Tp
*, _Alloc
>::_Alloc_type _Map_alloc_type
;
280 _Tp
* _M_allocate_node() {
281 return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp
)));
283 void _M_deallocate_node(_Tp
* __p
) {
284 _Node_alloc_type::deallocate(__p
, __deque_buf_size(sizeof(_Tp
)));
286 _Tp
** _M_allocate_map(size_t __n
)
287 { return _Map_alloc_type::allocate(__n
); }
288 void _M_deallocate_map(_Tp
** __p
, size_t __n
)
289 { _Map_alloc_type::deallocate(__p
, __n
); }
295 template <class _Tp
, class _Alloc
>
297 : public _Deque_alloc_base
<_Tp
,_Alloc
,
298 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
301 typedef _Deque_alloc_base
<_Tp
,_Alloc
,
302 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
304 typedef typename
_Base::allocator_type allocator_type
;
305 typedef _Deque_iterator
<_Tp
,_Tp
&,_Tp
*> iterator
;
306 typedef _Deque_iterator
<_Tp
,const _Tp
&,const _Tp
*> const_iterator
;
308 _Deque_base(const allocator_type
& __a
, size_t __num_elements
)
309 : _Base(__a
), _M_start(), _M_finish()
310 { _M_initialize_map(__num_elements
); }
311 _Deque_base(const allocator_type
& __a
)
312 : _Base(__a
), _M_start(), _M_finish() {}
316 void _M_initialize_map(size_t);
317 void _M_create_nodes(_Tp
** __nstart
, _Tp
** __nfinish
);
318 void _M_destroy_nodes(_Tp
** __nstart
, _Tp
** __nfinish
);
319 enum { _S_initial_map_size
= 8 };
326 #else /* __STL_USE_STD_ALLOCATORS */
328 template <class _Tp
, class _Alloc
>
331 typedef _Deque_iterator
<_Tp
,_Tp
&,_Tp
*> iterator
;
332 typedef _Deque_iterator
<_Tp
,const _Tp
&,const _Tp
*> const_iterator
;
334 typedef _Alloc allocator_type
;
335 allocator_type
get_allocator() const { return allocator_type(); }
337 _Deque_base(const allocator_type
&, size_t __num_elements
)
338 : _M_map(0), _M_map_size(0), _M_start(), _M_finish() {
339 _M_initialize_map(__num_elements
);
341 _Deque_base(const allocator_type
&)
342 : _M_map(0), _M_map_size(0), _M_start(), _M_finish() {}
346 void _M_initialize_map(size_t);
347 void _M_create_nodes(_Tp
** __nstart
, _Tp
** __nfinish
);
348 void _M_destroy_nodes(_Tp
** __nstart
, _Tp
** __nfinish
);
349 enum { _S_initial_map_size
= 8 };
357 typedef simple_alloc
<_Tp
, _Alloc
> _Node_alloc_type
;
358 typedef simple_alloc
<_Tp
*, _Alloc
> _Map_alloc_type
;
360 _Tp
* _M_allocate_node()
361 { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp
))); }
362 void _M_deallocate_node(_Tp
* __p
)
363 { _Node_alloc_type::deallocate(__p
, __deque_buf_size(sizeof(_Tp
))); }
364 _Tp
** _M_allocate_map(size_t __n
)
365 { return _Map_alloc_type::allocate(__n
); }
366 void _M_deallocate_map(_Tp
** __p
, size_t __n
)
367 { _Map_alloc_type::deallocate(__p
, __n
); }
370 #endif /* __STL_USE_STD_ALLOCATORS */
372 // Non-inline member functions from _Deque_base.
374 template <class _Tp
, class _Alloc
>
375 _Deque_base
<_Tp
,_Alloc
>::~_Deque_base() {
377 _M_destroy_nodes(_M_start
._M_node
, _M_finish
._M_node
+ 1);
378 _M_deallocate_map(_M_map
, _M_map_size
);
382 template <class _Tp
, class _Alloc
>
384 _Deque_base
<_Tp
,_Alloc
>::_M_initialize_map(size_t __num_elements
)
387 __num_elements
/ __deque_buf_size(sizeof(_Tp
)) + 1;
389 _M_map_size
= max((size_t) _S_initial_map_size
, __num_nodes
+ 2);
390 _M_map
= _M_allocate_map(_M_map_size
);
392 _Tp
** __nstart
= _M_map
+ (_M_map_size
- __num_nodes
) / 2;
393 _Tp
** __nfinish
= __nstart
+ __num_nodes
;
396 _M_create_nodes(__nstart
, __nfinish
);
398 __STL_UNWIND((_M_deallocate_map(_M_map
, _M_map_size
),
399 _M_map
= 0, _M_map_size
= 0));
400 _M_start
._M_set_node(__nstart
);
401 _M_finish
._M_set_node(__nfinish
- 1);
402 _M_start
._M_cur
= _M_start
._M_first
;
403 _M_finish
._M_cur
= _M_finish
._M_first
+
404 __num_elements
% __deque_buf_size(sizeof(_Tp
));
407 template <class _Tp
, class _Alloc
>
408 void _Deque_base
<_Tp
,_Alloc
>::_M_create_nodes(_Tp
** __nstart
, _Tp
** __nfinish
)
412 for (__cur
= __nstart
; __cur
< __nfinish
; ++__cur
)
413 *__cur
= _M_allocate_node();
415 __STL_UNWIND(_M_destroy_nodes(__nstart
, __cur
));
418 template <class _Tp
, class _Alloc
>
420 _Deque_base
<_Tp
,_Alloc
>::_M_destroy_nodes(_Tp
** __nstart
, _Tp
** __nfinish
)
422 for (_Tp
** __n
= __nstart
; __n
< __nfinish
; ++__n
)
423 _M_deallocate_node(*__n
);
426 template <class _Tp
, class _Alloc
= __STL_DEFAULT_ALLOCATOR(_Tp
) >
427 class deque
: protected _Deque_base
<_Tp
, _Alloc
> {
431 __STL_CLASS_REQUIRES(_Tp
, _Assignable
);
433 typedef _Deque_base
<_Tp
, _Alloc
> _Base
;
434 public: // Basic types
435 typedef _Tp value_type
;
436 typedef value_type
* pointer
;
437 typedef const value_type
* const_pointer
;
438 typedef value_type
& reference
;
439 typedef const value_type
& const_reference
;
440 typedef size_t size_type
;
441 typedef ptrdiff_t difference_type
;
443 typedef typename
_Base::allocator_type allocator_type
;
444 allocator_type
get_allocator() const { return _Base::get_allocator(); }
447 typedef typename
_Base::iterator iterator
;
448 typedef typename
_Base::const_iterator const_iterator
;
450 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
451 typedef reverse_iterator
<const_iterator
> const_reverse_iterator
;
452 typedef reverse_iterator
<iterator
> reverse_iterator
;
453 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
454 typedef reverse_iterator
<const_iterator
, value_type
, const_reference
,
456 const_reverse_iterator
;
457 typedef reverse_iterator
<iterator
, value_type
, reference
, difference_type
>
459 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
461 protected: // Internal typedefs
462 typedef pointer
* _Map_pointer
;
463 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp
)); }
466 #ifdef __STL_USE_NAMESPACES
467 using _Base::_M_initialize_map
;
468 using _Base::_M_create_nodes
;
469 using _Base::_M_destroy_nodes
;
470 using _Base::_M_allocate_node
;
471 using _Base::_M_deallocate_node
;
472 using _Base::_M_allocate_map
;
473 using _Base::_M_deallocate_map
;
476 using _Base::_M_map_size
;
477 using _Base::_M_start
;
478 using _Base::_M_finish
;
479 #endif /* __STL_USE_NAMESPACES */
481 public: // Basic accessors
482 iterator
begin() { return _M_start
; }
483 iterator
end() { return _M_finish
; }
484 const_iterator
begin() const { return _M_start
; }
485 const_iterator
end() const { return _M_finish
; }
487 reverse_iterator
rbegin() { return reverse_iterator(_M_finish
); }
488 reverse_iterator
rend() { return reverse_iterator(_M_start
); }
489 const_reverse_iterator
rbegin() const
490 { return const_reverse_iterator(_M_finish
); }
491 const_reverse_iterator
rend() const
492 { return const_reverse_iterator(_M_start
); }
494 reference
operator[](size_type __n
)
495 { return _M_start
[difference_type(__n
)]; }
496 const_reference
operator[](size_type __n
) const
497 { return _M_start
[difference_type(__n
)]; }
499 #ifdef __STL_THROW_RANGE_ERRORS
500 void _M_range_check(size_type __n
) const {
501 if (__n
>= this->size())
502 __throw_range_error("deque");
505 reference
at(size_type __n
)
506 { _M_range_check(__n
); return (*this)[__n
]; }
507 const_reference
at(size_type __n
) const
508 { _M_range_check(__n
); return (*this)[__n
]; }
509 #endif /* __STL_THROW_RANGE_ERRORS */
511 reference
front() { return *_M_start
; }
513 iterator __tmp
= _M_finish
;
517 const_reference
front() const { return *_M_start
; }
518 const_reference
back() const {
519 const_iterator __tmp
= _M_finish
;
524 size_type
size() const { return _M_finish
- _M_start
; }
525 size_type
max_size() const { return size_type(-1); }
526 bool empty() const { return _M_finish
== _M_start
; }
528 public: // Constructor, destructor.
529 explicit deque(const allocator_type
& __a
= allocator_type())
531 deque(const deque
& __x
) : _Base(__x
.get_allocator(), __x
.size())
532 { uninitialized_copy(__x
.begin(), __x
.end(), _M_start
); }
533 deque(size_type __n
, const value_type
& __value
,
534 const allocator_type
& __a
= allocator_type()) : _Base(__a
, __n
)
535 { _M_fill_initialize(__value
); }
536 explicit deque(size_type __n
) : _Base(allocator_type(), __n
)
537 { _M_fill_initialize(value_type()); }
539 #ifdef __STL_MEMBER_TEMPLATES
541 // Check whether it's an integral type. If so, it's not an iterator.
542 template <class _InputIterator
>
543 deque(_InputIterator __first
, _InputIterator __last
,
544 const allocator_type
& __a
= allocator_type()) : _Base(__a
) {
545 typedef typename _Is_integer
<_InputIterator
>::_Integral _Integral
;
546 _M_initialize_dispatch(__first
, __last
, _Integral());
549 template <class _Integer
>
550 void _M_initialize_dispatch(_Integer __n
, _Integer __x
, __true_type
) {
551 _M_initialize_map(__n
);
552 _M_fill_initialize(__x
);
555 template <class _InputIter
>
556 void _M_initialize_dispatch(_InputIter __first
, _InputIter __last
,
558 _M_range_initialize(__first
, __last
, __ITERATOR_CATEGORY(__first
));
561 #else /* __STL_MEMBER_TEMPLATES */
563 deque(const value_type
* __first
, const value_type
* __last
,
564 const allocator_type
& __a
= allocator_type())
565 : _Base(__a
, __last
- __first
)
566 { uninitialized_copy(__first
, __last
, _M_start
); }
567 deque(const_iterator __first
, const_iterator __last
,
568 const allocator_type
& __a
= allocator_type())
569 : _Base(__a
, __last
- __first
)
570 { uninitialized_copy(__first
, __last
, _M_start
); }
572 #endif /* __STL_MEMBER_TEMPLATES */
574 ~deque() { destroy(_M_start
, _M_finish
); }
576 deque
& operator= (const deque
& __x
) {
577 const size_type __len
= size();
579 if (__len
>= __x
.size())
580 erase(copy(__x
.begin(), __x
.end(), _M_start
), _M_finish
);
582 const_iterator __mid
= __x
.begin() + difference_type(__len
);
583 copy(__x
.begin(), __mid
, _M_start
);
584 insert(_M_finish
, __mid
, __x
.end());
590 void swap(deque
& __x
) {
591 __STD::swap(_M_start
, __x
._M_start
);
592 __STD::swap(_M_finish
, __x
._M_finish
);
593 __STD::swap(_M_map
, __x
._M_map
);
594 __STD::swap(_M_map_size
, __x
._M_map_size
);
598 // assign(), a generalized assignment member function. Two
599 // versions: one that takes a count, and one that takes a range.
600 // The range version is a member template, so we dispatch on whether
601 // or not the type is an integer.
603 void _M_fill_assign(size_type __n
, const _Tp
& __val
) {
605 fill(begin(), end(), __val
);
606 insert(end(), __n
- size(), __val
);
609 erase(begin() + __n
, end());
610 fill(begin(), end(), __val
);
614 void assign(size_type __n
, const _Tp
& __val
) {
615 _M_fill_assign(__n
, __val
);
618 #ifdef __STL_MEMBER_TEMPLATES
620 template <class _InputIterator
>
621 void assign(_InputIterator __first
, _InputIterator __last
) {
622 typedef typename _Is_integer
<_InputIterator
>::_Integral _Integral
;
623 _M_assign_dispatch(__first
, __last
, _Integral());
626 private: // helper functions for assign()
628 template <class _Integer
>
629 void _M_assign_dispatch(_Integer __n
, _Integer __val
, __true_type
)
630 { _M_fill_assign((size_type
) __n
, (_Tp
) __val
); }
632 template <class _InputIterator
>
633 void _M_assign_dispatch(_InputIterator __first
, _InputIterator __last
,
635 _M_assign_aux(__first
, __last
, __ITERATOR_CATEGORY(__first
));
638 template <class _InputIterator
>
639 void _M_assign_aux(_InputIterator __first
, _InputIterator __last
,
642 template <class _ForwardIterator
>
643 void _M_assign_aux(_ForwardIterator __first
, _ForwardIterator __last
,
644 forward_iterator_tag
) {
646 distance(__first
, __last
, __len
);
647 if (__len
> size()) {
648 _ForwardIterator __mid
= __first
;
649 advance(__mid
, size());
650 copy(__first
, __mid
, begin());
651 insert(end(), __mid
, __last
);
654 erase(copy(__first
, __last
, begin()), end());
657 #endif /* __STL_MEMBER_TEMPLATES */
659 public: // push_* and pop_*
661 void push_back(const value_type
& __t
) {
662 if (_M_finish
._M_cur
!= _M_finish
._M_last
- 1) {
663 construct(_M_finish
._M_cur
, __t
);
667 _M_push_back_aux(__t
);
671 if (_M_finish
._M_cur
!= _M_finish
._M_last
- 1) {
672 construct(_M_finish
._M_cur
);
679 void push_front(const value_type
& __t
) {
680 if (_M_start
._M_cur
!= _M_start
._M_first
) {
681 construct(_M_start
._M_cur
- 1, __t
);
685 _M_push_front_aux(__t
);
689 if (_M_start
._M_cur
!= _M_start
._M_first
) {
690 construct(_M_start
._M_cur
- 1);
699 if (_M_finish
._M_cur
!= _M_finish
._M_first
) {
701 destroy(_M_finish
._M_cur
);
708 if (_M_start
._M_cur
!= _M_start
._M_last
- 1) {
709 destroy(_M_start
._M_cur
);
718 iterator
insert(iterator position
, const value_type
& __x
) {
719 if (position
._M_cur
== _M_start
._M_cur
) {
723 else if (position
._M_cur
== _M_finish
._M_cur
) {
725 iterator __tmp
= _M_finish
;
730 return _M_insert_aux(position
, __x
);
734 iterator
insert(iterator __position
)
735 { return insert(__position
, value_type()); }
737 void insert(iterator __pos
, size_type __n
, const value_type
& __x
)
738 { _M_fill_insert(__pos
, __n
, __x
); }
740 void _M_fill_insert(iterator __pos
, size_type __n
, const value_type
& __x
);
742 #ifdef __STL_MEMBER_TEMPLATES
744 // Check whether it's an integral type. If so, it's not an iterator.
745 template <class _InputIterator
>
746 void insert(iterator __pos
, _InputIterator __first
, _InputIterator __last
) {
747 typedef typename _Is_integer
<_InputIterator
>::_Integral _Integral
;
748 _M_insert_dispatch(__pos
, __first
, __last
, _Integral());
751 template <class _Integer
>
752 void _M_insert_dispatch(iterator __pos
, _Integer __n
, _Integer __x
,
754 _M_fill_insert(__pos
, (size_type
) __n
, (value_type
) __x
);
757 template <class _InputIterator
>
758 void _M_insert_dispatch(iterator __pos
,
759 _InputIterator __first
, _InputIterator __last
,
761 insert(__pos
, __first
, __last
, __ITERATOR_CATEGORY(__first
));
764 #else /* __STL_MEMBER_TEMPLATES */
766 void insert(iterator __pos
,
767 const value_type
* __first
, const value_type
* __last
);
768 void insert(iterator __pos
,
769 const_iterator __first
, const_iterator __last
);
771 #endif /* __STL_MEMBER_TEMPLATES */
773 void resize(size_type __new_size
, const value_type
& __x
) {
774 const size_type __len
= size();
775 if (__new_size
< __len
)
776 erase(_M_start
+ __new_size
, _M_finish
);
778 insert(_M_finish
, __new_size
- __len
, __x
);
781 void resize(size_type new_size
) { resize(new_size
, value_type()); }
784 iterator
erase(iterator __pos
) {
785 iterator __next
= __pos
;
787 size_type __index
= __pos
- _M_start
;
788 if (__index
< (size() >> 1)) {
789 copy_backward(_M_start
, __pos
, __next
);
793 copy(__next
, _M_finish
, __pos
);
796 return _M_start
+ __index
;
799 iterator
erase(iterator __first
, iterator __last
);
802 protected: // Internal construction/destruction
804 void _M_fill_initialize(const value_type
& __value
);
806 #ifdef __STL_MEMBER_TEMPLATES
808 template <class _InputIterator
>
809 void _M_range_initialize(_InputIterator __first
, _InputIterator __last
,
812 template <class _ForwardIterator
>
813 void _M_range_initialize(_ForwardIterator __first
, _ForwardIterator __last
,
814 forward_iterator_tag
);
816 #endif /* __STL_MEMBER_TEMPLATES */
818 protected: // Internal push_* and pop_*
820 void _M_push_back_aux(const value_type
&);
821 void _M_push_back_aux();
822 void _M_push_front_aux(const value_type
&);
823 void _M_push_front_aux();
824 void _M_pop_back_aux();
825 void _M_pop_front_aux();
827 protected: // Internal insert functions
829 #ifdef __STL_MEMBER_TEMPLATES
831 template <class _InputIterator
>
832 void insert(iterator __pos
, _InputIterator __first
, _InputIterator __last
,
835 template <class _ForwardIterator
>
836 void insert(iterator __pos
,
837 _ForwardIterator __first
, _ForwardIterator __last
,
838 forward_iterator_tag
);
840 #endif /* __STL_MEMBER_TEMPLATES */
842 iterator
_M_insert_aux(iterator __pos
, const value_type
& __x
);
843 iterator
_M_insert_aux(iterator __pos
);
844 void _M_insert_aux(iterator __pos
, size_type __n
, const value_type
& __x
);
846 #ifdef __STL_MEMBER_TEMPLATES
848 template <class _ForwardIterator
>
849 void _M_insert_aux(iterator __pos
,
850 _ForwardIterator __first
, _ForwardIterator __last
,
853 #else /* __STL_MEMBER_TEMPLATES */
855 void _M_insert_aux(iterator __pos
,
856 const value_type
* __first
, const value_type
* __last
,
859 void _M_insert_aux(iterator __pos
,
860 const_iterator __first
, const_iterator __last
,
863 #endif /* __STL_MEMBER_TEMPLATES */
865 iterator
_M_reserve_elements_at_front(size_type __n
) {
866 size_type __vacancies
= _M_start
._M_cur
- _M_start
._M_first
;
867 if (__n
> __vacancies
)
868 _M_new_elements_at_front(__n
- __vacancies
);
869 return _M_start
- difference_type(__n
);
872 iterator
_M_reserve_elements_at_back(size_type __n
) {
873 size_type __vacancies
= (_M_finish
._M_last
- _M_finish
._M_cur
) - 1;
874 if (__n
> __vacancies
)
875 _M_new_elements_at_back(__n
- __vacancies
);
876 return _M_finish
+ difference_type(__n
);
879 void _M_new_elements_at_front(size_type __new_elements
);
880 void _M_new_elements_at_back(size_type __new_elements
);
882 protected: // Allocation of _M_map and nodes
884 // Makes sure the _M_map has space for new nodes. Does not actually
885 // add the nodes. Can invalidate _M_map pointers. (And consequently,
888 void _M_reserve_map_at_back (size_type __nodes_to_add
= 1) {
889 if (__nodes_to_add
+ 1 > _M_map_size
- (_M_finish
._M_node
- _M_map
))
890 _M_reallocate_map(__nodes_to_add
, false);
893 void _M_reserve_map_at_front (size_type __nodes_to_add
= 1) {
894 if (__nodes_to_add
> size_type(_M_start
._M_node
- _M_map
))
895 _M_reallocate_map(__nodes_to_add
, true);
898 void _M_reallocate_map(size_type __nodes_to_add
, bool __add_at_front
);
901 // Non-inline member functions
903 #ifdef __STL_MEMBER_TEMPLATES
905 template <class _Tp
, class _Alloc
>
906 template <class _InputIter
>
907 void deque
<_Tp
, _Alloc
>
908 ::_M_assign_aux(_InputIter __first
, _InputIter __last
, input_iterator_tag
)
910 iterator __cur
= begin();
911 for ( ; __first
!= __last
&& __cur
!= end(); ++__cur
, ++__first
)
913 if (__first
== __last
)
916 insert(end(), __first
, __last
);
919 #endif /* __STL_MEMBER_TEMPLATES */
921 template <class _Tp
, class _Alloc
>
922 void deque
<_Tp
, _Alloc
>::_M_fill_insert(iterator __pos
,
923 size_type __n
, const value_type
& __x
)
925 if (__pos
._M_cur
== _M_start
._M_cur
) {
926 iterator __new_start
= _M_reserve_elements_at_front(__n
);
928 uninitialized_fill(__new_start
, _M_start
, __x
);
929 _M_start
= __new_start
;
931 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
933 else if (__pos
._M_cur
== _M_finish
._M_cur
) {
934 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
936 uninitialized_fill(_M_finish
, __new_finish
, __x
);
937 _M_finish
= __new_finish
;
939 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
940 __new_finish
._M_node
+ 1));
943 _M_insert_aux(__pos
, __n
, __x
);
946 #ifndef __STL_MEMBER_TEMPLATES
948 template <class _Tp
, class _Alloc
>
949 void deque
<_Tp
, _Alloc
>::insert(iterator __pos
,
950 const value_type
* __first
,
951 const value_type
* __last
) {
952 size_type __n
= __last
- __first
;
953 if (__pos
._M_cur
== _M_start
._M_cur
) {
954 iterator __new_start
= _M_reserve_elements_at_front(__n
);
956 uninitialized_copy(__first
, __last
, __new_start
);
957 _M_start
= __new_start
;
959 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
961 else if (__pos
._M_cur
== _M_finish
._M_cur
) {
962 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
964 uninitialized_copy(__first
, __last
, _M_finish
);
965 _M_finish
= __new_finish
;
967 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
968 __new_finish
._M_node
+ 1));
971 _M_insert_aux(__pos
, __first
, __last
, __n
);
974 template <class _Tp
, class _Alloc
>
975 void deque
<_Tp
,_Alloc
>::insert(iterator __pos
,
976 const_iterator __first
, const_iterator __last
)
978 size_type __n
= __last
- __first
;
979 if (__pos
._M_cur
== _M_start
._M_cur
) {
980 iterator __new_start
= _M_reserve_elements_at_front(__n
);
982 uninitialized_copy(__first
, __last
, __new_start
);
983 _M_start
= __new_start
;
985 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
987 else if (__pos
._M_cur
== _M_finish
._M_cur
) {
988 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
990 uninitialized_copy(__first
, __last
, _M_finish
);
991 _M_finish
= __new_finish
;
993 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
994 __new_finish
._M_node
+ 1));
997 _M_insert_aux(__pos
, __first
, __last
, __n
);
1000 #endif /* __STL_MEMBER_TEMPLATES */
1002 template <class _Tp
, class _Alloc
>
1003 typename deque
<_Tp
,_Alloc
>::iterator
1004 deque
<_Tp
,_Alloc
>::erase(iterator __first
, iterator __last
)
1006 if (__first
== _M_start
&& __last
== _M_finish
) {
1011 difference_type __n
= __last
- __first
;
1012 difference_type __elems_before
= __first
- _M_start
;
1013 if (static_cast<size_type
>(__elems_before
) < (size() - __n
) / 2) {
1014 copy_backward(_M_start
, __first
, __last
);
1015 iterator __new_start
= _M_start
+ __n
;
1016 destroy(_M_start
, __new_start
);
1017 _M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
);
1018 _M_start
= __new_start
;
1021 copy(__last
, _M_finish
, __first
);
1022 iterator __new_finish
= _M_finish
- __n
;
1023 destroy(__new_finish
, _M_finish
);
1024 _M_destroy_nodes(__new_finish
._M_node
+ 1, _M_finish
._M_node
+ 1);
1025 _M_finish
= __new_finish
;
1027 return _M_start
+ __elems_before
;
1031 template <class _Tp
, class _Alloc
>
1032 void deque
<_Tp
,_Alloc
>::clear()
1034 for (_Map_pointer __node
= _M_start
._M_node
+ 1;
1035 __node
< _M_finish
._M_node
;
1037 destroy(*__node
, *__node
+ _S_buffer_size());
1038 _M_deallocate_node(*__node
);
1041 if (_M_start
._M_node
!= _M_finish
._M_node
) {
1042 destroy(_M_start
._M_cur
, _M_start
._M_last
);
1043 destroy(_M_finish
._M_first
, _M_finish
._M_cur
);
1044 _M_deallocate_node(_M_finish
._M_first
);
1047 destroy(_M_start
._M_cur
, _M_finish
._M_cur
);
1049 _M_finish
= _M_start
;
1052 // Precondition: _M_start and _M_finish have already been initialized,
1053 // but none of the deque's elements have yet been constructed.
1054 template <class _Tp
, class _Alloc
>
1055 void deque
<_Tp
,_Alloc
>::_M_fill_initialize(const value_type
& __value
) {
1058 for (__cur
= _M_start
._M_node
; __cur
< _M_finish
._M_node
; ++__cur
)
1059 uninitialized_fill(*__cur
, *__cur
+ _S_buffer_size(), __value
);
1060 uninitialized_fill(_M_finish
._M_first
, _M_finish
._M_cur
, __value
);
1062 __STL_UNWIND(destroy(_M_start
, iterator(*__cur
, __cur
)));
1065 #ifdef __STL_MEMBER_TEMPLATES
1067 template <class _Tp
, class _Alloc
> template <class _InputIterator
>
1068 void deque
<_Tp
,_Alloc
>::_M_range_initialize(_InputIterator __first
,
1069 _InputIterator __last
,
1072 _M_initialize_map(0);
1074 for ( ; __first
!= __last
; ++__first
)
1075 push_back(*__first
);
1077 __STL_UNWIND(clear());
1080 template <class _Tp
, class _Alloc
> template <class _ForwardIterator
>
1081 void deque
<_Tp
,_Alloc
>::_M_range_initialize(_ForwardIterator __first
,
1082 _ForwardIterator __last
,
1083 forward_iterator_tag
)
1086 distance(__first
, __last
, __n
);
1087 _M_initialize_map(__n
);
1089 _Map_pointer __cur_node
;
1091 for (__cur_node
= _M_start
._M_node
;
1092 __cur_node
< _M_finish
._M_node
;
1094 _ForwardIterator __mid
= __first
;
1095 advance(__mid
, _S_buffer_size());
1096 uninitialized_copy(__first
, __mid
, *__cur_node
);
1099 uninitialized_copy(__first
, __last
, _M_finish
._M_first
);
1101 __STL_UNWIND(destroy(_M_start
, iterator(*__cur_node
, __cur_node
)));
1104 #endif /* __STL_MEMBER_TEMPLATES */
1106 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1107 template <class _Tp
, class _Alloc
>
1108 void deque
<_Tp
,_Alloc
>::_M_push_back_aux(const value_type
& __t
)
1110 value_type __t_copy
= __t
;
1111 _M_reserve_map_at_back();
1112 *(_M_finish
._M_node
+ 1) = _M_allocate_node();
1114 construct(_M_finish
._M_cur
, __t_copy
);
1115 _M_finish
._M_set_node(_M_finish
._M_node
+ 1);
1116 _M_finish
._M_cur
= _M_finish
._M_first
;
1118 __STL_UNWIND(_M_deallocate_node(*(_M_finish
._M_node
+ 1)));
1121 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
1122 template <class _Tp
, class _Alloc
>
1123 void deque
<_Tp
,_Alloc
>::_M_push_back_aux()
1125 _M_reserve_map_at_back();
1126 *(_M_finish
._M_node
+ 1) = _M_allocate_node();
1128 construct(_M_finish
._M_cur
);
1129 _M_finish
._M_set_node(_M_finish
._M_node
+ 1);
1130 _M_finish
._M_cur
= _M_finish
._M_first
;
1132 __STL_UNWIND(_M_deallocate_node(*(_M_finish
._M_node
+ 1)));
1135 // Called only if _M_start._M_cur == _M_start._M_first.
1136 template <class _Tp
, class _Alloc
>
1137 void deque
<_Tp
,_Alloc
>::_M_push_front_aux(const value_type
& __t
)
1139 value_type __t_copy
= __t
;
1140 _M_reserve_map_at_front();
1141 *(_M_start
._M_node
- 1) = _M_allocate_node();
1143 _M_start
._M_set_node(_M_start
._M_node
- 1);
1144 _M_start
._M_cur
= _M_start
._M_last
- 1;
1145 construct(_M_start
._M_cur
, __t_copy
);
1147 __STL_UNWIND((++_M_start
, _M_deallocate_node(*(_M_start
._M_node
- 1))));
1150 // Called only if _M_start._M_cur == _M_start._M_first.
1151 template <class _Tp
, class _Alloc
>
1152 void deque
<_Tp
,_Alloc
>::_M_push_front_aux()
1154 _M_reserve_map_at_front();
1155 *(_M_start
._M_node
- 1) = _M_allocate_node();
1157 _M_start
._M_set_node(_M_start
._M_node
- 1);
1158 _M_start
._M_cur
= _M_start
._M_last
- 1;
1159 construct(_M_start
._M_cur
);
1161 __STL_UNWIND((++_M_start
, _M_deallocate_node(*(_M_start
._M_node
- 1))));
1164 // Called only if _M_finish._M_cur == _M_finish._M_first.
1165 template <class _Tp
, class _Alloc
>
1166 void deque
<_Tp
,_Alloc
>::_M_pop_back_aux()
1168 _M_deallocate_node(_M_finish
._M_first
);
1169 _M_finish
._M_set_node(_M_finish
._M_node
- 1);
1170 _M_finish
._M_cur
= _M_finish
._M_last
- 1;
1171 destroy(_M_finish
._M_cur
);
1174 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
1175 // if the deque has at least one element (a precondition for this member
1176 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
1177 // must have at least two nodes.
1178 template <class _Tp
, class _Alloc
>
1179 void deque
<_Tp
,_Alloc
>::_M_pop_front_aux()
1181 destroy(_M_start
._M_cur
);
1182 _M_deallocate_node(_M_start
._M_first
);
1183 _M_start
._M_set_node(_M_start
._M_node
+ 1);
1184 _M_start
._M_cur
= _M_start
._M_first
;
1187 #ifdef __STL_MEMBER_TEMPLATES
1189 template <class _Tp
, class _Alloc
> template <class _InputIterator
>
1190 void deque
<_Tp
,_Alloc
>::insert(iterator __pos
,
1191 _InputIterator __first
, _InputIterator __last
,
1194 copy(__first
, __last
, inserter(*this, __pos
));
1197 template <class _Tp
, class _Alloc
> template <class _ForwardIterator
>
1199 deque
<_Tp
,_Alloc
>::insert(iterator __pos
,
1200 _ForwardIterator __first
, _ForwardIterator __last
,
1201 forward_iterator_tag
) {
1203 distance(__first
, __last
, __n
);
1204 if (__pos
._M_cur
== _M_start
._M_cur
) {
1205 iterator __new_start
= _M_reserve_elements_at_front(__n
);
1207 uninitialized_copy(__first
, __last
, __new_start
);
1208 _M_start
= __new_start
;
1210 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
1212 else if (__pos
._M_cur
== _M_finish
._M_cur
) {
1213 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
1215 uninitialized_copy(__first
, __last
, _M_finish
);
1216 _M_finish
= __new_finish
;
1218 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
1219 __new_finish
._M_node
+ 1));
1222 _M_insert_aux(__pos
, __first
, __last
, __n
);
1225 #endif /* __STL_MEMBER_TEMPLATES */
1227 template <class _Tp
, class _Alloc
>
1228 typename deque
<_Tp
, _Alloc
>::iterator
1229 deque
<_Tp
,_Alloc
>::_M_insert_aux(iterator __pos
, const value_type
& __x
)
1231 difference_type __index
= __pos
- _M_start
;
1232 value_type __x_copy
= __x
;
1233 if (static_cast<size_type
>(__index
) < size() / 2) {
1234 push_front(front());
1235 iterator __front1
= _M_start
;
1237 iterator __front2
= __front1
;
1239 __pos
= _M_start
+ __index
;
1240 iterator __pos1
= __pos
;
1242 copy(__front2
, __pos1
, __front1
);
1246 iterator __back1
= _M_finish
;
1248 iterator __back2
= __back1
;
1250 __pos
= _M_start
+ __index
;
1251 copy_backward(__pos
, __back2
, __back1
);
1257 template <class _Tp
, class _Alloc
>
1258 typename deque
<_Tp
,_Alloc
>::iterator
1259 deque
<_Tp
,_Alloc
>::_M_insert_aux(iterator __pos
)
1261 difference_type __index
= __pos
- _M_start
;
1262 if (static_cast<size_type
>(__index
) < size() / 2) {
1263 push_front(front());
1264 iterator __front1
= _M_start
;
1266 iterator __front2
= __front1
;
1268 __pos
= _M_start
+ __index
;
1269 iterator __pos1
= __pos
;
1271 copy(__front2
, __pos1
, __front1
);
1275 iterator __back1
= _M_finish
;
1277 iterator __back2
= __back1
;
1279 __pos
= _M_start
+ __index
;
1280 copy_backward(__pos
, __back2
, __back1
);
1282 *__pos
= value_type();
1286 template <class _Tp
, class _Alloc
>
1287 void deque
<_Tp
,_Alloc
>::_M_insert_aux(iterator __pos
,
1289 const value_type
& __x
)
1291 const difference_type __elems_before
= __pos
- _M_start
;
1292 size_type __length
= this->size();
1293 value_type __x_copy
= __x
;
1294 if (__elems_before
< difference_type(__length
/ 2)) {
1295 iterator __new_start
= _M_reserve_elements_at_front(__n
);
1296 iterator __old_start
= _M_start
;
1297 __pos
= _M_start
+ __elems_before
;
1299 if (__elems_before
>= difference_type(__n
)) {
1300 iterator __start_n
= _M_start
+ difference_type(__n
);
1301 uninitialized_copy(_M_start
, __start_n
, __new_start
);
1302 _M_start
= __new_start
;
1303 copy(__start_n
, __pos
, __old_start
);
1304 fill(__pos
- difference_type(__n
), __pos
, __x_copy
);
1307 __uninitialized_copy_fill(_M_start
, __pos
, __new_start
,
1308 _M_start
, __x_copy
);
1309 _M_start
= __new_start
;
1310 fill(__old_start
, __pos
, __x_copy
);
1313 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
1316 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
1317 iterator __old_finish
= _M_finish
;
1318 const difference_type __elems_after
=
1319 difference_type(__length
) - __elems_before
;
1320 __pos
= _M_finish
- __elems_after
;
1322 if (__elems_after
> difference_type(__n
)) {
1323 iterator __finish_n
= _M_finish
- difference_type(__n
);
1324 uninitialized_copy(__finish_n
, _M_finish
, _M_finish
);
1325 _M_finish
= __new_finish
;
1326 copy_backward(__pos
, __finish_n
, __old_finish
);
1327 fill(__pos
, __pos
+ difference_type(__n
), __x_copy
);
1330 __uninitialized_fill_copy(_M_finish
, __pos
+ difference_type(__n
),
1331 __x_copy
, __pos
, _M_finish
);
1332 _M_finish
= __new_finish
;
1333 fill(__pos
, __old_finish
, __x_copy
);
1336 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
1337 __new_finish
._M_node
+ 1));
1341 #ifdef __STL_MEMBER_TEMPLATES
1343 template <class _Tp
, class _Alloc
> template <class _ForwardIterator
>
1344 void deque
<_Tp
,_Alloc
>::_M_insert_aux(iterator __pos
,
1345 _ForwardIterator __first
,
1346 _ForwardIterator __last
,
1349 const difference_type __elemsbefore
= __pos
- _M_start
;
1350 size_type __length
= size();
1351 if (static_cast<size_type
>(__elemsbefore
) < __length
/ 2) {
1352 iterator __new_start
= _M_reserve_elements_at_front(__n
);
1353 iterator __old_start
= _M_start
;
1354 __pos
= _M_start
+ __elemsbefore
;
1356 if (__elemsbefore
>= difference_type(__n
)) {
1357 iterator __start_n
= _M_start
+ difference_type(__n
);
1358 uninitialized_copy(_M_start
, __start_n
, __new_start
);
1359 _M_start
= __new_start
;
1360 copy(__start_n
, __pos
, __old_start
);
1361 copy(__first
, __last
, __pos
- difference_type(__n
));
1364 _ForwardIterator __mid
= __first
;
1365 advance(__mid
, difference_type(__n
) - __elemsbefore
);
1366 __uninitialized_copy_copy(_M_start
, __pos
, __first
, __mid
,
1368 _M_start
= __new_start
;
1369 copy(__mid
, __last
, __old_start
);
1372 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
1375 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
1376 iterator __old_finish
= _M_finish
;
1377 const difference_type __elemsafter
=
1378 difference_type(__length
) - __elemsbefore
;
1379 __pos
= _M_finish
- __elemsafter
;
1381 if (__elemsafter
> difference_type(__n
)) {
1382 iterator __finish_n
= _M_finish
- difference_type(__n
);
1383 uninitialized_copy(__finish_n
, _M_finish
, _M_finish
);
1384 _M_finish
= __new_finish
;
1385 copy_backward(__pos
, __finish_n
, __old_finish
);
1386 copy(__first
, __last
, __pos
);
1389 _ForwardIterator __mid
= __first
;
1390 advance(__mid
, __elemsafter
);
1391 __uninitialized_copy_copy(__mid
, __last
, __pos
, _M_finish
, _M_finish
);
1392 _M_finish
= __new_finish
;
1393 copy(__first
, __mid
, __pos
);
1396 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
1397 __new_finish
._M_node
+ 1));
1401 #else /* __STL_MEMBER_TEMPLATES */
1403 template <class _Tp
, class _Alloc
>
1404 void deque
<_Tp
,_Alloc
>::_M_insert_aux(iterator __pos
,
1405 const value_type
* __first
,
1406 const value_type
* __last
,
1409 const difference_type __elemsbefore
= __pos
- _M_start
;
1410 size_type __length
= size();
1411 if (__elemsbefore
< __length
/ 2) {
1412 iterator __new_start
= _M_reserve_elements_at_front(__n
);
1413 iterator __old_start
= _M_start
;
1414 __pos
= _M_start
+ __elemsbefore
;
1416 if (__elemsbefore
>= difference_type(__n
)) {
1417 iterator __start_n
= _M_start
+ difference_type(__n
);
1418 uninitialized_copy(_M_start
, __start_n
, __new_start
);
1419 _M_start
= __new_start
;
1420 copy(__start_n
, __pos
, __old_start
);
1421 copy(__first
, __last
, __pos
- difference_type(__n
));
1424 const value_type
* __mid
=
1425 __first
+ (difference_type(__n
) - __elemsbefore
);
1426 __uninitialized_copy_copy(_M_start
, __pos
, __first
, __mid
,
1428 _M_start
= __new_start
;
1429 copy(__mid
, __last
, __old_start
);
1432 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
1435 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
1436 iterator __old_finish
= _M_finish
;
1437 const difference_type __elemsafter
=
1438 difference_type(__length
) - __elemsbefore
;
1439 __pos
= _M_finish
- __elemsafter
;
1441 if (__elemsafter
> difference_type(__n
)) {
1442 iterator __finish_n
= _M_finish
- difference_type(__n
);
1443 uninitialized_copy(__finish_n
, _M_finish
, _M_finish
);
1444 _M_finish
= __new_finish
;
1445 copy_backward(__pos
, __finish_n
, __old_finish
);
1446 copy(__first
, __last
, __pos
);
1449 const value_type
* __mid
= __first
+ __elemsafter
;
1450 __uninitialized_copy_copy(__mid
, __last
, __pos
, _M_finish
, _M_finish
);
1451 _M_finish
= __new_finish
;
1452 copy(__first
, __mid
, __pos
);
1455 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
1456 __new_finish
._M_node
+ 1));
1460 template <class _Tp
, class _Alloc
>
1461 void deque
<_Tp
,_Alloc
>::_M_insert_aux(iterator __pos
,
1462 const_iterator __first
,
1463 const_iterator __last
,
1466 const difference_type __elemsbefore
= __pos
- _M_start
;
1467 size_type __length
= size();
1468 if (__elemsbefore
< __length
/ 2) {
1469 iterator __new_start
= _M_reserve_elements_at_front(__n
);
1470 iterator __old_start
= _M_start
;
1471 __pos
= _M_start
+ __elemsbefore
;
1473 if (__elemsbefore
>= __n
) {
1474 iterator __start_n
= _M_start
+ __n
;
1475 uninitialized_copy(_M_start
, __start_n
, __new_start
);
1476 _M_start
= __new_start
;
1477 copy(__start_n
, __pos
, __old_start
);
1478 copy(__first
, __last
, __pos
- difference_type(__n
));
1481 const_iterator __mid
= __first
+ (__n
- __elemsbefore
);
1482 __uninitialized_copy_copy(_M_start
, __pos
, __first
, __mid
,
1484 _M_start
= __new_start
;
1485 copy(__mid
, __last
, __old_start
);
1488 __STL_UNWIND(_M_destroy_nodes(__new_start
._M_node
, _M_start
._M_node
));
1491 iterator __new_finish
= _M_reserve_elements_at_back(__n
);
1492 iterator __old_finish
= _M_finish
;
1493 const difference_type __elemsafter
= __length
- __elemsbefore
;
1494 __pos
= _M_finish
- __elemsafter
;
1496 if (__elemsafter
> __n
) {
1497 iterator __finish_n
= _M_finish
- difference_type(__n
);
1498 uninitialized_copy(__finish_n
, _M_finish
, _M_finish
);
1499 _M_finish
= __new_finish
;
1500 copy_backward(__pos
, __finish_n
, __old_finish
);
1501 copy(__first
, __last
, __pos
);
1504 const_iterator __mid
= __first
+ __elemsafter
;
1505 __uninitialized_copy_copy(__mid
, __last
, __pos
, _M_finish
, _M_finish
);
1506 _M_finish
= __new_finish
;
1507 copy(__first
, __mid
, __pos
);
1510 __STL_UNWIND(_M_destroy_nodes(_M_finish
._M_node
+ 1,
1511 __new_finish
._M_node
+ 1));
1515 #endif /* __STL_MEMBER_TEMPLATES */
1517 template <class _Tp
, class _Alloc
>
1518 void deque
<_Tp
,_Alloc
>::_M_new_elements_at_front(size_type __new_elems
)
1520 size_type __new_nodes
1521 = (__new_elems
+ _S_buffer_size() - 1) / _S_buffer_size();
1522 _M_reserve_map_at_front(__new_nodes
);
1525 for (__i
= 1; __i
<= __new_nodes
; ++__i
)
1526 *(_M_start
._M_node
- __i
) = _M_allocate_node();
1528 # ifdef __STL_USE_EXCEPTIONS
1530 for (size_type __j
= 1; __j
< __i
; ++__j
)
1531 _M_deallocate_node(*(_M_start
._M_node
- __j
));
1534 # endif /* __STL_USE_EXCEPTIONS */
1537 template <class _Tp
, class _Alloc
>
1538 void deque
<_Tp
,_Alloc
>::_M_new_elements_at_back(size_type __new_elems
)
1540 size_type __new_nodes
1541 = (__new_elems
+ _S_buffer_size() - 1) / _S_buffer_size();
1542 _M_reserve_map_at_back(__new_nodes
);
1545 for (__i
= 1; __i
<= __new_nodes
; ++__i
)
1546 *(_M_finish
._M_node
+ __i
) = _M_allocate_node();
1548 # ifdef __STL_USE_EXCEPTIONS
1550 for (size_type __j
= 1; __j
< __i
; ++__j
)
1551 _M_deallocate_node(*(_M_finish
._M_node
+ __j
));
1554 # endif /* __STL_USE_EXCEPTIONS */
1557 template <class _Tp
, class _Alloc
>
1558 void deque
<_Tp
,_Alloc
>::_M_reallocate_map(size_type __nodes_to_add
,
1559 bool __add_at_front
)
1561 size_type __old_num_nodes
= _M_finish
._M_node
- _M_start
._M_node
+ 1;
1562 size_type __new_num_nodes
= __old_num_nodes
+ __nodes_to_add
;
1564 _Map_pointer __new_nstart
;
1565 if (_M_map_size
> 2 * __new_num_nodes
) {
1566 __new_nstart
= _M_map
+ (_M_map_size
- __new_num_nodes
) / 2
1567 + (__add_at_front
? __nodes_to_add
: 0);
1568 if (__new_nstart
< _M_start
._M_node
)
1569 copy(_M_start
._M_node
, _M_finish
._M_node
+ 1, __new_nstart
);
1571 copy_backward(_M_start
._M_node
, _M_finish
._M_node
+ 1,
1572 __new_nstart
+ __old_num_nodes
);
1575 size_type __new_map_size
=
1576 _M_map_size
+ max(_M_map_size
, __nodes_to_add
) + 2;
1578 _Map_pointer __new_map
= _M_allocate_map(__new_map_size
);
1579 __new_nstart
= __new_map
+ (__new_map_size
- __new_num_nodes
) / 2
1580 + (__add_at_front
? __nodes_to_add
: 0);
1581 copy(_M_start
._M_node
, _M_finish
._M_node
+ 1, __new_nstart
);
1582 _M_deallocate_map(_M_map
, _M_map_size
);
1585 _M_map_size
= __new_map_size
;
1588 _M_start
._M_set_node(__new_nstart
);
1589 _M_finish
._M_set_node(__new_nstart
+ __old_num_nodes
- 1);
1593 // Nonmember functions.
1595 template <class _Tp
, class _Alloc
>
1596 inline bool operator==(const deque
<_Tp
, _Alloc
>& __x
,
1597 const deque
<_Tp
, _Alloc
>& __y
) {
1598 return __x
.size() == __y
.size() &&
1599 equal(__x
.begin(), __x
.end(), __y
.begin());
1602 template <class _Tp
, class _Alloc
>
1603 inline bool operator<(const deque
<_Tp
, _Alloc
>& __x
,
1604 const deque
<_Tp
, _Alloc
>& __y
) {
1605 return lexicographical_compare(__x
.begin(), __x
.end(),
1606 __y
.begin(), __y
.end());
1609 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
1611 template <class _Tp
, class _Alloc
>
1612 inline bool operator!=(const deque
<_Tp
, _Alloc
>& __x
,
1613 const deque
<_Tp
, _Alloc
>& __y
) {
1614 return !(__x
== __y
);
1617 template <class _Tp
, class _Alloc
>
1618 inline bool operator>(const deque
<_Tp
, _Alloc
>& __x
,
1619 const deque
<_Tp
, _Alloc
>& __y
) {
1623 template <class _Tp
, class _Alloc
>
1624 inline bool operator<=(const deque
<_Tp
, _Alloc
>& __x
,
1625 const deque
<_Tp
, _Alloc
>& __y
) {
1626 return !(__y
< __x
);
1628 template <class _Tp
, class _Alloc
>
1629 inline bool operator>=(const deque
<_Tp
, _Alloc
>& __x
,
1630 const deque
<_Tp
, _Alloc
>& __y
) {
1631 return !(__x
< __y
);
1634 template <class _Tp
, class _Alloc
>
1635 inline void swap(deque
<_Tp
,_Alloc
>& __x
, deque
<_Tp
,_Alloc
>& __y
) {
1639 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
1641 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
1642 #pragma reset woff 1174
1643 #pragma reset woff 1375
1648 #endif /* __SGI_STL_INTERNAL_DEQUE_H */