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