libstdc++
|
00001 // List implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996,1997 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file stl_list.h 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 */ 00056 00057 #ifndef _STL_LIST_H 00058 #define _STL_LIST_H 1 00059 00060 #include <bits/concept_check.h> 00061 #include <initializer_list> 00062 00063 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00064 00065 // Supporting structures are split into common and templated types; the 00066 // latter publicly inherits from the former in an effort to reduce code 00067 // duplication. This results in some "needless" static_cast'ing later on, 00068 // but it's all safe downcasting. 00069 00070 /// Common part of a node in the %list. 00071 struct _List_node_base 00072 { 00073 _List_node_base* _M_next; 00074 _List_node_base* _M_prev; 00075 00076 static void 00077 swap(_List_node_base& __x, _List_node_base& __y); 00078 00079 void 00080 transfer(_List_node_base * const __first, 00081 _List_node_base * const __last); 00082 00083 void 00084 reverse(); 00085 00086 void 00087 hook(_List_node_base * const __position); 00088 00089 void 00090 unhook(); 00091 }; 00092 00093 /// An actual node in the %list. 00094 template<typename _Tp> 00095 struct _List_node : public _List_node_base 00096 { 00097 ///< User's data. 00098 _Tp _M_data; 00099 00100 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00101 template<typename... _Args> 00102 _List_node(_Args&&... __args) 00103 : _List_node_base(), _M_data(std::forward<_Args>(__args)...) { } 00104 #endif 00105 }; 00106 00107 /** 00108 * @brief A list::iterator. 00109 * 00110 * All the functions are op overloads. 00111 */ 00112 template<typename _Tp> 00113 struct _List_iterator 00114 { 00115 typedef _List_iterator<_Tp> _Self; 00116 typedef _List_node<_Tp> _Node; 00117 00118 typedef ptrdiff_t difference_type; 00119 typedef std::bidirectional_iterator_tag iterator_category; 00120 typedef _Tp value_type; 00121 typedef _Tp* pointer; 00122 typedef _Tp& reference; 00123 00124 _List_iterator() 00125 : _M_node() { } 00126 00127 explicit 00128 _List_iterator(_List_node_base* __x) 00129 : _M_node(__x) { } 00130 00131 // Must downcast from List_node_base to _List_node to get to _M_data. 00132 reference 00133 operator*() const 00134 { return static_cast<_Node*>(_M_node)->_M_data; } 00135 00136 pointer 00137 operator->() const 00138 { return &static_cast<_Node*>(_M_node)->_M_data; } 00139 00140 _Self& 00141 operator++() 00142 { 00143 _M_node = _M_node->_M_next; 00144 return *this; 00145 } 00146 00147 _Self 00148 operator++(int) 00149 { 00150 _Self __tmp = *this; 00151 _M_node = _M_node->_M_next; 00152 return __tmp; 00153 } 00154 00155 _Self& 00156 operator--() 00157 { 00158 _M_node = _M_node->_M_prev; 00159 return *this; 00160 } 00161 00162 _Self 00163 operator--(int) 00164 { 00165 _Self __tmp = *this; 00166 _M_node = _M_node->_M_prev; 00167 return __tmp; 00168 } 00169 00170 bool 00171 operator==(const _Self& __x) const 00172 { return _M_node == __x._M_node; } 00173 00174 bool 00175 operator!=(const _Self& __x) const 00176 { return _M_node != __x._M_node; } 00177 00178 // The only member points to the %list element. 00179 _List_node_base* _M_node; 00180 }; 00181 00182 /** 00183 * @brief A list::const_iterator. 00184 * 00185 * All the functions are op overloads. 00186 */ 00187 template<typename _Tp> 00188 struct _List_const_iterator 00189 { 00190 typedef _List_const_iterator<_Tp> _Self; 00191 typedef const _List_node<_Tp> _Node; 00192 typedef _List_iterator<_Tp> iterator; 00193 00194 typedef ptrdiff_t difference_type; 00195 typedef std::bidirectional_iterator_tag iterator_category; 00196 typedef _Tp value_type; 00197 typedef const _Tp* pointer; 00198 typedef const _Tp& reference; 00199 00200 _List_const_iterator() 00201 : _M_node() { } 00202 00203 explicit 00204 _List_const_iterator(const _List_node_base* __x) 00205 : _M_node(__x) { } 00206 00207 _List_const_iterator(const iterator& __x) 00208 : _M_node(__x._M_node) { } 00209 00210 // Must downcast from List_node_base to _List_node to get to 00211 // _M_data. 00212 reference 00213 operator*() const 00214 { return static_cast<_Node*>(_M_node)->_M_data; } 00215 00216 pointer 00217 operator->() const 00218 { return &static_cast<_Node*>(_M_node)->_M_data; } 00219 00220 _Self& 00221 operator++() 00222 { 00223 _M_node = _M_node->_M_next; 00224 return *this; 00225 } 00226 00227 _Self 00228 operator++(int) 00229 { 00230 _Self __tmp = *this; 00231 _M_node = _M_node->_M_next; 00232 return __tmp; 00233 } 00234 00235 _Self& 00236 operator--() 00237 { 00238 _M_node = _M_node->_M_prev; 00239 return *this; 00240 } 00241 00242 _Self 00243 operator--(int) 00244 { 00245 _Self __tmp = *this; 00246 _M_node = _M_node->_M_prev; 00247 return __tmp; 00248 } 00249 00250 bool 00251 operator==(const _Self& __x) const 00252 { return _M_node == __x._M_node; } 00253 00254 bool 00255 operator!=(const _Self& __x) const 00256 { return _M_node != __x._M_node; } 00257 00258 // The only member points to the %list element. 00259 const _List_node_base* _M_node; 00260 }; 00261 00262 template<typename _Val> 00263 inline bool 00264 operator==(const _List_iterator<_Val>& __x, 00265 const _List_const_iterator<_Val>& __y) 00266 { return __x._M_node == __y._M_node; } 00267 00268 template<typename _Val> 00269 inline bool 00270 operator!=(const _List_iterator<_Val>& __x, 00271 const _List_const_iterator<_Val>& __y) 00272 { return __x._M_node != __y._M_node; } 00273 00274 00275 /// See bits/stl_deque.h's _Deque_base for an explanation. 00276 template<typename _Tp, typename _Alloc> 00277 class _List_base 00278 { 00279 protected: 00280 // NOTA BENE 00281 // The stored instance is not actually of "allocator_type"'s 00282 // type. Instead we rebind the type to 00283 // Allocator<List_node<Tp>>, which according to [20.1.5]/4 00284 // should probably be the same. List_node<Tp> is not the same 00285 // size as Tp (it's two pointers larger), and specializations on 00286 // Tp may go unused because List_node<Tp> is being bound 00287 // instead. 00288 // 00289 // We put this to the test in the constructors and in 00290 // get_allocator, where we use conversions between 00291 // allocator_type and _Node_alloc_type. The conversion is 00292 // required by table 32 in [20.1.5]. 00293 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other 00294 _Node_alloc_type; 00295 00296 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 00297 00298 struct _List_impl 00299 : public _Node_alloc_type 00300 { 00301 _List_node_base _M_node; 00302 00303 _List_impl() 00304 : _Node_alloc_type(), _M_node() 00305 { } 00306 00307 _List_impl(const _Node_alloc_type& __a) 00308 : _Node_alloc_type(__a), _M_node() 00309 { } 00310 }; 00311 00312 _List_impl _M_impl; 00313 00314 _List_node<_Tp>* 00315 _M_get_node() 00316 { return _M_impl._Node_alloc_type::allocate(1); } 00317 00318 void 00319 _M_put_node(_List_node<_Tp>* __p) 00320 { _M_impl._Node_alloc_type::deallocate(__p, 1); } 00321 00322 public: 00323 typedef _Alloc allocator_type; 00324 00325 _Node_alloc_type& 00326 _M_get_Node_allocator() 00327 { return *static_cast<_Node_alloc_type*>(&this->_M_impl); } 00328 00329 const _Node_alloc_type& 00330 _M_get_Node_allocator() const 00331 { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); } 00332 00333 _Tp_alloc_type 00334 _M_get_Tp_allocator() const 00335 { return _Tp_alloc_type(_M_get_Node_allocator()); } 00336 00337 allocator_type 00338 get_allocator() const 00339 { return allocator_type(_M_get_Node_allocator()); } 00340 00341 _List_base() 00342 : _M_impl() 00343 { _M_init(); } 00344 00345 _List_base(const allocator_type& __a) 00346 : _M_impl(__a) 00347 { _M_init(); } 00348 00349 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00350 _List_base(_List_base&& __x) 00351 : _M_impl(__x._M_get_Node_allocator()) 00352 { 00353 _M_init(); 00354 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); 00355 } 00356 #endif 00357 00358 // This is what actually destroys the list. 00359 ~_List_base() 00360 { _M_clear(); } 00361 00362 void 00363 _M_clear(); 00364 00365 void 00366 _M_init() 00367 { 00368 this->_M_impl._M_node._M_next = &this->_M_impl._M_node; 00369 this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; 00370 } 00371 }; 00372 00373 /** 00374 * @brief A standard container with linear time access to elements, 00375 * and fixed time insertion/deletion at any point in the sequence. 00376 * 00377 * @ingroup sequences 00378 * 00379 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00380 * <a href="tables.html#66">reversible container</a>, and a 00381 * <a href="tables.html#67">sequence</a>, including the 00382 * <a href="tables.html#68">optional sequence requirements</a> with the 00383 * %exception of @c at and @c operator[]. 00384 * 00385 * This is a @e doubly @e linked %list. Traversal up and down the 00386 * %list requires linear time, but adding and removing elements (or 00387 * @e nodes) is done in constant time, regardless of where the 00388 * change takes place. Unlike std::vector and std::deque, 00389 * random-access iterators are not provided, so subscripting ( @c 00390 * [] ) access is not allowed. For algorithms which only need 00391 * sequential access, this lack makes no difference. 00392 * 00393 * Also unlike the other standard containers, std::list provides 00394 * specialized algorithms %unique to linked lists, such as 00395 * splicing, sorting, and in-place reversal. 00396 * 00397 * A couple points on memory allocation for list<Tp>: 00398 * 00399 * First, we never actually allocate a Tp, we allocate 00400 * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure 00401 * that after elements from %list<X,Alloc1> are spliced into 00402 * %list<X,Alloc2>, destroying the memory of the second %list is a 00403 * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away. 00404 * 00405 * Second, a %list conceptually represented as 00406 * @code 00407 * A <---> B <---> C <---> D 00408 * @endcode 00409 * is actually circular; a link exists between A and D. The %list 00410 * class holds (as its only data member) a private list::iterator 00411 * pointing to @e D, not to @e A! To get to the head of the %list, 00412 * we start at the tail and move forward by one. When this member 00413 * iterator's next/previous pointers refer to itself, the %list is 00414 * %empty. 00415 */ 00416 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 00417 class list : protected _List_base<_Tp, _Alloc> 00418 { 00419 // concept requirements 00420 typedef typename _Alloc::value_type _Alloc_value_type; 00421 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00422 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 00423 00424 typedef _List_base<_Tp, _Alloc> _Base; 00425 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 00426 00427 public: 00428 typedef _Tp value_type; 00429 typedef typename _Tp_alloc_type::pointer pointer; 00430 typedef typename _Tp_alloc_type::const_pointer const_pointer; 00431 typedef typename _Tp_alloc_type::reference reference; 00432 typedef typename _Tp_alloc_type::const_reference const_reference; 00433 typedef _List_iterator<_Tp> iterator; 00434 typedef _List_const_iterator<_Tp> const_iterator; 00435 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00436 typedef std::reverse_iterator<iterator> reverse_iterator; 00437 typedef size_t size_type; 00438 typedef ptrdiff_t difference_type; 00439 typedef _Alloc allocator_type; 00440 00441 protected: 00442 // Note that pointers-to-_Node's can be ctor-converted to 00443 // iterator types. 00444 typedef _List_node<_Tp> _Node; 00445 00446 using _Base::_M_impl; 00447 using _Base::_M_put_node; 00448 using _Base::_M_get_node; 00449 using _Base::_M_get_Tp_allocator; 00450 using _Base::_M_get_Node_allocator; 00451 00452 /** 00453 * @param x An instance of user data. 00454 * 00455 * Allocates space for a new node and constructs a copy of @a x in it. 00456 */ 00457 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00458 _Node* 00459 _M_create_node(const value_type& __x) 00460 { 00461 _Node* __p = this->_M_get_node(); 00462 __try 00463 { 00464 _M_get_Tp_allocator().construct(&__p->_M_data, __x); 00465 } 00466 __catch(...) 00467 { 00468 _M_put_node(__p); 00469 __throw_exception_again; 00470 } 00471 return __p; 00472 } 00473 #else 00474 template<typename... _Args> 00475 _Node* 00476 _M_create_node(_Args&&... __args) 00477 { 00478 _Node* __p = this->_M_get_node(); 00479 __try 00480 { 00481 _M_get_Node_allocator().construct(__p, 00482 std::forward<_Args>(__args)...); 00483 } 00484 __catch(...) 00485 { 00486 _M_put_node(__p); 00487 __throw_exception_again; 00488 } 00489 return __p; 00490 } 00491 #endif 00492 00493 public: 00494 // [23.2.2.1] construct/copy/destroy 00495 // (assign() and get_allocator() are also listed in this section) 00496 /** 00497 * @brief Default constructor creates no elements. 00498 */ 00499 list() 00500 : _Base() { } 00501 00502 /** 00503 * @brief Creates a %list with no elements. 00504 * @param a An allocator object. 00505 */ 00506 explicit 00507 list(const allocator_type& __a) 00508 : _Base(__a) { } 00509 00510 /** 00511 * @brief Creates a %list with copies of an exemplar element. 00512 * @param n The number of elements to initially create. 00513 * @param value An element to copy. 00514 * @param a An allocator object. 00515 * 00516 * This constructor fills the %list with @a n copies of @a value. 00517 */ 00518 explicit 00519 list(size_type __n, const value_type& __value = value_type(), 00520 const allocator_type& __a = allocator_type()) 00521 : _Base(__a) 00522 { _M_fill_initialize(__n, __value); } 00523 00524 /** 00525 * @brief %List copy constructor. 00526 * @param x A %list of identical element and allocator types. 00527 * 00528 * The newly-created %list uses a copy of the allocation object used 00529 * by @a x. 00530 */ 00531 list(const list& __x) 00532 : _Base(__x._M_get_Node_allocator()) 00533 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } 00534 00535 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00536 /** 00537 * @brief %List move constructor. 00538 * @param x A %list of identical element and allocator types. 00539 * 00540 * The newly-created %list contains the exact contents of @a x. 00541 * The contents of @a x are a valid, but unspecified %list. 00542 */ 00543 list(list&& __x) 00544 : _Base(std::forward<_Base>(__x)) { } 00545 00546 /** 00547 * @brief Builds a %list from an initializer_list 00548 * @param l An initializer_list of value_type. 00549 * @param a An allocator object. 00550 * 00551 * Create a %list consisting of copies of the elements in the 00552 * initializer_list @a l. This is linear in l.size(). 00553 */ 00554 list(initializer_list<value_type> __l, 00555 const allocator_type& __a = allocator_type()) 00556 : _Base(__a) 00557 { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); } 00558 #endif 00559 00560 /** 00561 * @brief Builds a %list from a range. 00562 * @param first An input iterator. 00563 * @param last An input iterator. 00564 * @param a An allocator object. 00565 * 00566 * Create a %list consisting of copies of the elements from 00567 * [@a first,@a last). This is linear in N (where N is 00568 * distance(@a first,@a last)). 00569 */ 00570 template<typename _InputIterator> 00571 list(_InputIterator __first, _InputIterator __last, 00572 const allocator_type& __a = allocator_type()) 00573 : _Base(__a) 00574 { 00575 // Check whether it's an integral type. If so, it's not an iterator. 00576 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00577 _M_initialize_dispatch(__first, __last, _Integral()); 00578 } 00579 00580 /** 00581 * No explicit dtor needed as the _Base dtor takes care of 00582 * things. The _Base dtor only erases the elements, and note 00583 * that if the elements themselves are pointers, the pointed-to 00584 * memory is not touched in any way. Managing the pointer is 00585 * the user's responsibility. 00586 */ 00587 00588 /** 00589 * @brief %List assignment operator. 00590 * @param x A %list of identical element and allocator types. 00591 * 00592 * All the elements of @a x are copied, but unlike the copy 00593 * constructor, the allocator object is not copied. 00594 */ 00595 list& 00596 operator=(const list& __x); 00597 00598 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00599 /** 00600 * @brief %List move assignment operator. 00601 * @param x A %list of identical element and allocator types. 00602 * 00603 * The contents of @a x are moved into this %list (without copying). 00604 * @a x is a valid, but unspecified %list 00605 */ 00606 list& 00607 operator=(list&& __x) 00608 { 00609 // NB: DR 675. 00610 this->clear(); 00611 this->swap(__x); 00612 return *this; 00613 } 00614 00615 /** 00616 * @brief %List initializer list assignment operator. 00617 * @param l An initializer_list of value_type. 00618 * 00619 * Replace the contents of the %list with copies of the elements 00620 * in the initializer_list @a l. This is linear in l.size(). 00621 */ 00622 list& 00623 operator=(initializer_list<value_type> __l) 00624 { 00625 this->assign(__l.begin(), __l.end()); 00626 return *this; 00627 } 00628 #endif 00629 00630 /** 00631 * @brief Assigns a given value to a %list. 00632 * @param n Number of elements to be assigned. 00633 * @param val Value to be assigned. 00634 * 00635 * This function fills a %list with @a n copies of the given 00636 * value. Note that the assignment completely changes the %list 00637 * and that the resulting %list's size is the same as the number 00638 * of elements assigned. Old data may be lost. 00639 */ 00640 void 00641 assign(size_type __n, const value_type& __val) 00642 { _M_fill_assign(__n, __val); } 00643 00644 /** 00645 * @brief Assigns a range to a %list. 00646 * @param first An input iterator. 00647 * @param last An input iterator. 00648 * 00649 * This function fills a %list with copies of the elements in the 00650 * range [@a first,@a last). 00651 * 00652 * Note that the assignment completely changes the %list and 00653 * that the resulting %list's size is the same as the number of 00654 * elements assigned. Old data may be lost. 00655 */ 00656 template<typename _InputIterator> 00657 void 00658 assign(_InputIterator __first, _InputIterator __last) 00659 { 00660 // Check whether it's an integral type. If so, it's not an iterator. 00661 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00662 _M_assign_dispatch(__first, __last, _Integral()); 00663 } 00664 00665 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00666 /** 00667 * @brief Assigns an initializer_list to a %list. 00668 * @param l An initializer_list of value_type. 00669 * 00670 * Replace the contents of the %list with copies of the elements 00671 * in the initializer_list @a l. This is linear in l.size(). 00672 */ 00673 void 00674 assign(initializer_list<value_type> __l) 00675 { this->assign(__l.begin(), __l.end()); } 00676 #endif 00677 00678 /// Get a copy of the memory allocation object. 00679 allocator_type 00680 get_allocator() const 00681 { return _Base::get_allocator(); } 00682 00683 // iterators 00684 /** 00685 * Returns a read/write iterator that points to the first element in the 00686 * %list. Iteration is done in ordinary element order. 00687 */ 00688 iterator 00689 begin() 00690 { return iterator(this->_M_impl._M_node._M_next); } 00691 00692 /** 00693 * Returns a read-only (constant) iterator that points to the 00694 * first element in the %list. Iteration is done in ordinary 00695 * element order. 00696 */ 00697 const_iterator 00698 begin() const 00699 { return const_iterator(this->_M_impl._M_node._M_next); } 00700 00701 /** 00702 * Returns a read/write iterator that points one past the last 00703 * element in the %list. Iteration is done in ordinary element 00704 * order. 00705 */ 00706 iterator 00707 end() 00708 { return iterator(&this->_M_impl._M_node); } 00709 00710 /** 00711 * Returns a read-only (constant) iterator that points one past 00712 * the last element in the %list. Iteration is done in ordinary 00713 * element order. 00714 */ 00715 const_iterator 00716 end() const 00717 { return const_iterator(&this->_M_impl._M_node); } 00718 00719 /** 00720 * Returns a read/write reverse iterator that points to the last 00721 * element in the %list. Iteration is done in reverse element 00722 * order. 00723 */ 00724 reverse_iterator 00725 rbegin() 00726 { return reverse_iterator(end()); } 00727 00728 /** 00729 * Returns a read-only (constant) reverse iterator that points to 00730 * the last element in the %list. Iteration is done in reverse 00731 * element order. 00732 */ 00733 const_reverse_iterator 00734 rbegin() const 00735 { return const_reverse_iterator(end()); } 00736 00737 /** 00738 * Returns a read/write reverse iterator that points to one 00739 * before the first element in the %list. Iteration is done in 00740 * reverse element order. 00741 */ 00742 reverse_iterator 00743 rend() 00744 { return reverse_iterator(begin()); } 00745 00746 /** 00747 * Returns a read-only (constant) reverse iterator that points to one 00748 * before the first element in the %list. Iteration is done in reverse 00749 * element order. 00750 */ 00751 const_reverse_iterator 00752 rend() const 00753 { return const_reverse_iterator(begin()); } 00754 00755 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00756 /** 00757 * Returns a read-only (constant) iterator that points to the 00758 * first element in the %list. Iteration is done in ordinary 00759 * element order. 00760 */ 00761 const_iterator 00762 cbegin() const 00763 { return const_iterator(this->_M_impl._M_node._M_next); } 00764 00765 /** 00766 * Returns a read-only (constant) iterator that points one past 00767 * the last element in the %list. Iteration is done in ordinary 00768 * element order. 00769 */ 00770 const_iterator 00771 cend() const 00772 { return const_iterator(&this->_M_impl._M_node); } 00773 00774 /** 00775 * Returns a read-only (constant) reverse iterator that points to 00776 * the last element in the %list. Iteration is done in reverse 00777 * element order. 00778 */ 00779 const_reverse_iterator 00780 crbegin() const 00781 { return const_reverse_iterator(end()); } 00782 00783 /** 00784 * Returns a read-only (constant) reverse iterator that points to one 00785 * before the first element in the %list. Iteration is done in reverse 00786 * element order. 00787 */ 00788 const_reverse_iterator 00789 crend() const 00790 { return const_reverse_iterator(begin()); } 00791 #endif 00792 00793 // [23.2.2.2] capacity 00794 /** 00795 * Returns true if the %list is empty. (Thus begin() would equal 00796 * end().) 00797 */ 00798 bool 00799 empty() const 00800 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } 00801 00802 /** Returns the number of elements in the %list. */ 00803 size_type 00804 size() const 00805 { return std::distance(begin(), end()); } 00806 00807 /** Returns the size() of the largest possible %list. */ 00808 size_type 00809 max_size() const 00810 { return _M_get_Node_allocator().max_size(); } 00811 00812 /** 00813 * @brief Resizes the %list to the specified number of elements. 00814 * @param new_size Number of elements the %list should contain. 00815 * @param x Data with which new elements should be populated. 00816 * 00817 * This function will %resize the %list to the specified number 00818 * of elements. If the number is smaller than the %list's 00819 * current size the %list is truncated, otherwise the %list is 00820 * extended and new elements are populated with given data. 00821 */ 00822 void 00823 resize(size_type __new_size, value_type __x = value_type()); 00824 00825 // element access 00826 /** 00827 * Returns a read/write reference to the data at the first 00828 * element of the %list. 00829 */ 00830 reference 00831 front() 00832 { return *begin(); } 00833 00834 /** 00835 * Returns a read-only (constant) reference to the data at the first 00836 * element of the %list. 00837 */ 00838 const_reference 00839 front() const 00840 { return *begin(); } 00841 00842 /** 00843 * Returns a read/write reference to the data at the last element 00844 * of the %list. 00845 */ 00846 reference 00847 back() 00848 { 00849 iterator __tmp = end(); 00850 --__tmp; 00851 return *__tmp; 00852 } 00853 00854 /** 00855 * Returns a read-only (constant) reference to the data at the last 00856 * element of the %list. 00857 */ 00858 const_reference 00859 back() const 00860 { 00861 const_iterator __tmp = end(); 00862 --__tmp; 00863 return *__tmp; 00864 } 00865 00866 // [23.2.2.3] modifiers 00867 /** 00868 * @brief Add data to the front of the %list. 00869 * @param x Data to be added. 00870 * 00871 * This is a typical stack operation. The function creates an 00872 * element at the front of the %list and assigns the given data 00873 * to it. Due to the nature of a %list this operation can be 00874 * done in constant time, and does not invalidate iterators and 00875 * references. 00876 */ 00877 void 00878 push_front(const value_type& __x) 00879 { this->_M_insert(begin(), __x); } 00880 00881 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00882 void 00883 push_front(value_type&& __x) 00884 { this->_M_insert(begin(), std::move(__x)); } 00885 00886 template<typename... _Args> 00887 void 00888 emplace_front(_Args&&... __args) 00889 { this->_M_insert(begin(), std::forward<_Args>(__args)...); } 00890 #endif 00891 00892 /** 00893 * @brief Removes first element. 00894 * 00895 * This is a typical stack operation. It shrinks the %list by 00896 * one. Due to the nature of a %list this operation can be done 00897 * in constant time, and only invalidates iterators/references to 00898 * the element being removed. 00899 * 00900 * Note that no data is returned, and if the first element's data 00901 * is needed, it should be retrieved before pop_front() is 00902 * called. 00903 */ 00904 void 00905 pop_front() 00906 { this->_M_erase(begin()); } 00907 00908 /** 00909 * @brief Add data to the end of the %list. 00910 * @param x Data to be added. 00911 * 00912 * This is a typical stack operation. The function creates an 00913 * element at the end of the %list and assigns the given data to 00914 * it. Due to the nature of a %list this operation can be done 00915 * in constant time, and does not invalidate iterators and 00916 * references. 00917 */ 00918 void 00919 push_back(const value_type& __x) 00920 { this->_M_insert(end(), __x); } 00921 00922 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00923 void 00924 push_back(value_type&& __x) 00925 { this->_M_insert(end(), std::move(__x)); } 00926 00927 template<typename... _Args> 00928 void 00929 emplace_back(_Args&&... __args) 00930 { this->_M_insert(end(), std::forward<_Args>(__args)...); } 00931 #endif 00932 00933 /** 00934 * @brief Removes last element. 00935 * 00936 * This is a typical stack operation. It shrinks the %list by 00937 * one. Due to the nature of a %list this operation can be done 00938 * in constant time, and only invalidates iterators/references to 00939 * the element being removed. 00940 * 00941 * Note that no data is returned, and if the last element's data 00942 * is needed, it should be retrieved before pop_back() is called. 00943 */ 00944 void 00945 pop_back() 00946 { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } 00947 00948 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00949 /** 00950 * @brief Constructs object in %list before specified iterator. 00951 * @param position A const_iterator into the %list. 00952 * @param args Arguments. 00953 * @return An iterator that points to the inserted data. 00954 * 00955 * This function will insert an object of type T constructed 00956 * with T(std::forward<Args>(args)...) before the specified 00957 * location. Due to the nature of a %list this operation can 00958 * be done in constant time, and does not invalidate iterators 00959 * and references. 00960 */ 00961 template<typename... _Args> 00962 iterator 00963 emplace(iterator __position, _Args&&... __args); 00964 #endif 00965 00966 /** 00967 * @brief Inserts given value into %list before specified iterator. 00968 * @param position An iterator into the %list. 00969 * @param x Data to be inserted. 00970 * @return An iterator that points to the inserted data. 00971 * 00972 * This function will insert a copy of the given value before 00973 * the specified location. Due to the nature of a %list this 00974 * operation can be done in constant time, and does not 00975 * invalidate iterators and references. 00976 */ 00977 iterator 00978 insert(iterator __position, const value_type& __x); 00979 00980 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00981 /** 00982 * @brief Inserts given rvalue into %list before specified iterator. 00983 * @param position An iterator into the %list. 00984 * @param x Data to be inserted. 00985 * @return An iterator that points to the inserted data. 00986 * 00987 * This function will insert a copy of the given rvalue before 00988 * the specified location. Due to the nature of a %list this 00989 * operation can be done in constant time, and does not 00990 * invalidate iterators and references. 00991 */ 00992 iterator 00993 insert(iterator __position, value_type&& __x) 00994 { return emplace(__position, std::move(__x)); } 00995 00996 /** 00997 * @brief Inserts the contents of an initializer_list into %list 00998 * before specified iterator. 00999 * @param p An iterator into the %list. 01000 * @param l An initializer_list of value_type. 01001 * 01002 * This function will insert copies of the data in the 01003 * initializer_list @a l into the %list before the location 01004 * specified by @a p. 01005 * 01006 * This operation is linear in the number of elements inserted and 01007 * does not invalidate iterators and references. 01008 */ 01009 void 01010 insert(iterator __p, initializer_list<value_type> __l) 01011 { this->insert(__p, __l.begin(), __l.end()); } 01012 #endif 01013 01014 /** 01015 * @brief Inserts a number of copies of given data into the %list. 01016 * @param position An iterator into the %list. 01017 * @param n Number of elements to be inserted. 01018 * @param x Data to be inserted. 01019 * 01020 * This function will insert a specified number of copies of the 01021 * given data before the location specified by @a position. 01022 * 01023 * This operation is linear in the number of elements inserted and 01024 * does not invalidate iterators and references. 01025 */ 01026 void 01027 insert(iterator __position, size_type __n, const value_type& __x) 01028 { 01029 list __tmp(__n, __x, _M_get_Node_allocator()); 01030 splice(__position, __tmp); 01031 } 01032 01033 /** 01034 * @brief Inserts a range into the %list. 01035 * @param position An iterator into the %list. 01036 * @param first An input iterator. 01037 * @param last An input iterator. 01038 * 01039 * This function will insert copies of the data in the range [@a 01040 * first,@a last) into the %list before the location specified by 01041 * @a position. 01042 * 01043 * This operation is linear in the number of elements inserted and 01044 * does not invalidate iterators and references. 01045 */ 01046 template<typename _InputIterator> 01047 void 01048 insert(iterator __position, _InputIterator __first, 01049 _InputIterator __last) 01050 { 01051 list __tmp(__first, __last, _M_get_Node_allocator()); 01052 splice(__position, __tmp); 01053 } 01054 01055 /** 01056 * @brief Remove element at given position. 01057 * @param position Iterator pointing to element to be erased. 01058 * @return An iterator pointing to the next element (or end()). 01059 * 01060 * This function will erase the element at the given position and thus 01061 * shorten the %list by one. 01062 * 01063 * Due to the nature of a %list this operation can be done in 01064 * constant time, and only invalidates iterators/references to 01065 * the element being removed. The user is also cautioned that 01066 * this function only erases the element, and that if the element 01067 * is itself a pointer, the pointed-to memory is not touched in 01068 * any way. Managing the pointer is the user's responsibility. 01069 */ 01070 iterator 01071 erase(iterator __position); 01072 01073 /** 01074 * @brief Remove a range of elements. 01075 * @param first Iterator pointing to the first element to be erased. 01076 * @param last Iterator pointing to one past the last element to be 01077 * erased. 01078 * @return An iterator pointing to the element pointed to by @a last 01079 * prior to erasing (or end()). 01080 * 01081 * This function will erase the elements in the range @a 01082 * [first,last) and shorten the %list accordingly. 01083 * 01084 * This operation is linear time in the size of the range and only 01085 * invalidates iterators/references to the element being removed. 01086 * The user is also cautioned that this function only erases the 01087 * elements, and that if the elements themselves are pointers, the 01088 * pointed-to memory is not touched in any way. Managing the pointer 01089 * is the user's responsibility. 01090 */ 01091 iterator 01092 erase(iterator __first, iterator __last) 01093 { 01094 while (__first != __last) 01095 __first = erase(__first); 01096 return __last; 01097 } 01098 01099 /** 01100 * @brief Swaps data with another %list. 01101 * @param x A %list of the same element and allocator types. 01102 * 01103 * This exchanges the elements between two lists in constant 01104 * time. Note that the global std::swap() function is 01105 * specialized such that std::swap(l1,l2) will feed to this 01106 * function. 01107 */ 01108 void 01109 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01110 swap(list&& __x) 01111 #else 01112 swap(list& __x) 01113 #endif 01114 { 01115 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); 01116 01117 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01118 // 431. Swapping containers with unequal allocators. 01119 std::__alloc_swap<typename _Base::_Node_alloc_type>:: 01120 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()); 01121 } 01122 01123 /** 01124 * Erases all the elements. Note that this function only erases 01125 * the elements, and that if the elements themselves are 01126 * pointers, the pointed-to memory is not touched in any way. 01127 * Managing the pointer is the user's responsibility. 01128 */ 01129 void 01130 clear() 01131 { 01132 _Base::_M_clear(); 01133 _Base::_M_init(); 01134 } 01135 01136 // [23.2.2.4] list operations 01137 /** 01138 * @brief Insert contents of another %list. 01139 * @param position Iterator referencing the element to insert before. 01140 * @param x Source list. 01141 * 01142 * The elements of @a x are inserted in constant time in front of 01143 * the element referenced by @a position. @a x becomes an empty 01144 * list. 01145 * 01146 * Requires this != @a x. 01147 */ 01148 void 01149 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01150 splice(iterator __position, list&& __x) 01151 #else 01152 splice(iterator __position, list& __x) 01153 #endif 01154 { 01155 if (!__x.empty()) 01156 { 01157 _M_check_equal_allocators(__x); 01158 01159 this->_M_transfer(__position, __x.begin(), __x.end()); 01160 } 01161 } 01162 01163 /** 01164 * @brief Insert element from another %list. 01165 * @param position Iterator referencing the element to insert before. 01166 * @param x Source list. 01167 * @param i Iterator referencing the element to move. 01168 * 01169 * Removes the element in list @a x referenced by @a i and 01170 * inserts it into the current list before @a position. 01171 */ 01172 void 01173 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01174 splice(iterator __position, list&& __x, iterator __i) 01175 #else 01176 splice(iterator __position, list& __x, iterator __i) 01177 #endif 01178 { 01179 iterator __j = __i; 01180 ++__j; 01181 if (__position == __i || __position == __j) 01182 return; 01183 01184 if (this != &__x) 01185 _M_check_equal_allocators(__x); 01186 01187 this->_M_transfer(__position, __i, __j); 01188 } 01189 01190 /** 01191 * @brief Insert range from another %list. 01192 * @param position Iterator referencing the element to insert before. 01193 * @param x Source list. 01194 * @param first Iterator referencing the start of range in x. 01195 * @param last Iterator referencing the end of range in x. 01196 * 01197 * Removes elements in the range [first,last) and inserts them 01198 * before @a position in constant time. 01199 * 01200 * Undefined if @a position is in [first,last). 01201 */ 01202 void 01203 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01204 splice(iterator __position, list&& __x, iterator __first, 01205 iterator __last) 01206 #else 01207 splice(iterator __position, list& __x, iterator __first, 01208 iterator __last) 01209 #endif 01210 { 01211 if (__first != __last) 01212 { 01213 if (this != &__x) 01214 _M_check_equal_allocators(__x); 01215 01216 this->_M_transfer(__position, __first, __last); 01217 } 01218 } 01219 01220 /** 01221 * @brief Remove all elements equal to value. 01222 * @param value The value to remove. 01223 * 01224 * Removes every element in the list equal to @a value. 01225 * Remaining elements stay in list order. Note that this 01226 * function only erases the elements, and that if the elements 01227 * themselves are pointers, the pointed-to memory is not 01228 * touched in any way. Managing the pointer is the user's 01229 * responsibility. 01230 */ 01231 void 01232 remove(const _Tp& __value); 01233 01234 /** 01235 * @brief Remove all elements satisfying a predicate. 01236 * @param Predicate Unary predicate function or object. 01237 * 01238 * Removes every element in the list for which the predicate 01239 * returns true. Remaining elements stay in list order. Note 01240 * that this function only erases the elements, and that if the 01241 * elements themselves are pointers, the pointed-to memory is 01242 * not touched in any way. Managing the pointer is the user's 01243 * responsibility. 01244 */ 01245 template<typename _Predicate> 01246 void 01247 remove_if(_Predicate); 01248 01249 /** 01250 * @brief Remove consecutive duplicate elements. 01251 * 01252 * For each consecutive set of elements with the same value, 01253 * remove all but the first one. Remaining elements stay in 01254 * list order. Note that this function only erases the 01255 * elements, and that if the elements themselves are pointers, 01256 * the pointed-to memory is not touched in any way. Managing 01257 * the pointer is the user's responsibility. 01258 */ 01259 void 01260 unique(); 01261 01262 /** 01263 * @brief Remove consecutive elements satisfying a predicate. 01264 * @param BinaryPredicate Binary predicate function or object. 01265 * 01266 * For each consecutive set of elements [first,last) that 01267 * satisfy predicate(first,i) where i is an iterator in 01268 * [first,last), remove all but the first one. Remaining 01269 * elements stay in list order. Note that this function only 01270 * erases the elements, and that if the elements themselves are 01271 * pointers, the pointed-to memory is not touched in any way. 01272 * Managing the pointer is the user's responsibility. 01273 */ 01274 template<typename _BinaryPredicate> 01275 void 01276 unique(_BinaryPredicate); 01277 01278 /** 01279 * @brief Merge sorted lists. 01280 * @param x Sorted list to merge. 01281 * 01282 * Assumes that both @a x and this list are sorted according to 01283 * operator<(). Merges elements of @a x into this list in 01284 * sorted order, leaving @a x empty when complete. Elements in 01285 * this list precede elements in @a x that are equal. 01286 */ 01287 void 01288 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01289 merge(list&& __x); 01290 #else 01291 merge(list& __x); 01292 #endif 01293 01294 /** 01295 * @brief Merge sorted lists according to comparison function. 01296 * @param x Sorted list to merge. 01297 * @param StrictWeakOrdering Comparison function defining 01298 * sort order. 01299 * 01300 * Assumes that both @a x and this list are sorted according to 01301 * StrictWeakOrdering. Merges elements of @a x into this list 01302 * in sorted order, leaving @a x empty when complete. Elements 01303 * in this list precede elements in @a x that are equivalent 01304 * according to StrictWeakOrdering(). 01305 */ 01306 template<typename _StrictWeakOrdering> 01307 void 01308 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01309 merge(list&&, _StrictWeakOrdering); 01310 #else 01311 merge(list&, _StrictWeakOrdering); 01312 #endif 01313 01314 /** 01315 * @brief Reverse the elements in list. 01316 * 01317 * Reverse the order of elements in the list in linear time. 01318 */ 01319 void 01320 reverse() 01321 { this->_M_impl._M_node.reverse(); } 01322 01323 /** 01324 * @brief Sort the elements. 01325 * 01326 * Sorts the elements of this list in NlogN time. Equivalent 01327 * elements remain in list order. 01328 */ 01329 void 01330 sort(); 01331 01332 /** 01333 * @brief Sort the elements according to comparison function. 01334 * 01335 * Sorts the elements of this list in NlogN time. Equivalent 01336 * elements remain in list order. 01337 */ 01338 template<typename _StrictWeakOrdering> 01339 void 01340 sort(_StrictWeakOrdering); 01341 01342 protected: 01343 // Internal constructor functions follow. 01344 01345 // Called by the range constructor to implement [23.1.1]/9 01346 01347 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01348 // 438. Ambiguity in the "do the right thing" clause 01349 template<typename _Integer> 01350 void 01351 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 01352 { _M_fill_initialize(static_cast<size_type>(__n), __x); } 01353 01354 // Called by the range constructor to implement [23.1.1]/9 01355 template<typename _InputIterator> 01356 void 01357 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01358 __false_type) 01359 { 01360 for (; __first != __last; ++__first) 01361 push_back(*__first); 01362 } 01363 01364 // Called by list(n,v,a), and the range constructor when it turns out 01365 // to be the same thing. 01366 void 01367 _M_fill_initialize(size_type __n, const value_type& __x) 01368 { 01369 for (; __n > 0; --__n) 01370 push_back(__x); 01371 } 01372 01373 01374 // Internal assign functions follow. 01375 01376 // Called by the range assign to implement [23.1.1]/9 01377 01378 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01379 // 438. Ambiguity in the "do the right thing" clause 01380 template<typename _Integer> 01381 void 01382 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01383 { _M_fill_assign(__n, __val); } 01384 01385 // Called by the range assign to implement [23.1.1]/9 01386 template<typename _InputIterator> 01387 void 01388 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01389 __false_type); 01390 01391 // Called by assign(n,t), and the range assign when it turns out 01392 // to be the same thing. 01393 void 01394 _M_fill_assign(size_type __n, const value_type& __val); 01395 01396 01397 // Moves the elements from [first,last) before position. 01398 void 01399 _M_transfer(iterator __position, iterator __first, iterator __last) 01400 { __position._M_node->transfer(__first._M_node, __last._M_node); } 01401 01402 // Inserts new element at position given and with value given. 01403 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 01404 void 01405 _M_insert(iterator __position, const value_type& __x) 01406 { 01407 _Node* __tmp = _M_create_node(__x); 01408 __tmp->hook(__position._M_node); 01409 } 01410 #else 01411 template<typename... _Args> 01412 void 01413 _M_insert(iterator __position, _Args&&... __args) 01414 { 01415 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 01416 __tmp->hook(__position._M_node); 01417 } 01418 #endif 01419 01420 // Erases element at position given. 01421 void 01422 _M_erase(iterator __position) 01423 { 01424 __position._M_node->unhook(); 01425 _Node* __n = static_cast<_Node*>(__position._M_node); 01426 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01427 _M_get_Node_allocator().destroy(__n); 01428 #else 01429 _M_get_Tp_allocator().destroy(&__n->_M_data); 01430 #endif 01431 _M_put_node(__n); 01432 } 01433 01434 // To implement the splice (and merge) bits of N1599. 01435 void 01436 _M_check_equal_allocators(list& __x) 01437 { 01438 if (std::__alloc_neq<typename _Base::_Node_alloc_type>:: 01439 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) 01440 __throw_runtime_error(__N("list::_M_check_equal_allocators")); 01441 } 01442 }; 01443 01444 /** 01445 * @brief List equality comparison. 01446 * @param x A %list. 01447 * @param y A %list of the same type as @a x. 01448 * @return True iff the size and elements of the lists are equal. 01449 * 01450 * This is an equivalence relation. It is linear in the size of 01451 * the lists. Lists are considered equivalent if their sizes are 01452 * equal, and if corresponding elements compare equal. 01453 */ 01454 template<typename _Tp, typename _Alloc> 01455 inline bool 01456 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 01457 { 01458 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; 01459 const_iterator __end1 = __x.end(); 01460 const_iterator __end2 = __y.end(); 01461 01462 const_iterator __i1 = __x.begin(); 01463 const_iterator __i2 = __y.begin(); 01464 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 01465 { 01466 ++__i1; 01467 ++__i2; 01468 } 01469 return __i1 == __end1 && __i2 == __end2; 01470 } 01471 01472 /** 01473 * @brief List ordering relation. 01474 * @param x A %list. 01475 * @param y A %list of the same type as @a x. 01476 * @return True iff @a x is lexicographically less than @a y. 01477 * 01478 * This is a total ordering relation. It is linear in the size of the 01479 * lists. The elements must be comparable with @c <. 01480 * 01481 * See std::lexicographical_compare() for how the determination is made. 01482 */ 01483 template<typename _Tp, typename _Alloc> 01484 inline bool 01485 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 01486 { return std::lexicographical_compare(__x.begin(), __x.end(), 01487 __y.begin(), __y.end()); } 01488 01489 /// Based on operator== 01490 template<typename _Tp, typename _Alloc> 01491 inline bool 01492 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 01493 { return !(__x == __y); } 01494 01495 /// Based on operator< 01496 template<typename _Tp, typename _Alloc> 01497 inline bool 01498 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 01499 { return __y < __x; } 01500 01501 /// Based on operator< 01502 template<typename _Tp, typename _Alloc> 01503 inline bool 01504 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 01505 { return !(__y < __x); } 01506 01507 /// Based on operator< 01508 template<typename _Tp, typename _Alloc> 01509 inline bool 01510 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 01511 { return !(__x < __y); } 01512 01513 /// See std::list::swap(). 01514 template<typename _Tp, typename _Alloc> 01515 inline void 01516 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 01517 { __x.swap(__y); } 01518 01519 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01520 template<typename _Tp, typename _Alloc> 01521 inline void 01522 swap(list<_Tp, _Alloc>&& __x, list<_Tp, _Alloc>& __y) 01523 { __x.swap(__y); } 01524 01525 template<typename _Tp, typename _Alloc> 01526 inline void 01527 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>&& __y) 01528 { __x.swap(__y); } 01529 #endif 01530 01531 _GLIBCXX_END_NESTED_NAMESPACE 01532 01533 #endif /* _STL_LIST_H */