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