1 // List implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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); 78 79 void 80 transfer(_List_node_base * const __first, 81 _List_node_base * const __last); 82 83 void 84 reverse(); 85 86 void 87 hook(_List_node_base * const __position); 88 89 void 90 unhook(); 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 675. 610 this->clear(); 611 this->swap(__x); 612 return *this; 613 } 614 615 /** 616 * @brief %List initializer list assignment operator. 617 * @param l An initializer_list of value_type. 618 * 619 * Replace the contents of the %list with copies of the elements 620 * in the initializer_list @a l. This is linear in l.size(). 621 */ 622 list& 623 operator=(initializer_list<value_type> __l) 624 { 625 this->assign(__l.begin(), __l.end()); 626 return *this; 627 } 628 #endif 629 630 /** 631 * @brief Assigns a given value to a %list. 632 * @param n Number of elements to be assigned. 633 * @param val Value to be assigned. 634 * 635 * This function fills a %list with @a n copies of the given 636 * value. Note that the assignment completely changes the %list 637 * and that the resulting %list's size is the same as the number 638 * of elements assigned. Old data may be lost. 639 */ 640 void 641 assign(size_type __n, const value_type& __val) 642 { _M_fill_assign(__n, __val); } 643 644 /** 645 * @brief Assigns a range to a %list. 646 * @param first An input iterator. 647 * @param last An input iterator. 648 * 649 * This function fills a %list with copies of the elements in the 650 * range [@a first,@a last). 651 * 652 * Note that the assignment completely changes the %list and 653 * that the resulting %list's size is the same as the number of 654 * elements assigned. Old data may be lost. 655 */ 656 template<typename _InputIterator> 657 void 658 assign(_InputIterator __first, _InputIterator __last) 659 { 660 // Check whether it's an integral type. If so, it's not an iterator. 661 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 662 _M_assign_dispatch(__first, __last, _Integral()); 663 } 664 665 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 666 /** 667 * @brief Assigns an initializer_list to a %list. 668 * @param l An initializer_list of value_type. 669 * 670 * Replace the contents of the %list with copies of the elements 671 * in the initializer_list @a l. This is linear in l.size(). 672 */ 673 void 674 assign(initializer_list<value_type> __l) 675 { this->assign(__l.begin(), __l.end()); } 676 #endif 677 678 /// Get a copy of the memory allocation object. 679 allocator_type 680 get_allocator() const 681 { return _Base::get_allocator(); } 682 683 // iterators 684 /** 685 * Returns a read/write iterator that points to the first element in the 686 * %list. Iteration is done in ordinary element order. 687 */ 688 iterator 689 begin() 690 { return iterator(this->_M_impl._M_node._M_next); } 691 692 /** 693 * Returns a read-only (constant) iterator that points to the 694 * first element in the %list. Iteration is done in ordinary 695 * element order. 696 */ 697 const_iterator 698 begin() const 699 { return const_iterator(this->_M_impl._M_node._M_next); } 700 701 /** 702 * Returns a read/write iterator that points one past the last 703 * element in the %list. Iteration is done in ordinary element 704 * order. 705 */ 706 iterator 707 end() 708 { return iterator(&this->_M_impl._M_node); } 709 710 /** 711 * Returns a read-only (constant) iterator that points one past 712 * the last element in the %list. Iteration is done in ordinary 713 * element order. 714 */ 715 const_iterator 716 end() const 717 { return const_iterator(&this->_M_impl._M_node); } 718 719 /** 720 * Returns a read/write reverse iterator that points to the last 721 * element in the %list. Iteration is done in reverse element 722 * order. 723 */ 724 reverse_iterator 725 rbegin() 726 { return reverse_iterator(end()); } 727 728 /** 729 * Returns a read-only (constant) reverse iterator that points to 730 * the last element in the %list. Iteration is done in reverse 731 * element order. 732 */ 733 const_reverse_iterator 734 rbegin() const 735 { return const_reverse_iterator(end()); } 736 737 /** 738 * Returns a read/write reverse iterator that points to one 739 * before the first element in the %list. Iteration is done in 740 * reverse element order. 741 */ 742 reverse_iterator 743 rend() 744 { return reverse_iterator(begin()); } 745 746 /** 747 * Returns a read-only (constant) reverse iterator that points to one 748 * before the first element in the %list. Iteration is done in reverse 749 * element order. 750 */ 751 const_reverse_iterator 752 rend() const 753 { return const_reverse_iterator(begin()); } 754 755 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 756 /** 757 * Returns a read-only (constant) iterator that points to the 758 * first element in the %list. Iteration is done in ordinary 759 * element order. 760 */ 761 const_iterator 762 cbegin() const 763 { return const_iterator(this->_M_impl._M_node._M_next); } 764 765 /** 766 * Returns a read-only (constant) iterator that points one past 767 * the last element in the %list. Iteration is done in ordinary 768 * element order. 769 */ 770 const_iterator 771 cend() const 772 { return const_iterator(&this->_M_impl._M_node); } 773 774 /** 775 * Returns a read-only (constant) reverse iterator that points to 776 * the last element in the %list. Iteration is done in reverse 777 * element order. 778 */ 779 const_reverse_iterator 780 crbegin() const 781 { return const_reverse_iterator(end()); } 782 783 /** 784 * Returns a read-only (constant) reverse iterator that points to one 785 * before the first element in the %list. Iteration is done in reverse 786 * element order. 787 */ 788 const_reverse_iterator 789 crend() const 790 { return const_reverse_iterator(begin()); } 791 #endif 792 793 // [23.2.2.2] capacity 794 /** 795 * Returns true if the %list is empty. (Thus begin() would equal 796 * end().) 797 */ 798 bool 799 empty() const 800 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } 801 802 /** Returns the number of elements in the %list. */ 803 size_type 804 size() const 805 { return std::distance(begin(), end()); } 806 807 /** Returns the size() of the largest possible %list. */ 808 size_type 809 max_size() const 810 { return _M_get_Node_allocator().max_size(); } 811 812 /** 813 * @brief Resizes the %list to the specified number of elements. 814 * @param new_size Number of elements the %list should contain. 815 * @param x Data with which new elements should be populated. 816 * 817 * This function will %resize the %list to the specified number 818 * of elements. If the number is smaller than the %list's 819 * current size the %list is truncated, otherwise the %list is 820 * extended and new elements are populated with given data. 821 */ 822 void 823 resize(size_type __new_size, value_type __x = value_type()); 824 825 // element access 826 /** 827 * Returns a read/write reference to the data at the first 828 * element of the %list. 829 */ 830 reference 831 front() 832 { return *begin(); } 833 834 /** 835 * Returns a read-only (constant) reference to the data at the first 836 * element of the %list. 837 */ 838 const_reference 839 front() const 840 { return *begin(); } 841 842 /** 843 * Returns a read/write reference to the data at the last element 844 * of the %list. 845 */ 846 reference 847 back() 848 { 849 iterator __tmp = end(); 850 --__tmp; 851 return *__tmp; 852 } 853 854 /** 855 * Returns a read-only (constant) reference to the data at the last 856 * element of the %list. 857 */ 858 const_reference 859 back() const 860 { 861 const_iterator __tmp = end(); 862 --__tmp; 863 return *__tmp; 864 } 865 866 // [23.2.2.3] modifiers 867 /** 868 * @brief Add data to the front of the %list. 869 * @param x Data to be added. 870 * 871 * This is a typical stack operation. The function creates an 872 * element at the front of the %list and assigns the given data 873 * to it. Due to the nature of a %list this operation can be 874 * done in constant time, and does not invalidate iterators and 875 * references. 876 */ 877 void 878 push_front(const value_type& __x) 879 { this->_M_insert(begin(), __x); } 880 881 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 882 void 883 push_front(value_type&& __x) 884 { this->_M_insert(begin(), std::move(__x)); } 885 886 template<typename... _Args> 887 void 888 emplace_front(_Args&&... __args) 889 { this->_M_insert(begin(), std::forward<_Args>(__args)...); } 890 #endif 891 892 /** 893 * @brief Removes first element. 894 * 895 * This is a typical stack operation. It shrinks the %list by 896 * one. Due to the nature of a %list this operation can be done 897 * in constant time, and only invalidates iterators/references to 898 * the element being removed. 899 * 900 * Note that no data is returned, and if the first element's data 901 * is needed, it should be retrieved before pop_front() is 902 * called. 903 */ 904 void 905 pop_front() 906 { this->_M_erase(begin()); } 907 908 /** 909 * @brief Add data to the end of the %list. 910 * @param x Data to be added. 911 * 912 * This is a typical stack operation. The function creates an 913 * element at the end of the %list and assigns the given data to 914 * it. Due to the nature of a %list this operation can be done 915 * in constant time, and does not invalidate iterators and 916 * references. 917 */ 918 void 919 push_back(const value_type& __x) 920 { this->_M_insert(end(), __x); } 921 922 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 923 void 924 push_back(value_type&& __x) 925 { this->_M_insert(end(), std::move(__x)); } 926 927 template<typename... _Args> 928 void 929 emplace_back(_Args&&... __args) 930 { this->_M_insert(end(), std::forward<_Args>(__args)...); } 931 #endif 932 933 /** 934 * @brief Removes last element. 935 * 936 * This is a typical stack operation. It shrinks the %list by 937 * one. Due to the nature of a %list this operation can be done 938 * in constant time, and only invalidates iterators/references to 939 * the element being removed. 940 * 941 * Note that no data is returned, and if the last element's data 942 * is needed, it should be retrieved before pop_back() is called. 943 */ 944 void 945 pop_back() 946 { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } 947 948 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 949 /** 950 * @brief Constructs object in %list before specified iterator. 951 * @param position A const_iterator into the %list. 952 * @param args Arguments. 953 * @return An iterator that points to the inserted data. 954 * 955 * This function will insert an object of type T constructed 956 * with T(std::forward<Args>(args)...) before the specified 957 * location. Due to the nature of a %list this operation can 958 * be done in constant time, and does not invalidate iterators 959 * and references. 960 */ 961 template<typename... _Args> 962 iterator 963 emplace(iterator __position, _Args&&... __args); 964 #endif 965 966 /** 967 * @brief Inserts given value into %list before specified iterator. 968 * @param position An iterator into the %list. 969 * @param x Data to be inserted. 970 * @return An iterator that points to the inserted data. 971 * 972 * This function will insert a copy of the given value before 973 * the specified location. Due to the nature of a %list this 974 * operation can be done in constant time, and does not 975 * invalidate iterators and references. 976 */ 977 iterator 978 insert(iterator __position, const value_type& __x); 979 980 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 981 /** 982 * @brief Inserts given rvalue into %list before specified iterator. 983 * @param position An iterator into the %list. 984 * @param x Data to be inserted. 985 * @return An iterator that points to the inserted data. 986 * 987 * This function will insert a copy of the given rvalue before 988 * the specified location. Due to the nature of a %list this 989 * operation can be done in constant time, and does not 990 * invalidate iterators and references. 991 */ 992 iterator 993 insert(iterator __position, value_type&& __x) 994 { return emplace(__position, std::move(__x)); } 995 996 /** 997 * @brief Inserts the contents of an initializer_list into %list 998 * before specified iterator. 999 * @param p An iterator into the %list. 1000 * @param l An initializer_list of value_type. 1001 * 1002 * This function will insert copies of the data in the 1003 * initializer_list @a l into the %list before the location 1004 * specified by @a p. 1005 * 1006 * This operation is linear in the number of elements inserted and 1007 * does not invalidate iterators and references. 1008 */ 1009 void 1010 insert(iterator __p, initializer_list<value_type> __l) 1011 { this->insert(__p, __l.begin(), __l.end()); } 1012 #endif 1013 1014 /** 1015 * @brief Inserts a number of copies of given data into the %list. 1016 * @param position An iterator into the %list. 1017 * @param n Number of elements to be inserted. 1018 * @param x Data to be inserted. 1019 * 1020 * This function will insert a specified number of copies of the 1021 * given data before the location specified by @a position. 1022 * 1023 * This operation is linear in the number of elements inserted and 1024 * does not invalidate iterators and references. 1025 */ 1026 void 1027 insert(iterator __position, size_type __n, const value_type& __x) 1028 { 1029 list __tmp(__n, __x, _M_get_Node_allocator()); 1030 splice(__position, __tmp); 1031 } 1032 1033 /** 1034 * @brief Inserts a range into the %list. 1035 * @param position An iterator into the %list. 1036 * @param first An input iterator. 1037 * @param last An input iterator. 1038 * 1039 * This function will insert copies of the data in the range [@a 1040 * first,@a last) into the %list before the location specified by 1041 * @a position. 1042 * 1043 * This operation is linear in the number of elements inserted and 1044 * does not invalidate iterators and references. 1045 */ 1046 template<typename _InputIterator> 1047 void 1048 insert(iterator __position, _InputIterator __first, 1049 _InputIterator __last) 1050 { 1051 list __tmp(__first, __last, _M_get_Node_allocator()); 1052 splice(__position, __tmp); 1053 } 1054 1055 /** 1056 * @brief Remove element at given position. 1057 * @param position Iterator pointing to element to be erased. 1058 * @return An iterator pointing to the next element (or end()). 1059 * 1060 * This function will erase the element at the given position and thus 1061 * shorten the %list by one. 1062 * 1063 * Due to the nature of a %list this operation can be done in 1064 * constant time, and only invalidates iterators/references to 1065 * the element being removed. The user is also cautioned that 1066 * this function only erases the element, and that if the element 1067 * is itself a pointer, the pointed-to memory is not touched in 1068 * any way. Managing the pointer is the user's responsibility. 1069 */ 1070 iterator 1071 erase(iterator __position); 1072 1073 /** 1074 * @brief Remove a range of elements. 1075 * @param first Iterator pointing to the first element to be erased. 1076 * @param last Iterator pointing to one past the last element to be 1077 * erased. 1078 * @return An iterator pointing to the element pointed to by @a last 1079 * prior to erasing (or end()). 1080 * 1081 * This function will erase the elements in the range @a 1082 * [first,last) and shorten the %list accordingly. 1083 * 1084 * This operation is linear time in the size of the range and only 1085 * invalidates iterators/references to the element being removed. 1086 * The user is also cautioned that this function only erases the 1087 * elements, and that if the elements themselves are pointers, the 1088 * pointed-to memory is not touched in any way. Managing the pointer 1089 * is the user's responsibility. 1090 */ 1091 iterator 1092 erase(iterator __first, iterator __last) 1093 { 1094 while (__first != __last) 1095 __first = erase(__first); 1096 return __last; 1097 } 1098 1099 /** 1100 * @brief Swaps data with another %list. 1101 * @param x A %list of the same element and allocator types. 1102 * 1103 * This exchanges the elements between two lists in constant 1104 * time. Note that the global std::swap() function is 1105 * specialized such that std::swap(l1,l2) will feed to this 1106 * function. 1107 */ 1108 void 1109 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1110 swap(list&& __x) 1111 #else 1112 swap(list& __x) 1113 #endif 1114 { 1115 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); 1116 1117 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1118 // 431. Swapping containers with unequal allocators. 1119 std::__alloc_swap<typename _Base::_Node_alloc_type>:: 1120 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()); 1121 } 1122 1123 /** 1124 * Erases all the elements. Note that this function only erases 1125 * the elements, and that if the elements themselves are 1126 * pointers, the pointed-to memory is not touched in any way. 1127 * Managing the pointer is the user's responsibility. 1128 */ 1129 void 1130 clear() 1131 { 1132 _Base::_M_clear(); 1133 _Base::_M_init(); 1134 } 1135 1136 // [23.2.2.4] list operations 1137 /** 1138 * @brief Insert contents of another %list. 1139 * @param position Iterator referencing the element to insert before. 1140 * @param x Source list. 1141 * 1142 * The elements of @a x are inserted in constant time in front of 1143 * the element referenced by @a position. @a x becomes an empty 1144 * list. 1145 * 1146 * Requires this != @a x. 1147 */ 1148 void 1149 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1150 splice(iterator __position, list&& __x) 1151 #else 1152 splice(iterator __position, list& __x) 1153 #endif 1154 { 1155 if (!__x.empty()) 1156 { 1157 _M_check_equal_allocators(__x); 1158 1159 this->_M_transfer(__position, __x.begin(), __x.end()); 1160 } 1161 } 1162 1163 /** 1164 * @brief Insert element from another %list. 1165 * @param position Iterator referencing the element to insert before. 1166 * @param x Source list. 1167 * @param i Iterator referencing the element to move. 1168 * 1169 * Removes the element in list @a x referenced by @a i and 1170 * inserts it into the current list before @a position. 1171 */ 1172 void 1173 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1174 splice(iterator __position, list&& __x, iterator __i) 1175 #else 1176 splice(iterator __position, list& __x, iterator __i) 1177 #endif 1178 { 1179 iterator __j = __i; 1180 ++__j; 1181 if (__position == __i || __position == __j) 1182 return; 1183 1184 if (this != &__x) 1185 _M_check_equal_allocators(__x); 1186 1187 this->_M_transfer(__position, __i, __j); 1188 } 1189 1190 /** 1191 * @brief Insert range from another %list. 1192 * @param position Iterator referencing the element to insert before. 1193 * @param x Source list. 1194 * @param first Iterator referencing the start of range in x. 1195 * @param last Iterator referencing the end of range in x. 1196 * 1197 * Removes elements in the range [first,last) and inserts them 1198 * before @a position in constant time. 1199 * 1200 * Undefined if @a position is in [first,last). 1201 */ 1202 void 1203 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1204 splice(iterator __position, list&& __x, iterator __first, 1205 iterator __last) 1206 #else 1207 splice(iterator __position, list& __x, iterator __first, 1208 iterator __last) 1209 #endif 1210 { 1211 if (__first != __last) 1212 { 1213 if (this != &__x) 1214 _M_check_equal_allocators(__x); 1215 1216 this->_M_transfer(__position, __first, __last); 1217 } 1218 } 1219 1220 /** 1221 * @brief Remove all elements equal to value. 1222 * @param value The value to remove. 1223 * 1224 * Removes every element in the list equal to @a value. 1225 * Remaining elements stay in list order. Note that this 1226 * function only erases the elements, and that if the elements 1227 * themselves are pointers, the pointed-to memory is not 1228 * touched in any way. Managing the pointer is the user's 1229 * responsibility. 1230 */ 1231 void 1232 remove(const _Tp& __value); 1233 1234 /** 1235 * @brief Remove all elements satisfying a predicate. 1236 * @param Predicate Unary predicate function or object. 1237 * 1238 * Removes every element in the list for which the predicate 1239 * returns true. Remaining elements stay in list order. Note 1240 * that this function only erases the elements, and that if the 1241 * elements themselves are pointers, the pointed-to memory is 1242 * not touched in any way. Managing the pointer is the user's 1243 * responsibility. 1244 */ 1245 template<typename _Predicate> 1246 void 1247 remove_if(_Predicate); 1248 1249 /** 1250 * @brief Remove consecutive duplicate elements. 1251 * 1252 * For each consecutive set of elements with the same value, 1253 * remove all but the first one. Remaining elements stay in 1254 * list order. Note that this function only erases the 1255 * elements, and that if the elements themselves are pointers, 1256 * the pointed-to memory is not touched in any way. Managing 1257 * the pointer is the user's responsibility. 1258 */ 1259 void 1260 unique(); 1261 1262 /** 1263 * @brief Remove consecutive elements satisfying a predicate. 1264 * @param BinaryPredicate Binary predicate function or object. 1265 * 1266 * For each consecutive set of elements [first,last) that 1267 * satisfy predicate(first,i) where i is an iterator in 1268 * [first,last), remove all but the first one. Remaining 1269 * elements stay in list order. Note that this function only 1270 * erases the elements, and that if the elements themselves are 1271 * pointers, the pointed-to memory is not touched in any way. 1272 * Managing the pointer is the user's responsibility. 1273 */ 1274 template<typename _BinaryPredicate> 1275 void 1276 unique(_BinaryPredicate); 1277 1278 /** 1279 * @brief Merge sorted lists. 1280 * @param x Sorted list to merge. 1281 * 1282 * Assumes that both @a x and this list are sorted according to 1283 * operator<(). Merges elements of @a x into this list in 1284 * sorted order, leaving @a x empty when complete. Elements in 1285 * this list precede elements in @a x that are equal. 1286 */ 1287 void 1288 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1289 merge(list&& __x); 1290 #else 1291 merge(list& __x); 1292 #endif 1293 1294 /** 1295 * @brief Merge sorted lists according to comparison function. 1296 * @param x Sorted list to merge. 1297 * @param StrictWeakOrdering Comparison function defining 1298 * sort order. 1299 * 1300 * Assumes that both @a x and this list are sorted according to 1301 * StrictWeakOrdering. Merges elements of @a x into this list 1302 * in sorted order, leaving @a x empty when complete. Elements 1303 * in this list precede elements in @a x that are equivalent 1304 * according to StrictWeakOrdering(). 1305 */ 1306 template<typename _StrictWeakOrdering> 1307 void 1308 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1309 merge(list&&, _StrictWeakOrdering); 1310 #else 1311 merge(list&, _StrictWeakOrdering); 1312 #endif 1313 1314 /** 1315 * @brief Reverse the elements in list. 1316 * 1317 * Reverse the order of elements in the list in linear time. 1318 */ 1319 void 1320 reverse() 1321 { this->_M_impl._M_node.reverse(); } 1322 1323 /** 1324 * @brief Sort the elements. 1325 * 1326 * Sorts the elements of this list in NlogN time. Equivalent 1327 * elements remain in list order. 1328 */ 1329 void 1330 sort(); 1331 1332 /** 1333 * @brief Sort the elements according to comparison function. 1334 * 1335 * Sorts the elements of this list in NlogN time. Equivalent 1336 * elements remain in list order. 1337 */ 1338 template<typename _StrictWeakOrdering> 1339 void 1340 sort(_StrictWeakOrdering); 1341 1342 protected: 1343 // Internal constructor functions follow. 1344 1345 // Called by the range constructor to implement [23.1.1]/9 1346 1347 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1348 // 438. Ambiguity in the "do the right thing" clause 1349 template<typename _Integer> 1350 void 1351 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 1352 { _M_fill_initialize(static_cast<size_type>(__n), __x); } 1353 1354 // Called by the range constructor to implement [23.1.1]/9 1355 template<typename _InputIterator> 1356 void 1357 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1358 __false_type) 1359 { 1360 for (; __first != __last; ++__first) 1361 push_back(*__first); 1362 } 1363 1364 // Called by list(n,v,a), and the range constructor when it turns out 1365 // to be the same thing. 1366 void 1367 _M_fill_initialize(size_type __n, const value_type& __x) 1368 { 1369 for (; __n > 0; --__n) 1370 push_back(__x); 1371 } 1372 1373 1374 // Internal assign functions follow. 1375 1376 // Called by the range assign to implement [23.1.1]/9 1377 1378 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1379 // 438. Ambiguity in the "do the right thing" clause 1380 template<typename _Integer> 1381 void 1382 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1383 { _M_fill_assign(__n, __val); } 1384 1385 // Called by the range assign to implement [23.1.1]/9 1386 template<typename _InputIterator> 1387 void 1388 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1389 __false_type); 1390 1391 // Called by assign(n,t), and the range assign when it turns out 1392 // to be the same thing. 1393 void 1394 _M_fill_assign(size_type __n, const value_type& __val); 1395 1396 1397 // Moves the elements from [first,last) before position. 1398 void 1399 _M_transfer(iterator __position, iterator __first, iterator __last) 1400 { __position._M_node->transfer(__first._M_node, __last._M_node); } 1401 1402 // Inserts new element at position given and with value given. 1403 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 1404 void 1405 _M_insert(iterator __position, const value_type& __x) 1406 { 1407 _Node* __tmp = _M_create_node(__x); 1408 __tmp->hook(__position._M_node); 1409 } 1410 #else 1411 template<typename... _Args> 1412 void 1413 _M_insert(iterator __position, _Args&&... __args) 1414 { 1415 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 1416 __tmp->hook(__position._M_node); 1417 } 1418 #endif 1419 1420 // Erases element at position given. 1421 void 1422 _M_erase(iterator __position) 1423 { 1424 __position._M_node->unhook(); 1425 _Node* __n = static_cast<_Node*>(__position._M_node); 1426 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1427 _M_get_Node_allocator().destroy(__n); 1428 #else 1429 _M_get_Tp_allocator().destroy(&__n->_M_data); 1430 #endif 1431 _M_put_node(__n); 1432 } 1433 1434 // To implement the splice (and merge) bits of N1599. 1435 void 1436 _M_check_equal_allocators(list& __x) 1437 { 1438 if (std::__alloc_neq<typename _Base::_Node_alloc_type>:: 1439 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) 1440 __throw_runtime_error(__N("list::_M_check_equal_allocators")); 1441 } 1442 }; 1443 1444 /** 1445 * @brief List equality comparison. 1446 * @param x A %list. 1447 * @param y A %list of the same type as @a x. 1448 * @return True iff the size and elements of the lists are equal. 1449 * 1450 * This is an equivalence relation. It is linear in the size of 1451 * the lists. Lists are considered equivalent if their sizes are 1452 * equal, and if corresponding elements compare equal. 1453 */ 1454 template<typename _Tp, typename _Alloc> 1455 inline bool 1456 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1457 { 1458 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; 1459 const_iterator __end1 = __x.end(); 1460 const_iterator __end2 = __y.end(); 1461 1462 const_iterator __i1 = __x.begin(); 1463 const_iterator __i2 = __y.begin(); 1464 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 1465 { 1466 ++__i1; 1467 ++__i2; 1468 } 1469 return __i1 == __end1 && __i2 == __end2; 1470 } 1471 1472 /** 1473 * @brief List ordering relation. 1474 * @param x A %list. 1475 * @param y A %list of the same type as @a x. 1476 * @return True iff @a x is lexicographically less than @a y. 1477 * 1478 * This is a total ordering relation. It is linear in the size of the 1479 * lists. The elements must be comparable with @c <. 1480 * 1481 * See std::lexicographical_compare() for how the determination is made. 1482 */ 1483 template<typename _Tp, typename _Alloc> 1484 inline bool 1485 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1486 { return std::lexicographical_compare(__x.begin(), __x.end(), 1487 __y.begin(), __y.end()); } 1488 1489 /// Based on operator== 1490 template<typename _Tp, typename _Alloc> 1491 inline bool 1492 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1493 { return !(__x == __y); } 1494 1495 /// Based on operator< 1496 template<typename _Tp, typename _Alloc> 1497 inline bool 1498 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1499 { return __y < __x; } 1500 1501 /// Based on operator< 1502 template<typename _Tp, typename _Alloc> 1503 inline bool 1504 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1505 { return !(__y < __x); } 1506 1507 /// Based on operator< 1508 template<typename _Tp, typename _Alloc> 1509 inline bool 1510 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1511 { return !(__x < __y); } 1512 1513 /// See std::list::swap(). 1514 template<typename _Tp, typename _Alloc> 1515 inline void 1516 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 1517 { __x.swap(__y); } 1518 1519 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1520 template<typename _Tp, typename _Alloc> 1521 inline void 1522 swap(list<_Tp, _Alloc>&& __x, list<_Tp, _Alloc>& __y) 1523 { __x.swap(__y); } 1524 1525 template<typename _Tp, typename _Alloc> 1526 inline void 1527 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>&& __y) 1528 { __x.swap(__y); } 1529 #endif 1530 1531 _GLIBCXX_END_NESTED_NAMESPACE 1532 1533 #endif /* _STL_LIST_H */ 1534