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