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