_deque.h revision 9720d5f59b9c1f5d1b9ecbc9173dbcb71bd557be
1/* 2 * Copyright (c) 2004 3 * Francois Dumont 4 * 5 * This material is provided "as is", with absolutely no warranty expressed 6 * or implied. Any use is at your own risk. 7 * 8 * Permission to use or copy this software for any purpose is hereby granted 9 * without fee, provided the above notices are retained on all copies. 10 * Permission to modify the code and to distribute modified code is granted, 11 * provided the above notices are retained, and a notice that the code was 12 * modified is included with the above copyright notice. 13 * 14 */ 15 16/* NOTE: This is an internal header file, included by other STL headers. 17 * You should not attempt to use it directly. 18 */ 19 20#ifndef _STLP_SPECIALIZED_DEQUE_H 21#define _STLP_SPECIALIZED_DEQUE_H 22 23#ifndef _STLP_POINTERS_SPEC_TOOLS_H 24# include <stl/pointers/_tools.h> 25#endif 26 27_STLP_BEGIN_NAMESPACE 28_STLP_MOVE_TO_PRIV_NAMESPACE 29 30/* 31 * struct helper to cast deque iterators: 32 */ 33template <class _StorageT, class _ValueT> 34struct _DequeIteCast { 35 typedef _Deque_iterator<_ValueT, _Nonconst_traits<_ValueT> > iterator; 36 typedef _Deque_iterator<_ValueT, _Const_traits<_ValueT> > const_iterator; 37 typedef _Deque_iterator<_StorageT, _Nonconst_traits<_StorageT> > storage_iterator; 38 typedef _Deque_iterator<_StorageT, _Const_traits<_StorageT> > const_storage_iterator; 39 typedef _CastTraits<_StorageT, _ValueT> cast_traits; 40 41 static iterator to_value_type_ite (storage_iterator const& __ite) { 42 iterator tmp; 43 tmp._M_cur = cast_traits::to_value_type_ptr(__ite._M_cur); 44 tmp._M_first = cast_traits::to_value_type_ptr(__ite._M_first); 45 tmp._M_last = cast_traits::to_value_type_ptr(__ite._M_last); 46 tmp._M_node = cast_traits::to_value_type_pptr(__ite._M_node); 47 return tmp; 48 } 49 static storage_iterator to_storage_type_ite (iterator const& __ite) { 50 storage_iterator tmp; 51 tmp._M_cur = cast_traits::to_storage_type_ptr(__ite._M_cur); 52 tmp._M_first = cast_traits::to_storage_type_ptr(__ite._M_first); 53 tmp._M_last = cast_traits::to_storage_type_ptr(__ite._M_last); 54 tmp._M_node = cast_traits::to_storage_type_pptr(__ite._M_node); 55 return tmp; 56 } 57 58 static const_iterator to_value_type_cite (const_storage_iterator const& __ite) { 59 const_iterator tmp; 60 tmp._M_cur = cast_traits::to_value_type_ptr(__ite._M_cur); 61 tmp._M_first = cast_traits::to_value_type_ptr(__ite._M_first); 62 tmp._M_last = cast_traits::to_value_type_ptr(__ite._M_last); 63 tmp._M_node = cast_traits::to_value_type_pptr(__ite._M_node); 64 return tmp; 65 } 66 67 static const_storage_iterator to_storage_type_cite (const_iterator const& __ite) { 68 const_storage_iterator tmp; 69 tmp._M_cur = cast_traits::to_storage_type_ptr(__ite._M_cur); 70 tmp._M_first = cast_traits::to_storage_type_ptr(__ite._M_first); 71 tmp._M_last = cast_traits::to_storage_type_ptr(__ite._M_last); 72 tmp._M_node = cast_traits::to_storage_type_pptr(__ite._M_node); 73 return tmp; 74 } 75}; 76 77#define DEQUE_IMPL _STLP_PTR_IMPL_NAME(deque) 78 79#if defined (_STLP_USE_TEMPLATE_EXPORT) && !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND) 80_STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<size_t, void*, allocator<void*> >; 81_STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<void***, void**, allocator<void**> >; 82_STLP_EXPORT template struct _STLP_CLASS_DECLSPEC _Deque_iterator<void*, _Nonconst_traits<void*> >; 83_STLP_EXPORT_TEMPLATE_CLASS _Deque_base<void*,allocator<void*> >; 84_STLP_EXPORT_TEMPLATE_CLASS DEQUE_IMPL<void*,allocator<void*> >; 85#endif 86 87#if defined (_STLP_DEBUG) 88# define deque _STLP_NON_DBG_NAME(deque) 89#else 90_STLP_MOVE_TO_STD_NAMESPACE 91#endif 92 93template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) > 94class deque 95#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (deque) 96 : public __stlport_class<deque<_Tp, _Alloc> > 97#endif 98{ 99 typedef typename _STLP_PRIV _StorageType<_Tp>::_Type _StorageType; 100 typedef typename _Alloc_traits<_StorageType, _Alloc>::allocator_type _StorageTypeAlloc; 101 typedef _STLP_PRIV DEQUE_IMPL<_StorageType, _StorageTypeAlloc> _Base; 102 typedef deque<_Tp, _Alloc> _Self; 103 104 typedef _STLP_PRIV _CastTraits<_StorageType, _Tp> cast_traits; 105 typedef _STLP_PRIV _DequeIteCast<_StorageType, _Tp> ite_cast_traits; 106 107public: 108 typedef _Tp value_type; 109 typedef value_type* pointer; 110 typedef const value_type* const_pointer; 111 typedef value_type& reference; 112 typedef const value_type& const_reference; 113 typedef size_t size_type; 114 typedef ptrdiff_t difference_type; 115 typedef random_access_iterator_tag _Iterator_category; 116 _STLP_FORCE_ALLOCATORS(value_type, _Alloc) 117 typedef typename _Alloc_traits<value_type, _Alloc>::allocator_type allocator_type; 118 typedef _STLP_PRIV _Deque_iterator<value_type, _Nonconst_traits<value_type> > iterator; 119 typedef _STLP_PRIV _Deque_iterator<value_type, _Const_traits<value_type> > const_iterator; 120 121 _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS; 122 123public: // Basic accessors 124 iterator begin() { return ite_cast_traits::to_value_type_ite(_M_impl.begin()); } 125 iterator end() { return ite_cast_traits::to_value_type_ite(_M_impl.end()); } 126 const_iterator begin() const { return ite_cast_traits::to_value_type_cite(_M_impl.begin()); } 127 const_iterator end() const { return ite_cast_traits::to_value_type_cite(_M_impl.end()); } 128 129 reverse_iterator rbegin() { return reverse_iterator(end()); } 130 reverse_iterator rend() { return reverse_iterator(begin()); } 131 const_reverse_iterator rbegin() const 132 { return const_reverse_iterator(end()); } 133 const_reverse_iterator rend() const 134 { return const_reverse_iterator(begin()); } 135 136 reference operator[](size_type __n) 137 { return cast_traits::to_value_type_ref(_M_impl[__n]); } 138 const_reference operator[](size_type __n) const 139 { return cast_traits::to_value_type_cref(_M_impl[__n]); } 140 141 reference at(size_type __n) 142 { return cast_traits::to_value_type_ref(_M_impl.at(__n)); } 143 const_reference at(size_type __n) const 144 { return cast_traits::to_value_type_cref(_M_impl.at(__n)); } 145 146 reference front() { return cast_traits::to_value_type_ref(_M_impl.front()); } 147 reference back() { return cast_traits::to_value_type_ref(_M_impl.back()); } 148 const_reference front() const { return cast_traits::to_value_type_cref(_M_impl.front()); } 149 const_reference back() const { return cast_traits::to_value_type_cref(_M_impl.back()); } 150 151 size_type size() const { return _M_impl.size(); } 152 size_type max_size() const { return _M_impl.max_size(); } 153 bool empty() const { return _M_impl.empty(); } 154 allocator_type get_allocator() const { return _STLP_CONVERT_ALLOCATOR(_M_impl.get_allocator(), value_type); } 155 156 explicit deque(const allocator_type& __a = allocator_type()) 157 : _M_impl(_STLP_CONVERT_ALLOCATOR(__a, _StorageType)) {} 158 159 deque(const _Self& __x) : _M_impl(__x._M_impl) {} 160 161#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 162 explicit deque(size_type __n, const value_type& __val = _STLP_DEFAULT_CONSTRUCTED(value_type), 163#else 164 deque(size_type __n, const value_type& __val, 165#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 166 const allocator_type& __a = allocator_type()) 167 : _M_impl(__n, cast_traits::to_storage_type_cref(__val), _STLP_CONVERT_ALLOCATOR(__a, _StorageType)) {} 168 // int,long variants may be needed 169#if defined (_STLP_DONT_SUP_DFLT_PARAM) 170 explicit deque(size_type __n) : _M_impl(__n) {} 171#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 172 173#if defined (_STLP_MEMBER_TEMPLATES) 174 template <class _InputIterator> 175 deque(_InputIterator __first, _InputIterator __last, 176 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 177#if !defined (_STLP_USE_ITERATOR_WRAPPER) 178 : _M_impl(__first, __last, 179 _STLP_CONVERT_ALLOCATOR(__a, _StorageType)) { 180#else 181 : _M_impl(_STLP_CONVERT_ALLOCATOR(__a, _StorageType)) { 182#endif 183#if defined (_STLP_USE_ITERATOR_WRAPPER) 184 insert(end(), __first, __last); 185#endif 186 } 187 188# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 189 template <class _InputIterator> 190 deque(_InputIterator __first, _InputIterator __last) 191# if !defined (_STLP_USE_ITERATOR_WRAPPER) 192 : _M_impl(__first, __last) {} 193# else 194 { insert(end(), __first, __last); } 195# endif 196# endif 197 198#else 199 deque(const_pointer __first, const_pointer __last, 200 const allocator_type& __a = allocator_type() ) 201 : _M_impl(cast_traits::to_storage_type_cptr(__first), 202 cast_traits::to_storage_type_cptr(__last), 203 _STLP_CONVERT_ALLOCATOR(__a, _StorageType)) {} 204 205 deque(const_iterator __first, const_iterator __last, 206 const allocator_type& __a = allocator_type() ) 207 : _M_impl(ite_cast_traits::to_storage_type_cite(__first), 208 ite_cast_traits::to_storage_type_cite(__last), 209 _STLP_CONVERT_ALLOCATOR(__a, _StorageType)) {} 210#endif /* _STLP_MEMBER_TEMPLATES */ 211 212 deque(__move_source<_Self> src) 213 : _M_impl(__move_source<_Base>(src.get()._M_impl)) {} 214 215 _Self& operator= (const _Self& __x) { _M_impl = __x._M_impl; return *this; } 216 217 void swap(_Self& __x) { _M_impl.swap(__x._M_impl); } 218 219 void assign(size_type __n, const value_type& __val) { 220 _M_impl.assign(__n, cast_traits::to_storage_type_cref(__val)); 221 } 222 223#if defined (_STLP_MEMBER_TEMPLATES) 224# if defined (_STLP_USE_ITERATOR_WRAPPER) 225private: 226 template <class _Integer> 227 void _M_assign_dispatch(_Integer __n, _Integer __val, 228 const __true_type&) 229 { _M_impl.assign(__n, __val); } 230 231 template <class _InputIterator> 232 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 233 const __false_type&) { 234 _M_impl.assign(typename _STLP_PRIV _IteWrapper<_StorageType, _Tp, _InputIterator>::_Ite(__first), 235 typename _STLP_PRIV _IteWrapper<_StorageType, _Tp, _InputIterator>::_Ite(__last)); 236 } 237 238public: 239# endif 240 template <class _InputIterator> 241 void assign(_InputIterator __first, _InputIterator __last) { 242# if defined (_STLP_USE_ITERATOR_WRAPPER) 243 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral; 244 _M_assign_dispatch(__first, __last, _Integral()); 245# else 246 _M_impl.assign(__first, __last); 247# endif 248 } 249#else 250 void assign(const_pointer __first, const_pointer __last) 251 { _M_impl.assign(cast_traits::to_storage_type_cptr(__first), 252 cast_traits::to_storage_type_cptr(__last)); } 253 void assign(const_iterator __first, const_iterator __last) 254 { _M_impl.assign(ite_cast_traits::to_storage_type_cite(__first), 255 ite_cast_traits::to_storage_type_cite(__last)); } 256#endif /* _STLP_MEMBER_TEMPLATES */ 257 258#if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 259 void push_back(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(value_type)) 260#else 261 void push_back(const value_type& __t) 262#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 263 { _M_impl.push_back(cast_traits::to_storage_type_cref(__t)); } 264 265#if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 266 void push_front(const value_type& __t = _STLP_DEFAULT_CONSTRUCTED(value_type)) 267#else 268 void push_front(const value_type& __t) 269#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 270 { _M_impl.push_front(cast_traits::to_storage_type_cref(__t)); } 271 272# if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 273 void push_back() { _M_impl.push_back(); } 274 void push_front() { _M_impl.push_front(); } 275# endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 276 277 void pop_back() { _M_impl.pop_back(); } 278 void pop_front() { _M_impl.pop_front(); } 279 280#if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 281 iterator insert(iterator __pos, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(value_type)) 282#else 283 iterator insert(iterator __pos, const value_type& __x) 284#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 285 { return ite_cast_traits::to_value_type_ite(_M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), 286 cast_traits::to_storage_type_cref(__x))); } 287 288#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 289 iterator insert(iterator __pos) { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(value_type)); } 290#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 291 292 void insert(iterator __pos, size_type __n, const value_type& __x) 293 { _M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), __n, cast_traits::to_storage_type_cref(__x)); } 294 295#if defined (_STLP_MEMBER_TEMPLATES) 296# if defined (_STLP_USE_ITERATOR_WRAPPER) 297private: 298 template <class _Integer> 299 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 300 const __true_type&) { 301 _M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), __n, __val); 302 } 303 304 template <class _InputIterator> 305 void _M_insert_dispatch(iterator __pos, 306 _InputIterator __first, _InputIterator __last, 307 const __false_type&) { 308 _M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), 309 typename _STLP_PRIV _IteWrapper<_StorageType, _Tp, _InputIterator>::_Ite(__first), 310 typename _STLP_PRIV _IteWrapper<_StorageType, _Tp, _InputIterator>::_Ite(__last)); 311 } 312 313public: 314# endif 315 316 template <class _InputIterator> 317 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { 318# if defined (_STLP_USE_ITERATOR_WRAPPER) 319 // Check whether it's an integral type. If so, it's not an iterator. 320 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral; 321 _M_insert_dispatch(__pos, __first, __last, _Integral()); 322# else 323 _M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), __first, __last); 324# endif 325 } 326 327#else /* _STLP_MEMBER_TEMPLATES */ 328 void insert(iterator __pos, 329 const_pointer __first, const_pointer __last) { 330 _M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), 331 cast_traits::to_storage_type_cptr(__first), 332 cast_traits::to_storage_type_cptr(__last)); 333 } 334 void insert(iterator __pos, 335 const_iterator __first, const_iterator __last) { 336 _M_impl.insert(ite_cast_traits::to_storage_type_ite(__pos), 337 ite_cast_traits::to_storage_type_cite(__first), 338 ite_cast_traits::to_storage_type_cite(__last)); 339 } 340 341#endif /* _STLP_MEMBER_TEMPLATES */ 342 343#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 344 void resize(size_type __new_size, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(value_type)) 345#else 346 void resize(size_type __new_size, const value_type& __x) 347#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 348 { _M_impl.resize(__new_size, cast_traits::to_storage_type_cref(__x)); } 349 350#if defined (_STLP_DONT_SUP_DFLT_PARAM) 351 void resize(size_type __new_size) { _M_impl.resize(__new_size); } 352#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 353 354 iterator erase(iterator __pos) 355 { return ite_cast_traits::to_value_type_ite(_M_impl.erase(ite_cast_traits::to_storage_type_ite(__pos))); } 356 357 iterator erase(iterator __first, iterator __last) 358 { return ite_cast_traits::to_value_type_ite(_M_impl.erase(ite_cast_traits::to_storage_type_ite(__first), 359 ite_cast_traits::to_storage_type_ite(__last))); } 360 void clear() { _M_impl.clear(); } 361 362private: 363 _Base _M_impl; 364}; 365 366#if defined (deque) 367# undef deque 368_STLP_MOVE_TO_STD_NAMESPACE 369#endif 370 371#undef DEQUE_IMPL 372 373_STLP_END_NAMESPACE 374 375#endif /* _STLP_SPECIALIZED_DEQUE_H */ 376 377// Local Variables: 378// mode:C++ 379// End: 380