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