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