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