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