1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1997 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_DEQUE_H 32 #define __SGI_STL_INTERNAL_DEQUE_H 33 34 /* Class invariants: 35 * For any nonsingular iterator i: 36 * i.node is the address of an element in the map array. The 37 * contents of i.node is a pointer to the beginning of a node. 38 * i.first == *(i.node) 39 * i.last == i.first + node_size 40 * i.cur is a pointer in the range [i.first, i.last). NOTE: 41 * the implication of this is that i.cur is always a dereferenceable 42 * pointer, even if i is a past-the-end iterator. 43 * Start and Finish are always nonsingular iterators. NOTE: this means 44 * that an empty deque must have one node, and that a deque 45 * with N elements, where N is the buffer size, must have two nodes. 46 * For every node other than start.node and finish.node, every element 47 * in the node is an initialized object. If start.node == finish.node, 48 * then [start.cur, finish.cur) are initialized objects, and 49 * the elements outside that range are uninitialized storage. Otherwise, 50 * [start.cur, start.last) and [finish.first, finish.cur) are initialized 51 * objects, and [start.first, start.cur) and [finish.cur, finish.last) 52 * are uninitialized storage. 53 * [map, map + map_size) is a valid, non-empty range. 54 * [start.node, finish.node] is a valid range contained within 55 * [map, map + map_size). 56 * A pointer in the range [map, map + map_size) points to an allocated node 57 * if and only if the pointer is in the range [start.node, finish.node]. 58 */ 59 60 61 /* 62 * In previous versions of deque, node_size was fixed by the 63 * implementation. In this version, however, users can select 64 * the node size. Deque has three template parameters; the third, 65 * a number of type size_t, is the number of elements per node. 66 * If the third template parameter is 0 (which is the default), 67 * then deque will use a default node size. 68 * 69 * The only reason for using an alternate node size is if your application 70 * requires a different performance tradeoff than the default. If, 71 * for example, your program contains many deques each of which contains 72 * only a few elements, then you might want to save memory (possibly 73 * by sacrificing some speed) by using smaller nodes. 74 * 75 * Unfortunately, some compilers have trouble with non-type template 76 * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if 77 * that is the case. If your compiler is one of them, then you will 78 * not be able to use alternate node sizes; you will have to use the 79 * default value. 80 */ 81 82 __STL_BEGIN_NAMESPACE 83 84 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 85 #pragma set woff 1174 86 #pragma set woff 1375 87 #endif 88 89 // Note: this function is simply a kludge to work around several compilers' 90 // bugs in handling constant expressions. 91 inline size_t 92 __deque_buf_size(size_t __n, size_t __size) 93 { 94 return __n != 0 ? __n : (__size < 512 ? size_t(512 / __size) : size_t(1)); 95 } 96 97 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG 98 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz> 99 struct _Deque_iterator { 100 typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator; 101 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*,__bufsiz> const_iterator; 102 static size_t 103 _S_buffer_size() { return __deque_buf_size(__bufsiz, sizeof(_Tp)); } 104 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 105 template <class _Tp, class _Ref, class _Ptr> 106 struct _Deque_iterator { 107 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; 108 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 109 static size_t 110 _S_buffer_size() { return __deque_buf_size(0, sizeof(_Tp)); } 111 #endif 112 113 typedef random_access_iterator_tag iterator_category; 114 typedef _Tp value_type; 115 typedef _Ptr pointer; 116 typedef _Ref reference; 117 typedef size_t size_type; 118 typedef ptrdiff_t difference_type; 119 typedef _Tp** _Map_pointer; 120 121 typedef _Deque_iterator _Self; 122 123 _Tp* _M_cur; 124 _Tp* _M_first; 125 _Tp* _M_last; 126 _Map_pointer _M_node; 127 128 _Deque_iterator(_Tp* __x, _Map_pointer __y) 129 : _M_cur(__x), _M_first(*__y), 130 _M_last(*__y + _S_buffer_size()), _M_node(__y) {} 131 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {} 132 _Deque_iterator(const iterator& __x) 133 : _M_cur(__x._M_cur), _M_first(__x._M_first), 134 _M_last(__x._M_last), _M_node(__x._M_node) {} 135 136 reference operator*() const { return *_M_cur; } 137 #ifndef __SGI_STL_NO_ARROW_OPERATOR 138 pointer operator->() const { return _M_cur; } 139 #endif /* __SGI_STL_NO_ARROW_OPERATOR */ 140 141 difference_type operator-(const _Self& __x) const { 142 return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) + 143 (_M_cur - _M_first) + (__x._M_last - __x._M_cur); 144 } 145 146 _Self& operator++() { 147 ++_M_cur; 148 if (_M_cur == _M_last) { 149 _M_set_node(_M_node + 1); 150 _M_cur = _M_first; 151 } 152 return *this; 153 } 154 _Self operator++(int) { 155 _Self __tmp = *this; 156 ++*this; 157 return __tmp; 158 } 159 160 _Self& operator--() { 161 if (_M_cur == _M_first) { 162 _M_set_node(_M_node - 1); 163 _M_cur = _M_last; 164 } 165 --_M_cur; 166 return *this; 167 } 168 _Self operator--(int) { 169 _Self __tmp = *this; 170 --*this; 171 return __tmp; 172 } 173 174 _Self& operator+=(difference_type __n) 175 { 176 difference_type __offset = __n + (_M_cur - _M_first); 177 if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) 178 _M_cur += __n; 179 else { 180 difference_type __node_offset = 181 __offset > 0 ? __offset / difference_type(_S_buffer_size()) 182 : -difference_type((-__offset - 1) / _S_buffer_size()) - 1; 183 _M_set_node(_M_node + __node_offset); 184 _M_cur = _M_first + 185 (__offset - __node_offset * difference_type(_S_buffer_size())); 186 } 187 return *this; 188 } 189 190 _Self operator+(difference_type __n) const 191 { 192 _Self __tmp = *this; 193 return __tmp += __n; 194 } 195 196 _Self& operator-=(difference_type __n) { return *this += -__n; } 197 198 _Self operator-(difference_type __n) const { 199 _Self __tmp = *this; 200 return __tmp -= __n; 201 } 202 203 reference operator[](difference_type __n) const { return *(*this + __n); } 204 205 bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; } 206 bool operator!=(const _Self& __x) const { return !(*this == __x); } 207 bool operator<(const _Self& __x) const { 208 return (_M_node == __x._M_node) ? 209 (_M_cur < __x._M_cur) : (_M_node < __x._M_node); 210 } 211 212 void _M_set_node(_Map_pointer __new_node) { 213 _M_node = __new_node; 214 _M_first = *__new_node; 215 _M_last = _M_first + difference_type(_S_buffer_size()); 216 } 217 }; 218 219 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION 220 221 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG 222 223 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz> 224 inline random_access_iterator_tag 225 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) { 226 return random_access_iterator_tag(); 227 } 228 229 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz> 230 inline _Tp* 231 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) { 232 return 0; 233 } 234 235 template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz> 236 inline ptrdiff_t* 237 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) { 238 return 0; 239 } 240 241 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 242 243 template <class _Tp, class _Ref, class _Ptr> 244 inline random_access_iterator_tag 245 iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&) 246 { 247 return random_access_iterator_tag(); 248 } 249 250 template <class _Tp, class _Ref, class _Ptr> 251 inline _Tp* 252 value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; } 253 254 template <class _Tp, class _Ref, class _Ptr> 255 inline ptrdiff_t* 256 distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { 257 return 0; 258 } 259 260 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 261 262 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 263 264 // Deque base class. It has two purposes. First, its constructor 265 // and destructor allocate (but don't initialize) storage. This makes 266 // exception safety easier. Second, the base class encapsulates all of 267 // the differences between SGI-style allocators and standard-conforming 268 // allocators. 269 270 #ifdef __STL_USE_STD_ALLOCATORS 271 272 // Base class for ordinary allocators. 273 template <class _Tp, class _Alloc, size_t __bufsiz, bool __is_static> 274 class _Deque_alloc_base { 275 public: 276 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; 277 allocator_type get_allocator() const { return node_allocator; } 278 279 _Deque_alloc_base(const allocator_type& __a) 280 : node_allocator(__a), map_allocator(__a), _M_map(0), _M_map_size(0) 281 {} 282 283 protected: 284 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type 285 map_allocator_type; 286 287 allocator_type node_allocator; 288 map_allocator_type map_allocator; 289 290 _Tp* _M_allocate_node() { 291 return node_allocator.allocate(__deque_buf_size(__bufsiz,sizeof(_Tp))); 292 } 293 void _M_deallocate_node(_Tp* __p) { 294 node_allocator.deallocate(__p, __deque_buf_size(__bufsiz,sizeof(_Tp))); 295 } 296 _Tp** _M_allocate_map(size_t __n) 297 { return map_allocator.allocate(__n); } 298 void _M_deallocate_map(_Tp** __p, size_t __n) 299 { map_allocator.deallocate(__p, __n); } 300 301 _Tp** _M_map; 302 size_t _M_map_size; 303 }; 304 305 // Specialization for instanceless allocators. 306 template <class _Tp, class _Alloc, size_t __bufsiz> 307 class _Deque_alloc_base<_Tp, _Alloc, __bufsiz, true> 308 { 309 public: 310 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; 311 allocator_type get_allocator() const { return allocator_type(); } 312 313 _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {} 314 315 protected: 316 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type; 317 typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type; 318 319 _Tp* _M_allocate_node() 320 { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz, 321 sizeof(_Tp))); } 322 void _M_deallocate_node(_Tp* __p) 323 { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz, 324 sizeof(_Tp))); } 325 _Tp** _M_allocate_map(size_t __n) 326 { return _Map_alloc_type::allocate(__n); } 327 void _M_deallocate_map(_Tp** __p, size_t __n) 328 { _Map_alloc_type::deallocate(__p, __n); } 329 330 _Tp** _M_map; 331 size_t _M_map_size; 332 }; 333 334 template <class _Tp, class _Alloc, size_t __bufsiz> 335 class _Deque_base 336 : public _Deque_alloc_base<_Tp,_Alloc,__bufsiz, 337 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 338 { 339 public: 340 typedef _Deque_alloc_base<_Tp,_Alloc,__bufsiz, 341 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 342 _Base; 343 typedef typename _Base::allocator_type allocator_type; 344 typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator; 345 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator; 346 347 _Deque_base(const allocator_type& __a, size_t __num_elements) 348 : _Base(__a), _M_start(), _M_finish() 349 { _M_initialize_map(__num_elements); } 350 _Deque_base(const allocator_type& __a) 351 : _Base(__a), _M_start(), _M_finish() {} 352 ~_Deque_base(); 353 354 protected: 355 void _M_initialize_map(size_t); 356 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); 357 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); 358 enum { _S_initial_map_size = 8 }; 359 360 protected: 361 iterator _M_start; 362 iterator _M_finish; 363 }; 364 365 #else /* __STL_USE_STD_ALLOCATORS */ 366 367 template <class _Tp, class _Alloc, size_t __bufsiz> 368 class _Deque_base { 369 public: 370 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG 371 typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator; 372 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator; 373 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 374 typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; 375 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; 376 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 377 378 typedef _Alloc allocator_type; 379 allocator_type get_allocator() const { return allocator_type(); } 380 381 _Deque_base(const allocator_type&, size_t __num_elements) 382 : _M_map(0), _M_map_size(0), _M_start(), _M_finish() { 383 _M_initialize_map(__num_elements); 384 } 385 _Deque_base(const allocator_type&) 386 : _M_map(0), _M_map_size(0), _M_start(), _M_finish() {} 387 ~_Deque_base(); 388 389 protected: 390 void _M_initialize_map(size_t); 391 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); 392 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); 393 enum { _S_initial_map_size = 8 }; 394 395 protected: 396 _Tp** _M_map; 397 size_t _M_map_size; 398 iterator _M_start; 399 iterator _M_finish; 400 401 typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type; 402 typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type; 403 404 _Tp* _M_allocate_node() 405 { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz, 406 sizeof(_Tp))); } 407 void _M_deallocate_node(_Tp* __p) 408 { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz, 409 sizeof(_Tp))); } 410 _Tp** _M_allocate_map(size_t __n) 411 { return _Map_alloc_type::allocate(__n); } 412 void _M_deallocate_map(_Tp** __p, size_t __n) 413 { _Map_alloc_type::deallocate(__p, __n); } 414 }; 415 416 #endif /* __STL_USE_STD_ALLOCATORS */ 417 418 // Non-inline member functions from _Deque_base. 419 420 template <class _Tp, class _Alloc, size_t __bufsiz> 421 _Deque_base<_Tp,_Alloc,__bufsiz>::~_Deque_base() { 422 if (_M_map) { 423 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1); 424 _M_deallocate_map(_M_map, _M_map_size); 425 } 426 } 427 428 template <class _Tp, class _Alloc, size_t __bufsiz> 429 void 430 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_initialize_map(size_t __num_elements) 431 { 432 size_t __num_nodes = 433 __num_elements / __deque_buf_size(__bufsiz, sizeof(_Tp)) + 1; 434 435 _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2); 436 _M_map = _M_allocate_map(_M_map_size); 437 438 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2; 439 _Tp** __nfinish = __nstart + __num_nodes; 440 441 __STL_TRY { 442 _M_create_nodes(__nstart, __nfinish); 443 } 444 __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), 445 _M_map = 0, _M_map_size = 0)); 446 _M_start._M_set_node(__nstart); 447 _M_finish._M_set_node(__nfinish - 1); 448 _M_start._M_cur = _M_start._M_first; 449 _M_finish._M_cur = _M_finish._M_first + 450 __num_elements % __deque_buf_size(__bufsiz, sizeof(_Tp)); 451 } 452 453 template <class _Tp, class _Alloc, size_t __bufsiz> 454 void 455 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_create_nodes(_Tp** __nstart, 456 _Tp** __nfinish) 457 { 458 _Tp** __cur; 459 __STL_TRY { 460 for (__cur = __nstart; __cur < __nfinish; ++__cur) 461 *__cur = _M_allocate_node(); 462 } 463 __STL_UNWIND(_M_destroy_nodes(__nstart, __cur)); 464 } 465 466 template <class _Tp, class _Alloc, size_t __bufsiz> 467 void 468 _Deque_base<_Tp,_Alloc,__bufsiz>::_M_destroy_nodes(_Tp** __nstart, 469 _Tp** __nfinish) 470 { 471 for (_Tp** __n = __nstart; __n < __nfinish; ++__n) 472 _M_deallocate_node(*__n); 473 } 474 475 // See __deque_buf_size(). The only reason that the default value is 0 476 // is as a workaround for bugs in the way that some compilers handle 477 // constant expressions. 478 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp), 479 size_t __bufsiz = 0> 480 class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> { 481 typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base; 482 public: // Basic types 483 typedef _Tp value_type; 484 typedef value_type* pointer; 485 typedef const value_type* const_pointer; 486 typedef value_type& reference; 487 typedef const value_type& const_reference; 488 typedef size_t size_type; 489 typedef ptrdiff_t difference_type; 490 491 typedef typename _Base::allocator_type allocator_type; 492 allocator_type get_allocator() const { return _Base::get_allocator(); } 493 494 public: // Iterators 495 typedef typename _Base::iterator iterator; 496 typedef typename _Base::const_iterator const_iterator; 497 498 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 499 typedef reverse_iterator<const_iterator> const_reverse_iterator; 500 typedef reverse_iterator<iterator> reverse_iterator; 501 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 502 typedef reverse_iterator<const_iterator, value_type, const_reference, 503 difference_type> 504 const_reverse_iterator; 505 typedef reverse_iterator<iterator, value_type, reference, difference_type> 506 reverse_iterator; 507 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 508 509 protected: // Internal typedefs 510 typedef pointer* _Map_pointer; 511 static size_t _S_buffer_size() 512 { return __deque_buf_size(__bufsiz, sizeof(_Tp)); } 513 514 protected: 515 #ifdef __STL_USE_NAMESPACES 516 using _Base::_M_initialize_map; 517 using _Base::_M_create_nodes; 518 using _Base::_M_destroy_nodes; 519 using _Base::_M_allocate_node; 520 using _Base::_M_deallocate_node; 521 using _Base::_M_allocate_map; 522 using _Base::_M_deallocate_map; 523 524 using _Base::_M_map; 525 using _Base::_M_map_size; 526 using _Base::_M_start; 527 using _Base::_M_finish; 528 #endif /* __STL_USE_NAMESPACES */ 529 530 public: // Basic accessors 531 iterator begin() { return _M_start; } 532 iterator end() { return _M_finish; } 533 const_iterator begin() const { return _M_start; } 534 const_iterator end() const { return _M_finish; } 535 536 reverse_iterator rbegin() { return reverse_iterator(_M_finish); } 537 reverse_iterator rend() { return reverse_iterator(_M_start); } 538 const_reverse_iterator rbegin() const 539 { return const_reverse_iterator(_M_finish); } 540 const_reverse_iterator rend() const 541 { return const_reverse_iterator(_M_start); } 542 543 reference operator[](size_type __n) 544 { return _M_start[difference_type(__n)]; } 545 const_reference operator[](size_type __n) const 546 { return _M_start[difference_type(__n)]; } 547 548 reference front() { return *_M_start; } 549 reference back() { 550 iterator __tmp = _M_finish; 551 --__tmp; 552 return *__tmp; 553 } 554 const_reference front() const { return *_M_start; } 555 const_reference back() const { 556 const_iterator __tmp = _M_finish; 557 --__tmp; 558 return *__tmp; 559 } 560 561 size_type size() const { return _M_finish - _M_start;; } 562 size_type max_size() const { return size_type(-1); } 563 bool empty() const { return _M_finish == _M_start; } 564 565 public: // Constructor, destructor. 566 explicit deque(const allocator_type& __a = allocator_type()) 567 : _Base(__a, 0) {} 568 deque(const deque& __x) : _Base(__x.get_allocator(), __x.size()) 569 { uninitialized_copy(__x.begin(), __x.end(), _M_start); } 570 deque(size_type __n, const value_type& __value, 571 const allocator_type& __a = allocator_type()) : _Base(__a, __n) 572 { _M_fill_initialize(__value); } 573 explicit deque(size_type __n) : _Base(allocator_type(), __n) 574 { _M_fill_initialize(value_type()); } 575 576 #ifdef __STL_MEMBER_TEMPLATES 577 578 // Check whether it's an integral type. If so, it's not an iterator. 579 template <class _InputIterator> 580 deque(_InputIterator __first, _InputIterator __last, 581 const allocator_type& __a = allocator_type()) : _Base(__a) { 582 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 583 _M_initialize_dispatch(__first, __last, _Integral()); 584 } 585 586 template <class _Integer> 587 void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { 588 _M_initialize_map(__n); 589 _M_fill_initialize(__x); 590 } 591 592 template <class _InputIter> 593 void _M_initialize_dispatch(_InputIter __first, _InputIter __last, 594 __false_type) { 595 _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first)); 596 } 597 598 #else /* __STL_MEMBER_TEMPLATES */ 599 600 deque(const value_type* __first, const value_type* __last, 601 const allocator_type& __a = allocator_type()) 602 : _Base(__a, __last - __first) 603 { uninitialized_copy(__first, __last, _M_start); } 604 deque(const_iterator __first, const_iterator __last, 605 const allocator_type& __a = allocator_type()) 606 : _Base(__a, __last - __first) 607 { uninitialized_copy(__first, __last, _M_start); } 608 609 #endif /* __STL_MEMBER_TEMPLATES */ 610 611 ~deque() { destroy(_M_start, _M_finish); } 612 613 deque& operator= (const deque& __x) { 614 const size_type __len = size(); 615 if (&__x != this) { 616 if (__len >= __x.size()) 617 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); 618 else { 619 const_iterator __mid = __x.begin() + difference_type(__len); 620 copy(__x.begin(), __mid, _M_start); 621 insert(_M_finish, __mid, __x.end()); 622 } 623 } 624 return *this; 625 } 626 627 void swap(deque& __x) { 628 __STD::swap(_M_start, __x._M_start); 629 __STD::swap(_M_finish, __x._M_finish); 630 __STD::swap(_M_map, __x._M_map); 631 __STD::swap(_M_map_size, __x._M_map_size); 632 } 633 634 public: 635 // assign(), a generalized assignment member function. Two 636 // versions: one that takes a count, and one that takes a range. 637 // The range version is a member template, so we dispatch on whether 638 // or not the type is an integer. 639 640 void assign(size_type __n, const _Tp& __val) { 641 if (__n > size()) { 642 fill(begin(), end(), __val); 643 insert(end(), __n - size(), __val); 644 } 645 else { 646 erase(begin() + __n, end()); 647 fill(begin(), end(), __val); 648 } 649 } 650 651 #ifdef __STL_MEMBER_TEMPLATES 652 653 template <class _InputIterator> 654 void assign(_InputIterator __first, _InputIterator __last) { 655 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 656 _M_assign_dispatch(__first, __last, _Integral()); 657 } 658 659 private: // helper functions for assign() 660 661 template <class _Integer> 662 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 663 { assign((size_type) __n, (_Tp) __val); } 664 665 template <class _InputIterator> 666 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 667 __false_type) { 668 _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); 669 } 670 671 template <class _InputIterator> 672 void _M_assign_aux(_InputIterator __first, _InputIterator __last, 673 input_iterator_tag); 674 675 template <class _ForwardIterator> 676 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 677 forward_iterator_tag) { 678 size_type __len = 0; 679 distance(__first, __last, __len); 680 if (__len > size()) { 681 _ForwardIterator __mid = __first; 682 advance(__mid, size()); 683 copy(__first, __mid, begin()); 684 insert(end(), __mid, __last); 685 } 686 else 687 erase(copy(__first, __last, begin()), end()); 688 } 689 690 #endif /* __STL_MEMBER_TEMPLATES */ 691 692 public: // push_* and pop_* 693 694 void push_back(const value_type& __t) { 695 if (_M_finish._M_cur != _M_finish._M_last - 1) { 696 construct(_M_finish._M_cur, __t); 697 ++_M_finish._M_cur; 698 } 699 else 700 _M_push_back_aux(__t); 701 } 702 703 void push_back() { 704 if (_M_finish._M_cur != _M_finish._M_last - 1) { 705 construct(_M_finish._M_cur); 706 ++_M_finish._M_cur; 707 } 708 else 709 _M_push_back_aux(); 710 } 711 712 void push_front(const value_type& __t) { 713 if (_M_start._M_cur != _M_start._M_first) { 714 construct(_M_start._M_cur - 1, __t); 715 --_M_start._M_cur; 716 } 717 else 718 _M_push_front_aux(__t); 719 } 720 721 void push_front() { 722 if (_M_start._M_cur != _M_start._M_first) { 723 construct(_M_start._M_cur - 1); 724 --_M_start._M_cur; 725 } 726 else 727 _M_push_front_aux(); 728 } 729 730 731 void pop_back() { 732 if (_M_finish._M_cur != _M_finish._M_first) { 733 --_M_finish._M_cur; 734 destroy(_M_finish._M_cur); 735 } 736 else 737 _M_pop_back_aux(); 738 } 739 740 void pop_front() { 741 if (_M_start._M_cur != _M_start._M_last - 1) { 742 destroy(_M_start._M_cur); 743 ++_M_start._M_cur; 744 } 745 else 746 _M_pop_front_aux(); 747 } 748 749 public: // Insert 750 751 iterator insert(iterator position, const value_type& __x) { 752 if (position._M_cur == _M_start._M_cur) { 753 push_front(__x); 754 return _M_start; 755 } 756 else if (position._M_cur == _M_finish._M_cur) { 757 push_back(__x); 758 iterator __tmp = _M_finish; 759 --__tmp; 760 return __tmp; 761 } 762 else { 763 return _M_insert_aux(position, __x); 764 } 765 } 766 767 iterator insert(iterator __position) 768 { return insert(__position, value_type()); } 769 770 void insert(iterator __pos, size_type __n, const value_type& __x); 771 772 #ifdef __STL_MEMBER_TEMPLATES 773 774 // Check whether it's an integral type. If so, it's not an iterator. 775 template <class _InputIterator> 776 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { 777 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 778 _M_insert_dispatch(__pos, __first, __last, _Integral()); 779 } 780 781 template <class _Integer> 782 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 783 __true_type) { 784 insert(__pos, (size_type) __n, (value_type) __x); 785 } 786 787 template <class _InputIterator> 788 void _M_insert_dispatch(iterator __pos, 789 _InputIterator __first, _InputIterator __last, 790 __false_type) { 791 insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first)); 792 } 793 794 #else /* __STL_MEMBER_TEMPLATES */ 795 796 void insert(iterator __pos, 797 const value_type* __first, const value_type* __last); 798 void insert(iterator __pos, 799 const_iterator __first, const_iterator __last); 800 801 #endif /* __STL_MEMBER_TEMPLATES */ 802 803 void resize(size_type __new_size, const value_type& __x) { 804 const size_type __len = size(); 805 if (__new_size < __len) 806 erase(_M_start + __new_size, _M_finish); 807 else 808 insert(_M_finish, __new_size - __len, __x); 809 } 810 811 void resize(size_type new_size) { resize(new_size, value_type()); } 812 813 public: // Erase 814 iterator erase(iterator __pos) { 815 iterator __next = __pos; 816 ++__next; 817 difference_type __index = __pos - _M_start; 818 if (static_cast<size_type>(__index) < (size() >> 1)) { 819 copy_backward(_M_start, __pos, __next); 820 pop_front(); 821 } 822 else { 823 copy(__next, _M_finish, __pos); 824 pop_back(); 825 } 826 return _M_start + __index; 827 } 828 829 iterator erase(iterator __first, iterator __last); 830 void clear(); 831 832 protected: // Internal construction/destruction 833 834 void _M_fill_initialize(const value_type& __value); 835 836 #ifdef __STL_MEMBER_TEMPLATES 837 838 template <class _InputIterator> 839 void _M_range_initialize(_InputIterator __first, _InputIterator __last, 840 input_iterator_tag); 841 842 template <class _ForwardIterator> 843 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 844 forward_iterator_tag); 845 846 #endif /* __STL_MEMBER_TEMPLATES */ 847 848 protected: // Internal push_* and pop_* 849 850 void _M_push_back_aux(const value_type&); 851 void _M_push_back_aux(); 852 void _M_push_front_aux(const value_type&); 853 void _M_push_front_aux(); 854 void _M_pop_back_aux(); 855 void _M_pop_front_aux(); 856 857 protected: // Internal insert functions 858 859 #ifdef __STL_MEMBER_TEMPLATES 860 861 template <class _InputIterator> 862 void insert(iterator __pos, _InputIterator __first, _InputIterator __last, 863 input_iterator_tag); 864 865 template <class _ForwardIterator> 866 void insert(iterator __pos, 867 _ForwardIterator __first, _ForwardIterator __last, 868 forward_iterator_tag); 869 870 #endif /* __STL_MEMBER_TEMPLATES */ 871 872 iterator _M_insert_aux(iterator __pos, const value_type& __x); 873 iterator _M_insert_aux(iterator __pos); 874 void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); 875 876 #ifdef __STL_MEMBER_TEMPLATES 877 878 template <class _ForwardIterator> 879 void _M_insert_aux(iterator __pos, 880 _ForwardIterator __first, _ForwardIterator __last, 881 size_type __n); 882 883 #else /* __STL_MEMBER_TEMPLATES */ 884 885 void _M_insert_aux(iterator __pos, 886 const value_type* __first, const value_type* __last, 887 size_type __n); 888 889 void _M_insert_aux(iterator __pos, 890 const_iterator __first, const_iterator __last, 891 size_type __n); 892 893 #endif /* __STL_MEMBER_TEMPLATES */ 894 895 iterator _M_reserve_elements_at_front(size_type __n) { 896 size_type __vacancies = _M_start._M_cur - _M_start._M_first; 897 if (__n > __vacancies) 898 _M_new_elements_at_front(__n - __vacancies); 899 return _M_start - difference_type(__n); 900 } 901 902 iterator _M_reserve_elements_at_back(size_type __n) { 903 size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1; 904 if (__n > __vacancies) 905 _M_new_elements_at_back(__n - __vacancies); 906 return _M_finish + difference_type(__n); 907 } 908 909 void _M_new_elements_at_front(size_type __new_elements); 910 void _M_new_elements_at_back(size_type __new_elements); 911 912 protected: // Allocation of _M_map and nodes 913 914 // Makes sure the _M_map has space for new nodes. Does not actually 915 // add the nodes. Can invalidate _M_map pointers. (And consequently, 916 // deque iterators.) 917 918 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) { 919 if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map)) 920 _M_reallocate_map(__nodes_to_add, false); 921 } 922 923 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) { 924 if (__nodes_to_add > size_type(_M_start._M_node - _M_map)) 925 _M_reallocate_map(__nodes_to_add, true); 926 } 927 928 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); 929 930 #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG 931 public: 932 bool operator==(const deque<_Tp,_Alloc,0>& __x) const { 933 return size() == __x.size() && equal(begin(), end(), __x.begin()); 934 } 935 bool operator!=(const deque<_Tp,_Alloc,0>& __x) const { 936 return size() != __x.size() || !equal(begin(), end(), __x.begin()); 937 } 938 bool operator<(const deque<_Tp,_Alloc,0>& __x) const { 939 return lexicographical_compare(begin(), end(), __x.begin(), __x.end()); 940 } 941 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 942 }; 943 944 // Non-inline member functions 945 946 #ifdef __STL_MEMBER_TEMPLATES 947 948 template <class _Tp, class _Alloc, size_t __bufsize> 949 template <class _InputIter> 950 void deque<_Tp, _Alloc, __bufsize> 951 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) 952 { 953 iterator __cur = begin(); 954 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 955 *__cur = *__first; 956 if (__first == __last) 957 erase(__cur, end()); 958 else 959 insert(end(), __first, __last); 960 } 961 962 #endif /* __STL_MEMBER_TEMPLATES */ 963 964 template <class _Tp, class _Alloc, size_t __bufsize> 965 void 966 deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos, 967 size_type __n, const value_type& __x) 968 { 969 if (__pos._M_cur == _M_start._M_cur) { 970 iterator __new_start = _M_reserve_elements_at_front(__n); 971 uninitialized_fill(__new_start, _M_start, __x); 972 _M_start = __new_start; 973 } 974 else if (__pos._M_cur == _M_finish._M_cur) { 975 iterator __new_finish = _M_reserve_elements_at_back(__n); 976 uninitialized_fill(_M_finish, __new_finish, __x); 977 _M_finish = __new_finish; 978 } 979 else 980 _M_insert_aux(__pos, __n, __x); 981 } 982 983 #ifndef __STL_MEMBER_TEMPLATES 984 985 template <class _Tp, class _Alloc, size_t __bufsize> 986 void deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos, 987 const value_type* __first, 988 const value_type* __last) { 989 size_type __n = __last - __first; 990 if (__pos._M_cur == _M_start._M_cur) { 991 iterator __new_start = _M_reserve_elements_at_front(__n); 992 __STL_TRY { 993 uninitialized_copy(__first, __last, __new_start); 994 _M_start = __new_start; 995 } 996 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 997 } 998 else if (__pos._M_cur == _M_finish._M_cur) { 999 iterator __new_finish = _M_reserve_elements_at_back(__n); 1000 __STL_TRY { 1001 uninitialized_copy(__first, __last, _M_finish); 1002 _M_finish = __new_finish; 1003 } 1004 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1005 __new_finish._M_node + 1)); 1006 } 1007 else 1008 _M_insert_aux(__pos, __first, __last, __n); 1009 } 1010 1011 template <class _Tp, class _Alloc, size_t __bufsize> 1012 void deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, 1013 const_iterator __first, 1014 const_iterator __last) 1015 { 1016 size_type __n = __last - __first; 1017 if (__pos._M_cur == _M_start._M_cur) { 1018 iterator __new_start = _M_reserve_elements_at_front(__n); 1019 __STL_TRY { 1020 uninitialized_copy(__first, __last, __new_start); 1021 _M_start = __new_start; 1022 } 1023 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 1024 } 1025 else if (__pos._M_cur == _M_finish._M_cur) { 1026 iterator __new_finish = _M_reserve_elements_at_back(__n); 1027 __STL_TRY { 1028 uninitialized_copy(__first, __last, _M_finish); 1029 _M_finish = __new_finish; 1030 } 1031 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1032 __new_finish._M_node + 1)); 1033 } 1034 else 1035 _M_insert_aux(__pos, __first, __last, __n); 1036 } 1037 1038 #endif /* __STL_MEMBER_TEMPLATES */ 1039 1040 template <class _Tp, class _Alloc, size_t __bufsize> 1041 deque<_Tp,_Alloc,__bufsize>::iterator 1042 deque<_Tp,_Alloc,__bufsize>::erase(iterator __first, iterator __last) 1043 { 1044 if (__first == _M_start && __last == _M_finish) { 1045 clear(); 1046 return _M_finish; 1047 } 1048 else { 1049 difference_type __n = __last - __first; 1050 difference_type __elems_before = __first - _M_start; 1051 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) { 1052 copy_backward(_M_start, __first, __last); 1053 iterator __new_start = _M_start + __n; 1054 destroy(_M_start, __new_start); 1055 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 1056 _M_start = __new_start; 1057 } 1058 else { 1059 copy(__last, _M_finish, __first); 1060 iterator __new_finish = _M_finish - __n; 1061 destroy(__new_finish, _M_finish); 1062 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); 1063 _M_finish = __new_finish; 1064 } 1065 return _M_start + __elems_before; 1066 } 1067 } 1068 1069 template <class _Tp, class _Alloc, size_t __bufsize> 1070 void deque<_Tp,_Alloc,__bufsize>::clear() 1071 { 1072 for (_Map_pointer __node = _M_start._M_node + 1; 1073 __node < _M_finish._M_node; 1074 ++__node) { 1075 destroy(*__node, *__node + _S_buffer_size()); 1076 _M_deallocate_node(*__node); 1077 } 1078 1079 if (_M_start._M_node != _M_finish._M_node) { 1080 destroy(_M_start._M_cur, _M_start._M_last); 1081 destroy(_M_finish._M_first, _M_finish._M_cur); 1082 _M_deallocate_node(_M_finish._M_first); 1083 } 1084 else 1085 destroy(_M_start._M_cur, _M_finish._M_cur); 1086 1087 _M_finish = _M_start; 1088 } 1089 1090 // Precondition: _M_start and _M_finish have already been initialized, 1091 // but none of the deque's elements have yet been constructed. 1092 template <class _Tp, class _Alloc, size_t __bufsize> 1093 void 1094 deque<_Tp,_Alloc,__bufsize>::_M_fill_initialize(const value_type& __value) { 1095 _Map_pointer __cur; 1096 __STL_TRY { 1097 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) 1098 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); 1099 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); 1100 } 1101 __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur))); 1102 } 1103 1104 #ifdef __STL_MEMBER_TEMPLATES 1105 1106 template <class _Tp, class _Alloc, size_t __bufsize> 1107 template <class _InputIterator> 1108 void 1109 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_InputIterator __first, 1110 _InputIterator __last, 1111 input_iterator_tag) 1112 { 1113 _M_initialize_map(0); 1114 for ( ; __first != __last; ++__first) 1115 push_back(*__first); 1116 } 1117 1118 template <class _Tp, class _Alloc, size_t __bufsize> 1119 template <class _ForwardIterator> 1120 void 1121 deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first, 1122 _ForwardIterator __last, 1123 forward_iterator_tag) 1124 { 1125 size_type __n = 0; 1126 distance(__first, __last, __n); 1127 _M_initialize_map(__n); 1128 1129 _Map_pointer __cur_node; 1130 __STL_TRY { 1131 for (__cur_node = _M_start._M_node; 1132 __cur_node < _M_finish._M_node; 1133 ++__cur_node) { 1134 _ForwardIterator __mid = __first; 1135 advance(__mid, _S_buffer_size()); 1136 uninitialized_copy(__first, __mid, *__cur_node); 1137 __first = __mid; 1138 } 1139 uninitialized_copy(__first, __last, _M_finish._M_first); 1140 } 1141 __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node))); 1142 } 1143 1144 #endif /* __STL_MEMBER_TEMPLATES */ 1145 1146 // Called only if _M_finish._M_cur == _M_finish._M_last - 1. 1147 template <class _Tp, class _Alloc, size_t __bufsize> 1148 void 1149 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux(const value_type& __t) 1150 { 1151 value_type __t_copy = __t; 1152 _M_reserve_map_at_back(); 1153 *(_M_finish._M_node + 1) = _M_allocate_node(); 1154 __STL_TRY { 1155 construct(_M_finish._M_cur, __t_copy); 1156 _M_finish._M_set_node(_M_finish._M_node + 1); 1157 _M_finish._M_cur = _M_finish._M_first; 1158 } 1159 __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1))); 1160 } 1161 1162 // Called only if _M_finish._M_cur == _M_finish._M_last - 1. 1163 template <class _Tp, class _Alloc, size_t __bufsize> 1164 void 1165 deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux() 1166 { 1167 _M_reserve_map_at_back(); 1168 *(_M_finish._M_node + 1) = _M_allocate_node(); 1169 __STL_TRY { 1170 construct(_M_finish._M_cur); 1171 _M_finish._M_set_node(_M_finish._M_node + 1); 1172 _M_finish._M_cur = _M_finish._M_first; 1173 } 1174 __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1))); 1175 } 1176 1177 // Called only if _M_start._M_cur == _M_start._M_first. 1178 template <class _Tp, class _Alloc, size_t __bufsize> 1179 void 1180 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux(const value_type& __t) 1181 { 1182 value_type __t_copy = __t; 1183 _M_reserve_map_at_front(); 1184 *(_M_start._M_node - 1) = _M_allocate_node(); 1185 __STL_TRY { 1186 _M_start._M_set_node(_M_start._M_node - 1); 1187 _M_start._M_cur = _M_start._M_last - 1; 1188 construct(_M_start._M_cur, __t_copy); 1189 } 1190 __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1)))); 1191 } 1192 1193 // Called only if _M_start._M_cur == _M_start._M_first. 1194 template <class _Tp, class _Alloc, size_t __bufsize> 1195 void 1196 deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux() 1197 { 1198 _M_reserve_map_at_front(); 1199 *(_M_start._M_node - 1) = _M_allocate_node(); 1200 __STL_TRY { 1201 _M_start._M_set_node(_M_start._M_node - 1); 1202 _M_start._M_cur = _M_start._M_last - 1; 1203 construct(_M_start._M_cur); 1204 } 1205 __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1)))); 1206 } 1207 1208 // Called only if _M_finish._M_cur == _M_finish._M_first. 1209 template <class _Tp, class _Alloc, size_t __bufsize> 1210 void 1211 deque<_Tp,_Alloc,__bufsize>::_M_pop_back_aux() 1212 { 1213 _M_deallocate_node(_M_finish._M_first); 1214 _M_finish._M_set_node(_M_finish._M_node - 1); 1215 _M_finish._M_cur = _M_finish._M_last - 1; 1216 destroy(_M_finish._M_cur); 1217 } 1218 1219 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that 1220 // if the deque has at least one element (a precondition for this member 1221 // function), and if _M_start._M_cur == _M_start._M_last, then the deque 1222 // must have at least two nodes. 1223 template <class _Tp, class _Alloc, size_t __bufsize> 1224 void 1225 deque<_Tp,_Alloc,__bufsize>::_M_pop_front_aux() 1226 { 1227 destroy(_M_start._M_cur); 1228 _M_deallocate_node(_M_start._M_first); 1229 _M_start._M_set_node(_M_start._M_node + 1); 1230 _M_start._M_cur = _M_start._M_first; 1231 } 1232 1233 #ifdef __STL_MEMBER_TEMPLATES 1234 1235 template <class _Tp, class _Alloc, size_t __bufsize> 1236 template <class _InputIterator> 1237 void 1238 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, 1239 _InputIterator __first, 1240 _InputIterator __last, 1241 input_iterator_tag) 1242 { 1243 copy(__first, __last, inserter(*this, __pos)); 1244 } 1245 1246 template <class _Tp, class _Alloc, size_t __bufsize> 1247 template <class _ForwardIterator> 1248 void 1249 deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, 1250 _ForwardIterator __first, 1251 _ForwardIterator __last, 1252 forward_iterator_tag) { 1253 size_type __n = 0; 1254 distance(__first, __last, __n); 1255 if (__pos._M_cur == _M_start._M_cur) { 1256 iterator __new_start = _M_reserve_elements_at_front(__n); 1257 __STL_TRY { 1258 uninitialized_copy(__first, __last, __new_start); 1259 _M_start = __new_start; 1260 } 1261 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 1262 } 1263 else if (__pos._M_cur == _M_finish._M_cur) { 1264 iterator __new_finish = _M_reserve_elements_at_back(__n); 1265 __STL_TRY { 1266 uninitialized_copy(__first, __last, _M_finish); 1267 _M_finish = __new_finish; 1268 } 1269 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1270 __new_finish._M_node + 1)); 1271 } 1272 else 1273 _M_insert_aux(__pos, __first, __last, __n); 1274 } 1275 1276 #endif /* __STL_MEMBER_TEMPLATES */ 1277 1278 template <class _Tp, class _Alloc, size_t __bufsize> 1279 typename deque<_Tp, _Alloc, __bufsize>::iterator 1280 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, 1281 const value_type& __x) 1282 { 1283 difference_type __index = __pos - _M_start; 1284 value_type __x_copy = __x; 1285 if (static_cast<size_type>(__index) < size() / 2) { 1286 push_front(front()); 1287 iterator __front1 = _M_start; 1288 ++__front1; 1289 iterator __front2 = __front1; 1290 ++__front2; 1291 __pos = _M_start + __index; 1292 iterator __pos1 = __pos; 1293 ++__pos1; 1294 copy(__front2, __pos1, __front1); 1295 } 1296 else { 1297 push_back(back()); 1298 iterator __back1 = _M_finish; 1299 --__back1; 1300 iterator __back2 = __back1; 1301 --__back2; 1302 __pos = _M_start + __index; 1303 copy_backward(__pos, __back2, __back1); 1304 } 1305 *__pos = __x_copy; 1306 return __pos; 1307 } 1308 1309 template <class _Tp, class _Alloc, size_t __bufsize> 1310 typename deque<_Tp,_Alloc,__bufsize>::iterator 1311 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos) 1312 { 1313 difference_type __index = __pos - _M_start; 1314 if (static_cast<size_type>(__index) < size() / 2) { 1315 push_front(front()); 1316 iterator __front1 = _M_start; 1317 ++__front1; 1318 iterator __front2 = __front1; 1319 ++__front2; 1320 __pos = _M_start + __index; 1321 iterator __pos1 = __pos; 1322 ++__pos1; 1323 copy(__front2, __pos1, __front1); 1324 } 1325 else { 1326 push_back(back()); 1327 iterator __back1 = _M_finish; 1328 --__back1; 1329 iterator __back2 = __back1; 1330 --__back2; 1331 __pos = _M_start + __index; 1332 copy_backward(__pos, __back2, __back1); 1333 } 1334 *__pos = value_type(); 1335 return __pos; 1336 } 1337 1338 template <class _Tp, class _Alloc, size_t __bufsize> 1339 void 1340 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, 1341 size_type __n, 1342 const value_type& __x) 1343 { 1344 const difference_type __elems_before = __pos - _M_start; 1345 size_type __length = size(); 1346 value_type __x_copy = __x; 1347 if (static_cast<size_type>(__elems_before) < __length / 2) { 1348 iterator __new_start = _M_reserve_elements_at_front(__n); 1349 iterator __old_start = _M_start; 1350 __pos = _M_start + __elems_before; 1351 __STL_TRY { 1352 if (__elems_before >= difference_type(__n)) { 1353 iterator __start_n = _M_start + difference_type(__n); 1354 uninitialized_copy(_M_start, __start_n, __new_start); 1355 _M_start = __new_start; 1356 copy(__start_n, __pos, __old_start); 1357 fill(__pos - difference_type(__n), __pos, __x_copy); 1358 } 1359 else { 1360 __uninitialized_copy_fill(_M_start, __pos, __new_start, 1361 _M_start, __x_copy); 1362 _M_start = __new_start; 1363 fill(__old_start, __pos, __x_copy); 1364 } 1365 } 1366 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 1367 } 1368 else { 1369 iterator __new_finish = _M_reserve_elements_at_back(__n); 1370 iterator __old_finish = _M_finish; 1371 const difference_type __elems_after = 1372 difference_type(__length) - __elems_before; 1373 __pos = _M_finish - __elems_after; 1374 __STL_TRY { 1375 if (__elems_after > difference_type(__n)) { 1376 iterator __finish_n = _M_finish - difference_type(__n); 1377 uninitialized_copy(__finish_n, _M_finish, _M_finish); 1378 _M_finish = __new_finish; 1379 copy_backward(__pos, __finish_n, __old_finish); 1380 fill(__pos, __pos + difference_type(__n), __x_copy); 1381 } 1382 else { 1383 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), 1384 __x_copy, __pos, _M_finish); 1385 _M_finish = __new_finish; 1386 fill(__pos, __old_finish, __x_copy); 1387 } 1388 } 1389 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1390 __new_finish._M_node + 1)); 1391 } 1392 } 1393 1394 #ifdef __STL_MEMBER_TEMPLATES 1395 1396 template <class _Tp, class _Alloc, size_t __bufsize> 1397 template <class _ForwardIterator> 1398 void 1399 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, 1400 _ForwardIterator __first, 1401 _ForwardIterator __last, 1402 size_type __n) 1403 { 1404 const difference_type __elemsbefore = __pos - _M_start; 1405 size_type __length = size(); 1406 if (static_cast<size_type>(__elemsbefore) < __length / 2) { 1407 iterator __new_start = _M_reserve_elements_at_front(__n); 1408 iterator __old_start = _M_start; 1409 __pos = _M_start + __elemsbefore; 1410 __STL_TRY { 1411 if (__elemsbefore >= difference_type(__n)) { 1412 iterator __start_n = _M_start + difference_type(__n); 1413 uninitialized_copy(_M_start, __start_n, __new_start); 1414 _M_start = __new_start; 1415 copy(__start_n, __pos, __old_start); 1416 copy(__first, __last, __pos - difference_type(__n)); 1417 } 1418 else { 1419 _ForwardIterator __mid = __first; 1420 advance(__mid, difference_type(__n) - __elemsbefore); 1421 __uninitialized_copy_copy(_M_start, __pos, __first, __mid, 1422 __new_start); 1423 _M_start = __new_start; 1424 copy(__mid, __last, __old_start); 1425 } 1426 } 1427 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 1428 } 1429 else { 1430 iterator __new_finish = _M_reserve_elements_at_back(__n); 1431 iterator __old_finish = _M_finish; 1432 const difference_type __elemsafter = 1433 difference_type(__length) - __elemsbefore; 1434 __pos = _M_finish - __elemsafter; 1435 __STL_TRY { 1436 if (__elemsafter > difference_type(__n)) { 1437 iterator __finish_n = _M_finish - difference_type(__n); 1438 uninitialized_copy(__finish_n, _M_finish, _M_finish); 1439 _M_finish = __new_finish; 1440 copy_backward(__pos, __finish_n, __old_finish); 1441 copy(__first, __last, __pos); 1442 } 1443 else { 1444 _ForwardIterator __mid = __first; 1445 advance(__mid, __elemsafter); 1446 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish); 1447 _M_finish = __new_finish; 1448 copy(__first, __mid, __pos); 1449 } 1450 } 1451 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1452 __new_finish._M_node + 1)); 1453 } 1454 } 1455 1456 #else /* __STL_MEMBER_TEMPLATES */ 1457 1458 template <class _Tp, class _Alloc, size_t __bufsize> 1459 void 1460 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, 1461 const value_type* __first, 1462 const value_type* __last, 1463 size_type __n) 1464 { 1465 const difference_type __elemsbefore = __pos - _M_start; 1466 size_type __length = size(); 1467 if (__elemsbefore < __length / 2) { 1468 iterator __new_start = _M_reserve_elements_at_front(__n); 1469 iterator __old_start = _M_start; 1470 __pos = _M_start + __elemsbefore; 1471 __STL_TRY { 1472 if (__elemsbefore >= difference_type(__n)) { 1473 iterator __start_n = _M_start + difference_type(__n); 1474 uninitialized_copy(_M_start, __start_n, __new_start); 1475 _M_start = __new_start; 1476 copy(__start_n, __pos, __old_start); 1477 copy(__first, __last, __pos - difference_type(__n)); 1478 } 1479 else { 1480 const value_type* __mid = 1481 __first + (difference_type(__n) - __elemsbefore); 1482 __uninitialized_copy_copy(_M_start, __pos, __first, __mid, 1483 __new_start); 1484 _M_start = __new_start; 1485 copy(__mid, __last, __old_start); 1486 } 1487 } 1488 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 1489 } 1490 else { 1491 iterator __new_finish = _M_reserve_elements_at_back(__n); 1492 iterator __old_finish = _M_finish; 1493 const difference_type __elemsafter = 1494 difference_type(__length) - __elemsbefore; 1495 __pos = _M_finish - __elemsafter; 1496 __STL_TRY { 1497 if (__elemsafter > difference_type(__n)) { 1498 iterator __finish_n = _M_finish - difference_type(__n); 1499 uninitialized_copy(__finish_n, _M_finish, _M_finish); 1500 _M_finish = __new_finish; 1501 copy_backward(__pos, __finish_n, __old_finish); 1502 copy(__first, __last, __pos); 1503 } 1504 else { 1505 const value_type* __mid = __first + __elemsafter; 1506 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish); 1507 _M_finish = __new_finish; 1508 copy(__first, __mid, __pos); 1509 } 1510 } 1511 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1512 __new_finish._M_node + 1)); 1513 } 1514 } 1515 1516 template <class _Tp, class _Alloc, size_t __bufsize> 1517 void 1518 deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, 1519 const_iterator __first, 1520 const_iterator __last, 1521 size_type __n) 1522 { 1523 const difference_type __elemsbefore = __pos - _M_start; 1524 size_type __length = size(); 1525 if (__elemsbefore < __length / 2) { 1526 iterator __new_start = _M_reserve_elements_at_front(__n); 1527 iterator __old_start = _M_start; 1528 __pos = _M_start + __elemsbefore; 1529 __STL_TRY { 1530 if (__elemsbefore >= __n) { 1531 iterator __start_n = _M_start + __n; 1532 uninitialized_copy(_M_start, __start_n, __new_start); 1533 _M_start = __new_start; 1534 copy(__start_n, __pos, __old_start); 1535 copy(__first, __last, __pos - difference_type(__n)); 1536 } 1537 else { 1538 const_iterator __mid = __first + (__n - __elemsbefore); 1539 __uninitialized_copy_copy(_M_start, __pos, __first, __mid, 1540 __new_start); 1541 _M_start = __new_start; 1542 copy(__mid, __last, __old_start); 1543 } 1544 } 1545 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); 1546 } 1547 else { 1548 iterator __new_finish = _M_reserve_elements_at_back(__n); 1549 iterator __old_finish = _M_finish; 1550 const difference_type __elemsafter = __length - __elemsbefore; 1551 __pos = _M_finish - __elemsafter; 1552 __STL_TRY { 1553 if (__elemsafter > __n) { 1554 iterator __finish_n = _M_finish - difference_type(__n); 1555 uninitialized_copy(__finish_n, _M_finish, _M_finish); 1556 _M_finish = __new_finish; 1557 copy_backward(__pos, __finish_n, __old_finish); 1558 copy(__first, __last, __pos); 1559 } 1560 else { 1561 const_iterator __mid = __first + __elemsafter; 1562 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish); 1563 _M_finish = __new_finish; 1564 copy(__first, __mid, __pos); 1565 } 1566 } 1567 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, 1568 __new_finish._M_node + 1)); 1569 } 1570 } 1571 1572 #endif /* __STL_MEMBER_TEMPLATES */ 1573 1574 template <class _Tp, class _Alloc, size_t __bufsize> 1575 void 1576 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_front(size_type __new_elems) 1577 { 1578 size_type __new_nodes 1579 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 1580 _M_reserve_map_at_front(__new_nodes); 1581 size_type __i; 1582 __STL_TRY { 1583 for (__i = 1; __i <= __new_nodes; ++__i) 1584 *(_M_start._M_node - __i) = _M_allocate_node(); 1585 } 1586 # ifdef __STL_USE_EXCEPTIONS 1587 catch(...) { 1588 for (size_type __j = 1; __j < __i; ++__j) 1589 _M_deallocate_node(*(_M_start._M_node - __j)); 1590 throw; 1591 } 1592 # endif /* __STL_USE_EXCEPTIONS */ 1593 } 1594 1595 template <class _Tp, class _Alloc, size_t __bufsize> 1596 void 1597 deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_back(size_type __new_elems) 1598 { 1599 size_type __new_nodes 1600 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 1601 _M_reserve_map_at_back(__new_nodes); 1602 size_type __i; 1603 __STL_TRY { 1604 for (__i = 1; __i <= __new_nodes; ++__i) 1605 *(_M_finish._M_node + __i) = _M_allocate_node(); 1606 } 1607 # ifdef __STL_USE_EXCEPTIONS 1608 catch(...) { 1609 for (size_type __j = 1; __j < __i; ++__j) 1610 _M_deallocate_node(*(_M_finish._M_node + __j)); 1611 throw; 1612 } 1613 # endif /* __STL_USE_EXCEPTIONS */ 1614 } 1615 1616 template <class _Tp, class _Alloc, size_t __bufsize> 1617 void 1618 deque<_Tp,_Alloc,__bufsize>::_M_reallocate_map(size_type __nodes_to_add, 1619 bool __add_at_front) 1620 { 1621 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; 1622 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 1623 1624 _Map_pointer __new_nstart; 1625 if (_M_map_size > 2 * __new_num_nodes) { 1626 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 1627 + (__add_at_front ? __nodes_to_add : 0); 1628 if (__new_nstart < _M_start._M_node) 1629 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); 1630 else 1631 copy_backward(_M_start._M_node, _M_finish._M_node + 1, 1632 __new_nstart + __old_num_nodes); 1633 } 1634 else { 1635 size_type __new_map_size = 1636 _M_map_size + max(_M_map_size, __nodes_to_add) + 2; 1637 1638 _Map_pointer __new_map = _M_allocate_map(__new_map_size); 1639 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 1640 + (__add_at_front ? __nodes_to_add : 0); 1641 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); 1642 _M_deallocate_map(_M_map, _M_map_size); 1643 1644 _M_map = __new_map; 1645 _M_map_size = __new_map_size; 1646 } 1647 1648 _M_start._M_set_node(__new_nstart); 1649 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 1650 } 1651 1652 1653 // Nonmember functions. 1654 1655 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG 1656 1657 template <class _Tp, class _Alloc, size_t __bufsiz> 1658 bool operator==(const deque<_Tp, _Alloc, __bufsiz>& __x, 1659 const deque<_Tp, _Alloc, __bufsiz>& __y) 1660 { 1661 return __x.size() == __y.size() && 1662 equal(__x.begin(), __x.end(), __y.begin()); 1663 } 1664 1665 template <class _Tp, class _Alloc, size_t __bufsiz> 1666 bool operator<(const deque<_Tp, _Alloc, __bufsiz>& __x, 1667 const deque<_Tp, _Alloc, __bufsiz>& __y) 1668 { 1669 return lexicographical_compare(__x.begin(), __x.end(), 1670 __y.begin(), __y.end()); 1671 } 1672 1673 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 1674 1675 #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && \ 1676 !defined(__STL_NON_TYPE_TMPL_PARAM_BUG) 1677 1678 template <class _Tp, class _Alloc, size_t __bufsiz> 1679 inline void 1680 swap(deque<_Tp,_Alloc,__bufsiz>& __x, deque<_Tp,_Alloc,__bufsiz>& __y) 1681 { 1682 __x.swap(__y); 1683 } 1684 1685 #endif 1686 1687 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 1688 #pragma reset woff 1174 1689 #pragma reset woff 1375 1690 #endif 1691 1692 __STL_END_NAMESPACE 1693 1694 #endif /* __SGI_STL_INTERNAL_DEQUE_H */ 1695 1696 // Local Variables: 1697 // mode:C++ 1698 // End: 1699