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