1// Deque implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1997 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52/** @file stl_deque.h 53 * This is an internal header file, included by other library headers. 54 * You should not attempt to use it directly. 55 */ 56 57#ifndef _STL_DEQUE_H 58#define _STL_DEQUE_H 1 59 60#include <bits/concept_check.h> 61#include <bits/stl_iterator_base_types.h> 62#include <bits/stl_iterator_base_funcs.h> 63#include <initializer_list> 64 65_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 66 67 /** 68 * @brief This function controls the size of memory nodes. 69 * @param size The size of an element. 70 * @return The number (not byte size) of elements per node. 71 * 72 * This function started off as a compiler kludge from SGI, but 73 * seems to be a useful wrapper around a repeated constant 74 * expression. The @b 512 is tunable (and no other code needs to 75 * change), but no investigation has been done since inheriting the 76 * SGI code. Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what 77 * you are doing, however: changing it breaks the binary 78 * compatibility!! 79 */ 80 81#ifndef _GLIBCXX_DEQUE_BUF_SIZE 82#define _GLIBCXX_DEQUE_BUF_SIZE 512 83#endif 84 85 inline size_t 86 __deque_buf_size(size_t __size) 87 { return (__size < _GLIBCXX_DEQUE_BUF_SIZE 88 ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); } 89 90 91 /** 92 * @brief A deque::iterator. 93 * 94 * Quite a bit of intelligence here. Much of the functionality of 95 * deque is actually passed off to this class. A deque holds two 96 * of these internally, marking its valid range. Access to 97 * elements is done as offsets of either of those two, relying on 98 * operator overloading in this class. 99 * 100 * All the functions are op overloads except for _M_set_node. 101 */ 102 template<typename _Tp, typename _Ref, typename _Ptr> 103 struct _Deque_iterator 104 { 105 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; 106 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 107 108 static size_t _S_buffer_size() 109 { return __deque_buf_size(sizeof(_Tp)); } 110 111 typedef std::random_access_iterator_tag iterator_category; 112 typedef _Tp value_type; 113 typedef _Ptr pointer; 114 typedef _Ref reference; 115 typedef size_t size_type; 116 typedef ptrdiff_t difference_type; 117 typedef _Tp** _Map_pointer; 118 typedef _Deque_iterator _Self; 119 120 _Tp* _M_cur; 121 _Tp* _M_first; 122 _Tp* _M_last; 123 _Map_pointer _M_node; 124 125 _Deque_iterator(_Tp* __x, _Map_pointer __y) 126 : _M_cur(__x), _M_first(*__y), 127 _M_last(*__y + _S_buffer_size()), _M_node(__y) { } 128 129 _Deque_iterator() 130 : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { } 131 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 137 operator*() const 138 { return *_M_cur; } 139 140 pointer 141 operator->() const 142 { return _M_cur; } 143 144 _Self& 145 operator++() 146 { 147 ++_M_cur; 148 if (_M_cur == _M_last) 149 { 150 _M_set_node(_M_node + 1); 151 _M_cur = _M_first; 152 } 153 return *this; 154 } 155 156 _Self 157 operator++(int) 158 { 159 _Self __tmp = *this; 160 ++*this; 161 return __tmp; 162 } 163 164 _Self& 165 operator--() 166 { 167 if (_M_cur == _M_first) 168 { 169 _M_set_node(_M_node - 1); 170 _M_cur = _M_last; 171 } 172 --_M_cur; 173 return *this; 174 } 175 176 _Self 177 operator--(int) 178 { 179 _Self __tmp = *this; 180 --*this; 181 return __tmp; 182 } 183 184 _Self& 185 operator+=(difference_type __n) 186 { 187 const difference_type __offset = __n + (_M_cur - _M_first); 188 if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) 189 _M_cur += __n; 190 else 191 { 192 const difference_type __node_offset = 193 __offset > 0 ? __offset / difference_type(_S_buffer_size()) 194 : -difference_type((-__offset - 1) 195 / _S_buffer_size()) - 1; 196 _M_set_node(_M_node + __node_offset); 197 _M_cur = _M_first + (__offset - __node_offset 198 * difference_type(_S_buffer_size())); 199 } 200 return *this; 201 } 202 203 _Self 204 operator+(difference_type __n) const 205 { 206 _Self __tmp = *this; 207 return __tmp += __n; 208 } 209 210 _Self& 211 operator-=(difference_type __n) 212 { return *this += -__n; } 213 214 _Self 215 operator-(difference_type __n) const 216 { 217 _Self __tmp = *this; 218 return __tmp -= __n; 219 } 220 221 reference 222 operator[](difference_type __n) const 223 { return *(*this + __n); } 224 225 /** 226 * Prepares to traverse new_node. Sets everything except 227 * _M_cur, which should therefore be set by the caller 228 * immediately afterwards, based on _M_first and _M_last. 229 */ 230 void 231 _M_set_node(_Map_pointer __new_node) 232 { 233 _M_node = __new_node; 234 _M_first = *__new_node; 235 _M_last = _M_first + difference_type(_S_buffer_size()); 236 } 237 }; 238 239 // Note: we also provide overloads whose operands are of the same type in 240 // order to avoid ambiguous overload resolution when std::rel_ops operators 241 // are in scope (for additional details, see libstdc++/3628) 242 template<typename _Tp, typename _Ref, typename _Ptr> 243 inline bool 244 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 245 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 246 { return __x._M_cur == __y._M_cur; } 247 248 template<typename _Tp, typename _RefL, typename _PtrL, 249 typename _RefR, typename _PtrR> 250 inline bool 251 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 252 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 253 { return __x._M_cur == __y._M_cur; } 254 255 template<typename _Tp, typename _Ref, typename _Ptr> 256 inline bool 257 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 258 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 259 { return !(__x == __y); } 260 261 template<typename _Tp, typename _RefL, typename _PtrL, 262 typename _RefR, typename _PtrR> 263 inline bool 264 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 265 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 266 { return !(__x == __y); } 267 268 template<typename _Tp, typename _Ref, typename _Ptr> 269 inline bool 270 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 271 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 272 { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) 273 : (__x._M_node < __y._M_node); } 274 275 template<typename _Tp, typename _RefL, typename _PtrL, 276 typename _RefR, typename _PtrR> 277 inline bool 278 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 279 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 280 { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) 281 : (__x._M_node < __y._M_node); } 282 283 template<typename _Tp, typename _Ref, typename _Ptr> 284 inline bool 285 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 286 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 287 { return __y < __x; } 288 289 template<typename _Tp, typename _RefL, typename _PtrL, 290 typename _RefR, typename _PtrR> 291 inline bool 292 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 293 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 294 { return __y < __x; } 295 296 template<typename _Tp, typename _Ref, typename _Ptr> 297 inline bool 298 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 299 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 300 { return !(__y < __x); } 301 302 template<typename _Tp, typename _RefL, typename _PtrL, 303 typename _RefR, typename _PtrR> 304 inline bool 305 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 306 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 307 { return !(__y < __x); } 308 309 template<typename _Tp, typename _Ref, typename _Ptr> 310 inline bool 311 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 312 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 313 { return !(__x < __y); } 314 315 template<typename _Tp, typename _RefL, typename _PtrL, 316 typename _RefR, typename _PtrR> 317 inline bool 318 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 319 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 320 { return !(__x < __y); } 321 322 // _GLIBCXX_RESOLVE_LIB_DEFECTS 323 // According to the resolution of DR179 not only the various comparison 324 // operators but also operator- must accept mixed iterator/const_iterator 325 // parameters. 326 template<typename _Tp, typename _Ref, typename _Ptr> 327 inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type 328 operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 329 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 330 { 331 return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type 332 (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size()) 333 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) 334 + (__y._M_last - __y._M_cur); 335 } 336 337 template<typename _Tp, typename _RefL, typename _PtrL, 338 typename _RefR, typename _PtrR> 339 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type 340 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 341 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 342 { 343 return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type 344 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) 345 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) 346 + (__y._M_last - __y._M_cur); 347 } 348 349 template<typename _Tp, typename _Ref, typename _Ptr> 350 inline _Deque_iterator<_Tp, _Ref, _Ptr> 351 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) 352 { return __x + __n; } 353 354 template<typename _Tp> 355 void 356 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&, 357 const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&); 358 359 template<typename _Tp> 360 _Deque_iterator<_Tp, _Tp&, _Tp*> 361 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, 362 _Deque_iterator<_Tp, const _Tp&, const _Tp*>, 363 _Deque_iterator<_Tp, _Tp&, _Tp*>); 364 365 template<typename _Tp> 366 inline _Deque_iterator<_Tp, _Tp&, _Tp*> 367 copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, 368 _Deque_iterator<_Tp, _Tp&, _Tp*> __last, 369 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 370 { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first), 371 _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last), 372 __result); } 373 374 template<typename _Tp> 375 _Deque_iterator<_Tp, _Tp&, _Tp*> 376 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, 377 _Deque_iterator<_Tp, const _Tp&, const _Tp*>, 378 _Deque_iterator<_Tp, _Tp&, _Tp*>); 379 380 template<typename _Tp> 381 inline _Deque_iterator<_Tp, _Tp&, _Tp*> 382 copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, 383 _Deque_iterator<_Tp, _Tp&, _Tp*> __last, 384 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 385 { return std::copy_backward(_Deque_iterator<_Tp, 386 const _Tp&, const _Tp*>(__first), 387 _Deque_iterator<_Tp, 388 const _Tp&, const _Tp*>(__last), 389 __result); } 390 391#ifdef __GXX_EXPERIMENTAL_CXX0X__ 392 template<typename _Tp> 393 _Deque_iterator<_Tp, _Tp&, _Tp*> 394 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, 395 _Deque_iterator<_Tp, const _Tp&, const _Tp*>, 396 _Deque_iterator<_Tp, _Tp&, _Tp*>); 397 398 template<typename _Tp> 399 inline _Deque_iterator<_Tp, _Tp&, _Tp*> 400 move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, 401 _Deque_iterator<_Tp, _Tp&, _Tp*> __last, 402 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 403 { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first), 404 _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last), 405 __result); } 406 407 template<typename _Tp> 408 _Deque_iterator<_Tp, _Tp&, _Tp*> 409 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, 410 _Deque_iterator<_Tp, const _Tp&, const _Tp*>, 411 _Deque_iterator<_Tp, _Tp&, _Tp*>); 412 413 template<typename _Tp> 414 inline _Deque_iterator<_Tp, _Tp&, _Tp*> 415 move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, 416 _Deque_iterator<_Tp, _Tp&, _Tp*> __last, 417 _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 418 { return std::move_backward(_Deque_iterator<_Tp, 419 const _Tp&, const _Tp*>(__first), 420 _Deque_iterator<_Tp, 421 const _Tp&, const _Tp*>(__last), 422 __result); } 423#endif 424 425 /** 426 * Deque base class. This class provides the unified face for %deque's 427 * allocation. This class's constructor and destructor allocate and 428 * deallocate (but do not initialize) storage. This makes %exception 429 * safety easier. 430 * 431 * Nothing in this class ever constructs or destroys an actual Tp element. 432 * (Deque handles that itself.) Only/All memory management is performed 433 * here. 434 */ 435 template<typename _Tp, typename _Alloc> 436 class _Deque_base 437 { 438 public: 439 typedef _Alloc allocator_type; 440 441 allocator_type 442 get_allocator() const 443 { return allocator_type(_M_get_Tp_allocator()); } 444 445 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; 446 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 447 448 _Deque_base() 449 : _M_impl() 450 { _M_initialize_map(0); } 451 452 _Deque_base(const allocator_type& __a, size_t __num_elements) 453 : _M_impl(__a) 454 { _M_initialize_map(__num_elements); } 455 456 _Deque_base(const allocator_type& __a) 457 : _M_impl(__a) 458 { } 459 460#ifdef __GXX_EXPERIMENTAL_CXX0X__ 461 _Deque_base(_Deque_base&& __x) 462 : _M_impl(__x._M_get_Tp_allocator()) 463 { 464 _M_initialize_map(0); 465 if (__x._M_impl._M_map) 466 { 467 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 468 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 469 std::swap(this->_M_impl._M_map, __x._M_impl._M_map); 470 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); 471 } 472 } 473#endif 474 475 ~_Deque_base(); 476 477 protected: 478 //This struct encapsulates the implementation of the std::deque 479 //standard container and at the same time makes use of the EBO 480 //for empty allocators. 481 typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; 482 483 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 484 485 struct _Deque_impl 486 : public _Tp_alloc_type 487 { 488 _Tp** _M_map; 489 size_t _M_map_size; 490 iterator _M_start; 491 iterator _M_finish; 492 493 _Deque_impl() 494 : _Tp_alloc_type(), _M_map(0), _M_map_size(0), 495 _M_start(), _M_finish() 496 { } 497 498 _Deque_impl(const _Tp_alloc_type& __a) 499 : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), 500 _M_start(), _M_finish() 501 { } 502 }; 503 504 _Tp_alloc_type& 505 _M_get_Tp_allocator() 506 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 507 508 const _Tp_alloc_type& 509 _M_get_Tp_allocator() const 510 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 511 512 _Map_alloc_type 513 _M_get_map_allocator() const 514 { return _Map_alloc_type(_M_get_Tp_allocator()); } 515 516 _Tp* 517 _M_allocate_node() 518 { 519 return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); 520 } 521 522 void 523 _M_deallocate_node(_Tp* __p) 524 { 525 _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); 526 } 527 528 _Tp** 529 _M_allocate_map(size_t __n) 530 { return _M_get_map_allocator().allocate(__n); } 531 532 void 533 _M_deallocate_map(_Tp** __p, size_t __n) 534 { _M_get_map_allocator().deallocate(__p, __n); } 535 536 protected: 537 void _M_initialize_map(size_t); 538 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); 539 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); 540 enum { _S_initial_map_size = 8 }; 541 542 _Deque_impl _M_impl; 543 }; 544 545 template<typename _Tp, typename _Alloc> 546 _Deque_base<_Tp, _Alloc>:: 547 ~_Deque_base() 548 { 549 if (this->_M_impl._M_map) 550 { 551 _M_destroy_nodes(this->_M_impl._M_start._M_node, 552 this->_M_impl._M_finish._M_node + 1); 553 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 554 } 555 } 556 557 /** 558 * @brief Layout storage. 559 * @param num_elements The count of T's for which to allocate space 560 * at first. 561 * @return Nothing. 562 * 563 * The initial underlying memory layout is a bit complicated... 564 */ 565 template<typename _Tp, typename _Alloc> 566 void 567 _Deque_base<_Tp, _Alloc>:: 568 _M_initialize_map(size_t __num_elements) 569 { 570 const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp)) 571 + 1); 572 573 this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size, 574 size_t(__num_nodes + 2)); 575 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size); 576 577 // For "small" maps (needing less than _M_map_size nodes), allocation 578 // starts in the middle elements and grows outwards. So nstart may be 579 // the beginning of _M_map, but for small maps it may be as far in as 580 // _M_map+3. 581 582 _Tp** __nstart = (this->_M_impl._M_map 583 + (this->_M_impl._M_map_size - __num_nodes) / 2); 584 _Tp** __nfinish = __nstart + __num_nodes; 585 586 __try 587 { _M_create_nodes(__nstart, __nfinish); } 588 __catch(...) 589 { 590 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 591 this->_M_impl._M_map = 0; 592 this->_M_impl._M_map_size = 0; 593 __throw_exception_again; 594 } 595 596 this->_M_impl._M_start._M_set_node(__nstart); 597 this->_M_impl._M_finish._M_set_node(__nfinish - 1); 598 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first; 599 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first 600 + __num_elements 601 % __deque_buf_size(sizeof(_Tp))); 602 } 603 604 template<typename _Tp, typename _Alloc> 605 void 606 _Deque_base<_Tp, _Alloc>:: 607 _M_create_nodes(_Tp** __nstart, _Tp** __nfinish) 608 { 609 _Tp** __cur; 610 __try 611 { 612 for (__cur = __nstart; __cur < __nfinish; ++__cur) 613 *__cur = this->_M_allocate_node(); 614 } 615 __catch(...) 616 { 617 _M_destroy_nodes(__nstart, __cur); 618 __throw_exception_again; 619 } 620 } 621 622 template<typename _Tp, typename _Alloc> 623 void 624 _Deque_base<_Tp, _Alloc>:: 625 _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) 626 { 627 for (_Tp** __n = __nstart; __n < __nfinish; ++__n) 628 _M_deallocate_node(*__n); 629 } 630 631 /** 632 * @brief A standard container using fixed-size memory allocation and 633 * constant-time manipulation of elements at either end. 634 * 635 * @ingroup sequences 636 * 637 * Meets the requirements of a <a href="tables.html#65">container</a>, a 638 * <a href="tables.html#66">reversible container</a>, and a 639 * <a href="tables.html#67">sequence</a>, including the 640 * <a href="tables.html#68">optional sequence requirements</a>. 641 * 642 * In previous HP/SGI versions of deque, there was an extra template 643 * parameter so users could control the node size. This extension turned 644 * out to violate the C++ standard (it can be detected using template 645 * template parameters), and it was removed. 646 * 647 * Here's how a deque<Tp> manages memory. Each deque has 4 members: 648 * 649 * - Tp** _M_map 650 * - size_t _M_map_size 651 * - iterator _M_start, _M_finish 652 * 653 * map_size is at least 8. %map is an array of map_size 654 * pointers-to-@anodes. (The name %map has nothing to do with the 655 * std::map class, and @b nodes should not be confused with 656 * std::list's usage of @a node.) 657 * 658 * A @a node has no specific type name as such, but it is referred 659 * to as @a node in this file. It is a simple array-of-Tp. If Tp 660 * is very large, there will be one Tp element per node (i.e., an 661 * @a array of one). For non-huge Tp's, node size is inversely 662 * related to Tp size: the larger the Tp, the fewer Tp's will fit 663 * in a node. The goal here is to keep the total size of a node 664 * relatively small and constant over different Tp's, to improve 665 * allocator efficiency. 666 * 667 * Not every pointer in the %map array will point to a node. If 668 * the initial number of elements in the deque is small, the 669 * /middle/ %map pointers will be valid, and the ones at the edges 670 * will be unused. This same situation will arise as the %map 671 * grows: available %map pointers, if any, will be on the ends. As 672 * new nodes are created, only a subset of the %map's pointers need 673 * to be copied @a outward. 674 * 675 * Class invariants: 676 * - For any nonsingular iterator i: 677 * - i.node points to a member of the %map array. (Yes, you read that 678 * correctly: i.node does not actually point to a node.) The member of 679 * the %map array is what actually points to the node. 680 * - i.first == *(i.node) (This points to the node (first Tp element).) 681 * - i.last == i.first + node_size 682 * - i.cur is a pointer in the range [i.first, i.last). NOTE: 683 * the implication of this is that i.cur is always a dereferenceable 684 * pointer, even if i is a past-the-end iterator. 685 * - Start and Finish are always nonsingular iterators. NOTE: this 686 * means that an empty deque must have one node, a deque with <N 687 * elements (where N is the node buffer size) must have one node, a 688 * deque with N through (2N-1) elements must have two nodes, etc. 689 * - For every node other than start.node and finish.node, every 690 * element in the node is an initialized object. If start.node == 691 * finish.node, then [start.cur, finish.cur) are initialized 692 * objects, and the elements outside that range are uninitialized 693 * storage. Otherwise, [start.cur, start.last) and [finish.first, 694 * finish.cur) are initialized objects, and [start.first, start.cur) 695 * and [finish.cur, finish.last) are uninitialized storage. 696 * - [%map, %map + map_size) is a valid, non-empty range. 697 * - [start.node, finish.node] is a valid range contained within 698 * [%map, %map + map_size). 699 * - A pointer in the range [%map, %map + map_size) points to an allocated 700 * node if and only if the pointer is in the range 701 * [start.node, finish.node]. 702 * 703 * Here's the magic: nothing in deque is @b aware of the discontiguous 704 * storage! 705 * 706 * The memory setup and layout occurs in the parent, _Base, and the iterator 707 * class is entirely responsible for @a leaping from one node to the next. 708 * All the implementation routines for deque itself work only through the 709 * start and finish iterators. This keeps the routines simple and sane, 710 * and we can use other standard algorithms as well. 711 */ 712 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 713 class deque : protected _Deque_base<_Tp, _Alloc> 714 { 715 // concept requirements 716 typedef typename _Alloc::value_type _Alloc_value_type; 717 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 718 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 719 720 typedef _Deque_base<_Tp, _Alloc> _Base; 721 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 722 723 public: 724 typedef _Tp value_type; 725 typedef typename _Tp_alloc_type::pointer pointer; 726 typedef typename _Tp_alloc_type::const_pointer const_pointer; 727 typedef typename _Tp_alloc_type::reference reference; 728 typedef typename _Tp_alloc_type::const_reference const_reference; 729 typedef typename _Base::iterator iterator; 730 typedef typename _Base::const_iterator const_iterator; 731 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 732 typedef std::reverse_iterator<iterator> reverse_iterator; 733 typedef size_t size_type; 734 typedef ptrdiff_t difference_type; 735 typedef _Alloc allocator_type; 736 737 protected: 738 typedef pointer* _Map_pointer; 739 740 static size_t _S_buffer_size() 741 { return __deque_buf_size(sizeof(_Tp)); } 742 743 // Functions controlling memory layout, and nothing else. 744 using _Base::_M_initialize_map; 745 using _Base::_M_create_nodes; 746 using _Base::_M_destroy_nodes; 747 using _Base::_M_allocate_node; 748 using _Base::_M_deallocate_node; 749 using _Base::_M_allocate_map; 750 using _Base::_M_deallocate_map; 751 using _Base::_M_get_Tp_allocator; 752 753 /** 754 * A total of four data members accumulated down the hierarchy. 755 * May be accessed via _M_impl.* 756 */ 757 using _Base::_M_impl; 758 759 public: 760 // [23.2.1.1] construct/copy/destroy 761 // (assign() and get_allocator() are also listed in this section) 762 /** 763 * @brief Default constructor creates no elements. 764 */ 765 deque() 766 : _Base() { } 767 768 /** 769 * @brief Creates a %deque with no elements. 770 * @param a An allocator object. 771 */ 772 explicit 773 deque(const allocator_type& __a) 774 : _Base(__a, 0) { } 775 776 /** 777 * @brief Creates a %deque with copies of an exemplar element. 778 * @param n The number of elements to initially create. 779 * @param value An element to copy. 780 * @param a An allocator. 781 * 782 * This constructor fills the %deque with @a n copies of @a value. 783 */ 784 explicit 785 deque(size_type __n, const value_type& __value = value_type(), 786 const allocator_type& __a = allocator_type()) 787 : _Base(__a, __n) 788 { _M_fill_initialize(__value); } 789 790 /** 791 * @brief %Deque copy constructor. 792 * @param x A %deque of identical element and allocator types. 793 * 794 * The newly-created %deque uses a copy of the allocation object used 795 * by @a x. 796 */ 797 deque(const deque& __x) 798 : _Base(__x._M_get_Tp_allocator(), __x.size()) 799 { std::__uninitialized_copy_a(__x.begin(), __x.end(), 800 this->_M_impl._M_start, 801 _M_get_Tp_allocator()); } 802 803#ifdef __GXX_EXPERIMENTAL_CXX0X__ 804 /** 805 * @brief %Deque move constructor. 806 * @param x A %deque of identical element and allocator types. 807 * 808 * The newly-created %deque contains the exact contents of @a x. 809 * The contents of @a x are a valid, but unspecified %deque. 810 */ 811 deque(deque&& __x) 812 : _Base(std::forward<_Base>(__x)) { } 813 814 /** 815 * @brief Builds a %deque from an initializer list. 816 * @param l An initializer_list. 817 * @param a An allocator object. 818 * 819 * Create a %deque consisting of copies of the elements in the 820 * initializer_list @a l. 821 * 822 * This will call the element type's copy constructor N times 823 * (where N is l.size()) and do no memory reallocation. 824 */ 825 deque(initializer_list<value_type> __l, 826 const allocator_type& __a = allocator_type()) 827 : _Base(__a) 828 { 829 _M_range_initialize(__l.begin(), __l.end(), 830 random_access_iterator_tag()); 831 } 832#endif 833 834 /** 835 * @brief Builds a %deque from a range. 836 * @param first An input iterator. 837 * @param last An input iterator. 838 * @param a An allocator object. 839 * 840 * Create a %deque consisting of copies of the elements from [first, 841 * last). 842 * 843 * If the iterators are forward, bidirectional, or random-access, then 844 * this will call the elements' copy constructor N times (where N is 845 * distance(first,last)) and do no memory reallocation. But if only 846 * input iterators are used, then this will do at most 2N calls to the 847 * copy constructor, and logN memory reallocations. 848 */ 849 template<typename _InputIterator> 850 deque(_InputIterator __first, _InputIterator __last, 851 const allocator_type& __a = allocator_type()) 852 : _Base(__a) 853 { 854 // Check whether it's an integral type. If so, it's not an iterator. 855 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 856 _M_initialize_dispatch(__first, __last, _Integral()); 857 } 858 859 /** 860 * The dtor only erases the elements, and note that if the elements 861 * themselves are pointers, the pointed-to memory is not touched in any 862 * way. Managing the pointer is the user's responsibility. 863 */ 864 ~deque() 865 { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); } 866 867 /** 868 * @brief %Deque assignment operator. 869 * @param x A %deque of identical element and allocator types. 870 * 871 * All the elements of @a x are copied, but unlike the copy constructor, 872 * the allocator object is not copied. 873 */ 874 deque& 875 operator=(const deque& __x); 876 877#ifdef __GXX_EXPERIMENTAL_CXX0X__ 878 /** 879 * @brief %Deque move assignment operator. 880 * @param x A %deque of identical element and allocator types. 881 * 882 * The contents of @a x are moved into this deque (without copying). 883 * @a x is a valid, but unspecified %deque. 884 */ 885 deque& 886 operator=(deque&& __x) 887 { 888 // NB: DR 1204. 889 // NB: DR 675. 890 this->clear(); 891 this->swap(__x); 892 return *this; 893 } 894 895 /** 896 * @brief Assigns an initializer list to a %deque. 897 * @param l An initializer_list. 898 * 899 * This function fills a %deque with copies of the elements in the 900 * initializer_list @a l. 901 * 902 * Note that the assignment completely changes the %deque and that the 903 * resulting %deque's size is the same as the number of elements 904 * assigned. Old data may be lost. 905 */ 906 deque& 907 operator=(initializer_list<value_type> __l) 908 { 909 this->assign(__l.begin(), __l.end()); 910 return *this; 911 } 912#endif 913 914 /** 915 * @brief Assigns a given value to a %deque. 916 * @param n Number of elements to be assigned. 917 * @param val Value to be assigned. 918 * 919 * This function fills a %deque with @a n copies of the given 920 * value. Note that the assignment completely changes the 921 * %deque and that the resulting %deque's size is the same as 922 * the number of elements assigned. Old data may be lost. 923 */ 924 void 925 assign(size_type __n, const value_type& __val) 926 { _M_fill_assign(__n, __val); } 927 928 /** 929 * @brief Assigns a range to a %deque. 930 * @param first An input iterator. 931 * @param last An input iterator. 932 * 933 * This function fills a %deque with copies of the elements in the 934 * range [first,last). 935 * 936 * Note that the assignment completely changes the %deque and that the 937 * resulting %deque's size is the same as the number of elements 938 * assigned. Old data may be lost. 939 */ 940 template<typename _InputIterator> 941 void 942 assign(_InputIterator __first, _InputIterator __last) 943 { 944 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 945 _M_assign_dispatch(__first, __last, _Integral()); 946 } 947 948#ifdef __GXX_EXPERIMENTAL_CXX0X__ 949 /** 950 * @brief Assigns an initializer list to a %deque. 951 * @param l An initializer_list. 952 * 953 * This function fills a %deque with copies of the elements in the 954 * initializer_list @a l. 955 * 956 * Note that the assignment completely changes the %deque and that the 957 * resulting %deque's size is the same as the number of elements 958 * assigned. Old data may be lost. 959 */ 960 void 961 assign(initializer_list<value_type> __l) 962 { this->assign(__l.begin(), __l.end()); } 963#endif 964 965 /// Get a copy of the memory allocation object. 966 allocator_type 967 get_allocator() const 968 { return _Base::get_allocator(); } 969 970 // iterators 971 /** 972 * Returns a read/write iterator that points to the first element in the 973 * %deque. Iteration is done in ordinary element order. 974 */ 975 iterator 976 begin() 977 { return this->_M_impl._M_start; } 978 979 /** 980 * Returns a read-only (constant) iterator that points to the first 981 * element in the %deque. Iteration is done in ordinary element order. 982 */ 983 const_iterator 984 begin() const 985 { return this->_M_impl._M_start; } 986 987 /** 988 * Returns a read/write iterator that points one past the last 989 * element in the %deque. Iteration is done in ordinary 990 * element order. 991 */ 992 iterator 993 end() 994 { return this->_M_impl._M_finish; } 995 996 /** 997 * Returns a read-only (constant) iterator that points one past 998 * the last element in the %deque. Iteration is done in 999 * ordinary element order. 1000 */ 1001 const_iterator 1002 end() const 1003 { return this->_M_impl._M_finish; } 1004 1005 /** 1006 * Returns a read/write reverse iterator that points to the 1007 * last element in the %deque. Iteration is done in reverse 1008 * element order. 1009 */ 1010 reverse_iterator 1011 rbegin() 1012 { return reverse_iterator(this->_M_impl._M_finish); } 1013 1014 /** 1015 * Returns a read-only (constant) reverse iterator that points 1016 * to the last element in the %deque. Iteration is done in 1017 * reverse element order. 1018 */ 1019 const_reverse_iterator 1020 rbegin() const 1021 { return const_reverse_iterator(this->_M_impl._M_finish); } 1022 1023 /** 1024 * Returns a read/write reverse iterator that points to one 1025 * before the first element in the %deque. Iteration is done 1026 * in reverse element order. 1027 */ 1028 reverse_iterator 1029 rend() 1030 { return reverse_iterator(this->_M_impl._M_start); } 1031 1032 /** 1033 * Returns a read-only (constant) reverse iterator that points 1034 * to one before the first element in the %deque. Iteration is 1035 * done in reverse element order. 1036 */ 1037 const_reverse_iterator 1038 rend() const 1039 { return const_reverse_iterator(this->_M_impl._M_start); } 1040 1041#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1042 /** 1043 * Returns a read-only (constant) iterator that points to the first 1044 * element in the %deque. Iteration is done in ordinary element order. 1045 */ 1046 const_iterator 1047 cbegin() const 1048 { return this->_M_impl._M_start; } 1049 1050 /** 1051 * Returns a read-only (constant) iterator that points one past 1052 * the last element in the %deque. Iteration is done in 1053 * ordinary element order. 1054 */ 1055 const_iterator 1056 cend() const 1057 { return this->_M_impl._M_finish; } 1058 1059 /** 1060 * Returns a read-only (constant) reverse iterator that points 1061 * to the last element in the %deque. Iteration is done in 1062 * reverse element order. 1063 */ 1064 const_reverse_iterator 1065 crbegin() const 1066 { return const_reverse_iterator(this->_M_impl._M_finish); } 1067 1068 /** 1069 * Returns a read-only (constant) reverse iterator that points 1070 * to one before the first element in the %deque. Iteration is 1071 * done in reverse element order. 1072 */ 1073 const_reverse_iterator 1074 crend() const 1075 { return const_reverse_iterator(this->_M_impl._M_start); } 1076#endif 1077 1078 // [23.2.1.2] capacity 1079 /** Returns the number of elements in the %deque. */ 1080 size_type 1081 size() const 1082 { return this->_M_impl._M_finish - this->_M_impl._M_start; } 1083 1084 /** Returns the size() of the largest possible %deque. */ 1085 size_type 1086 max_size() const 1087 { return _M_get_Tp_allocator().max_size(); } 1088 1089 /** 1090 * @brief Resizes the %deque to the specified number of elements. 1091 * @param new_size Number of elements the %deque should contain. 1092 * @param x Data with which new elements should be populated. 1093 * 1094 * This function will %resize the %deque to the specified 1095 * number of elements. If the number is smaller than the 1096 * %deque's current size the %deque is truncated, otherwise the 1097 * %deque is extended and new elements are populated with given 1098 * data. 1099 */ 1100 void 1101 resize(size_type __new_size, value_type __x = value_type()) 1102 { 1103 const size_type __len = size(); 1104 if (__new_size < __len) 1105 _M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size)); 1106 else 1107 insert(this->_M_impl._M_finish, __new_size - __len, __x); 1108 } 1109 1110#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1111 /** A non-binding request to reduce memory use. */ 1112 void 1113 shrink_to_fit() 1114 { std::__shrink_to_fit<deque>::_S_do_it(*this); } 1115#endif 1116 1117 /** 1118 * Returns true if the %deque is empty. (Thus begin() would 1119 * equal end().) 1120 */ 1121 bool 1122 empty() const 1123 { return this->_M_impl._M_finish == this->_M_impl._M_start; } 1124 1125 // element access 1126 /** 1127 * @brief Subscript access to the data contained in the %deque. 1128 * @param n The index of the element for which data should be 1129 * accessed. 1130 * @return Read/write reference to data. 1131 * 1132 * This operator allows for easy, array-style, data access. 1133 * Note that data access with this operator is unchecked and 1134 * out_of_range lookups are not defined. (For checked lookups 1135 * see at().) 1136 */ 1137 reference 1138 operator[](size_type __n) 1139 { return this->_M_impl._M_start[difference_type(__n)]; } 1140 1141 /** 1142 * @brief Subscript access to the data contained in the %deque. 1143 * @param n The index of the element for which data should be 1144 * accessed. 1145 * @return Read-only (constant) reference to data. 1146 * 1147 * This operator allows for easy, array-style, data access. 1148 * Note that data access with this operator is unchecked and 1149 * out_of_range lookups are not defined. (For checked lookups 1150 * see at().) 1151 */ 1152 const_reference 1153 operator[](size_type __n) const 1154 { return this->_M_impl._M_start[difference_type(__n)]; } 1155 1156 protected: 1157 /// Safety check used only from at(). 1158 void 1159 _M_range_check(size_type __n) const 1160 { 1161 if (__n >= this->size()) 1162 __throw_out_of_range(__N("deque::_M_range_check")); 1163 } 1164 1165 public: 1166 /** 1167 * @brief Provides access to the data contained in the %deque. 1168 * @param n The index of the element for which data should be 1169 * accessed. 1170 * @return Read/write reference to data. 1171 * @throw std::out_of_range If @a n is an invalid index. 1172 * 1173 * This function provides for safer data access. The parameter 1174 * is first checked that it is in the range of the deque. The 1175 * function throws out_of_range if the check fails. 1176 */ 1177 reference 1178 at(size_type __n) 1179 { 1180 _M_range_check(__n); 1181 return (*this)[__n]; 1182 } 1183 1184 /** 1185 * @brief Provides access to the data contained in the %deque. 1186 * @param n The index of the element for which data should be 1187 * accessed. 1188 * @return Read-only (constant) reference to data. 1189 * @throw std::out_of_range If @a n is an invalid index. 1190 * 1191 * This function provides for safer data access. The parameter is first 1192 * checked that it is in the range of the deque. The function throws 1193 * out_of_range if the check fails. 1194 */ 1195 const_reference 1196 at(size_type __n) const 1197 { 1198 _M_range_check(__n); 1199 return (*this)[__n]; 1200 } 1201 1202 /** 1203 * Returns a read/write reference to the data at the first 1204 * element of the %deque. 1205 */ 1206 reference 1207 front() 1208 { return *begin(); } 1209 1210 /** 1211 * Returns a read-only (constant) reference to the data at the first 1212 * element of the %deque. 1213 */ 1214 const_reference 1215 front() const 1216 { return *begin(); } 1217 1218 /** 1219 * Returns a read/write reference to the data at the last element of the 1220 * %deque. 1221 */ 1222 reference 1223 back() 1224 { 1225 iterator __tmp = end(); 1226 --__tmp; 1227 return *__tmp; 1228 } 1229 1230 /** 1231 * Returns a read-only (constant) reference to the data at the last 1232 * element of the %deque. 1233 */ 1234 const_reference 1235 back() const 1236 { 1237 const_iterator __tmp = end(); 1238 --__tmp; 1239 return *__tmp; 1240 } 1241 1242 // [23.2.1.2] modifiers 1243 /** 1244 * @brief Add data to the front of the %deque. 1245 * @param x Data to be added. 1246 * 1247 * This is a typical stack operation. The function creates an 1248 * element at the front of the %deque and assigns the given 1249 * data to it. Due to the nature of a %deque this operation 1250 * can be done in constant time. 1251 */ 1252 void 1253 push_front(const value_type& __x) 1254 { 1255 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) 1256 { 1257 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x); 1258 --this->_M_impl._M_start._M_cur; 1259 } 1260 else 1261 _M_push_front_aux(__x); 1262 } 1263 1264#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1265 void 1266 push_front(value_type&& __x) 1267 { emplace_front(std::move(__x)); } 1268 1269 template<typename... _Args> 1270 void 1271 emplace_front(_Args&&... __args); 1272#endif 1273 1274 /** 1275 * @brief Add data to the end of the %deque. 1276 * @param x Data to be added. 1277 * 1278 * This is a typical stack operation. The function creates an 1279 * element at the end of the %deque and assigns the given data 1280 * to it. Due to the nature of a %deque this operation can be 1281 * done in constant time. 1282 */ 1283 void 1284 push_back(const value_type& __x) 1285 { 1286 if (this->_M_impl._M_finish._M_cur 1287 != this->_M_impl._M_finish._M_last - 1) 1288 { 1289 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x); 1290 ++this->_M_impl._M_finish._M_cur; 1291 } 1292 else 1293 _M_push_back_aux(__x); 1294 } 1295 1296#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1297 void 1298 push_back(value_type&& __x) 1299 { emplace_back(std::move(__x)); } 1300 1301 template<typename... _Args> 1302 void 1303 emplace_back(_Args&&... __args); 1304#endif 1305 1306 /** 1307 * @brief Removes first element. 1308 * 1309 * This is a typical stack operation. It shrinks the %deque by one. 1310 * 1311 * Note that no data is returned, and if the first element's data is 1312 * needed, it should be retrieved before pop_front() is called. 1313 */ 1314 void 1315 pop_front() 1316 { 1317 if (this->_M_impl._M_start._M_cur 1318 != this->_M_impl._M_start._M_last - 1) 1319 { 1320 this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 1321 ++this->_M_impl._M_start._M_cur; 1322 } 1323 else 1324 _M_pop_front_aux(); 1325 } 1326 1327 /** 1328 * @brief Removes last element. 1329 * 1330 * This is a typical stack operation. It shrinks the %deque by one. 1331 * 1332 * Note that no data is returned, and if the last element's data is 1333 * needed, it should be retrieved before pop_back() is called. 1334 */ 1335 void 1336 pop_back() 1337 { 1338 if (this->_M_impl._M_finish._M_cur 1339 != this->_M_impl._M_finish._M_first) 1340 { 1341 --this->_M_impl._M_finish._M_cur; 1342 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 1343 } 1344 else 1345 _M_pop_back_aux(); 1346 } 1347 1348#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1349 /** 1350 * @brief Inserts an object in %deque before specified iterator. 1351 * @param position An iterator into the %deque. 1352 * @param args Arguments. 1353 * @return An iterator that points to the inserted data. 1354 * 1355 * This function will insert an object of type T constructed 1356 * with T(std::forward<Args>(args)...) before the specified location. 1357 */ 1358 template<typename... _Args> 1359 iterator 1360 emplace(iterator __position, _Args&&... __args); 1361#endif 1362 1363 /** 1364 * @brief Inserts given value into %deque before specified iterator. 1365 * @param position An iterator into the %deque. 1366 * @param x Data to be inserted. 1367 * @return An iterator that points to the inserted data. 1368 * 1369 * This function will insert a copy of the given value before the 1370 * specified location. 1371 */ 1372 iterator 1373 insert(iterator __position, const value_type& __x); 1374 1375#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1376 /** 1377 * @brief Inserts given rvalue into %deque before specified iterator. 1378 * @param position An iterator into the %deque. 1379 * @param x Data to be inserted. 1380 * @return An iterator that points to the inserted data. 1381 * 1382 * This function will insert a copy of the given rvalue before the 1383 * specified location. 1384 */ 1385 iterator 1386 insert(iterator __position, value_type&& __x) 1387 { return emplace(__position, std::move(__x)); } 1388 1389 /** 1390 * @brief Inserts an initializer list into the %deque. 1391 * @param p An iterator into the %deque. 1392 * @param l An initializer_list. 1393 * 1394 * This function will insert copies of the data in the 1395 * initializer_list @a l into the %deque before the location 1396 * specified by @a p. This is known as <em>list insert</em>. 1397 */ 1398 void 1399 insert(iterator __p, initializer_list<value_type> __l) 1400 { this->insert(__p, __l.begin(), __l.end()); } 1401#endif 1402 1403 /** 1404 * @brief Inserts a number of copies of given data into the %deque. 1405 * @param position An iterator into the %deque. 1406 * @param n Number of elements to be inserted. 1407 * @param x Data to be inserted. 1408 * 1409 * This function will insert a specified number of copies of the given 1410 * data before the location specified by @a position. 1411 */ 1412 void 1413 insert(iterator __position, size_type __n, const value_type& __x) 1414 { _M_fill_insert(__position, __n, __x); } 1415 1416 /** 1417 * @brief Inserts a range into the %deque. 1418 * @param position An iterator into the %deque. 1419 * @param first An input iterator. 1420 * @param last An input iterator. 1421 * 1422 * This function will insert copies of the data in the range 1423 * [first,last) into the %deque before the location specified 1424 * by @a pos. This is known as <em>range insert</em>. 1425 */ 1426 template<typename _InputIterator> 1427 void 1428 insert(iterator __position, _InputIterator __first, 1429 _InputIterator __last) 1430 { 1431 // Check whether it's an integral type. If so, it's not an iterator. 1432 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 1433 _M_insert_dispatch(__position, __first, __last, _Integral()); 1434 } 1435 1436 /** 1437 * @brief Remove element at given position. 1438 * @param position Iterator pointing to element to be erased. 1439 * @return An iterator pointing to the next element (or end()). 1440 * 1441 * This function will erase the element at the given position and thus 1442 * shorten the %deque by one. 1443 * 1444 * The user is cautioned that 1445 * this function only erases the element, and that if the element is 1446 * itself a pointer, the pointed-to memory is not touched in any way. 1447 * Managing the pointer is the user's responsibility. 1448 */ 1449 iterator 1450 erase(iterator __position); 1451 1452 /** 1453 * @brief Remove a range of elements. 1454 * @param first Iterator pointing to the first element to be erased. 1455 * @param last Iterator pointing to one past the last element to be 1456 * erased. 1457 * @return An iterator pointing to the element pointed to by @a last 1458 * prior to erasing (or end()). 1459 * 1460 * This function will erase the elements in the range [first,last) and 1461 * shorten the %deque accordingly. 1462 * 1463 * The user is cautioned that 1464 * this function only erases the elements, and that if the elements 1465 * themselves are pointers, the pointed-to memory is not touched in any 1466 * way. Managing the pointer is the user's responsibility. 1467 */ 1468 iterator 1469 erase(iterator __first, iterator __last); 1470 1471 /** 1472 * @brief Swaps data with another %deque. 1473 * @param x A %deque of the same element and allocator types. 1474 * 1475 * This exchanges the elements between two deques in constant time. 1476 * (Four pointers, so it should be quite fast.) 1477 * Note that the global std::swap() function is specialized such that 1478 * std::swap(d1,d2) will feed to this function. 1479 */ 1480 void 1481 swap(deque& __x) 1482 { 1483 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 1484 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 1485 std::swap(this->_M_impl._M_map, __x._M_impl._M_map); 1486 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); 1487 1488 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1489 // 431. Swapping containers with unequal allocators. 1490 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 1491 __x._M_get_Tp_allocator()); 1492 } 1493 1494 /** 1495 * Erases all the elements. Note that this function only erases the 1496 * elements, and that if the elements themselves are pointers, the 1497 * pointed-to memory is not touched in any way. Managing the pointer is 1498 * the user's responsibility. 1499 */ 1500 void 1501 clear() 1502 { _M_erase_at_end(begin()); } 1503 1504 protected: 1505 // Internal constructor functions follow. 1506 1507 // called by the range constructor to implement [23.1.1]/9 1508 1509 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1510 // 438. Ambiguity in the "do the right thing" clause 1511 template<typename _Integer> 1512 void 1513 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 1514 { 1515 _M_initialize_map(static_cast<size_type>(__n)); 1516 _M_fill_initialize(__x); 1517 } 1518 1519 // called by the range constructor to implement [23.1.1]/9 1520 template<typename _InputIterator> 1521 void 1522 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1523 __false_type) 1524 { 1525 typedef typename std::iterator_traits<_InputIterator>:: 1526 iterator_category _IterCategory; 1527 _M_range_initialize(__first, __last, _IterCategory()); 1528 } 1529 1530 // called by the second initialize_dispatch above 1531 //@{ 1532 /** 1533 * @brief Fills the deque with whatever is in [first,last). 1534 * @param first An input iterator. 1535 * @param last An input iterator. 1536 * @return Nothing. 1537 * 1538 * If the iterators are actually forward iterators (or better), then the 1539 * memory layout can be done all at once. Else we move forward using 1540 * push_back on each value from the iterator. 1541 */ 1542 template<typename _InputIterator> 1543 void 1544 _M_range_initialize(_InputIterator __first, _InputIterator __last, 1545 std::input_iterator_tag); 1546 1547 // called by the second initialize_dispatch above 1548 template<typename _ForwardIterator> 1549 void 1550 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 1551 std::forward_iterator_tag); 1552 //@} 1553 1554 /** 1555 * @brief Fills the %deque with copies of value. 1556 * @param value Initial value. 1557 * @return Nothing. 1558 * @pre _M_start and _M_finish have already been initialized, 1559 * but none of the %deque's elements have yet been constructed. 1560 * 1561 * This function is called only when the user provides an explicit size 1562 * (with or without an explicit exemplar value). 1563 */ 1564 void 1565 _M_fill_initialize(const value_type& __value); 1566 1567 // Internal assign functions follow. The *_aux functions do the actual 1568 // assignment work for the range versions. 1569 1570 // called by the range assign to implement [23.1.1]/9 1571 1572 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1573 // 438. Ambiguity in the "do the right thing" clause 1574 template<typename _Integer> 1575 void 1576 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1577 { _M_fill_assign(__n, __val); } 1578 1579 // called by the range assign to implement [23.1.1]/9 1580 template<typename _InputIterator> 1581 void 1582 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1583 __false_type) 1584 { 1585 typedef typename std::iterator_traits<_InputIterator>:: 1586 iterator_category _IterCategory; 1587 _M_assign_aux(__first, __last, _IterCategory()); 1588 } 1589 1590 // called by the second assign_dispatch above 1591 template<typename _InputIterator> 1592 void 1593 _M_assign_aux(_InputIterator __first, _InputIterator __last, 1594 std::input_iterator_tag); 1595 1596 // called by the second assign_dispatch above 1597 template<typename _ForwardIterator> 1598 void 1599 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 1600 std::forward_iterator_tag) 1601 { 1602 const size_type __len = std::distance(__first, __last); 1603 if (__len > size()) 1604 { 1605 _ForwardIterator __mid = __first; 1606 std::advance(__mid, size()); 1607 std::copy(__first, __mid, begin()); 1608 insert(end(), __mid, __last); 1609 } 1610 else 1611 _M_erase_at_end(std::copy(__first, __last, begin())); 1612 } 1613 1614 // Called by assign(n,t), and the range assign when it turns out 1615 // to be the same thing. 1616 void 1617 _M_fill_assign(size_type __n, const value_type& __val) 1618 { 1619 if (__n > size()) 1620 { 1621 std::fill(begin(), end(), __val); 1622 insert(end(), __n - size(), __val); 1623 } 1624 else 1625 { 1626 _M_erase_at_end(begin() + difference_type(__n)); 1627 std::fill(begin(), end(), __val); 1628 } 1629 } 1630 1631 //@{ 1632 /// Helper functions for push_* and pop_*. 1633#ifndef __GXX_EXPERIMENTAL_CXX0X__ 1634 void _M_push_back_aux(const value_type&); 1635 1636 void _M_push_front_aux(const value_type&); 1637#else 1638 template<typename... _Args> 1639 void _M_push_back_aux(_Args&&... __args); 1640 1641 template<typename... _Args> 1642 void _M_push_front_aux(_Args&&... __args); 1643#endif 1644 1645 void _M_pop_back_aux(); 1646 1647 void _M_pop_front_aux(); 1648 //@} 1649 1650 // Internal insert functions follow. The *_aux functions do the actual 1651 // insertion work when all shortcuts fail. 1652 1653 // called by the range insert to implement [23.1.1]/9 1654 1655 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1656 // 438. Ambiguity in the "do the right thing" clause 1657 template<typename _Integer> 1658 void 1659 _M_insert_dispatch(iterator __pos, 1660 _Integer __n, _Integer __x, __true_type) 1661 { _M_fill_insert(__pos, __n, __x); } 1662 1663 // called by the range insert to implement [23.1.1]/9 1664 template<typename _InputIterator> 1665 void 1666 _M_insert_dispatch(iterator __pos, 1667 _InputIterator __first, _InputIterator __last, 1668 __false_type) 1669 { 1670 typedef typename std::iterator_traits<_InputIterator>:: 1671 iterator_category _IterCategory; 1672 _M_range_insert_aux(__pos, __first, __last, _IterCategory()); 1673 } 1674 1675 // called by the second insert_dispatch above 1676 template<typename _InputIterator> 1677 void 1678 _M_range_insert_aux(iterator __pos, _InputIterator __first, 1679 _InputIterator __last, std::input_iterator_tag); 1680 1681 // called by the second insert_dispatch above 1682 template<typename _ForwardIterator> 1683 void 1684 _M_range_insert_aux(iterator __pos, _ForwardIterator __first, 1685 _ForwardIterator __last, std::forward_iterator_tag); 1686 1687 // Called by insert(p,n,x), and the range insert when it turns out to be 1688 // the same thing. Can use fill functions in optimal situations, 1689 // otherwise passes off to insert_aux(p,n,x). 1690 void 1691 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 1692 1693 // called by insert(p,x) 1694#ifndef __GXX_EXPERIMENTAL_CXX0X__ 1695 iterator 1696 _M_insert_aux(iterator __pos, const value_type& __x); 1697#else 1698 template<typename... _Args> 1699 iterator 1700 _M_insert_aux(iterator __pos, _Args&&... __args); 1701#endif 1702 1703 // called by insert(p,n,x) via fill_insert 1704 void 1705 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); 1706 1707 // called by range_insert_aux for forward iterators 1708 template<typename _ForwardIterator> 1709 void 1710 _M_insert_aux(iterator __pos, 1711 _ForwardIterator __first, _ForwardIterator __last, 1712 size_type __n); 1713 1714 1715 // Internal erase functions follow. 1716 1717 void 1718 _M_destroy_data_aux(iterator __first, iterator __last); 1719 1720 // Called by ~deque(). 1721 // NB: Doesn't deallocate the nodes. 1722 template<typename _Alloc1> 1723 void 1724 _M_destroy_data(iterator __first, iterator __last, const _Alloc1&) 1725 { _M_destroy_data_aux(__first, __last); } 1726 1727 void 1728 _M_destroy_data(iterator __first, iterator __last, 1729 const std::allocator<_Tp>&) 1730 { 1731 if (!__has_trivial_destructor(value_type)) 1732 _M_destroy_data_aux(__first, __last); 1733 } 1734 1735 // Called by erase(q1, q2). 1736 void 1737 _M_erase_at_begin(iterator __pos) 1738 { 1739 _M_destroy_data(begin(), __pos, _M_get_Tp_allocator()); 1740 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node); 1741 this->_M_impl._M_start = __pos; 1742 } 1743 1744 // Called by erase(q1, q2), resize(), clear(), _M_assign_aux, 1745 // _M_fill_assign, operator=. 1746 void 1747 _M_erase_at_end(iterator __pos) 1748 { 1749 _M_destroy_data(__pos, end(), _M_get_Tp_allocator()); 1750 _M_destroy_nodes(__pos._M_node + 1, 1751 this->_M_impl._M_finish._M_node + 1); 1752 this->_M_impl._M_finish = __pos; 1753 } 1754 1755 //@{ 1756 /// Memory-handling helpers for the previous internal insert functions. 1757 iterator 1758 _M_reserve_elements_at_front(size_type __n) 1759 { 1760 const size_type __vacancies = this->_M_impl._M_start._M_cur 1761 - this->_M_impl._M_start._M_first; 1762 if (__n > __vacancies) 1763 _M_new_elements_at_front(__n - __vacancies); 1764 return this->_M_impl._M_start - difference_type(__n); 1765 } 1766 1767 iterator 1768 _M_reserve_elements_at_back(size_type __n) 1769 { 1770 const size_type __vacancies = (this->_M_impl._M_finish._M_last 1771 - this->_M_impl._M_finish._M_cur) - 1; 1772 if (__n > __vacancies) 1773 _M_new_elements_at_back(__n - __vacancies); 1774 return this->_M_impl._M_finish + difference_type(__n); 1775 } 1776 1777 void 1778 _M_new_elements_at_front(size_type __new_elements); 1779 1780 void 1781 _M_new_elements_at_back(size_type __new_elements); 1782 //@} 1783 1784 1785 //@{ 1786 /** 1787 * @brief Memory-handling helpers for the major %map. 1788 * 1789 * Makes sure the _M_map has space for new nodes. Does not 1790 * actually add the nodes. Can invalidate _M_map pointers. 1791 * (And consequently, %deque iterators.) 1792 */ 1793 void 1794 _M_reserve_map_at_back(size_type __nodes_to_add = 1) 1795 { 1796 if (__nodes_to_add + 1 > this->_M_impl._M_map_size 1797 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map)) 1798 _M_reallocate_map(__nodes_to_add, false); 1799 } 1800 1801 void 1802 _M_reserve_map_at_front(size_type __nodes_to_add = 1) 1803 { 1804 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node 1805 - this->_M_impl._M_map)) 1806 _M_reallocate_map(__nodes_to_add, true); 1807 } 1808 1809 void 1810 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); 1811 //@} 1812 }; 1813 1814 1815 /** 1816 * @brief Deque equality comparison. 1817 * @param x A %deque. 1818 * @param y A %deque of the same type as @a x. 1819 * @return True iff the size and elements of the deques are equal. 1820 * 1821 * This is an equivalence relation. It is linear in the size of the 1822 * deques. Deques are considered equivalent if their sizes are equal, 1823 * and if corresponding elements compare equal. 1824 */ 1825 template<typename _Tp, typename _Alloc> 1826 inline bool 1827 operator==(const deque<_Tp, _Alloc>& __x, 1828 const deque<_Tp, _Alloc>& __y) 1829 { return __x.size() == __y.size() 1830 && std::equal(__x.begin(), __x.end(), __y.begin()); } 1831 1832 /** 1833 * @brief Deque ordering relation. 1834 * @param x A %deque. 1835 * @param y A %deque of the same type as @a x. 1836 * @return True iff @a x is lexicographically less than @a y. 1837 * 1838 * This is a total ordering relation. It is linear in the size of the 1839 * deques. The elements must be comparable with @c <. 1840 * 1841 * See std::lexicographical_compare() for how the determination is made. 1842 */ 1843 template<typename _Tp, typename _Alloc> 1844 inline bool 1845 operator<(const deque<_Tp, _Alloc>& __x, 1846 const deque<_Tp, _Alloc>& __y) 1847 { return std::lexicographical_compare(__x.begin(), __x.end(), 1848 __y.begin(), __y.end()); } 1849 1850 /// Based on operator== 1851 template<typename _Tp, typename _Alloc> 1852 inline bool 1853 operator!=(const deque<_Tp, _Alloc>& __x, 1854 const deque<_Tp, _Alloc>& __y) 1855 { return !(__x == __y); } 1856 1857 /// Based on operator< 1858 template<typename _Tp, typename _Alloc> 1859 inline bool 1860 operator>(const deque<_Tp, _Alloc>& __x, 1861 const deque<_Tp, _Alloc>& __y) 1862 { return __y < __x; } 1863 1864 /// Based on operator< 1865 template<typename _Tp, typename _Alloc> 1866 inline bool 1867 operator<=(const deque<_Tp, _Alloc>& __x, 1868 const deque<_Tp, _Alloc>& __y) 1869 { return !(__y < __x); } 1870 1871 /// Based on operator< 1872 template<typename _Tp, typename _Alloc> 1873 inline bool 1874 operator>=(const deque<_Tp, _Alloc>& __x, 1875 const deque<_Tp, _Alloc>& __y) 1876 { return !(__x < __y); } 1877 1878 /// See std::deque::swap(). 1879 template<typename _Tp, typename _Alloc> 1880 inline void 1881 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) 1882 { __x.swap(__y); } 1883 1884#undef _GLIBCXX_DEQUE_BUF_SIZE 1885 1886_GLIBCXX_END_NESTED_NAMESPACE 1887 1888#endif /* _STL_DEQUE_H */ 1889