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