1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_deque.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,1099 @@
1.4 +/*
1.5 + *
1.6 + * Copyright (c) 1994
1.7 + * Hewlett-Packard Company
1.8 + *
1.9 + * Copyright (c) 1996,1997
1.10 + * Silicon Graphics Computer Systems, Inc.
1.11 + *
1.12 + * Copyright (c) 1997
1.13 + * Moscow Center for SPARC Technology
1.14 + *
1.15 + * Copyright (c) 1999
1.16 + * Boris Fomitchev
1.17 + *
1.18 + * This material is provided "as is", with absolutely no warranty expressed
1.19 + * or implied. Any use is at your own risk.
1.20 + *
1.21 + * Permission to use or copy this software for any purpose is hereby granted
1.22 + * without fee, provided the above notices are retained on all copies.
1.23 + * Permission to modify the code and to distribute modified code is granted,
1.24 + * provided the above notices are retained, and a notice that the code was
1.25 + * modified is included with the above copyright notice.
1.26 + *
1.27 + */
1.28 +
1.29 +/* NOTE: This is an internal header file, included by other STL headers.
1.30 + * You should not attempt to use it directly.
1.31 + */
1.32 +
1.33 +#ifndef _STLP_INTERNAL_DEQUE_H
1.34 +#define _STLP_INTERNAL_DEQUE_H
1.35 +
1.36 +#ifndef _STLP_INTERNAL_ALGOBASE_H
1.37 +# include <stl/_algobase.h>
1.38 +#endif
1.39 +
1.40 +#ifndef _STLP_INTERNAL_ALLOC_H
1.41 +# include <stl/_alloc.h>
1.42 +#endif
1.43 +
1.44 +#ifndef _STLP_INTERNAL_ITERATOR_H
1.45 +# include <stl/_iterator.h>
1.46 +#endif
1.47 +
1.48 +#ifndef _STLP_INTERNAL_UNINITIALIZED_H
1.49 +# include <stl/_uninitialized.h>
1.50 +#endif
1.51 +
1.52 +#ifndef _STLP_RANGE_ERRORS_H
1.53 +# include <stl/_range_errors.h>
1.54 +#endif
1.55 +
1.56 +/* Class invariants:
1.57 + * For any nonsingular iterator i:
1.58 + * i.node is the address of an element in the map array. The
1.59 + * contents of i.node is a pointer to the beginning of a node.
1.60 + * i.first == *(i.node)
1.61 + * i.last == i.first + node_size
1.62 + * i.cur is a pointer in the range [i.first, i.last). NOTE:
1.63 + * the implication of this is that i.cur is always a dereferenceable
1.64 + * pointer, even if i is a past-the-end iterator.
1.65 + * Start and Finish are always nonsingular iterators. NOTE: this means
1.66 + * that an empty deque must have one node, and that a deque
1.67 + * with N elements, where N is the buffer size, must have two nodes.
1.68 + * For every node other than start.node and finish.node, every element
1.69 + * in the node is an initialized object. If start.node == finish.node,
1.70 + * then [start.cur, finish.cur) are initialized objects, and
1.71 + * the elements outside that range are uninitialized storage. Otherwise,
1.72 + * [start.cur, start.last) and [finish.first, finish.cur) are initialized
1.73 + * objects, and [start.first, start.cur) and [finish.cur, finish.last)
1.74 + * are uninitialized storage.
1.75 + * [map, map + map_size) is a valid, non-empty range.
1.76 + * [start.node, finish.node] is a valid range contained within
1.77 + * [map, map + map_size).
1.78 + * A pointer in the range [map, map + map_size) points to an allocated node
1.79 + * if and only if the pointer is in the range [start.node, finish.node].
1.80 + */
1.81 +
1.82 +_STLP_BEGIN_NAMESPACE
1.83 +
1.84 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.85 +
1.86 +template <class _Tp>
1.87 +struct _Deque_iterator_base {
1.88 +
1.89 + enum _Constants {
1.90 + _blocksize = _MAX_BYTES,
1.91 + __buffer_size = (sizeof(_Tp) < (size_t)_blocksize ?
1.92 + ( (size_t)_blocksize / sizeof(_Tp)) : size_t(1))
1.93 + };
1.94 +
1.95 + typedef random_access_iterator_tag iterator_category;
1.96 +
1.97 + typedef _Tp value_type;
1.98 + typedef size_t size_type;
1.99 + typedef ptrdiff_t difference_type;
1.100 +
1.101 + typedef value_type** _Map_pointer;
1.102 +
1.103 + typedef _Deque_iterator_base< _Tp > _Self;
1.104 +
1.105 + value_type* _M_cur;
1.106 + value_type* _M_first;
1.107 + value_type* _M_last;
1.108 + _Map_pointer _M_node;
1.109 +
1.110 + _Deque_iterator_base(value_type* __x, _Map_pointer __y)
1.111 + : _M_cur(__x), _M_first(*__y),
1.112 + _M_last(*__y + __buffer_size), _M_node(__y) {}
1.113 +
1.114 + _Deque_iterator_base() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
1.115 +
1.116 +// see comment in doc/README.evc4
1.117 +// TODO: since this still applies to the MIPS compiler delivered with VC8,
1.118 +// but isn't mentioned in its (yet nonexistant) README.evc8.
1.119 +#if defined (_STLP_MSVC) && (_STLP_MSVC <= 1400) && defined (MIPS) && defined (NDEBUG)
1.120 + _Deque_iterator_base(_Deque_iterator_base const& __other)
1.121 + : _M_cur(__other._M_cur), _M_first(__other._M_first),
1.122 + _M_last(__other._M_last), _M_node(__other._M_node) {}
1.123 +#endif
1.124 +
1.125 + difference_type _M_subtract(const _Self& __x) const {
1.126 + return difference_type(__buffer_size) * (_M_node - __x._M_node - 1) +
1.127 + (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
1.128 + }
1.129 +
1.130 + void _M_increment() {
1.131 + if (++_M_cur == _M_last) {
1.132 + _M_set_node(_M_node + 1);
1.133 + _M_cur = _M_first;
1.134 + }
1.135 + }
1.136 +
1.137 + void _M_decrement() {
1.138 + if (_M_cur == _M_first) {
1.139 + _M_set_node(_M_node - 1);
1.140 + _M_cur = _M_last;
1.141 + }
1.142 + --_M_cur;
1.143 + }
1.144 +
1.145 + void _M_advance(difference_type __n) {
1.146 + difference_type __offset = __n + (_M_cur - _M_first);
1.147 + if (__offset >= 0 && __offset < difference_type(__buffer_size))
1.148 + _M_cur += __n;
1.149 + else {
1.150 + difference_type __node_offset =
1.151 + __offset > 0 ? __offset / __buffer_size
1.152 + : -difference_type((-__offset - 1) / __buffer_size) - 1;
1.153 + _M_set_node(_M_node + __node_offset);
1.154 + _M_cur = _M_first +
1.155 +
1.156 + (__offset - __node_offset * difference_type(__buffer_size));
1.157 + }
1.158 + }
1.159 +
1.160 + void _M_set_node(_Map_pointer __new_node) {
1.161 + _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(__buffer_size);
1.162 + }
1.163 +};
1.164 +
1.165 +
1.166 +template <class _Tp, class _Traits>
1.167 +struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
1.168 + typedef random_access_iterator_tag iterator_category;
1.169 + typedef _Tp value_type;
1.170 + typedef typename _Traits::reference reference;
1.171 + typedef typename _Traits::pointer pointer;
1.172 + typedef size_t size_type;
1.173 + typedef ptrdiff_t difference_type;
1.174 + typedef value_type** _Map_pointer;
1.175 +
1.176 + typedef _Deque_iterator_base< _Tp > _Base;
1.177 + typedef _Deque_iterator<_Tp, _Traits> _Self;
1.178 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.179 + typedef _Deque_iterator<_Tp, _NonConstTraits> iterator;
1.180 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.181 + typedef _Deque_iterator<_Tp, _ConstTraits> const_iterator;
1.182 +
1.183 + _Deque_iterator(value_type* __x, _Map_pointer __y) :
1.184 + _Deque_iterator_base<value_type>(__x,__y) {}
1.185 +
1.186 + _Deque_iterator() {}
1.187 + //copy constructor for iterator and constructor from iterator for const_iterator
1.188 + _Deque_iterator(const iterator& __x) :
1.189 + _Deque_iterator_base<value_type>(__x) {}
1.190 +
1.191 + reference operator*() const {
1.192 + return *this->_M_cur;
1.193 + }
1.194 +
1.195 + _STLP_DEFINE_ARROW_OPERATOR
1.196 +
1.197 + difference_type operator-(const const_iterator& __x) const { return this->_M_subtract(__x); }
1.198 +
1.199 + _Self& operator++() { this->_M_increment(); return *this; }
1.200 + _Self operator++(int) {
1.201 + _Self __tmp = *this;
1.202 + ++*this;
1.203 + return __tmp;
1.204 + }
1.205 +
1.206 + _Self& operator--() { this->_M_decrement(); return *this; }
1.207 + _Self operator--(int) {
1.208 + _Self __tmp = *this;
1.209 + --*this;
1.210 + return __tmp;
1.211 + }
1.212 +
1.213 + _Self& operator+=(difference_type __n) { this->_M_advance(__n); return *this; }
1.214 + _Self operator+(difference_type __n) const {
1.215 + _Self __tmp = *this;
1.216 + return __tmp += __n;
1.217 + }
1.218 +
1.219 + _Self& operator-=(difference_type __n) { return *this += -__n; }
1.220 + _Self operator-(difference_type __n) const {
1.221 + _Self __tmp = *this;
1.222 + return __tmp -= __n;
1.223 + }
1.224 +
1.225 + reference operator[](difference_type __n) const { return *(*this + __n); }
1.226 +};
1.227 +
1.228 +
1.229 +template <class _Tp, class _Traits>
1.230 +inline _Deque_iterator<_Tp, _Traits> _STLP_CALL
1.231 +operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Traits>& __x)
1.232 +{ return __x + __n; }
1.233 +
1.234 +
1.235 +#if defined (_STLP_USE_SEPARATE_RELOPS_NAMESPACE)
1.236 +template <class _Tp>
1.237 +inline bool _STLP_CALL
1.238 +operator==(const _Deque_iterator_base<_Tp >& __x,
1.239 + const _Deque_iterator_base<_Tp >& __y)
1.240 +{ return __x._M_cur == __y._M_cur; }
1.241 +
1.242 +template <class _Tp>
1.243 +inline bool _STLP_CALL
1.244 +operator < (const _Deque_iterator_base<_Tp >& __x,
1.245 + const _Deque_iterator_base<_Tp >& __y) {
1.246 + return (__x._M_node == __y._M_node) ?
1.247 + (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
1.248 +}
1.249 +
1.250 +template <class _Tp>
1.251 +inline bool _STLP_CALL
1.252 +operator!=(const _Deque_iterator_base<_Tp >& __x,
1.253 + const _Deque_iterator_base<_Tp >& __y)
1.254 +{ return __x._M_cur != __y._M_cur; }
1.255 +
1.256 +template <class _Tp>
1.257 +inline bool _STLP_CALL
1.258 +operator>(const _Deque_iterator_base<_Tp >& __x,
1.259 + const _Deque_iterator_base<_Tp >& __y)
1.260 +{ return __y < __x; }
1.261 +
1.262 +template <class _Tp>
1.263 +inline bool _STLP_CALL operator>=(const _Deque_iterator_base<_Tp >& __x,
1.264 + const _Deque_iterator_base<_Tp >& __y)
1.265 +{ return !(__x < __y); }
1.266 +
1.267 +template <class _Tp>
1.268 +inline bool _STLP_CALL operator<=(const _Deque_iterator_base<_Tp >& __x,
1.269 + const _Deque_iterator_base<_Tp >& __y)
1.270 +{ return !(__y < __x); }
1.271 +
1.272 +#else /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
1.273 +
1.274 +template <class _Tp, class _Traits1, class _Traits2>
1.275 +inline bool _STLP_CALL
1.276 +operator==(const _Deque_iterator<_Tp, _Traits1 >& __x,
1.277 + const _Deque_iterator<_Tp, _Traits2 >& __y)
1.278 +{ return __x._M_cur == __y._M_cur; }
1.279 +
1.280 +template <class _Tp, class _Traits1, class _Traits2>
1.281 +inline bool _STLP_CALL
1.282 +operator < (const _Deque_iterator<_Tp, _Traits1 >& __x,
1.283 + const _Deque_iterator<_Tp, _Traits2 >& __y) {
1.284 + return (__x._M_node == __y._M_node) ?
1.285 + (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
1.286 +}
1.287 +
1.288 +template <class _Tp>
1.289 +inline bool _STLP_CALL
1.290 +operator!=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.291 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
1.292 +{ return __x._M_cur != __y._M_cur; }
1.293 +
1.294 +template <class _Tp>
1.295 +inline bool _STLP_CALL
1.296 +operator>(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.297 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
1.298 +{ return __y < __x; }
1.299 +
1.300 +template <class _Tp>
1.301 +inline bool _STLP_CALL
1.302 +operator>=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.303 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
1.304 +{ return !(__x < __y); }
1.305 +
1.306 +template <class _Tp>
1.307 +inline bool _STLP_CALL
1.308 +operator<=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.309 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y)
1.310 +{ return !(__y < __x); }
1.311 +#endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
1.312 +
1.313 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.314 +_STLP_MOVE_TO_STD_NAMESPACE
1.315 +template <class _Tp, class _Traits>
1.316 +struct __type_traits<_STLP_PRIV _Deque_iterator<_Tp, _Traits> > {
1.317 + typedef __false_type has_trivial_default_constructor;
1.318 + typedef __true_type has_trivial_copy_constructor;
1.319 + typedef __true_type has_trivial_assignment_operator;
1.320 + typedef __true_type has_trivial_destructor;
1.321 + typedef __false_type is_POD_type;
1.322 +};
1.323 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.324 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.325 +
1.326 +#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
1.327 +_STLP_MOVE_TO_STD_NAMESPACE
1.328 +template <class _Tp, class _Traits> inline _Tp* _STLP_CALL
1.329 +value_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return (_Tp*)0; }
1.330 +template <class _Tp, class _Traits> inline random_access_iterator_tag _STLP_CALL
1.331 +iterator_category(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return random_access_iterator_tag(); }
1.332 +template <class _Tp, class _Traits> inline ptrdiff_t* _STLP_CALL
1.333 +distance_type(const _STLP_PRIV _Deque_iterator<_Tp, _Traits >&) { return 0; }
1.334 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.335 +#endif
1.336 +
1.337 +/* Deque base class. It has two purposes. First, its constructor
1.338 + * and destructor allocate (but don't initialize) storage. This makes
1.339 + * exception safety easier. Second, the base class encapsulates all of
1.340 + * the differences between SGI-style allocators and standard-conforming
1.341 + * allocators.
1.342 + */
1.343 +
1.344 +template <class _Tp, class _Alloc>
1.345 +class _Deque_base {
1.346 + typedef _Deque_base<_Tp, _Alloc> _Self;
1.347 +public:
1.348 + typedef _Tp value_type;
1.349 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.350 + typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
1.351 + typedef _STLP_alloc_proxy<size_t, value_type, allocator_type> _Alloc_proxy;
1.352 +
1.353 + typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;
1.354 + typedef _STLP_alloc_proxy<value_type**, value_type*, _Map_alloc_type> _Map_alloc_proxy;
1.355 +
1.356 + typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
1.357 + typedef _Deque_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
1.358 +
1.359 + static size_t _STLP_CALL buffer_size() { return (size_t)_Deque_iterator_base<_Tp>::__buffer_size; }
1.360 +
1.361 + _Deque_base(const allocator_type& __a, size_t __num_elements)
1.362 + : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
1.363 + _M_map_size(__a, (size_t)0)
1.364 + { _M_initialize_map(__num_elements); }
1.365 +
1.366 + _Deque_base(const allocator_type& __a)
1.367 + : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
1.368 + _M_map_size(__a, (size_t)0) {}
1.369 +
1.370 + _Deque_base(__move_source<_Self> src)
1.371 + : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
1.372 + _M_map(__move_source<_Map_alloc_proxy>(src.get()._M_map)),
1.373 + _M_map_size(__move_source<_Alloc_proxy>(src.get()._M_map_size)) {
1.374 + src.get()._M_map._M_data = 0;
1.375 + src.get()._M_map_size._M_data = 0;
1.376 + src.get()._M_finish = src.get()._M_start;
1.377 + }
1.378 +
1.379 + ~_Deque_base();
1.380 +
1.381 +protected:
1.382 + void _M_initialize_map(size_t);
1.383 + void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
1.384 + void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
1.385 + enum { _S_initial_map_size = 8 };
1.386 +
1.387 +protected:
1.388 + iterator _M_start;
1.389 + iterator _M_finish;
1.390 + _Map_alloc_proxy _M_map;
1.391 + _Alloc_proxy _M_map_size;
1.392 +};
1.393 +
1.394 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.395 +# define deque _STLP_PTR_IMPL_NAME(deque)
1.396 +#elif defined (_STLP_DEBUG)
1.397 +# define deque _STLP_NON_DBG_NAME(deque)
1.398 +#else
1.399 +_STLP_MOVE_TO_STD_NAMESPACE
1.400 +#endif
1.401 +
1.402 +template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
1.403 +class deque : protected _STLP_PRIV _Deque_base<_Tp, _Alloc>
1.404 +#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (deque)
1.405 + , public __stlport_class<deque<_Tp, _Alloc> >
1.406 +#endif
1.407 +{
1.408 + typedef _STLP_PRIV _Deque_base<_Tp, _Alloc> _Base;
1.409 + typedef deque<_Tp, _Alloc> _Self;
1.410 +public: // Basic types
1.411 + typedef _Tp value_type;
1.412 + typedef value_type* pointer;
1.413 + typedef const value_type* const_pointer;
1.414 + typedef value_type& reference;
1.415 + typedef const value_type& const_reference;
1.416 + typedef size_t size_type;
1.417 + typedef ptrdiff_t difference_type;
1.418 + typedef random_access_iterator_tag _Iterator_category;
1.419 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.420 + typedef typename _Base::allocator_type allocator_type;
1.421 +
1.422 +public: // Iterators
1.423 + typedef typename _Base::iterator iterator;
1.424 + typedef typename _Base::const_iterator const_iterator;
1.425 +
1.426 + _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
1.427 +
1.428 +protected: // Internal typedefs
1.429 + typedef pointer* _Map_pointer;
1.430 + typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _TrivialAss;
1.431 + typedef typename __type_traits<_Tp>::has_trivial_copy_constructor _TrivialCpy;
1.432 + typedef typename _TrivialInit<_Tp>::_Ret _TrivialInit;
1.433 +#if !defined (_STLP_NO_MOVE_SEMANTIC)
1.434 + typedef typename __move_traits<_Tp>::implemented _Movable;
1.435 +#else
1.436 + typedef __false_type _Movable;
1.437 +#endif
1.438 +
1.439 +public: // Basic accessors
1.440 + iterator begin() { return this->_M_start; }
1.441 + iterator end() { return this->_M_finish; }
1.442 + const_iterator begin() const { return const_iterator(this->_M_start); }
1.443 + const_iterator end() const { return const_iterator(this->_M_finish); }
1.444 +
1.445 + reverse_iterator rbegin() { return reverse_iterator(this->_M_finish); }
1.446 + reverse_iterator rend() { return reverse_iterator(this->_M_start); }
1.447 + const_reverse_iterator rbegin() const
1.448 + { return const_reverse_iterator(this->_M_finish); }
1.449 + const_reverse_iterator rend() const
1.450 + { return const_reverse_iterator(this->_M_start); }
1.451 +
1.452 + reference operator[](size_type __n)
1.453 + { return this->_M_start[difference_type(__n)]; }
1.454 + const_reference operator[](size_type __n) const
1.455 + { return this->_M_start[difference_type(__n)]; }
1.456 +
1.457 + void _M_range_check(size_type __n) const {
1.458 + if (__n >= this->size())
1.459 + __stl_throw_out_of_range("deque");
1.460 + }
1.461 + reference at(size_type __n)
1.462 + { _M_range_check(__n); return (*this)[__n]; }
1.463 + const_reference at(size_type __n) const
1.464 + { _M_range_check(__n); return (*this)[__n]; }
1.465 +
1.466 + reference front() { return *this->_M_start; }
1.467 + reference back() {
1.468 + iterator __tmp = this->_M_finish;
1.469 + --__tmp;
1.470 + return *__tmp;
1.471 + }
1.472 + const_reference front() const { return *this->_M_start; }
1.473 + const_reference back() const {
1.474 + const_iterator __tmp = this->_M_finish;
1.475 + --__tmp;
1.476 + return *__tmp;
1.477 + }
1.478 +
1.479 + size_type size() const { return this->_M_finish - this->_M_start; }
1.480 + size_type max_size() const { return size_type(-1); }
1.481 + bool empty() const { return this->_M_finish == this->_M_start; }
1.482 + allocator_type get_allocator() const { return this->_M_map_size; }
1.483 +
1.484 +public: // Constructor, destructor.
1.485 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.486 + explicit deque(const allocator_type& __a = allocator_type())
1.487 +#else
1.488 + deque()
1.489 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), 0) {}
1.490 + deque(const allocator_type& __a)
1.491 +#endif
1.492 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, 0) {}
1.493 +
1.494 + deque(const _Self& __x)
1.495 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size())
1.496 + { _STLP_PRIV __ucopy(__x.begin(), __x.end(), this->_M_start); }
1.497 +
1.498 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.499 +private:
1.500 + void _M_initialize(size_type __n, const value_type& __val = _STLP_DEFAULT_CONSTRUCTED(_Tp))
1.501 + { _M_fill_initialize(__val, _TrivialInit()); }
1.502 +public:
1.503 + explicit deque(size_type __n)
1.504 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
1.505 + { _M_initialize(__n); }
1.506 + deque(size_type __n, const value_type& __val, const allocator_type& __a = allocator_type())
1.507 +#else
1.508 + explicit deque(size_type __n)
1.509 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
1.510 + { _M_fill_initialize(_STLP_DEFAULT_CONSTRUCTED(_Tp), _TrivialInit()); }
1.511 + deque(size_type __n, const value_type& __val)
1.512 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
1.513 + { _M_fill_initialize(__val, __false_type()); }
1.514 + deque(size_type __n, const value_type& __val, const allocator_type& __a)
1.515 +#endif
1.516 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __n)
1.517 + { _M_fill_initialize(__val, __false_type()); }
1.518 +
1.519 +#if defined (_STLP_MEMBER_TEMPLATES)
1.520 +protected:
1.521 + template <class _Integer>
1.522 + void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
1.523 + this->_M_initialize_map(__n);
1.524 + _M_fill_initialize(__x, __false_type());
1.525 + }
1.526 +
1.527 + template <class _InputIter>
1.528 + void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
1.529 + const __false_type&) {
1.530 + _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
1.531 + }
1.532 +
1.533 +public:
1.534 + // Check whether it's an integral type. If so, it's not an iterator.
1.535 + template <class _InputIterator>
1.536 + deque(_InputIterator __first, _InputIterator __last,
1.537 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
1.538 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a) {
1.539 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.540 + _M_initialize_dispatch(__first, __last, _Integral());
1.541 + }
1.542 +
1.543 +# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
1.544 + template <class _InputIterator>
1.545 + deque(_InputIterator __first, _InputIterator __last)
1.546 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(allocator_type()) {
1.547 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.548 + _M_initialize_dispatch(__first, __last, _Integral());
1.549 + }
1.550 +# endif
1.551 +
1.552 +#else
1.553 + deque(const value_type* __first, const value_type* __last,
1.554 + const allocator_type& __a = allocator_type() )
1.555 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
1.556 + { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
1.557 +
1.558 + deque(const_iterator __first, const_iterator __last,
1.559 + const allocator_type& __a = allocator_type() )
1.560 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__a, __last - __first)
1.561 + { _STLP_PRIV __ucopy(__first, __last, this->_M_start); }
1.562 +#endif /* _STLP_MEMBER_TEMPLATES */
1.563 +
1.564 + deque(__move_source<_Self> src)
1.565 + : _STLP_PRIV _Deque_base<_Tp, _Alloc>(__move_source<_Base>(src.get()))
1.566 + {}
1.567 +
1.568 + ~deque()
1.569 + { _STLP_STD::_Destroy_Range(this->_M_start, this->_M_finish); }
1.570 +
1.571 + _Self& operator= (const _Self& __x);
1.572 +
1.573 + void swap(_Self& __x) {
1.574 + _STLP_STD::swap(this->_M_start, __x._M_start);
1.575 + _STLP_STD::swap(this->_M_finish, __x._M_finish);
1.576 + this->_M_map.swap(__x._M_map);
1.577 + this->_M_map_size.swap(__x._M_map_size);
1.578 + }
1.579 +
1.580 +public:
1.581 + // assign(), a generalized assignment member function. Two
1.582 + // versions: one that takes a count, and one that takes a range.
1.583 + // The range version is a member template, so we dispatch on whether
1.584 + // or not the type is an integer.
1.585 +
1.586 + void _M_fill_assign(size_type __n, const _Tp& __val) {
1.587 + if (__n > size()) {
1.588 + _STLP_STD::fill(begin(), end(), __val);
1.589 + insert(end(), __n - size(), __val);
1.590 + }
1.591 + else {
1.592 + erase(begin() + __n, end());
1.593 + _STLP_STD::fill(begin(), end(), __val);
1.594 + }
1.595 + }
1.596 +
1.597 + void assign(size_type __n, const _Tp& __val) {
1.598 + _M_fill_assign(__n, __val);
1.599 + }
1.600 +
1.601 +#if defined (_STLP_MEMBER_TEMPLATES)
1.602 + template <class _InputIterator>
1.603 + void assign(_InputIterator __first, _InputIterator __last) {
1.604 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.605 + _M_assign_dispatch(__first, __last, _Integral());
1.606 + }
1.607 +
1.608 +private: // helper functions for assign()
1.609 +
1.610 + template <class _Integer>
1.611 + void _M_assign_dispatch(_Integer __n, _Integer __val,
1.612 + const __true_type& /*_IsIntegral*/)
1.613 + { _M_fill_assign((size_type) __n, (_Tp) __val); }
1.614 +
1.615 + template <class _InputIterator>
1.616 + void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1.617 + const __false_type& /*_IsIntegral*/) {
1.618 + _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
1.619 + }
1.620 +
1.621 + template <class _InputIter>
1.622 + void _M_assign_aux(_InputIter __first, _InputIter __last, const input_iterator_tag &) {
1.623 + iterator __cur = begin();
1.624 + for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
1.625 + *__cur = *__first;
1.626 + if (__first == __last)
1.627 + erase(__cur, end());
1.628 + else
1.629 + insert(end(), __first, __last);
1.630 + }
1.631 +
1.632 + template <class _ForwardIterator>
1.633 + void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1.634 + const forward_iterator_tag &) {
1.635 +#else
1.636 + void assign(const value_type *__first, const value_type *__last) {
1.637 + size_type __size = size();
1.638 + size_type __len = __last - __first;
1.639 + if (__len > __size) {
1.640 + const value_type *__mid = __first + __size;
1.641 + copy(__first, __mid, begin());
1.642 + insert(end(), __mid, __last);
1.643 + }
1.644 + else {
1.645 + erase(copy(__first, __last, begin()), end());
1.646 + }
1.647 + }
1.648 + void assign(const_iterator __first, const_iterator __last) {
1.649 + typedef const_iterator _ForwardIterator;
1.650 +#endif /* _STLP_MEMBER_TEMPLATES */
1.651 + size_type __len = distance(__first, __last);
1.652 + if (__len > size()) {
1.653 + _ForwardIterator __mid = __first;
1.654 + advance(__mid, size());
1.655 + copy(__first, __mid, begin());
1.656 + insert(end(), __mid, __last);
1.657 + }
1.658 + else {
1.659 + erase(copy(__first, __last, begin()), end());
1.660 + }
1.661 + }
1.662 +
1.663 +
1.664 +public: // push_* and pop_*
1.665 +
1.666 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.667 + void push_back(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
1.668 +#else
1.669 + void push_back(const value_type& __t) {
1.670 +#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.671 + if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
1.672 + _Copy_Construct(this->_M_finish._M_cur, __t);
1.673 + ++this->_M_finish._M_cur;
1.674 + }
1.675 + else
1.676 + _M_push_back_aux_v(__t);
1.677 + }
1.678 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.679 + void push_front(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
1.680 +#else
1.681 + void push_front(const value_type& __t) {
1.682 +#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.683 + if (this->_M_start._M_cur != this->_M_start._M_first) {
1.684 + _Copy_Construct(this->_M_start._M_cur - 1, __t);
1.685 + --this->_M_start._M_cur;
1.686 + }
1.687 + else
1.688 + _M_push_front_aux_v(__t);
1.689 + }
1.690 +
1.691 +#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.692 + void push_back() {
1.693 + if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
1.694 + _STLP_STD::_Construct(this->_M_finish._M_cur);
1.695 + ++this->_M_finish._M_cur;
1.696 + }
1.697 + else
1.698 + _M_push_back_aux();
1.699 + }
1.700 + void push_front() {
1.701 + if (this->_M_start._M_cur != this->_M_start._M_first) {
1.702 + _STLP_STD::_Construct(this->_M_start._M_cur - 1);
1.703 + --this->_M_start._M_cur;
1.704 + }
1.705 + else
1.706 + _M_push_front_aux();
1.707 + }
1.708 +#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.709 +
1.710 + void pop_back() {
1.711 + if (this->_M_finish._M_cur != this->_M_finish._M_first) {
1.712 + --this->_M_finish._M_cur;
1.713 + _STLP_STD::_Destroy(this->_M_finish._M_cur);
1.714 + }
1.715 + else {
1.716 + _M_pop_back_aux();
1.717 + _STLP_STD::_Destroy(this->_M_finish._M_cur);
1.718 + }
1.719 + }
1.720 +
1.721 + void pop_front() {
1.722 + _STLP_STD::_Destroy(this->_M_start._M_cur);
1.723 + _M_pop_front_aux();
1.724 + }
1.725 +
1.726 +public: // Insert
1.727 +
1.728 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.729 + iterator insert(iterator __pos, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
1.730 +#else
1.731 + iterator insert(iterator __pos, const value_type& __x) {
1.732 +#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.733 + if (__pos._M_cur == this->_M_start._M_cur) {
1.734 + push_front(__x);
1.735 + return this->_M_start;
1.736 + }
1.737 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.738 + push_back(__x);
1.739 + iterator __tmp = this->_M_finish;
1.740 + --__tmp;
1.741 + return __tmp;
1.742 + }
1.743 + else {
1.744 + return _M_fill_insert_aux(__pos, 1, __x, _Movable());
1.745 + }
1.746 + }
1.747 +
1.748 +#if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
1.749 + iterator insert(iterator __pos)
1.750 + { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
1.751 +#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.752 +
1.753 + void insert(iterator __pos, size_type __n, const value_type& __x)
1.754 + { _M_fill_insert(__pos, __n, __x); }
1.755 +
1.756 +protected:
1.757 + iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __true_type& /*_Movable*/);
1.758 + iterator _M_fill_insert_aux(iterator __pos, size_type __n, const value_type& __x, const __false_type& /*_Movable*/);
1.759 +
1.760 + void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1.761 +
1.762 +#if defined (_STLP_MEMBER_TEMPLATES)
1.763 + template <class _Integer>
1.764 + void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1.765 + const __true_type& /*_IsIntegral*/) {
1.766 + _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
1.767 + }
1.768 +
1.769 + template <class _InputIterator>
1.770 + void _M_insert_dispatch(iterator __pos,
1.771 + _InputIterator __first, _InputIterator __last,
1.772 + const __false_type& /*_IsIntegral*/) {
1.773 + _M_insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
1.774 + }
1.775 +
1.776 +public:
1.777 + // Check whether it's an integral type. If so, it's not an iterator.
1.778 + template <class _InputIterator>
1.779 + void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
1.780 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.781 + _M_insert_dispatch(__pos, __first, __last, _Integral());
1.782 + }
1.783 +
1.784 +#else /* _STLP_MEMBER_TEMPLATES */
1.785 + void _M_insert_range_aux(iterator __pos,
1.786 + const value_type* __first, const value_type* __last,
1.787 + size_type __n, const __true_type& /*_Movable*/);
1.788 + void _M_insert_range_aux(iterator __pos,
1.789 + const value_type* __first, const value_type* __last,
1.790 + size_type __n, const __false_type& /*_Movable*/);
1.791 + void _M_insert_range_aux(iterator __pos,
1.792 + const_iterator __first, const_iterator __last,
1.793 + size_type __n, const __true_type& /*_Movable*/);
1.794 + void _M_insert_range_aux(iterator __pos,
1.795 + const_iterator __first, const_iterator __last,
1.796 + size_type __n, const __false_type& /*_Movable*/);
1.797 +public:
1.798 + void insert(iterator __pos,
1.799 + const value_type* __first, const value_type* __last);
1.800 + void insert(iterator __pos,
1.801 + const_iterator __first, const_iterator __last);
1.802 +
1.803 +#endif /* _STLP_MEMBER_TEMPLATES */
1.804 +
1.805 +public:
1.806 +#if !defined(_STLP_DONT_SUP_DFLT_PARAM)
1.807 + void resize(size_type __new_size,
1.808 + const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) {
1.809 +#else
1.810 + void resize(size_type __new_size, const value_type& __x) {
1.811 +#endif /*_STLP_DONT_SUP_DFLT_PARAM*/
1.812 + const size_type __len = size();
1.813 + if (__new_size < __len)
1.814 + erase(this->_M_start + __new_size, this->_M_finish);
1.815 + else
1.816 + insert(this->_M_finish, __new_size - __len, __x);
1.817 + }
1.818 +
1.819 +#if defined (_STLP_DONT_SUP_DFLT_PARAM)
1.820 + void resize(size_type __new_size)
1.821 + { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
1.822 +#endif /*_STLP_DONT_SUP_DFLT_PARAM*/
1.823 +
1.824 +protected:
1.825 + iterator _M_erase(iterator __pos, const __true_type& /*_Movable*/);
1.826 + iterator _M_erase(iterator __pos, const __false_type& /*_Movable*/);
1.827 +
1.828 + iterator _M_erase(iterator __first, iterator __last, const __true_type& /*_Movable*/);
1.829 + iterator _M_erase(iterator __first, iterator __last, const __false_type& /*_Movable*/);
1.830 +public: // Erase
1.831 + iterator erase(iterator __pos) {
1.832 + return _M_erase(__pos, _Movable());
1.833 + }
1.834 + iterator erase(iterator __first, iterator __last) {
1.835 + if (__first == this->_M_start && __last == this->_M_finish) {
1.836 + clear();
1.837 + return this->_M_finish;
1.838 + }
1.839 + else {
1.840 + if (__first == __last)
1.841 + return __first;
1.842 + return _M_erase(__first, __last, _Movable());
1.843 + }
1.844 + }
1.845 + void clear();
1.846 +
1.847 +protected: // Internal construction/destruction
1.848 +
1.849 + void _M_fill_initialize(const value_type& __val, const __true_type& /*_TrivialInit*/)
1.850 + {}
1.851 + void _M_fill_initialize(const value_type& __val, const __false_type& /*_TrivialInit*/);
1.852 +
1.853 +#if defined (_STLP_MEMBER_TEMPLATES)
1.854 + template <class _InputIterator>
1.855 + void _M_range_initialize(_InputIterator __first, _InputIterator __last,
1.856 + const input_iterator_tag &) {
1.857 + this->_M_initialize_map(0);
1.858 + _STLP_TRY {
1.859 + for ( ; __first != __last; ++__first)
1.860 + push_back(*__first);
1.861 + }
1.862 + _STLP_UNWIND(clear())
1.863 + }
1.864 + template <class _ForwardIterator>
1.865 + void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1.866 + const forward_iterator_tag &) {
1.867 + size_type __n = distance(__first, __last);
1.868 + this->_M_initialize_map(__n);
1.869 + _Map_pointer __cur_node = this->_M_start._M_node;
1.870 + _STLP_TRY {
1.871 + for (; __cur_node < this->_M_finish._M_node; ++__cur_node) {
1.872 + _ForwardIterator __mid = __first;
1.873 + advance(__mid, this->buffer_size());
1.874 + uninitialized_copy(__first, __mid, *__cur_node);
1.875 + __first = __mid;
1.876 + }
1.877 + uninitialized_copy(__first, __last, this->_M_finish._M_first);
1.878 + }
1.879 + _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur_node, __cur_node)))
1.880 + }
1.881 +#endif /* _STLP_MEMBER_TEMPLATES */
1.882 +
1.883 +protected: // Internal push_* and pop_*
1.884 +
1.885 + void _M_push_back_aux_v(const value_type&);
1.886 + void _M_push_front_aux_v(const value_type&);
1.887 +#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.888 + void _M_push_back_aux();
1.889 + void _M_push_front_aux();
1.890 +#endif /*_STLP_DONT_SUP_DFLT_PARAM !_STLP_NO_ANACHRONISMS*/
1.891 + void _M_pop_back_aux();
1.892 + void _M_pop_front_aux();
1.893 +
1.894 +protected: // Internal insert functions
1.895 +
1.896 +#if defined (_STLP_MEMBER_TEMPLATES)
1.897 +
1.898 + template <class _InputIterator>
1.899 + void _M_insert(iterator __pos,
1.900 + _InputIterator __first,
1.901 + _InputIterator __last,
1.902 + const input_iterator_tag &) {
1.903 + copy(__first, __last, inserter(*this, __pos));
1.904 + }
1.905 +
1.906 + template <class _ForwardIterator>
1.907 + void _M_insert(iterator __pos,
1.908 + _ForwardIterator __first, _ForwardIterator __last,
1.909 + const forward_iterator_tag &) {
1.910 + size_type __n = distance(__first, __last);
1.911 + if (__pos._M_cur == this->_M_start._M_cur) {
1.912 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.913 + _STLP_TRY {
1.914 + uninitialized_copy(__first, __last, __new_start);
1.915 + this->_M_start = __new_start;
1.916 + }
1.917 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.918 + }
1.919 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.920 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.921 + _STLP_TRY {
1.922 + uninitialized_copy(__first, __last, this->_M_finish);
1.923 + this->_M_finish = __new_finish;
1.924 + }
1.925 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.926 + }
1.927 + else
1.928 + _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
1.929 + }
1.930 +
1.931 + template <class _ForwardIterator>
1.932 + void _M_insert_range_aux(iterator __pos,
1.933 + _ForwardIterator __first, _ForwardIterator __last,
1.934 + size_type __n, const __true_type& /*_Movable*/) {
1.935 + const difference_type __elemsbefore = __pos - this->_M_start;
1.936 + size_type __length = size();
1.937 + if (__elemsbefore <= difference_type(__length / 2)) {
1.938 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.939 + __pos = this->_M_start + __elemsbefore;
1.940 + _STLP_TRY {
1.941 + iterator __dst = __new_start;
1.942 + iterator __src = this->_M_start;
1.943 + for (; __src != __pos; ++__dst, ++__src) {
1.944 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.945 + _STLP_STD::_Destroy_Moved(&(*__src));
1.946 + }
1.947 + this->_M_start = __new_start;
1.948 + uninitialized_copy(__first, __last, __dst);
1.949 + }
1.950 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.951 + }
1.952 + else {
1.953 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.954 + const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
1.955 + __pos = this->_M_finish - __elemsafter;
1.956 + _STLP_TRY {
1.957 + iterator __dst = __new_finish;
1.958 + iterator __src = this->_M_finish;
1.959 + for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
1.960 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.961 + _STLP_STD::_Destroy_Moved(&(*__src));
1.962 + }
1.963 + this->_M_finish = __new_finish;
1.964 + uninitialized_copy(__first, __last, __pos);
1.965 + }
1.966 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.967 + }
1.968 + }
1.969 +
1.970 + template <class _ForwardIterator>
1.971 + void _M_insert_range_aux(iterator __pos,
1.972 + _ForwardIterator __first, _ForwardIterator __last,
1.973 + size_type __n, const __false_type& /*_Movable*/) {
1.974 + const difference_type __elemsbefore = __pos - this->_M_start;
1.975 + size_type __length = size();
1.976 + if (__elemsbefore <= difference_type(__length / 2)) {
1.977 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.978 + iterator __old_start = this->_M_start;
1.979 + __pos = this->_M_start + __elemsbefore;
1.980 + _STLP_TRY {
1.981 + if (__elemsbefore >= difference_type(__n)) {
1.982 + iterator __start_n = this->_M_start + difference_type(__n);
1.983 + uninitialized_copy(this->_M_start, __start_n, __new_start);
1.984 + this->_M_start = __new_start;
1.985 + copy(__start_n, __pos, __old_start);
1.986 + copy(__first, __last, __pos - difference_type(__n));
1.987 + }
1.988 + else {
1.989 + _ForwardIterator __mid = __first;
1.990 + advance(__mid, difference_type(__n) - __elemsbefore);
1.991 + _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
1.992 + this->_M_start = __new_start;
1.993 + copy(__mid, __last, __old_start);
1.994 + }
1.995 + }
1.996 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.997 + }
1.998 + else {
1.999 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.1000 + iterator __old_finish = this->_M_finish;
1.1001 + const difference_type __elemsafter = difference_type(__length) - __elemsbefore;
1.1002 + __pos = this->_M_finish - __elemsafter;
1.1003 + _STLP_TRY {
1.1004 + if (__elemsafter > difference_type(__n)) {
1.1005 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.1006 + uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1.1007 + this->_M_finish = __new_finish;
1.1008 + copy_backward(__pos, __finish_n, __old_finish);
1.1009 + copy(__first, __last, __pos);
1.1010 + }
1.1011 + else {
1.1012 + _ForwardIterator __mid = __first;
1.1013 + advance(__mid, __elemsafter);
1.1014 + _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
1.1015 + this->_M_finish = __new_finish;
1.1016 + copy(__first, __mid, __pos);
1.1017 + }
1.1018 + }
1.1019 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.1020 + }
1.1021 + }
1.1022 +#endif /* _STLP_MEMBER_TEMPLATES */
1.1023 +
1.1024 + iterator _M_reserve_elements_at_front(size_type __n) {
1.1025 + size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;
1.1026 + if (__n > __vacancies)
1.1027 + _M_new_elements_at_front(__n - __vacancies);
1.1028 + return this->_M_start - difference_type(__n);
1.1029 + }
1.1030 +
1.1031 + iterator _M_reserve_elements_at_back(size_type __n) {
1.1032 + size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;
1.1033 + if (__n > __vacancies)
1.1034 + _M_new_elements_at_back(__n - __vacancies);
1.1035 + return this->_M_finish + difference_type(__n);
1.1036 + }
1.1037 +
1.1038 + void _M_new_elements_at_front(size_type __new_elements);
1.1039 + void _M_new_elements_at_back(size_type __new_elements);
1.1040 +
1.1041 +protected: // Allocation of _M_map and nodes
1.1042 +
1.1043 + // Makes sure the _M_map has space for new nodes. Does not actually
1.1044 + // add the nodes. Can invalidate _M_map pointers. (And consequently,
1.1045 + // deque iterators.)
1.1046 +
1.1047 + void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
1.1048 + if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data))
1.1049 + _M_reallocate_map(__nodes_to_add, false);
1.1050 + }
1.1051 +
1.1052 + void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
1.1053 + if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data))
1.1054 + _M_reallocate_map(__nodes_to_add, true);
1.1055 + }
1.1056 +
1.1057 + void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1.1058 +};
1.1059 +
1.1060 +#if defined (deque)
1.1061 +# undef deque
1.1062 +_STLP_MOVE_TO_STD_NAMESPACE
1.1063 +#endif
1.1064 +
1.1065 +_STLP_END_NAMESPACE
1.1066 +
1.1067 +#if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.1068 +# include <stl/_deque.c>
1.1069 +#endif
1.1070 +
1.1071 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.1072 +# include <stl/pointers/_deque.h>
1.1073 +#endif
1.1074 +
1.1075 +#if defined (_STLP_DEBUG)
1.1076 +# include <stl/debug/_deque.h>
1.1077 +#endif
1.1078 +
1.1079 +_STLP_BEGIN_NAMESPACE
1.1080 +
1.1081 +#define _STLP_TEMPLATE_CONTAINER deque<_Tp, _Alloc>
1.1082 +#define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
1.1083 +#include <stl/_relops_cont.h>
1.1084 +#undef _STLP_TEMPLATE_CONTAINER
1.1085 +#undef _STLP_TEMPLATE_HEADER
1.1086 +
1.1087 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.1088 +template <class _Tp, class _Alloc>
1.1089 +struct __move_traits<deque<_Tp, _Alloc> > {
1.1090 + typedef __stlp_movable implemented;
1.1091 + typedef typename __move_traits<_Alloc>::complete complete;
1.1092 +};
1.1093 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.1094 +
1.1095 +_STLP_END_NAMESPACE
1.1096 +
1.1097 +#endif /* _STLP_INTERNAL_DEQUE_H */
1.1098 +
1.1099 +// Local Variables:
1.1100 +// mode:C++
1.1101 +// End:
1.1102 +