1// List 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) 1996,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_list.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_LIST_H 58#define _STL_LIST_H 1 59 60#include <bits/concept_check.h> 61#include <initializer_list> 62 63_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 64 65 // Supporting structures are split into common and templated types; the 66 // latter publicly inherits from the former in an effort to reduce code 67 // duplication. This results in some "needless" static_cast'ing later on, 68 // but it's all safe downcasting. 69 70 /// Common part of a node in the %list. 71 struct _List_node_base 72 { 73 _List_node_base* _M_next; 74 _List_node_base* _M_prev; 75 76 static void 77 swap(_List_node_base& __x, _List_node_base& __y) throw (); 78 79 void 80 _M_transfer(_List_node_base * const __first, 81 _List_node_base * const __last) throw (); 82 83 void 84 _M_reverse() throw (); 85 86 void 87 _M_hook(_List_node_base * const __position) throw (); 88 89 void 90 _M_unhook() throw (); 91 }; 92 93 /// An actual node in the %list. 94 template<typename _Tp> 95 struct _List_node : public _List_node_base 96 { 97 ///< User's data. 98 _Tp _M_data; 99 100#ifdef __GXX_EXPERIMENTAL_CXX0X__ 101 template<typename... _Args> 102 _List_node(_Args&&... __args) 103 : _List_node_base(), _M_data(std::forward<_Args>(__args)...) { } 104#endif 105 }; 106 107 /** 108 * @brief A list::iterator. 109 * 110 * All the functions are op overloads. 111 */ 112 template<typename _Tp> 113 struct _List_iterator 114 { 115 typedef _List_iterator<_Tp> _Self; 116 typedef _List_node<_Tp> _Node; 117 118 typedef ptrdiff_t difference_type; 119 typedef std::bidirectional_iterator_tag iterator_category; 120 typedef _Tp value_type; 121 typedef _Tp* pointer; 122 typedef _Tp& reference; 123 124 _List_iterator() 125 : _M_node() { } 126 127 explicit 128 _List_iterator(_List_node_base* __x) 129 : _M_node(__x) { } 130 131 // Must downcast from List_node_base to _List_node to get to _M_data. 132 reference 133 operator*() const 134 { return static_cast<_Node*>(_M_node)->_M_data; } 135 136 pointer 137 operator->() const 138 { return &static_cast<_Node*>(_M_node)->_M_data; } 139 140 _Self& 141 operator++() 142 { 143 _M_node = _M_node->_M_next; 144 return *this; 145 } 146 147 _Self 148 operator++(int) 149 { 150 _Self __tmp = *this; 151 _M_node = _M_node->_M_next; 152 return __tmp; 153 } 154 155 _Self& 156 operator--() 157 { 158 _M_node = _M_node->_M_prev; 159 return *this; 160 } 161 162 _Self 163 operator--(int) 164 { 165 _Self __tmp = *this; 166 _M_node = _M_node->_M_prev; 167 return __tmp; 168 } 169 170 bool 171 operator==(const _Self& __x) const 172 { return _M_node == __x._M_node; } 173 174 bool 175 operator!=(const _Self& __x) const 176 { return _M_node != __x._M_node; } 177 178 // The only member points to the %list element. 179 _List_node_base* _M_node; 180 }; 181 182 /** 183 * @brief A list::const_iterator. 184 * 185 * All the functions are op overloads. 186 */ 187 template<typename _Tp> 188 struct _List_const_iterator 189 { 190 typedef _List_const_iterator<_Tp> _Self; 191 typedef const _List_node<_Tp> _Node; 192 typedef _List_iterator<_Tp> iterator; 193 194 typedef ptrdiff_t difference_type; 195 typedef std::bidirectional_iterator_tag iterator_category; 196 typedef _Tp value_type; 197 typedef const _Tp* pointer; 198 typedef const _Tp& reference; 199 200 _List_const_iterator() 201 : _M_node() { } 202 203 explicit 204 _List_const_iterator(const _List_node_base* __x) 205 : _M_node(__x) { } 206 207 _List_const_iterator(const iterator& __x) 208 : _M_node(__x._M_node) { } 209 210 // Must downcast from List_node_base to _List_node to get to 211 // _M_data. 212 reference 213 operator*() const 214 { return static_cast<_Node*>(_M_node)->_M_data; } 215 216 pointer 217 operator->() const 218 { return &static_cast<_Node*>(_M_node)->_M_data; } 219 220 _Self& 221 operator++() 222 { 223 _M_node = _M_node->_M_next; 224 return *this; 225 } 226 227 _Self 228 operator++(int) 229 { 230 _Self __tmp = *this; 231 _M_node = _M_node->_M_next; 232 return __tmp; 233 } 234 235 _Self& 236 operator--() 237 { 238 _M_node = _M_node->_M_prev; 239 return *this; 240 } 241 242 _Self 243 operator--(int) 244 { 245 _Self __tmp = *this; 246 _M_node = _M_node->_M_prev; 247 return __tmp; 248 } 249 250 bool 251 operator==(const _Self& __x) const 252 { return _M_node == __x._M_node; } 253 254 bool 255 operator!=(const _Self& __x) const 256 { return _M_node != __x._M_node; } 257 258 // The only member points to the %list element. 259 const _List_node_base* _M_node; 260 }; 261 262 template<typename _Val> 263 inline bool 264 operator==(const _List_iterator<_Val>& __x, 265 const _List_const_iterator<_Val>& __y) 266 { return __x._M_node == __y._M_node; } 267 268 template<typename _Val> 269 inline bool 270 operator!=(const _List_iterator<_Val>& __x, 271 const _List_const_iterator<_Val>& __y) 272 { return __x._M_node != __y._M_node; } 273 274 275 /// See bits/stl_deque.h's _Deque_base for an explanation. 276 template<typename _Tp, typename _Alloc> 277 class _List_base 278 { 279 protected: 280 // NOTA BENE 281 // The stored instance is not actually of "allocator_type"'s 282 // type. Instead we rebind the type to 283 // Allocator<List_node<Tp>>, which according to [20.1.5]/4 284 // should probably be the same. List_node<Tp> is not the same 285 // size as Tp (it's two pointers larger), and specializations on 286 // Tp may go unused because List_node<Tp> is being bound 287 // instead. 288 // 289 // We put this to the test in the constructors and in 290 // get_allocator, where we use conversions between 291 // allocator_type and _Node_alloc_type. The conversion is 292 // required by table 32 in [20.1.5]. 293 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other 294 _Node_alloc_type; 295 296 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 297 298 struct _List_impl 299 : public _Node_alloc_type 300 { 301 _List_node_base _M_node; 302 303 _List_impl() 304 : _Node_alloc_type(), _M_node() 305 { } 306 307 _List_impl(const _Node_alloc_type& __a) 308 : _Node_alloc_type(__a), _M_node() 309 { } 310 }; 311 312 _List_impl _M_impl; 313 314 _List_node<_Tp>* 315 _M_get_node() 316 { return _M_impl._Node_alloc_type::allocate(1); } 317 318 void 319 _M_put_node(_List_node<_Tp>* __p) 320 { _M_impl._Node_alloc_type::deallocate(__p, 1); } 321 322 public: 323 typedef _Alloc allocator_type; 324 325 _Node_alloc_type& 326 _M_get_Node_allocator() 327 { return *static_cast<_Node_alloc_type*>(&this->_M_impl); } 328 329 const _Node_alloc_type& 330 _M_get_Node_allocator() const 331 { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); } 332 333 _Tp_alloc_type 334 _M_get_Tp_allocator() const 335 { return _Tp_alloc_type(_M_get_Node_allocator()); } 336 337 allocator_type 338 get_allocator() const 339 { return allocator_type(_M_get_Node_allocator()); } 340 341 _List_base() 342 : _M_impl() 343 { _M_init(); } 344 345 _List_base(const allocator_type& __a) 346 : _M_impl(__a) 347 { _M_init(); } 348 349#ifdef __GXX_EXPERIMENTAL_CXX0X__ 350 _List_base(_List_base&& __x) 351 : _M_impl(__x._M_get_Node_allocator()) 352 { 353 _M_init(); 354 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); 355 } 356#endif 357 358 // This is what actually destroys the list. 359 ~_List_base() 360 { _M_clear(); } 361 362 void 363 _M_clear(); 364 365 void 366 _M_init() 367 { 368 this->_M_impl._M_node._M_next = &this->_M_impl._M_node; 369 this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; 370 } 371 }; 372 373 /** 374 * @brief A standard container with linear time access to elements, 375 * and fixed time insertion/deletion at any point in the sequence. 376 * 377 * @ingroup sequences 378 * 379 * Meets the requirements of a <a href="tables.html#65">container</a>, a 380 * <a href="tables.html#66">reversible container</a>, and a 381 * <a href="tables.html#67">sequence</a>, including the 382 * <a href="tables.html#68">optional sequence requirements</a> with the 383 * %exception of @c at and @c operator[]. 384 * 385 * This is a @e doubly @e linked %list. Traversal up and down the 386 * %list requires linear time, but adding and removing elements (or 387 * @e nodes) is done in constant time, regardless of where the 388 * change takes place. Unlike std::vector and std::deque, 389 * random-access iterators are not provided, so subscripting ( @c 390 * [] ) access is not allowed. For algorithms which only need 391 * sequential access, this lack makes no difference. 392 * 393 * Also unlike the other standard containers, std::list provides 394 * specialized algorithms %unique to linked lists, such as 395 * splicing, sorting, and in-place reversal. 396 * 397 * A couple points on memory allocation for list<Tp>: 398 * 399 * First, we never actually allocate a Tp, we allocate 400 * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure 401 * that after elements from %list<X,Alloc1> are spliced into 402 * %list<X,Alloc2>, destroying the memory of the second %list is a 403 * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away. 404 * 405 * Second, a %list conceptually represented as 406 * @code 407 * A <---> B <---> C <---> D 408 * @endcode 409 * is actually circular; a link exists between A and D. The %list 410 * class holds (as its only data member) a private list::iterator 411 * pointing to @e D, not to @e A! To get to the head of the %list, 412 * we start at the tail and move forward by one. When this member 413 * iterator's next/previous pointers refer to itself, the %list is 414 * %empty. 415 */ 416 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 417 class list : protected _List_base<_Tp, _Alloc> 418 { 419 // concept requirements 420 typedef typename _Alloc::value_type _Alloc_value_type; 421 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 422 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 423 424 typedef _List_base<_Tp, _Alloc> _Base; 425 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 426 427 public: 428 typedef _Tp value_type; 429 typedef typename _Tp_alloc_type::pointer pointer; 430 typedef typename _Tp_alloc_type::const_pointer const_pointer; 431 typedef typename _Tp_alloc_type::reference reference; 432 typedef typename _Tp_alloc_type::const_reference const_reference; 433 typedef _List_iterator<_Tp> iterator; 434 typedef _List_const_iterator<_Tp> const_iterator; 435 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 436 typedef std::reverse_iterator<iterator> reverse_iterator; 437 typedef size_t size_type; 438 typedef ptrdiff_t difference_type; 439 typedef _Alloc allocator_type; 440 441 protected: 442 // Note that pointers-to-_Node's can be ctor-converted to 443 // iterator types. 444 typedef _List_node<_Tp> _Node; 445 446 using _Base::_M_impl; 447 using _Base::_M_put_node; 448 using _Base::_M_get_node; 449 using _Base::_M_get_Tp_allocator; 450 using _Base::_M_get_Node_allocator; 451 452 /** 453 * @param x An instance of user data. 454 * 455 * Allocates space for a new node and constructs a copy of @a x in it. 456 */ 457#ifndef __GXX_EXPERIMENTAL_CXX0X__ 458 _Node* 459 _M_create_node(const value_type& __x) 460 { 461 _Node* __p = this->_M_get_node(); 462 __try 463 { 464 _M_get_Tp_allocator().construct(&__p->_M_data, __x); 465 } 466 __catch(...) 467 { 468 _M_put_node(__p); 469 __throw_exception_again; 470 } 471 return __p; 472 } 473#else 474 template<typename... _Args> 475 _Node* 476 _M_create_node(_Args&&... __args) 477 { 478 _Node* __p = this->_M_get_node(); 479 __try 480 { 481 _M_get_Node_allocator().construct(__p, 482 std::forward<_Args>(__args)...); 483 } 484 __catch(...) 485 { 486 _M_put_node(__p); 487 __throw_exception_again; 488 } 489 return __p; 490 } 491#endif 492 493 public: 494 // [23.2.2.1] construct/copy/destroy 495 // (assign() and get_allocator() are also listed in this section) 496 /** 497 * @brief Default constructor creates no elements. 498 */ 499 list() 500 : _Base() { } 501 502 /** 503 * @brief Creates a %list with no elements. 504 * @param a An allocator object. 505 */ 506 explicit 507 list(const allocator_type& __a) 508 : _Base(__a) { } 509 510 /** 511 * @brief Creates a %list with copies of an exemplar element. 512 * @param n The number of elements to initially create. 513 * @param value An element to copy. 514 * @param a An allocator object. 515 * 516 * This constructor fills the %list with @a n copies of @a value. 517 */ 518 explicit 519 list(size_type __n, const value_type& __value = value_type(), 520 const allocator_type& __a = allocator_type()) 521 : _Base(__a) 522 { _M_fill_initialize(__n, __value); } 523 524 /** 525 * @brief %List copy constructor. 526 * @param x A %list of identical element and allocator types. 527 * 528 * The newly-created %list uses a copy of the allocation object used 529 * by @a x. 530 */ 531 list(const list& __x) 532 : _Base(__x._M_get_Node_allocator()) 533 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } 534 535#ifdef __GXX_EXPERIMENTAL_CXX0X__ 536 /** 537 * @brief %List move constructor. 538 * @param x A %list of identical element and allocator types. 539 * 540 * The newly-created %list contains the exact contents of @a x. 541 * The contents of @a x are a valid, but unspecified %list. 542 */ 543 list(list&& __x) 544 : _Base(std::forward<_Base>(__x)) { } 545 546 /** 547 * @brief Builds a %list from an initializer_list 548 * @param l An initializer_list of value_type. 549 * @param a An allocator object. 550 * 551 * Create a %list consisting of copies of the elements in the 552 * initializer_list @a l. This is linear in l.size(). 553 */ 554 list(initializer_list<value_type> __l, 555 const allocator_type& __a = allocator_type()) 556 : _Base(__a) 557 { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); } 558#endif 559 560 /** 561 * @brief Builds a %list from a range. 562 * @param first An input iterator. 563 * @param last An input iterator. 564 * @param a An allocator object. 565 * 566 * Create a %list consisting of copies of the elements from 567 * [@a first,@a last). This is linear in N (where N is 568 * distance(@a first,@a last)). 569 */ 570 template<typename _InputIterator> 571 list(_InputIterator __first, _InputIterator __last, 572 const allocator_type& __a = allocator_type()) 573 : _Base(__a) 574 { 575 // Check whether it's an integral type. If so, it's not an iterator. 576 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 577 _M_initialize_dispatch(__first, __last, _Integral()); 578 } 579 580 /** 581 * No explicit dtor needed as the _Base dtor takes care of 582 * things. The _Base dtor only erases the elements, and note 583 * that if the elements themselves are pointers, the pointed-to 584 * memory is not touched in any way. Managing the pointer is 585 * the user's responsibility. 586 */ 587 588 /** 589 * @brief %List assignment operator. 590 * @param x A %list of identical element and allocator types. 591 * 592 * All the elements of @a x are copied, but unlike the copy 593 * constructor, the allocator object is not copied. 594 */ 595 list& 596 operator=(const list& __x); 597 598#ifdef __GXX_EXPERIMENTAL_CXX0X__ 599 /** 600 * @brief %List move assignment operator. 601 * @param x A %list of identical element and allocator types. 602 * 603 * The contents of @a x are moved into this %list (without copying). 604 * @a x is a valid, but unspecified %list 605 */ 606 list& 607 operator=(list&& __x) 608 { 609 // NB: DR 1204. 610 // NB: DR 675. 611 this->clear(); 612 this->swap(__x); 613 return *this; 614 } 615 616 /** 617 * @brief %List initializer list assignment operator. 618 * @param l An initializer_list of value_type. 619 * 620 * Replace the contents of the %list with copies of the elements 621 * in the initializer_list @a l. This is linear in l.size(). 622 */ 623 list& 624 operator=(initializer_list<value_type> __l) 625 { 626 this->assign(__l.begin(), __l.end()); 627 return *this; 628 } 629#endif 630 631 /** 632 * @brief Assigns a given value to a %list. 633 * @param n Number of elements to be assigned. 634 * @param val Value to be assigned. 635 * 636 * This function fills a %list with @a n copies of the given 637 * value. Note that the assignment completely changes the %list 638 * and that the resulting %list's size is the same as the number 639 * of elements assigned. Old data may be lost. 640 */ 641 void 642 assign(size_type __n, const value_type& __val) 643 { _M_fill_assign(__n, __val); } 644 645 /** 646 * @brief Assigns a range to a %list. 647 * @param first An input iterator. 648 * @param last An input iterator. 649 * 650 * This function fills a %list with copies of the elements in the 651 * range [@a first,@a last). 652 * 653 * Note that the assignment completely changes the %list and 654 * that the resulting %list's size is the same as the number of 655 * elements assigned. Old data may be lost. 656 */ 657 template<typename _InputIterator> 658 void 659 assign(_InputIterator __first, _InputIterator __last) 660 { 661 // Check whether it's an integral type. If so, it's not an iterator. 662 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 663 _M_assign_dispatch(__first, __last, _Integral()); 664 } 665 666#ifdef __GXX_EXPERIMENTAL_CXX0X__ 667 /** 668 * @brief Assigns an initializer_list to a %list. 669 * @param l An initializer_list of value_type. 670 * 671 * Replace the contents of the %list with copies of the elements 672 * in the initializer_list @a l. This is linear in l.size(). 673 */ 674 void 675 assign(initializer_list<value_type> __l) 676 { this->assign(__l.begin(), __l.end()); } 677#endif 678 679 /// Get a copy of the memory allocation object. 680 allocator_type 681 get_allocator() const 682 { return _Base::get_allocator(); } 683 684 // iterators 685 /** 686 * Returns a read/write iterator that points to the first element in the 687 * %list. Iteration is done in ordinary element order. 688 */ 689 iterator 690 begin() 691 { return iterator(this->_M_impl._M_node._M_next); } 692 693 /** 694 * Returns a read-only (constant) iterator that points to the 695 * first element in the %list. Iteration is done in ordinary 696 * element order. 697 */ 698 const_iterator 699 begin() const 700 { return const_iterator(this->_M_impl._M_node._M_next); } 701 702 /** 703 * Returns a read/write iterator that points one past the last 704 * element in the %list. Iteration is done in ordinary element 705 * order. 706 */ 707 iterator 708 end() 709 { return iterator(&this->_M_impl._M_node); } 710 711 /** 712 * Returns a read-only (constant) iterator that points one past 713 * the last element in the %list. Iteration is done in ordinary 714 * element order. 715 */ 716 const_iterator 717 end() const 718 { return const_iterator(&this->_M_impl._M_node); } 719 720 /** 721 * Returns a read/write reverse iterator that points to the last 722 * element in the %list. Iteration is done in reverse element 723 * order. 724 */ 725 reverse_iterator 726 rbegin() 727 { return reverse_iterator(end()); } 728 729 /** 730 * Returns a read-only (constant) reverse iterator that points to 731 * the last element in the %list. Iteration is done in reverse 732 * element order. 733 */ 734 const_reverse_iterator 735 rbegin() const 736 { return const_reverse_iterator(end()); } 737 738 /** 739 * Returns a read/write reverse iterator that points to one 740 * before the first element in the %list. Iteration is done in 741 * reverse element order. 742 */ 743 reverse_iterator 744 rend() 745 { return reverse_iterator(begin()); } 746 747 /** 748 * Returns a read-only (constant) reverse iterator that points to one 749 * before the first element in the %list. Iteration is done in reverse 750 * element order. 751 */ 752 const_reverse_iterator 753 rend() const 754 { return const_reverse_iterator(begin()); } 755 756#ifdef __GXX_EXPERIMENTAL_CXX0X__ 757 /** 758 * Returns a read-only (constant) iterator that points to the 759 * first element in the %list. Iteration is done in ordinary 760 * element order. 761 */ 762 const_iterator 763 cbegin() const 764 { return const_iterator(this->_M_impl._M_node._M_next); } 765 766 /** 767 * Returns a read-only (constant) iterator that points one past 768 * the last element in the %list. Iteration is done in ordinary 769 * element order. 770 */ 771 const_iterator 772 cend() const 773 { return const_iterator(&this->_M_impl._M_node); } 774 775 /** 776 * Returns a read-only (constant) reverse iterator that points to 777 * the last element in the %list. Iteration is done in reverse 778 * element order. 779 */ 780 const_reverse_iterator 781 crbegin() const 782 { return const_reverse_iterator(end()); } 783 784 /** 785 * Returns a read-only (constant) reverse iterator that points to one 786 * before the first element in the %list. Iteration is done in reverse 787 * element order. 788 */ 789 const_reverse_iterator 790 crend() const 791 { return const_reverse_iterator(begin()); } 792#endif 793 794 // [23.2.2.2] capacity 795 /** 796 * Returns true if the %list is empty. (Thus begin() would equal 797 * end().) 798 */ 799 bool 800 empty() const 801 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } 802 803 /** Returns the number of elements in the %list. */ 804 size_type 805 size() const 806 { return std::distance(begin(), end()); } 807 808 /** Returns the size() of the largest possible %list. */ 809 size_type 810 max_size() const 811 { return _M_get_Node_allocator().max_size(); } 812 813 /** 814 * @brief Resizes the %list to the specified number of elements. 815 * @param new_size Number of elements the %list should contain. 816 * @param x Data with which new elements should be populated. 817 * 818 * This function will %resize the %list to the specified number 819 * of elements. If the number is smaller than the %list's 820 * current size the %list is truncated, otherwise the %list is 821 * extended and new elements are populated with given data. 822 */ 823 void 824 resize(size_type __new_size, value_type __x = value_type()); 825 826 // element access 827 /** 828 * Returns a read/write reference to the data at the first 829 * element of the %list. 830 */ 831 reference 832 front() 833 { return *begin(); } 834 835 /** 836 * Returns a read-only (constant) reference to the data at the first 837 * element of the %list. 838 */ 839 const_reference 840 front() const 841 { return *begin(); } 842 843 /** 844 * Returns a read/write reference to the data at the last element 845 * of the %list. 846 */ 847 reference 848 back() 849 { 850 iterator __tmp = end(); 851 --__tmp; 852 return *__tmp; 853 } 854 855 /** 856 * Returns a read-only (constant) reference to the data at the last 857 * element of the %list. 858 */ 859 const_reference 860 back() const 861 { 862 const_iterator __tmp = end(); 863 --__tmp; 864 return *__tmp; 865 } 866 867 // [23.2.2.3] modifiers 868 /** 869 * @brief Add data to the front of the %list. 870 * @param x Data to be added. 871 * 872 * This is a typical stack operation. The function creates an 873 * element at the front of the %list and assigns the given data 874 * to it. Due to the nature of a %list this operation can be 875 * done in constant time, and does not invalidate iterators and 876 * references. 877 */ 878 void 879 push_front(const value_type& __x) 880 { this->_M_insert(begin(), __x); } 881 882#ifdef __GXX_EXPERIMENTAL_CXX0X__ 883 void 884 push_front(value_type&& __x) 885 { this->_M_insert(begin(), std::move(__x)); } 886 887 template<typename... _Args> 888 void 889 emplace_front(_Args&&... __args) 890 { this->_M_insert(begin(), std::forward<_Args>(__args)...); } 891#endif 892 893 /** 894 * @brief Removes first element. 895 * 896 * This is a typical stack operation. It shrinks the %list by 897 * one. Due to the nature of a %list this operation can be done 898 * in constant time, and only invalidates iterators/references to 899 * the element being removed. 900 * 901 * Note that no data is returned, and if the first element's data 902 * is needed, it should be retrieved before pop_front() is 903 * called. 904 */ 905 void 906 pop_front() 907 { this->_M_erase(begin()); } 908 909 /** 910 * @brief Add data to the end of the %list. 911 * @param x Data to be added. 912 * 913 * This is a typical stack operation. The function creates an 914 * element at the end of the %list and assigns the given data to 915 * it. Due to the nature of a %list this operation can be done 916 * in constant time, and does not invalidate iterators and 917 * references. 918 */ 919 void 920 push_back(const value_type& __x) 921 { this->_M_insert(end(), __x); } 922 923#ifdef __GXX_EXPERIMENTAL_CXX0X__ 924 void 925 push_back(value_type&& __x) 926 { this->_M_insert(end(), std::move(__x)); } 927 928 template<typename... _Args> 929 void 930 emplace_back(_Args&&... __args) 931 { this->_M_insert(end(), std::forward<_Args>(__args)...); } 932#endif 933 934 /** 935 * @brief Removes last element. 936 * 937 * This is a typical stack operation. It shrinks the %list by 938 * one. Due to the nature of a %list this operation can be done 939 * in constant time, and only invalidates iterators/references to 940 * the element being removed. 941 * 942 * Note that no data is returned, and if the last element's data 943 * is needed, it should be retrieved before pop_back() is called. 944 */ 945 void 946 pop_back() 947 { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } 948 949#ifdef __GXX_EXPERIMENTAL_CXX0X__ 950 /** 951 * @brief Constructs object in %list before specified iterator. 952 * @param position A const_iterator into the %list. 953 * @param args Arguments. 954 * @return An iterator that points to the inserted data. 955 * 956 * This function will insert an object of type T constructed 957 * with T(std::forward<Args>(args)...) before the specified 958 * location. Due to the nature of a %list this operation can 959 * be done in constant time, and does not invalidate iterators 960 * and references. 961 */ 962 template<typename... _Args> 963 iterator 964 emplace(iterator __position, _Args&&... __args); 965#endif 966 967 /** 968 * @brief Inserts given value into %list before specified iterator. 969 * @param position An iterator into the %list. 970 * @param x Data to be inserted. 971 * @return An iterator that points to the inserted data. 972 * 973 * This function will insert a copy of the given value before 974 * the specified location. Due to the nature of a %list this 975 * operation can be done in constant time, and does not 976 * invalidate iterators and references. 977 */ 978 iterator 979 insert(iterator __position, const value_type& __x); 980 981#ifdef __GXX_EXPERIMENTAL_CXX0X__ 982 /** 983 * @brief Inserts given rvalue into %list before specified iterator. 984 * @param position An iterator into the %list. 985 * @param x Data to be inserted. 986 * @return An iterator that points to the inserted data. 987 * 988 * This function will insert a copy of the given rvalue before 989 * the specified location. Due to the nature of a %list this 990 * operation can be done in constant time, and does not 991 * invalidate iterators and references. 992 */ 993 iterator 994 insert(iterator __position, value_type&& __x) 995 { return emplace(__position, std::move(__x)); } 996 997 /** 998 * @brief Inserts the contents of an initializer_list into %list 999 * before specified iterator. 1000 * @param p An iterator into the %list. 1001 * @param l An initializer_list of value_type. 1002 * 1003 * This function will insert copies of the data in the 1004 * initializer_list @a l into the %list before the location 1005 * specified by @a p. 1006 * 1007 * This operation is linear in the number of elements inserted and 1008 * does not invalidate iterators and references. 1009 */ 1010 void 1011 insert(iterator __p, initializer_list<value_type> __l) 1012 { this->insert(__p, __l.begin(), __l.end()); } 1013#endif 1014 1015 /** 1016 * @brief Inserts a number of copies of given data into the %list. 1017 * @param position An iterator into the %list. 1018 * @param n Number of elements to be inserted. 1019 * @param x Data to be inserted. 1020 * 1021 * This function will insert a specified number of copies of the 1022 * given data before the location specified by @a position. 1023 * 1024 * This operation is linear in the number of elements inserted and 1025 * does not invalidate iterators and references. 1026 */ 1027 void 1028 insert(iterator __position, size_type __n, const value_type& __x) 1029 { 1030 list __tmp(__n, __x, _M_get_Node_allocator()); 1031 splice(__position, __tmp); 1032 } 1033 1034 /** 1035 * @brief Inserts a range into the %list. 1036 * @param position An iterator into the %list. 1037 * @param first An input iterator. 1038 * @param last An input iterator. 1039 * 1040 * This function will insert copies of the data in the range [@a 1041 * first,@a last) into the %list before the location specified by 1042 * @a position. 1043 * 1044 * This operation is linear in the number of elements inserted and 1045 * does not invalidate iterators and references. 1046 */ 1047 template<typename _InputIterator> 1048 void 1049 insert(iterator __position, _InputIterator __first, 1050 _InputIterator __last) 1051 { 1052 list __tmp(__first, __last, _M_get_Node_allocator()); 1053 splice(__position, __tmp); 1054 } 1055 1056 /** 1057 * @brief Remove element at given position. 1058 * @param position Iterator pointing to element to be erased. 1059 * @return An iterator pointing to the next element (or end()). 1060 * 1061 * This function will erase the element at the given position and thus 1062 * shorten the %list by one. 1063 * 1064 * Due to the nature of a %list this operation can be done in 1065 * constant time, and only invalidates iterators/references to 1066 * the element being removed. The user is also cautioned that 1067 * this function only erases the element, and that if the element 1068 * is itself a pointer, the pointed-to memory is not touched in 1069 * any way. Managing the pointer is the user's responsibility. 1070 */ 1071 iterator 1072 erase(iterator __position); 1073 1074 /** 1075 * @brief Remove a range of elements. 1076 * @param first Iterator pointing to the first element to be erased. 1077 * @param last Iterator pointing to one past the last element to be 1078 * erased. 1079 * @return An iterator pointing to the element pointed to by @a last 1080 * prior to erasing (or end()). 1081 * 1082 * This function will erase the elements in the range @a 1083 * [first,last) and shorten the %list accordingly. 1084 * 1085 * This operation is linear time in the size of the range and only 1086 * invalidates iterators/references to the element being removed. 1087 * The user is also cautioned that this function only erases the 1088 * elements, and that if the elements themselves are pointers, the 1089 * pointed-to memory is not touched in any way. Managing the pointer 1090 * is the user's responsibility. 1091 */ 1092 iterator 1093 erase(iterator __first, iterator __last) 1094 { 1095 while (__first != __last) 1096 __first = erase(__first); 1097 return __last; 1098 } 1099 1100 /** 1101 * @brief Swaps data with another %list. 1102 * @param x A %list of the same element and allocator types. 1103 * 1104 * This exchanges the elements between two lists in constant 1105 * time. Note that the global std::swap() function is 1106 * specialized such that std::swap(l1,l2) will feed to this 1107 * function. 1108 */ 1109 void 1110 swap(list& __x) 1111 { 1112 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); 1113 1114 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1115 // 431. Swapping containers with unequal allocators. 1116 std::__alloc_swap<typename _Base::_Node_alloc_type>:: 1117 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()); 1118 } 1119 1120 /** 1121 * Erases all the elements. Note that this function only erases 1122 * the elements, and that if the elements themselves are 1123 * pointers, the pointed-to memory is not touched in any way. 1124 * Managing the pointer is the user's responsibility. 1125 */ 1126 void 1127 clear() 1128 { 1129 _Base::_M_clear(); 1130 _Base::_M_init(); 1131 } 1132 1133 // [23.2.2.4] list operations 1134 /** 1135 * @brief Insert contents of another %list. 1136 * @param position Iterator referencing the element to insert before. 1137 * @param x Source list. 1138 * 1139 * The elements of @a x are inserted in constant time in front of 1140 * the element referenced by @a position. @a x becomes an empty 1141 * list. 1142 * 1143 * Requires this != @a x. 1144 */ 1145 void 1146#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1147 splice(iterator __position, list&& __x) 1148#else 1149 splice(iterator __position, list& __x) 1150#endif 1151 { 1152 if (!__x.empty()) 1153 { 1154 _M_check_equal_allocators(__x); 1155 1156 this->_M_transfer(__position, __x.begin(), __x.end()); 1157 } 1158 } 1159 1160#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1161 void 1162 splice(iterator __position, list& __x) 1163 { splice(__position, std::move(__x)); } 1164#endif 1165 1166 /** 1167 * @brief Insert element from another %list. 1168 * @param position Iterator referencing the element to insert before. 1169 * @param x Source list. 1170 * @param i Iterator referencing the element to move. 1171 * 1172 * Removes the element in list @a x referenced by @a i and 1173 * inserts it into the current list before @a position. 1174 */ 1175 void 1176#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1177 splice(iterator __position, list&& __x, iterator __i) 1178#else 1179 splice(iterator __position, list& __x, iterator __i) 1180#endif 1181 { 1182 iterator __j = __i; 1183 ++__j; 1184 if (__position == __i || __position == __j) 1185 return; 1186 1187 if (this != &__x) 1188 _M_check_equal_allocators(__x); 1189 1190 this->_M_transfer(__position, __i, __j); 1191 } 1192 1193#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1194 void 1195 splice(iterator __position, list& __x, iterator __i) 1196 { splice(__position, std::move(__x), __i); } 1197#endif 1198 1199 /** 1200 * @brief Insert range from another %list. 1201 * @param position Iterator referencing the element to insert before. 1202 * @param x Source list. 1203 * @param first Iterator referencing the start of range in x. 1204 * @param last Iterator referencing the end of range in x. 1205 * 1206 * Removes elements in the range [first,last) and inserts them 1207 * before @a position in constant time. 1208 * 1209 * Undefined if @a position is in [first,last). 1210 */ 1211 void 1212#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1213 splice(iterator __position, list&& __x, iterator __first, 1214 iterator __last) 1215#else 1216 splice(iterator __position, list& __x, iterator __first, 1217 iterator __last) 1218#endif 1219 { 1220 if (__first != __last) 1221 { 1222 if (this != &__x) 1223 _M_check_equal_allocators(__x); 1224 1225 this->_M_transfer(__position, __first, __last); 1226 } 1227 } 1228 1229#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1230 void 1231 splice(iterator __position, list& __x, iterator __first, iterator __last) 1232 { splice(__position, std::move(__x), __first, __last); } 1233#endif 1234 1235 /** 1236 * @brief Remove all elements equal to value. 1237 * @param value The value to remove. 1238 * 1239 * Removes every element in the list equal to @a value. 1240 * Remaining elements stay in list order. Note that this 1241 * function only erases the elements, and that if the elements 1242 * themselves are pointers, the pointed-to memory is not 1243 * touched in any way. Managing the pointer is the user's 1244 * responsibility. 1245 */ 1246 void 1247 remove(const _Tp& __value); 1248 1249 /** 1250 * @brief Remove all elements satisfying a predicate. 1251 * @param Predicate Unary predicate function or object. 1252 * 1253 * Removes every element in the list for which the predicate 1254 * returns true. Remaining elements stay in list order. Note 1255 * that this function only erases the elements, and that if the 1256 * elements themselves are pointers, the pointed-to memory is 1257 * not touched in any way. Managing the pointer is the user's 1258 * responsibility. 1259 */ 1260 template<typename _Predicate> 1261 void 1262 remove_if(_Predicate); 1263 1264 /** 1265 * @brief Remove consecutive duplicate elements. 1266 * 1267 * For each consecutive set of elements with the same value, 1268 * remove all but the first one. Remaining elements stay in 1269 * list order. Note that this function only erases the 1270 * elements, and that if the elements themselves are pointers, 1271 * the pointed-to memory is not touched in any way. Managing 1272 * the pointer is the user's responsibility. 1273 */ 1274 void 1275 unique(); 1276 1277 /** 1278 * @brief Remove consecutive elements satisfying a predicate. 1279 * @param BinaryPredicate Binary predicate function or object. 1280 * 1281 * For each consecutive set of elements [first,last) that 1282 * satisfy predicate(first,i) where i is an iterator in 1283 * [first,last), remove all but the first one. Remaining 1284 * elements stay in list order. Note that this function only 1285 * erases the elements, and that if the elements themselves are 1286 * pointers, the pointed-to memory is not touched in any way. 1287 * Managing the pointer is the user's responsibility. 1288 */ 1289 template<typename _BinaryPredicate> 1290 void 1291 unique(_BinaryPredicate); 1292 1293 /** 1294 * @brief Merge sorted lists. 1295 * @param x Sorted list to merge. 1296 * 1297 * Assumes that both @a x and this list are sorted according to 1298 * operator<(). Merges elements of @a x into this list in 1299 * sorted order, leaving @a x empty when complete. Elements in 1300 * this list precede elements in @a x that are equal. 1301 */ 1302#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1303 void 1304 merge(list&& __x); 1305 1306 void 1307 merge(list& __x) 1308 { merge(std::move(__x)); } 1309#else 1310 void 1311 merge(list& __x); 1312#endif 1313 1314 /** 1315 * @brief Merge sorted lists according to comparison function. 1316 * @param x Sorted list to merge. 1317 * @param StrictWeakOrdering Comparison function defining 1318 * sort order. 1319 * 1320 * Assumes that both @a x and this list are sorted according to 1321 * StrictWeakOrdering. Merges elements of @a x into this list 1322 * in sorted order, leaving @a x empty when complete. Elements 1323 * in this list precede elements in @a x that are equivalent 1324 * according to StrictWeakOrdering(). 1325 */ 1326#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1327 template<typename _StrictWeakOrdering> 1328 void 1329 merge(list&&, _StrictWeakOrdering); 1330 1331 template<typename _StrictWeakOrdering> 1332 void 1333 merge(list& __x, _StrictWeakOrdering __comp) 1334 { merge(std::move(__x), __comp); } 1335#else 1336 template<typename _StrictWeakOrdering> 1337 void 1338 merge(list&, _StrictWeakOrdering); 1339#endif 1340 1341 /** 1342 * @brief Reverse the elements in list. 1343 * 1344 * Reverse the order of elements in the list in linear time. 1345 */ 1346 void 1347 reverse() 1348 { this->_M_impl._M_node._M_reverse(); } 1349 1350 /** 1351 * @brief Sort the elements. 1352 * 1353 * Sorts the elements of this list in NlogN time. Equivalent 1354 * elements remain in list order. 1355 */ 1356 void 1357 sort(); 1358 1359 /** 1360 * @brief Sort the elements according to comparison function. 1361 * 1362 * Sorts the elements of this list in NlogN time. Equivalent 1363 * elements remain in list order. 1364 */ 1365 template<typename _StrictWeakOrdering> 1366 void 1367 sort(_StrictWeakOrdering); 1368 1369 protected: 1370 // Internal constructor functions follow. 1371 1372 // Called by the range constructor to implement [23.1.1]/9 1373 1374 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1375 // 438. Ambiguity in the "do the right thing" clause 1376 template<typename _Integer> 1377 void 1378 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 1379 { _M_fill_initialize(static_cast<size_type>(__n), __x); } 1380 1381 // Called by the range constructor to implement [23.1.1]/9 1382 template<typename _InputIterator> 1383 void 1384 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1385 __false_type) 1386 { 1387 for (; __first != __last; ++__first) 1388 push_back(*__first); 1389 } 1390 1391 // Called by list(n,v,a), and the range constructor when it turns out 1392 // to be the same thing. 1393 void 1394 _M_fill_initialize(size_type __n, const value_type& __x) 1395 { 1396 for (; __n > 0; --__n) 1397 push_back(__x); 1398 } 1399 1400 1401 // Internal assign functions follow. 1402 1403 // Called by the range assign to implement [23.1.1]/9 1404 1405 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1406 // 438. Ambiguity in the "do the right thing" clause 1407 template<typename _Integer> 1408 void 1409 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1410 { _M_fill_assign(__n, __val); } 1411 1412 // Called by the range assign to implement [23.1.1]/9 1413 template<typename _InputIterator> 1414 void 1415 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1416 __false_type); 1417 1418 // Called by assign(n,t), and the range assign when it turns out 1419 // to be the same thing. 1420 void 1421 _M_fill_assign(size_type __n, const value_type& __val); 1422 1423 1424 // Moves the elements from [first,last) before position. 1425 void 1426 _M_transfer(iterator __position, iterator __first, iterator __last) 1427 { __position._M_node->_M_transfer(__first._M_node, __last._M_node); } 1428 1429 // Inserts new element at position given and with value given. 1430#ifndef __GXX_EXPERIMENTAL_CXX0X__ 1431 void 1432 _M_insert(iterator __position, const value_type& __x) 1433 { 1434 _Node* __tmp = _M_create_node(__x); 1435 __tmp->_M_hook(__position._M_node); 1436 } 1437#else 1438 template<typename... _Args> 1439 void 1440 _M_insert(iterator __position, _Args&&... __args) 1441 { 1442 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 1443 __tmp->_M_hook(__position._M_node); 1444 } 1445#endif 1446 1447 // Erases element at position given. 1448 void 1449 _M_erase(iterator __position) 1450 { 1451 __position._M_node->_M_unhook(); 1452 _Node* __n = static_cast<_Node*>(__position._M_node); 1453#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1454 _M_get_Node_allocator().destroy(__n); 1455#else 1456 _M_get_Tp_allocator().destroy(&__n->_M_data); 1457#endif 1458 _M_put_node(__n); 1459 } 1460 1461 // To implement the splice (and merge) bits of N1599. 1462 void 1463 _M_check_equal_allocators(list& __x) 1464 { 1465 if (std::__alloc_neq<typename _Base::_Node_alloc_type>:: 1466 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) 1467 __throw_runtime_error(__N("list::_M_check_equal_allocators")); 1468 } 1469 }; 1470 1471 /** 1472 * @brief List equality comparison. 1473 * @param x A %list. 1474 * @param y A %list of the same type as @a x. 1475 * @return True iff the size and elements of the lists are equal. 1476 * 1477 * This is an equivalence relation. It is linear in the size of 1478 * the lists. Lists are considered equivalent if their sizes are 1479 * equal, and if corresponding elements compare equal. 1480 */ 1481 template<typename _Tp, typename _Alloc> 1482 inline bool 1483 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1484 { 1485 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; 1486 const_iterator __end1 = __x.end(); 1487 const_iterator __end2 = __y.end(); 1488 1489 const_iterator __i1 = __x.begin(); 1490 const_iterator __i2 = __y.begin(); 1491 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 1492 { 1493 ++__i1; 1494 ++__i2; 1495 } 1496 return __i1 == __end1 && __i2 == __end2; 1497 } 1498 1499 /** 1500 * @brief List ordering relation. 1501 * @param x A %list. 1502 * @param y A %list of the same type as @a x. 1503 * @return True iff @a x is lexicographically less than @a y. 1504 * 1505 * This is a total ordering relation. It is linear in the size of the 1506 * lists. The elements must be comparable with @c <. 1507 * 1508 * See std::lexicographical_compare() for how the determination is made. 1509 */ 1510 template<typename _Tp, typename _Alloc> 1511 inline bool 1512 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1513 { return std::lexicographical_compare(__x.begin(), __x.end(), 1514 __y.begin(), __y.end()); } 1515 1516 /// Based on operator== 1517 template<typename _Tp, typename _Alloc> 1518 inline bool 1519 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1520 { return !(__x == __y); } 1521 1522 /// Based on operator< 1523 template<typename _Tp, typename _Alloc> 1524 inline bool 1525 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1526 { return __y < __x; } 1527 1528 /// Based on operator< 1529 template<typename _Tp, typename _Alloc> 1530 inline bool 1531 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1532 { return !(__y < __x); } 1533 1534 /// Based on operator< 1535 template<typename _Tp, typename _Alloc> 1536 inline bool 1537 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1538 { return !(__x < __y); } 1539 1540 /// See std::list::swap(). 1541 template<typename _Tp, typename _Alloc> 1542 inline void 1543 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 1544 { __x.swap(__y); } 1545 1546_GLIBCXX_END_NESTED_NAMESPACE 1547 1548#endif /* _STL_LIST_H */ 1549