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