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