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