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