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