4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_DEQUE_H
31 #define _STLP_INTERNAL_DEQUE_H
33 #ifndef _STLP_INTERNAL_ALGOBASE_H
34 # include <stl/_algobase.h>
37 #ifndef _STLP_INTERNAL_ALLOC_H
38 # include <stl/_alloc.h>
41 #ifndef _STLP_INTERNAL_ITERATOR_H
42 # include <stl/_iterator.h>
45 #ifndef _STLP_INTERNAL_UNINITIALIZED_H
46 # include <stl/_uninitialized.h>
49 #ifndef _STLP_RANGE_ERRORS_H
50 # include <stl/_range_errors.h>
54 * For any nonsingular iterator i:
55 * i.node is the address of an element in the map array. The
56 * contents of i.node is a pointer to the beginning of a node.
57 * i.first == *(i.node)
58 * i.last == i.first + node_size
59 * i.cur is a pointer in the range [i.first, i.last). NOTE:
60 * the implication of this is that i.cur is always a dereferenceable
61 * pointer, even if i is a past-the-end iterator.
62 * Start and Finish are always nonsingular iterators. NOTE: this means
63 * that an empty deque must have one node, and that a deque
64 * with N elements, where N is the buffer size, must have two nodes.
65 * For every node other than start.node and finish.node, every element
66 * in the node is an initialized object. If start.node == finish.node,
67 * then [start.cur, finish.cur) are initialized objects, and
68 * the elements outside that range are uninitialized storage. Otherwise,
69 * [start.cur, start.last) and [finish.first, finish.cur) are initialized
70 * objects, and [start.first, start.cur) and [finish.cur, finish.last)
71 * are uninitialized storage.
72 * [map, map + map_size) is a valid, non-empty range.
73 * [start.node, finish.node] is a valid range contained within
74 * [map, map + map_size).
75 * A pointer in the range [map, map + map_size) points to an allocated node
76 * if and only if the pointer is in the range [start.node, finish.node].
81 _STLP_MOVE_TO_PRIV_NAMESPACE
84 struct _Deque_iterator_base {
87 _blocksize = _MAX_BYTES,
88 __buffer_size = (sizeof(_Tp) < (size_t)_blocksize ?
89 ( (size_t)_blocksize / sizeof(_Tp)) : size_t(1))
92 typedef random_access_iterator_tag iterator_category;
94 typedef _Tp value_type;
95 typedef size_t size_type;
96 typedef ptrdiff_t difference_type;
98 typedef value_type** _Map_pointer;
100 typedef _Deque_iterator_base< _Tp > _Self;
103 value_type* _M_first;
105 _Map_pointer _M_node;
107 _Deque_iterator_base(value_type* __x, _Map_pointer __y)
108 : _M_cur(__x), _M_first(*__y),
109 _M_last(*__y + __buffer_size), _M_node(__y) {}
111 _Deque_iterator_base() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
113 // see comment in doc/README.evc4 and doc/README.evc8
114 #if defined (_STLP_MSVC) && (_STLP_MSVC <= 1401) && defined (MIPS) && defined (NDEBUG)
115 _Deque_iterator_base(_Deque_iterator_base const& __other)
116 : _M_cur(__other._M_cur), _M_first(__other._M_first),
117 _M_last(__other._M_last), _M_node(__other._M_node) {}
120 difference_type _M_subtract(const _Self& __x) const {
121 return difference_type(__buffer_size) * (_M_node - __x._M_node - 1) +
122 (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
125 void _M_increment() {
126 if (++_M_cur == _M_last) {
127 _M_set_node(_M_node + 1);
132 void _M_decrement() {
133 if (_M_cur == _M_first) {
134 _M_set_node(_M_node - 1);
140 void _M_advance(difference_type __n) {
141 difference_type __offset = __n + (_M_cur - _M_first);
142 if (__offset >= 0 && __offset < difference_type(__buffer_size))
145 difference_type __node_offset =
146 __offset > 0 ? __offset / __buffer_size
147 : -difference_type((-__offset - 1) / __buffer_size) - 1;
148 _M_set_node(_M_node + __node_offset);
151 (__offset - __node_offset * difference_type(__buffer_size));
155 void _M_set_node(_Map_pointer __new_node) {
156 _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(__buffer_size);
161 template <class _Tp, class _Traits>
162 struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
163 typedef random_access_iterator_tag iterator_category;
164 typedef _Tp value_type;
165 typedef typename _Traits::reference reference;
166 typedef typename _Traits::pointer pointer;
167 typedef size_t size_type;
168 typedef ptrdiff_t difference_type;
169 typedef value_type** _Map_pointer;
171 typedef _Deque_iterator_base< _Tp > _Base;
172 typedef _Deque_iterator<_Tp, _Traits> _Self;
173 typedef typename _Traits::_NonConstTraits _NonConstTraits;
174 typedef _Deque_iterator<_Tp, _NonConstTraits> iterator;
175 typedef typename _Traits::_ConstTraits _ConstTraits;
176 typedef _Deque_iterator<_Tp, _ConstTraits> const_iterator;
178 _Deque_iterator(value_type* __x, _Map_pointer __y) :
179 _Deque_iterator_base<value_type>(__x,__y) {}
182 //copy constructor for iterator and constructor from iterator for const_iterator
183 _Deque_iterator(const iterator& __x) :
184 _Deque_iterator_base<value_type>(__x) {}
186 reference operator*() const {
187 return *this->_M_cur;
190 _STLP_DEFINE_ARROW_OPERATOR
192 difference_type operator-(const const_iterator& __x) const { return this->_M_subtract(__x); }
194 _Self& operator++() { this->_M_increment(); return *this; }
195 _Self operator++(int) {
201 _Self& operator--() { this->_M_decrement(); return *this; }
202 _Self operator--(int) {
208 _Self& operator+=(difference_type __n) { this->_M_advance(__n); return *this; }
209 _Self operator+(difference_type __n) const {
214 _Self& operator-=(difference_type __n) { return *this += -__n; }
215 _Self operator-(difference_type __n) const {
220 reference operator[](difference_type __n) const { return *(*this + __n); }
224 template <class _Tp, class _Traits>
225 inline _Deque_iterator<_Tp, _Traits> _STLP_CALL
226 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Traits>& __x)
227 { return __x + __n; }
230 #if defined (_STLP_USE_SEPARATE_RELOPS_NAMESPACE)
232 inline bool _STLP_CALL
233 operator==(const _Deque_iterator_base<_Tp >& __x,
234 const _Deque_iterator_base<_Tp >& __y)
235 { return __x._M_cur == __y._M_cur; }
238 inline bool _STLP_CALL
239 operator < (const _Deque_iterator_base<_Tp >& __x,
240 const _Deque_iterator_base<_Tp >& __y) {
241 return (__x._M_node == __y._M_node) ?
242 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
246 inline bool _STLP_CALL
247 operator!=(const _Deque_iterator_base<_Tp >& __x,
248 const _Deque_iterator_base<_Tp >& __y)
249 { return __x._M_cur != __y._M_cur; }
252 inline bool _STLP_CALL
253 operator>(const _Deque_iterator_base<_Tp >& __x,
254 const _Deque_iterator_base<_Tp >& __y)
255 { return __y < __x; }
258 inline bool _STLP_CALL operator>=(const _Deque_iterator_base<_Tp >& __x,
259 const _Deque_iterator_base<_Tp >& __y)
260 { return !(__x < __y); }
263 inline bool _STLP_CALL operator<=(const _Deque_iterator_base<_Tp >& __x,
264 const _Deque_iterator_base<_Tp >& __y)
265 { return !(__y < __x); }
267 #else /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
269 template <class _Tp, class _Traits1, class _Traits2>
270 inline bool _STLP_CALL
271 operator==(const _Deque_iterator<_Tp, _Traits1 >& __x,
272 const _Deque_iterator<_Tp, _Traits2 >& __y)
273 { return __x._M_cur == __y._M_cur; }
275 template <class _Tp, class _Traits1, class _Traits2>
276 inline bool _STLP_CALL
277 operator < (const _Deque_iterator<_Tp, _Traits1 >& __x,
278 const _Deque_iterator<_Tp, _Traits2 >& __y) {
279 return (__x._M_node == __y._M_node) ?
280 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
284 inline bool _STLP_CALL
285 operator!=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
286 const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
287 { return __x._M_cur != __y._M_cur; }
290 inline bool _STLP_CALL
291 operator>(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
292 const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
293 { return __y < __x; }
296 inline bool _STLP_CALL
297 operator>=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
298 const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
299 { return !(__x < __y); }
302 inline bool _STLP_CALL
303 operator<=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
304 const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
305 { return !(__y < __x); }
306 #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
308 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
309 _STLP_MOVE_TO_STD_NAMESPACE
310 template <class _Tp, class _Traits>
311 struct __type_traits<_STLP_PRIV _Deque_iterator<_Tp, _Traits> > {
312 typedef __false_type has_trivial_default_constructor;
313 typedef __true_type has_trivial_copy_constructor;
314 typedef __true_type has_trivial_assignment_operator;
315 typedef __true_type has_trivial_destructor;
316 typedef __false_type is_POD_type;
318 _STLP_MOVE_TO_PRIV_NAMESPACE
319 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
321 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
322 _STLP_MOVE_TO_STD_NAMESPACE
323 template <class _Tp, class _Traits> inline _Tp* _STLP_CALL
324 value_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return (_Tp*)0; }
325 template <class _Tp, class _Traits> inline random_access_iterator_tag _STLP_CALL
326 iterator_category(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return random_access_iterator_tag(); }
327 template <class _Tp, class _Traits> inline ptrdiff_t* _STLP_CALL
328 distance_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return 0; }
329 _STLP_MOVE_TO_PRIV_NAMESPACE
332 /* Deque base class. It has two purposes. First, its constructor
333 * and destructor allocate (but don't initialize) storage. This makes
334 * exception safety easier. Second, the base class encapsulates all of
335 * the differences between SGI-style allocators and standard-conforming
339 template <class _Tp, class _Alloc>
341 typedef _Deque_base<_Tp, _Alloc> _Self;
343 typedef _Tp value_type;
344 _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
345 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
346 typedef _STLP_alloc_proxy<size_t, value_type, allocator_type> _Alloc_proxy;
348 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;
349 typedef _STLP_alloc_proxy<value_type**, value_type*, _Map_alloc_type> _Map_alloc_proxy;
351 typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
352 typedef _Deque_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
354 static size_t _STLP_CALL buffer_size() { return (size_t)_Deque_iterator_base<_Tp>::__buffer_size; }
356 _Deque_base(const allocator_type& __a, size_t __num_elements)
357 : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
358 _M_map_size(__a, (size_t)0)
359 { _M_initialize_map(__num_elements); }
361 _Deque_base(const allocator_type& __a)
362 : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
363 _M_map_size(__a, (size_t)0) {}
365 _Deque_base(__move_source<_Self> src)
366 : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
367 _M_map(__move_source<_Map_alloc_proxy>(src.get()._M_map)),
368 _M_map_size(__move_source<_Alloc_proxy>(src.get()._M_map_size)) {
369 src.get()._M_map._M_data = 0;
370 src.get()._M_map_size._M_data = 0;
371 src.get()._M_finish = src.get()._M_start;
377 void _M_initialize_map(size_t);
378 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
379 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
380 enum { _S_initial_map_size = 8 };
385 _Map_alloc_proxy _M_map;
386 _Alloc_proxy _M_map_size;
389 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
390 # define deque _STLP_PTR_IMPL_NAME(deque)
391 #elif defined (_STLP_DEBUG)
392 # define deque _STLP_NON_DBG_NAME(deque)
394 _STLP_MOVE_TO_STD_NAMESPACE
397 template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
398 class deque : protected _STLP_PRIV _Deque_base<_Tp, _Alloc>
399 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (deque)
400 , public __stlport_class<deque<_Tp, _Alloc> >
403 typedef _STLP_PRIV _Deque_base<_Tp, _Alloc> _Base;
404 typedef deque<_Tp, _Alloc> _Self;
405 public: // Basic types
406 typedef _Tp value_type;
407 typedef value_type* pointer;
408 typedef const value_type* const_pointer;
409 typedef value_type& reference;
410 typedef const value_type& const_reference;
411 typedef size_t size_type;
412 typedef ptrdiff_t difference_type;
413 typedef random_access_iterator_tag _Iterator_category;
414 _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
415 typedef typename _Base::allocator_type allocator_type;
418 typedef typename _Base::iterator iterator;
419 typedef typename _Base::const_iterator const_iterator;
421 _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
423 protected: // Internal typedefs
424 typedef pointer* _Map_pointer;
425 typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _TrivialAss;
426 typedef typename __type_traits<_Tp>::has_trivial_copy_constructor _TrivialCpy;
427 typedef typename _TrivialInit<_Tp>::_Ret _TrivialInit;
428 #if !defined (_STLP_NO_MOVE_SEMANTIC)
429 typedef typename __move_traits<_Tp>::implemented _Movable;
431 typedef __false_type _Movable;
434 public: // Basic accessors
435 iterator begin() { return this->_M_start; }
436 iterator end() { return this->_M_finish; }
437 const_iterator begin() const { return const_iterator(this->_M_start); }
438 const_iterator end() const { return const_iterator(this->_M_finish); }
440 reverse_iterator rbegin() { return reverse_iterator(this->_M_finish); }
441 reverse_iterator rend() { return reverse_iterator(this->_M_start); }
442 const_reverse_iterator rbegin() const
443 { return const_reverse_iterator(this->_M_finish); }
444 const_reverse_iterator rend() const
445 { return const_reverse_iterator(this->_M_start); }
447 reference operator[](size_type __n)
448 { return this->_M_start[difference_type(__n)]; }
449 const_reference operator[](size_type __n) const
450 { return this->_M_start[difference_type(__n)]; }
452 void _M_range_check(size_type __n) const {
453 if (__n >= this->size())
454 __stl_throw_out_of_range("deque");
456 reference at(size_type __n)
457 { _M_range_check(__n); return (*this)[__n]; }
458 const_reference at(size_type __n) const
459 { _M_range_check(__n); return (*this)[__n]; }
461 reference front() { return *this->_M_start; }
463 iterator __tmp = this->_M_finish;
467 const_reference front() const { return *this->_M_start; }
468 const_reference back() const {
469 const_iterator __tmp = this->_M_finish;
474 size_type size() const { return this->_M_finish - this->_M_start; }
475 size_type max_size() const { return size_type(-1); }
476 bool empty() const { return this->_M_finish == this->_M_start; }
477 allocator_type get_allocator() const { return this->_M_map_size; }
479 public: // Constructor, destructor.
480 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
481 explicit deque(const allocator_type& __a = allocator_type())
484 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), 0) {}
485 deque(const allocator_type& __a)
487 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, 0) {}
489 deque(const _Self& __x)
490 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size())
491 { _STLP_PRIV __ucopy(__x.begin(), __x.end(), this->_M_start); }
493 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
495 void _M_initialize(size_type __n, const value_type& __val = _STLP_DEFAULT_CONSTRUCTED(_Tp))
496 { _M_fill_initialize(__val, _TrivialInit()); }
498 explicit deque(size_type __n)
499 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
500 { _M_initialize(__n); }
501 deque(size_type __n, const value_type& __val, const allocator_type& __a = allocator_type())
503 explicit deque(size_type __n)
504 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
505 { _M_fill_initialize(_STLP_DEFAULT_CONSTRUCTED(_Tp), _TrivialInit()); }
506 deque(size_type __n, const value_type& __val)
507 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
508 { _M_fill_initialize(__val, __false_type()); }
509 deque(size_type __n, const value_type& __val, const allocator_type& __a)
511 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __n)
512 { _M_fill_initialize(__val, __false_type()); }
514 #if defined (_STLP_MEMBER_TEMPLATES)
516 template <class _Integer>
517 void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
518 this->_M_initialize_map(__n);
519 _M_fill_initialize(__x, __false_type());
522 template <class _InputIter>
523 void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
524 const __false_type&) {
525 _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
529 // Check whether it's an integral type. If so, it's not an iterator.
530 template <class _InputIterator>
531 deque(_InputIterator __first, _InputIterator __last,
532 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
533 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a) {
534 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
535 _M_initialize_dispatch(__first, __last, _Integral());
538 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
539 template <class _InputIterator>
540 deque(_InputIterator __first, _InputIterator __last)
541 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type()) {
542 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
543 _M_initialize_dispatch(__first, __last, _Integral());
548 deque(const value_type* __first, const value_type* __last,
549 const allocator_type& __a = allocator_type() )
550 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
551 { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
553 deque(const_iterator __first, const_iterator __last,
554 const allocator_type& __a = allocator_type() )
555 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
556 { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
557 #endif /* _STLP_MEMBER_TEMPLATES */
559 deque(__move_source<_Self> src)
560 : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__move_source<_Base>(src.get()))
564 { _STLP_STD::_Destroy_Range(this->_M_start, this->_M_finish); }
566 _Self& operator= (const _Self& __x);
568 void swap(_Self& __x) {
569 _STLP_STD::swap(this->_M_start, __x._M_start);
570 _STLP_STD::swap(this->_M_finish, __x._M_finish);
571 this->_M_map.swap(__x._M_map);
572 this->_M_map_size.swap(__x._M_map_size);
576 // assign(), a generalized assignment member function. Two
577 // versions: one that takes a count, and one that takes a range.
578 // The range version is a member template, so we dispatch on whether
579 // or not the type is an integer.
581 void _M_fill_assign(size_type __n, const _Tp& __val) {
583 _STLP_STD::fill(begin(), end(), __val);
584 insert(end(), __n - size(), __val);
587 erase(begin() + __n, end());
588 _STLP_STD::fill(begin(), end(), __val);
592 void assign(size_type __n, const _Tp& __val) {
593 _M_fill_assign(__n, __val);
596 #if defined (_STLP_MEMBER_TEMPLATES)
597 template <class _InputIterator>
598 void assign(_InputIterator __first, _InputIterator __last) {
599 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
600 _M_assign_dispatch(__first, __last, _Integral());
603 private: // helper functions for assign()
605 template <class _Integer>
606 void _M_assign_dispatch(_Integer __n, _Integer __val,
607 const __true_type& /*_IsIntegral*/)
608 { _M_fill_assign((size_type) __n, (_Tp) __val); }
610 template <class _InputIterator>
611 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
612 const __false_type& /*_IsIntegral*/) {
613 _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
616 template <class _InputIter>
617 void _M_assign_aux(_InputIter __first, _InputIter __last, const input_iterator_tag &) {
618 iterator __cur = begin();
619 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
621 if (__first == __last)
624 insert(end(), __first, __last);
627 template <class _ForwardIterator>
628 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
629 const forward_iterator_tag &) {
631 void assign(const value_type *__first, const value_type *__last) {
632 size_type __size = size();
633 size_type __len = __last - __first;
634 if (__len > __size) {
635 const value_type *__mid = __first + __size;
636 copy(__first, __mid, begin());
637 insert(end(), __mid, __last);
640 erase(copy(__first, __last, begin()), end());
643 void assign(const_iterator __first, const_iterator __last) {
644 typedef const_iterator _ForwardIterator;
645 #endif /* _STLP_MEMBER_TEMPLATES */
646 size_type __len = distance(__first, __last);
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());
659 public: // push_* and pop_*
661 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
662 void push_back(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
664 void push_back(const value_type& __t) {
665 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
666 if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
667 _Copy_Construct(this->_M_finish._M_cur, __t);
668 ++this->_M_finish._M_cur;
671 _M_push_back_aux_v(__t);
673 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
674 void push_front(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
676 void push_front(const value_type& __t) {
677 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
678 if (this->_M_start._M_cur != this->_M_start._M_first) {
679 _Copy_Construct(this->_M_start._M_cur - 1, __t);
680 --this->_M_start._M_cur;
683 _M_push_front_aux_v(__t);
686 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
688 if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
689 _STLP_STD::_Construct(this->_M_finish._M_cur);
690 ++this->_M_finish._M_cur;
696 if (this->_M_start._M_cur != this->_M_start._M_first) {
697 _STLP_STD::_Construct(this->_M_start._M_cur - 1);
698 --this->_M_start._M_cur;
703 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
706 if (this->_M_finish._M_cur != this->_M_finish._M_first) {
707 --this->_M_finish._M_cur;
708 _STLP_STD::_Destroy(this->_M_finish._M_cur);
712 _STLP_STD::_Destroy(this->_M_finish._M_cur);
717 _STLP_STD::_Destroy(this->_M_start._M_cur);
723 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
724 iterator insert(iterator __pos, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
726 iterator insert(iterator __pos, const value_type& __x) {
727 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
728 if (__pos._M_cur == this->_M_start._M_cur) {
730 return this->_M_start;
732 else if (__pos._M_cur == this->_M_finish._M_cur) {
734 iterator __tmp = this->_M_finish;
739 return _M_fill_insert_aux(__pos, 1, __x, _Movable());
743 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
744 iterator insert(iterator __pos)
745 { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
746 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
748 void insert(iterator __pos, size_type __n, const value_type& __x)
749 { _M_fill_insert(__pos, __n, __x); }
752 iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __true_type& /*_Movable*/);
753 iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __false_type& /*_Movable*/);
755 void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
757 #if defined (_STLP_MEMBER_TEMPLATES)
758 template <class _Integer>
759 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
760 const __true_type& /*_IsIntegral*/) {
761 _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
764 template <class _InputIterator>
765 void _M_insert_dispatch(iterator __pos,
766 _InputIterator __first, _InputIterator __last,
767 const __false_type& /*_IsIntegral*/) {
768 _M_insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
772 // Check whether it's an integral type. If so, it's not an iterator.
773 template <class _InputIterator>
774 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
775 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
776 _M_insert_dispatch(__pos, __first, __last, _Integral());
779 #else /* _STLP_MEMBER_TEMPLATES */
780 void _M_insert_range_aux(iterator __pos,
781 const value_type* __first, const value_type* __last,
782 size_type __n, const __true_type& /*_Movable*/);
783 void _M_insert_range_aux(iterator __pos,
784 const value_type* __first, const value_type* __last,
785 size_type __n, const __false_type& /*_Movable*/);
786 void _M_insert_range_aux(iterator __pos,
787 const_iterator __first, const_iterator __last,
788 size_type __n, const __true_type& /*_Movable*/);
789 void _M_insert_range_aux(iterator __pos,
790 const_iterator __first, const_iterator __last,
791 size_type __n, const __false_type& /*_Movable*/);
793 void insert(iterator __pos,
794 const value_type* __first, const value_type* __last);
795 void insert(iterator __pos,
796 const_iterator __first, const_iterator __last);
798 #endif /* _STLP_MEMBER_TEMPLATES */
801 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
802 void resize(size_type __new_size,
803 const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
805 void resize(size_type __new_size, const value_type& __x) {
806 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
807 const size_type __len = size();
808 if (__new_size < __len)
809 erase(this->_M_start + __new_size, this->_M_finish);
811 insert(this->_M_finish, __new_size - __len, __x);
814 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
815 void resize(size_type __new_size)
816 { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
817 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
820 iterator _M_erase(iterator __pos, const __true_type& /*_Movable*/);
821 iterator _M_erase(iterator __pos, const __false_type& /*_Movable*/);
823 iterator _M_erase(iterator __first, iterator __last, const __true_type& /*_Movable*/);
824 iterator _M_erase(iterator __first, iterator __last, const __false_type& /*_Movable*/);
826 iterator erase(iterator __pos) {
827 return _M_erase(__pos, _Movable());
829 iterator erase(iterator __first, iterator __last) {
830 if (__first == this->_M_start && __last == this->_M_finish) {
832 return this->_M_finish;
835 if (__first == __last)
837 return _M_erase(__first, __last, _Movable());
842 protected: // Internal construction/destruction
844 void _M_fill_initialize(const value_type& __val, const __true_type& /*_TrivialInit*/)
846 void _M_fill_initialize(const value_type& __val, const __false_type& /*_TrivialInit*/);
848 #if defined (_STLP_MEMBER_TEMPLATES)
849 template <class _InputIterator>
850 void _M_range_initialize(_InputIterator __first, _InputIterator __last,
851 const input_iterator_tag &) {
852 this->_M_initialize_map(0);
854 for ( ; __first != __last; ++__first)
857 _STLP_UNWIND(clear())
859 template <class _ForwardIterator>
860 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
861 const forward_iterator_tag &) {
862 size_type __n = distance(__first, __last);
863 this->_M_initialize_map(__n);
864 _Map_pointer __cur_node = this->_M_start._M_node;
866 for (; __cur_node < this->_M_finish._M_node; ++__cur_node) {
867 _ForwardIterator __mid = __first;
868 advance(__mid, this->buffer_size());
869 uninitialized_copy(__first, __mid, *__cur_node);
872 uninitialized_copy(__first, __last, this->_M_finish._M_first);
874 _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur_node, __cur_node)))
876 #endif /* _STLP_MEMBER_TEMPLATES */
878 protected: // Internal push_* and pop_*
880 void _M_push_back_aux_v(const value_type&);
881 void _M_push_front_aux_v(const value_type&);
882 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
883 void _M_push_back_aux();
884 void _M_push_front_aux();
885 #endif /*_STLP_DONT_SUP_DFLT_PARAM !_STLP_NO_ANACHRONISMS*/
886 void _M_pop_back_aux();
887 void _M_pop_front_aux();
889 protected: // Internal insert functions
891 #if defined (_STLP_MEMBER_TEMPLATES)
893 template <class _InputIterator>
894 void _M_insert(iterator __pos,
895 _InputIterator __first,
896 _InputIterator __last,
897 const input_iterator_tag &) {
898 copy(__first, __last, inserter(*this, __pos));
901 template <class _ForwardIterator>
902 void _M_insert(iterator __pos,
903 _ForwardIterator __first, _ForwardIterator __last,
904 const forward_iterator_tag &) {
905 size_type __n = distance(__first, __last);
906 if (__pos._M_cur == this->_M_start._M_cur) {
907 iterator __new_start = _M_reserve_elements_at_front(__n);
909 uninitialized_copy(__first, __last, __new_start);
910 this->_M_start = __new_start;
912 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
914 else if (__pos._M_cur == this->_M_finish._M_cur) {
915 iterator __new_finish = _M_reserve_elements_at_back(__n);
917 uninitialized_copy(__first, __last, this->_M_finish);
918 this->_M_finish = __new_finish;
920 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
923 _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
926 template <class _ForwardIterator>
927 void _M_insert_range_aux(iterator __pos,
928 _ForwardIterator __first, _ForwardIterator __last,
929 size_type __n, const __true_type& /*_Movable*/) {
930 const difference_type __elemsbefore = __pos - this->_M_start;
931 size_type __length = size();
932 if (__elemsbefore <= difference_type(__length / 2)) {
933 iterator __new_start = _M_reserve_elements_at_front(__n);
934 __pos = this->_M_start + __elemsbefore;
936 iterator __dst = __new_start;
937 iterator __src = this->_M_start;
938 for (; __src != __pos; ++__dst, ++__src) {
939 _STLP_STD::_Move_Construct(&(*__dst), *__src);
940 _STLP_STD::_Destroy_Moved(&(*__src));
942 this->_M_start = __new_start;
943 uninitialized_copy(__first, __last, __dst);
945 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
948 iterator __new_finish = _M_reserve_elements_at_back(__n);
949 const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
950 __pos = this->_M_finish - __elemsafter;
952 iterator __dst = __new_finish;
953 iterator __src = this->_M_finish;
954 for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
955 _STLP_STD::_Move_Construct(&(*__dst), *__src);
956 _STLP_STD::_Destroy_Moved(&(*__src));
958 this->_M_finish = __new_finish;
959 uninitialized_copy(__first, __last, __pos);
961 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
965 template <class _ForwardIterator>
966 void _M_insert_range_aux(iterator __pos,
967 _ForwardIterator __first, _ForwardIterator __last,
968 size_type __n, const __false_type& /*_Movable*/) {
969 const difference_type __elemsbefore = __pos - this->_M_start;
970 size_type __length = size();
971 if (__elemsbefore <= difference_type(__length / 2)) {
972 iterator __new_start = _M_reserve_elements_at_front(__n);
973 iterator __old_start = this->_M_start;
974 __pos = this->_M_start + __elemsbefore;
976 if (__elemsbefore >= difference_type(__n)) {
977 iterator __start_n = this->_M_start + difference_type(__n);
978 uninitialized_copy(this->_M_start, __start_n, __new_start);
979 this->_M_start = __new_start;
980 copy(__start_n, __pos, __old_start);
981 copy(__first, __last, __pos - difference_type(__n));
984 _ForwardIterator __mid = __first;
985 advance(__mid, difference_type(__n) - __elemsbefore);
986 _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
987 this->_M_start = __new_start;
988 copy(__mid, __last, __old_start);
991 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
994 iterator __new_finish = _M_reserve_elements_at_back(__n);
995 iterator __old_finish = this->_M_finish;
996 const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
997 __pos = this->_M_finish - __elemsafter;
999 if (__elemsafter > difference_type(__n)) {
1000 iterator __finish_n = this->_M_finish - difference_type(__n);
1001 uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1002 this->_M_finish = __new_finish;
1003 copy_backward(__pos, __finish_n, __old_finish);
1004 copy(__first, __last, __pos);
1007 _ForwardIterator __mid = __first;
1008 advance(__mid, __elemsafter);
1009 _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
1010 this->_M_finish = __new_finish;
1011 copy(__first, __mid, __pos);
1014 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1017 #endif /* _STLP_MEMBER_TEMPLATES */
1019 iterator _M_reserve_elements_at_front(size_type __n) {
1020 size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;
1021 if (__n > __vacancies)
1022 _M_new_elements_at_front(__n - __vacancies);
1023 return this->_M_start - difference_type(__n);
1026 iterator _M_reserve_elements_at_back(size_type __n) {
1027 size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;
1028 if (__n > __vacancies)
1029 _M_new_elements_at_back(__n - __vacancies);
1030 return this->_M_finish + difference_type(__n);
1033 void _M_new_elements_at_front(size_type __new_elements);
1034 void _M_new_elements_at_back(size_type __new_elements);
1036 protected: // Allocation of _M_map and nodes
1038 // Makes sure the _M_map has space for new nodes. Does not actually
1039 // add the nodes. Can invalidate _M_map pointers. (And consequently,
1040 // deque iterators.)
1042 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
1043 if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data))
1044 _M_reallocate_map(__nodes_to_add, false);
1047 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
1048 if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data))
1049 _M_reallocate_map(__nodes_to_add, true);
1052 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1057 _STLP_MOVE_TO_STD_NAMESPACE
1062 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
1063 # include <stl/_deque.c>
1066 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1067 # include <stl/pointers/_deque.h>
1070 #if defined (_STLP_DEBUG)
1071 # include <stl/debug/_deque.h>
1074 _STLP_BEGIN_NAMESPACE
1076 #define _STLP_TEMPLATE_CONTAINER deque<_Tp, _Alloc>
1077 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
1078 #include <stl/_relops_cont.h>
1079 #undef _STLP_TEMPLATE_CONTAINER
1080 #undef _STLP_TEMPLATE_HEADER
1082 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1083 template <class _Tp, class _Alloc>
1084 struct __move_traits<deque<_Tp, _Alloc> > {
1085 typedef __stlp_movable implemented;
1086 typedef typename __move_traits<_Alloc>::complete complete;
1088 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1092 #endif /* _STLP_INTERNAL_DEQUE_H */