libstdc++
|
00001 // <forward_list.h> -*- C++ -*- 00002 00003 // Copyright (C) 2008-2013 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 /** @file bits/forward_list.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{forward_list} 00028 */ 00029 00030 #ifndef _FORWARD_LIST_H 00031 #define _FORWARD_LIST_H 1 00032 00033 #pragma GCC system_header 00034 00035 #include <memory> 00036 #if __cplusplus >= 201103L 00037 #include <initializer_list> 00038 #endif 00039 00040 namespace std _GLIBCXX_VISIBILITY(default) 00041 { 00042 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00043 00044 /** 00045 * @brief A helper basic node class for %forward_list. 00046 * This is just a linked list with nothing inside it. 00047 * There are purely list shuffling utility methods here. 00048 */ 00049 struct _Fwd_list_node_base 00050 { 00051 _Fwd_list_node_base() = default; 00052 00053 _Fwd_list_node_base* _M_next = nullptr; 00054 00055 _Fwd_list_node_base* 00056 _M_transfer_after(_Fwd_list_node_base* __begin, 00057 _Fwd_list_node_base* __end) 00058 { 00059 _Fwd_list_node_base* __keep = __begin->_M_next; 00060 if (__end) 00061 { 00062 __begin->_M_next = __end->_M_next; 00063 __end->_M_next = _M_next; 00064 } 00065 else 00066 __begin->_M_next = 0; 00067 _M_next = __keep; 00068 return __end; 00069 } 00070 00071 void 00072 _M_reverse_after() noexcept 00073 { 00074 _Fwd_list_node_base* __tail = _M_next; 00075 if (!__tail) 00076 return; 00077 while (_Fwd_list_node_base* __temp = __tail->_M_next) 00078 { 00079 _Fwd_list_node_base* __keep = _M_next; 00080 _M_next = __temp; 00081 __tail->_M_next = __temp->_M_next; 00082 _M_next->_M_next = __keep; 00083 } 00084 } 00085 }; 00086 00087 /** 00088 * @brief A helper node class for %forward_list. 00089 * This is just a linked list with uninitialized storage for a 00090 * data value in each node. 00091 * There is a sorting utility method. 00092 */ 00093 template<typename _Tp> 00094 struct _Fwd_list_node 00095 : public _Fwd_list_node_base 00096 { 00097 _Fwd_list_node() = default; 00098 00099 typename aligned_storage<sizeof(_Tp), alignment_of<_Tp>::value>::type 00100 _M_storage; 00101 00102 _Tp* 00103 _M_valptr() noexcept 00104 { 00105 return static_cast<_Tp*>(static_cast<void*>(&_M_storage)); 00106 } 00107 00108 const _Tp* 00109 _M_valptr() const noexcept 00110 { 00111 return static_cast<const _Tp*>(static_cast<const void*>(&_M_storage)); 00112 } 00113 }; 00114 00115 /** 00116 * @brief A forward_list::iterator. 00117 * 00118 * All the functions are op overloads. 00119 */ 00120 template<typename _Tp> 00121 struct _Fwd_list_iterator 00122 { 00123 typedef _Fwd_list_iterator<_Tp> _Self; 00124 typedef _Fwd_list_node<_Tp> _Node; 00125 00126 typedef _Tp value_type; 00127 typedef _Tp* pointer; 00128 typedef _Tp& reference; 00129 typedef ptrdiff_t difference_type; 00130 typedef std::forward_iterator_tag iterator_category; 00131 00132 _Fwd_list_iterator() 00133 : _M_node() { } 00134 00135 explicit 00136 _Fwd_list_iterator(_Fwd_list_node_base* __n) 00137 : _M_node(__n) { } 00138 00139 reference 00140 operator*() const 00141 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } 00142 00143 pointer 00144 operator->() const 00145 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } 00146 00147 _Self& 00148 operator++() 00149 { 00150 _M_node = _M_node->_M_next; 00151 return *this; 00152 } 00153 00154 _Self 00155 operator++(int) 00156 { 00157 _Self __tmp(*this); 00158 _M_node = _M_node->_M_next; 00159 return __tmp; 00160 } 00161 00162 bool 00163 operator==(const _Self& __x) const 00164 { return _M_node == __x._M_node; } 00165 00166 bool 00167 operator!=(const _Self& __x) const 00168 { return _M_node != __x._M_node; } 00169 00170 _Self 00171 _M_next() const 00172 { 00173 if (_M_node) 00174 return _Fwd_list_iterator(_M_node->_M_next); 00175 else 00176 return _Fwd_list_iterator(0); 00177 } 00178 00179 _Fwd_list_node_base* _M_node; 00180 }; 00181 00182 /** 00183 * @brief A forward_list::const_iterator. 00184 * 00185 * All the functions are op overloads. 00186 */ 00187 template<typename _Tp> 00188 struct _Fwd_list_const_iterator 00189 { 00190 typedef _Fwd_list_const_iterator<_Tp> _Self; 00191 typedef const _Fwd_list_node<_Tp> _Node; 00192 typedef _Fwd_list_iterator<_Tp> iterator; 00193 00194 typedef _Tp value_type; 00195 typedef const _Tp* pointer; 00196 typedef const _Tp& reference; 00197 typedef ptrdiff_t difference_type; 00198 typedef std::forward_iterator_tag iterator_category; 00199 00200 _Fwd_list_const_iterator() 00201 : _M_node() { } 00202 00203 explicit 00204 _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) 00205 : _M_node(__n) { } 00206 00207 _Fwd_list_const_iterator(const iterator& __iter) 00208 : _M_node(__iter._M_node) { } 00209 00210 reference 00211 operator*() const 00212 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } 00213 00214 pointer 00215 operator->() const 00216 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } 00217 00218 _Self& 00219 operator++() 00220 { 00221 _M_node = _M_node->_M_next; 00222 return *this; 00223 } 00224 00225 _Self 00226 operator++(int) 00227 { 00228 _Self __tmp(*this); 00229 _M_node = _M_node->_M_next; 00230 return __tmp; 00231 } 00232 00233 bool 00234 operator==(const _Self& __x) const 00235 { return _M_node == __x._M_node; } 00236 00237 bool 00238 operator!=(const _Self& __x) const 00239 { return _M_node != __x._M_node; } 00240 00241 _Self 00242 _M_next() const 00243 { 00244 if (this->_M_node) 00245 return _Fwd_list_const_iterator(_M_node->_M_next); 00246 else 00247 return _Fwd_list_const_iterator(0); 00248 } 00249 00250 const _Fwd_list_node_base* _M_node; 00251 }; 00252 00253 /** 00254 * @brief Forward list iterator equality comparison. 00255 */ 00256 template<typename _Tp> 00257 inline bool 00258 operator==(const _Fwd_list_iterator<_Tp>& __x, 00259 const _Fwd_list_const_iterator<_Tp>& __y) 00260 { return __x._M_node == __y._M_node; } 00261 00262 /** 00263 * @brief Forward list iterator inequality comparison. 00264 */ 00265 template<typename _Tp> 00266 inline bool 00267 operator!=(const _Fwd_list_iterator<_Tp>& __x, 00268 const _Fwd_list_const_iterator<_Tp>& __y) 00269 { return __x._M_node != __y._M_node; } 00270 00271 /** 00272 * @brief Base class for %forward_list. 00273 */ 00274 template<typename _Tp, typename _Alloc> 00275 struct _Fwd_list_base 00276 { 00277 protected: 00278 typedef typename __gnu_cxx::__alloc_traits<_Alloc> _Alloc_traits; 00279 typedef typename _Alloc_traits::template rebind<_Tp>::other 00280 _Tp_alloc_type; 00281 00282 typedef typename _Alloc_traits::template 00283 rebind<_Fwd_list_node<_Tp>>::other _Node_alloc_type; 00284 00285 typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; 00286 00287 struct _Fwd_list_impl 00288 : public _Node_alloc_type 00289 { 00290 _Fwd_list_node_base _M_head; 00291 00292 _Fwd_list_impl() 00293 : _Node_alloc_type(), _M_head() 00294 { } 00295 00296 _Fwd_list_impl(const _Node_alloc_type& __a) 00297 : _Node_alloc_type(__a), _M_head() 00298 { } 00299 00300 _Fwd_list_impl(_Node_alloc_type&& __a) 00301 : _Node_alloc_type(std::move(__a)), _M_head() 00302 { } 00303 }; 00304 00305 _Fwd_list_impl _M_impl; 00306 00307 public: 00308 typedef _Fwd_list_iterator<_Tp> iterator; 00309 typedef _Fwd_list_const_iterator<_Tp> const_iterator; 00310 typedef _Fwd_list_node<_Tp> _Node; 00311 00312 _Node_alloc_type& 00313 _M_get_Node_allocator() noexcept 00314 { return *static_cast<_Node_alloc_type*>(&this->_M_impl); } 00315 00316 const _Node_alloc_type& 00317 _M_get_Node_allocator() const noexcept 00318 { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); } 00319 00320 _Fwd_list_base() 00321 : _M_impl() { } 00322 00323 _Fwd_list_base(const _Node_alloc_type& __a) 00324 : _M_impl(__a) { } 00325 00326 _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a); 00327 00328 _Fwd_list_base(_Fwd_list_base&& __lst) 00329 : _M_impl(std::move(__lst._M_get_Node_allocator())) 00330 { 00331 this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next; 00332 __lst._M_impl._M_head._M_next = 0; 00333 } 00334 00335 ~_Fwd_list_base() 00336 { _M_erase_after(&_M_impl._M_head, 0); } 00337 00338 protected: 00339 00340 _Node* 00341 _M_get_node() 00342 { return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); } 00343 00344 template<typename... _Args> 00345 _Node* 00346 _M_create_node(_Args&&... __args) 00347 { 00348 _Node* __node = this->_M_get_node(); 00349 __try 00350 { 00351 _Tp_alloc_type __a(_M_get_Node_allocator()); 00352 typedef allocator_traits<_Tp_alloc_type> _Alloc_traits; 00353 ::new ((void*)__node) _Node(); 00354 _Alloc_traits::construct(__a, __node->_M_valptr(), 00355 std::forward<_Args>(__args)...); 00356 } 00357 __catch(...) 00358 { 00359 this->_M_put_node(__node); 00360 __throw_exception_again; 00361 } 00362 return __node; 00363 } 00364 00365 template<typename... _Args> 00366 _Fwd_list_node_base* 00367 _M_insert_after(const_iterator __pos, _Args&&... __args); 00368 00369 void 00370 _M_put_node(_Node* __p) 00371 { _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 00372 00373 _Fwd_list_node_base* 00374 _M_erase_after(_Fwd_list_node_base* __pos); 00375 00376 _Fwd_list_node_base* 00377 _M_erase_after(_Fwd_list_node_base* __pos, 00378 _Fwd_list_node_base* __last); 00379 }; 00380 00381 /** 00382 * @brief A standard container with linear time access to elements, 00383 * and fixed time insertion/deletion at any point in the sequence. 00384 * 00385 * @ingroup sequences 00386 * 00387 * @tparam _Tp Type of element. 00388 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. 00389 * 00390 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00391 * <a href="tables.html#67">sequence</a>, including the 00392 * <a href="tables.html#68">optional sequence requirements</a> with the 00393 * %exception of @c at and @c operator[]. 00394 * 00395 * This is a @e singly @e linked %list. Traversal up the 00396 * %list requires linear time, but adding and removing elements (or 00397 * @e nodes) is done in constant time, regardless of where the 00398 * change takes place. Unlike std::vector and std::deque, 00399 * random-access iterators are not provided, so subscripting ( @c 00400 * [] ) access is not allowed. For algorithms which only need 00401 * sequential access, this lack makes no difference. 00402 * 00403 * Also unlike the other standard containers, std::forward_list provides 00404 * specialized algorithms %unique to linked lists, such as 00405 * splicing, sorting, and in-place reversal. 00406 */ 00407 template<typename _Tp, typename _Alloc = allocator<_Tp> > 00408 class forward_list : private _Fwd_list_base<_Tp, _Alloc> 00409 { 00410 private: 00411 typedef _Fwd_list_base<_Tp, _Alloc> _Base; 00412 typedef _Fwd_list_node<_Tp> _Node; 00413 typedef _Fwd_list_node_base _Node_base; 00414 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 00415 typedef typename _Base::_Node_alloc_type _Node_alloc_type; 00416 typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; 00417 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; 00418 00419 public: 00420 // types: 00421 typedef _Tp value_type; 00422 typedef typename _Alloc_traits::pointer pointer; 00423 typedef typename _Alloc_traits::const_pointer const_pointer; 00424 typedef typename _Alloc_traits::reference reference; 00425 typedef typename _Alloc_traits::const_reference const_reference; 00426 00427 typedef _Fwd_list_iterator<_Tp> iterator; 00428 typedef _Fwd_list_const_iterator<_Tp> const_iterator; 00429 typedef std::size_t size_type; 00430 typedef std::ptrdiff_t difference_type; 00431 typedef _Alloc allocator_type; 00432 00433 // 23.3.4.2 construct/copy/destroy: 00434 00435 /** 00436 * @brief Creates a %forward_list with no elements. 00437 * @param __al An allocator object. 00438 */ 00439 explicit 00440 forward_list(const _Alloc& __al = _Alloc()) 00441 : _Base(_Node_alloc_type(__al)) 00442 { } 00443 00444 /** 00445 * @brief Copy constructor with allocator argument. 00446 * @param __list Input list to copy. 00447 * @param __al An allocator object. 00448 */ 00449 forward_list(const forward_list& __list, const _Alloc& __al) 00450 : _Base(_Node_alloc_type(__al)) 00451 { _M_range_initialize(__list.begin(), __list.end()); } 00452 00453 /** 00454 * @brief Move constructor with allocator argument. 00455 * @param __list Input list to move. 00456 * @param __al An allocator object. 00457 */ 00458 forward_list(forward_list&& __list, const _Alloc& __al) 00459 noexcept(_Node_alloc_traits::_S_always_equal()) 00460 : _Base(std::move(__list), _Node_alloc_type(__al)) 00461 { } 00462 00463 /** 00464 * @brief Creates a %forward_list with default constructed elements. 00465 * @param __n The number of elements to initially create. 00466 * 00467 * This constructor creates the %forward_list with @a __n default 00468 * constructed elements. 00469 */ 00470 explicit 00471 forward_list(size_type __n, const _Alloc& __al = _Alloc()) 00472 : _Base(_Node_alloc_type(__al)) 00473 { _M_default_initialize(__n); } 00474 00475 /** 00476 * @brief Creates a %forward_list with copies of an exemplar element. 00477 * @param __n The number of elements to initially create. 00478 * @param __value An element to copy. 00479 * @param __al An allocator object. 00480 * 00481 * This constructor fills the %forward_list with @a __n copies of 00482 * @a __value. 00483 */ 00484 forward_list(size_type __n, const _Tp& __value, 00485 const _Alloc& __al = _Alloc()) 00486 : _Base(_Node_alloc_type(__al)) 00487 { _M_fill_initialize(__n, __value); } 00488 00489 /** 00490 * @brief Builds a %forward_list from a range. 00491 * @param __first An input iterator. 00492 * @param __last An input iterator. 00493 * @param __al An allocator object. 00494 * 00495 * Create a %forward_list consisting of copies of the elements from 00496 * [@a __first,@a __last). This is linear in N (where N is 00497 * distance(@a __first,@a __last)). 00498 */ 00499 template<typename _InputIterator, 00500 typename = std::_RequireInputIter<_InputIterator>> 00501 forward_list(_InputIterator __first, _InputIterator __last, 00502 const _Alloc& __al = _Alloc()) 00503 : _Base(_Node_alloc_type(__al)) 00504 { _M_range_initialize(__first, __last); } 00505 00506 /** 00507 * @brief The %forward_list copy constructor. 00508 * @param __list A %forward_list of identical element and allocator 00509 * types. 00510 */ 00511 forward_list(const forward_list& __list) 00512 : _Base(_Node_alloc_traits::_S_select_on_copy( 00513 __list._M_get_Node_allocator())) 00514 { _M_range_initialize(__list.begin(), __list.end()); } 00515 00516 /** 00517 * @brief The %forward_list move constructor. 00518 * @param __list A %forward_list of identical element and allocator 00519 * types. 00520 * 00521 * The newly-created %forward_list contains the exact contents of @a 00522 * __list. The contents of @a __list are a valid, but unspecified 00523 * %forward_list. 00524 */ 00525 forward_list(forward_list&& __list) noexcept 00526 : _Base(std::move(__list)) { } 00527 00528 /** 00529 * @brief Builds a %forward_list from an initializer_list 00530 * @param __il An initializer_list of value_type. 00531 * @param __al An allocator object. 00532 * 00533 * Create a %forward_list consisting of copies of the elements 00534 * in the initializer_list @a __il. This is linear in __il.size(). 00535 */ 00536 forward_list(std::initializer_list<_Tp> __il, 00537 const _Alloc& __al = _Alloc()) 00538 : _Base(_Node_alloc_type(__al)) 00539 { _M_range_initialize(__il.begin(), __il.end()); } 00540 00541 /** 00542 * @brief The forward_list dtor. 00543 */ 00544 ~forward_list() noexcept 00545 { } 00546 00547 /** 00548 * @brief The %forward_list assignment operator. 00549 * @param __list A %forward_list of identical element and allocator 00550 * types. 00551 * 00552 * All the elements of @a __list are copied, but unlike the copy 00553 * constructor, the allocator object is not copied. 00554 */ 00555 forward_list& 00556 operator=(const forward_list& __list); 00557 00558 /** 00559 * @brief The %forward_list move assignment operator. 00560 * @param __list A %forward_list of identical element and allocator 00561 * types. 00562 * 00563 * The contents of @a __list are moved into this %forward_list 00564 * (without copying, if the allocators permit it). 00565 * @a __list is a valid, but unspecified %forward_list 00566 */ 00567 forward_list& 00568 operator=(forward_list&& __list) 00569 noexcept(_Node_alloc_traits::_S_nothrow_move()) 00570 { 00571 constexpr bool __move_storage = 00572 _Node_alloc_traits::_S_propagate_on_move_assign() 00573 || _Node_alloc_traits::_S_always_equal(); 00574 _M_move_assign(std::move(__list), 00575 integral_constant<bool, __move_storage>()); 00576 return *this; 00577 } 00578 00579 /** 00580 * @brief The %forward_list initializer list assignment operator. 00581 * @param __il An initializer_list of value_type. 00582 * 00583 * Replace the contents of the %forward_list with copies of the 00584 * elements in the initializer_list @a __il. This is linear in 00585 * __il.size(). 00586 */ 00587 forward_list& 00588 operator=(std::initializer_list<_Tp> __il) 00589 { 00590 assign(__il); 00591 return *this; 00592 } 00593 00594 /** 00595 * @brief Assigns a range to a %forward_list. 00596 * @param __first An input iterator. 00597 * @param __last An input iterator. 00598 * 00599 * This function fills a %forward_list with copies of the elements 00600 * in the range [@a __first,@a __last). 00601 * 00602 * Note that the assignment completely changes the %forward_list and 00603 * that the number of elements of the resulting %forward_list is the 00604 * same as the number of elements assigned. Old data is lost. 00605 */ 00606 template<typename _InputIterator, 00607 typename = std::_RequireInputIter<_InputIterator>> 00608 void 00609 assign(_InputIterator __first, _InputIterator __last) 00610 { 00611 typedef is_assignable<_Tp, decltype(*__first)> __assignable; 00612 _M_assign(__first, __last, __assignable()); 00613 } 00614 00615 /** 00616 * @brief Assigns a given value to a %forward_list. 00617 * @param __n Number of elements to be assigned. 00618 * @param __val Value to be assigned. 00619 * 00620 * This function fills a %forward_list with @a __n copies of the 00621 * given value. Note that the assignment completely changes the 00622 * %forward_list, and that the resulting %forward_list has __n 00623 * elements. Old data is lost. 00624 */ 00625 void 00626 assign(size_type __n, const _Tp& __val) 00627 { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); } 00628 00629 /** 00630 * @brief Assigns an initializer_list to a %forward_list. 00631 * @param __il An initializer_list of value_type. 00632 * 00633 * Replace the contents of the %forward_list with copies of the 00634 * elements in the initializer_list @a __il. This is linear in 00635 * il.size(). 00636 */ 00637 void 00638 assign(std::initializer_list<_Tp> __il) 00639 { assign(__il.begin(), __il.end()); } 00640 00641 /// Get a copy of the memory allocation object. 00642 allocator_type 00643 get_allocator() const noexcept 00644 { return allocator_type(this->_M_get_Node_allocator()); } 00645 00646 // 23.3.4.3 iterators: 00647 00648 /** 00649 * Returns a read/write iterator that points before the first element 00650 * in the %forward_list. Iteration is done in ordinary element order. 00651 */ 00652 iterator 00653 before_begin() noexcept 00654 { return iterator(&this->_M_impl._M_head); } 00655 00656 /** 00657 * Returns a read-only (constant) iterator that points before the 00658 * first element in the %forward_list. Iteration is done in ordinary 00659 * element order. 00660 */ 00661 const_iterator 00662 before_begin() const noexcept 00663 { return const_iterator(&this->_M_impl._M_head); } 00664 00665 /** 00666 * Returns a read/write iterator that points to the first element 00667 * in the %forward_list. Iteration is done in ordinary element order. 00668 */ 00669 iterator 00670 begin() noexcept 00671 { return iterator(this->_M_impl._M_head._M_next); } 00672 00673 /** 00674 * Returns a read-only (constant) iterator that points to the first 00675 * element in the %forward_list. Iteration is done in ordinary 00676 * element order. 00677 */ 00678 const_iterator 00679 begin() const noexcept 00680 { return const_iterator(this->_M_impl._M_head._M_next); } 00681 00682 /** 00683 * Returns a read/write iterator that points one past the last 00684 * element in the %forward_list. Iteration is done in ordinary 00685 * element order. 00686 */ 00687 iterator 00688 end() noexcept 00689 { return iterator(0); } 00690 00691 /** 00692 * Returns a read-only iterator that points one past the last 00693 * element in the %forward_list. Iteration is done in ordinary 00694 * element order. 00695 */ 00696 const_iterator 00697 end() const noexcept 00698 { return const_iterator(0); } 00699 00700 /** 00701 * Returns a read-only (constant) iterator that points to the 00702 * first element in the %forward_list. Iteration is done in ordinary 00703 * element order. 00704 */ 00705 const_iterator 00706 cbegin() const noexcept 00707 { return const_iterator(this->_M_impl._M_head._M_next); } 00708 00709 /** 00710 * Returns a read-only (constant) iterator that points before the 00711 * first element in the %forward_list. Iteration is done in ordinary 00712 * element order. 00713 */ 00714 const_iterator 00715 cbefore_begin() const noexcept 00716 { return const_iterator(&this->_M_impl._M_head); } 00717 00718 /** 00719 * Returns a read-only (constant) iterator that points one past 00720 * the last element in the %forward_list. Iteration is done in 00721 * ordinary element order. 00722 */ 00723 const_iterator 00724 cend() const noexcept 00725 { return const_iterator(0); } 00726 00727 /** 00728 * Returns true if the %forward_list is empty. (Thus begin() would 00729 * equal end().) 00730 */ 00731 bool 00732 empty() const noexcept 00733 { return this->_M_impl._M_head._M_next == 0; } 00734 00735 /** 00736 * Returns the largest possible number of elements of %forward_list. 00737 */ 00738 size_type 00739 max_size() const noexcept 00740 { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); } 00741 00742 // 23.3.4.4 element access: 00743 00744 /** 00745 * Returns a read/write reference to the data at the first 00746 * element of the %forward_list. 00747 */ 00748 reference 00749 front() 00750 { 00751 _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next); 00752 return *__front->_M_valptr(); 00753 } 00754 00755 /** 00756 * Returns a read-only (constant) reference to the data at the first 00757 * element of the %forward_list. 00758 */ 00759 const_reference 00760 front() const 00761 { 00762 _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next); 00763 return *__front->_M_valptr(); 00764 } 00765 00766 // 23.3.4.5 modifiers: 00767 00768 /** 00769 * @brief Constructs object in %forward_list at the front of the 00770 * list. 00771 * @param __args Arguments. 00772 * 00773 * This function will insert an object of type Tp constructed 00774 * with Tp(std::forward<Args>(args)...) at the front of the list 00775 * Due to the nature of a %forward_list this operation can 00776 * be done in constant time, and does not invalidate iterators 00777 * and references. 00778 */ 00779 template<typename... _Args> 00780 void 00781 emplace_front(_Args&&... __args) 00782 { this->_M_insert_after(cbefore_begin(), 00783 std::forward<_Args>(__args)...); } 00784 00785 /** 00786 * @brief Add data to the front of the %forward_list. 00787 * @param __val Data to be added. 00788 * 00789 * This is a typical stack operation. The function creates an 00790 * element at the front of the %forward_list and assigns the given 00791 * data to it. Due to the nature of a %forward_list this operation 00792 * can be done in constant time, and does not invalidate iterators 00793 * and references. 00794 */ 00795 void 00796 push_front(const _Tp& __val) 00797 { this->_M_insert_after(cbefore_begin(), __val); } 00798 00799 /** 00800 * 00801 */ 00802 void 00803 push_front(_Tp&& __val) 00804 { this->_M_insert_after(cbefore_begin(), std::move(__val)); } 00805 00806 /** 00807 * @brief Removes first element. 00808 * 00809 * This is a typical stack operation. It shrinks the %forward_list 00810 * by one. Due to the nature of a %forward_list this operation can 00811 * be done in constant time, and only invalidates iterators/references 00812 * to the element being removed. 00813 * 00814 * Note that no data is returned, and if the first element's data 00815 * is needed, it should be retrieved before pop_front() is 00816 * called. 00817 */ 00818 void 00819 pop_front() 00820 { this->_M_erase_after(&this->_M_impl._M_head); } 00821 00822 /** 00823 * @brief Constructs object in %forward_list after the specified 00824 * iterator. 00825 * @param __pos A const_iterator into the %forward_list. 00826 * @param __args Arguments. 00827 * @return An iterator that points to the inserted data. 00828 * 00829 * This function will insert an object of type T constructed 00830 * with T(std::forward<Args>(args)...) after the specified 00831 * location. Due to the nature of a %forward_list this operation can 00832 * be done in constant time, and does not invalidate iterators 00833 * and references. 00834 */ 00835 template<typename... _Args> 00836 iterator 00837 emplace_after(const_iterator __pos, _Args&&... __args) 00838 { return iterator(this->_M_insert_after(__pos, 00839 std::forward<_Args>(__args)...)); } 00840 00841 /** 00842 * @brief Inserts given value into %forward_list after specified 00843 * iterator. 00844 * @param __pos An iterator into the %forward_list. 00845 * @param __val Data to be inserted. 00846 * @return An iterator that points to the inserted data. 00847 * 00848 * This function will insert a copy of the given value after 00849 * the specified location. Due to the nature of a %forward_list this 00850 * operation can be done in constant time, and does not 00851 * invalidate iterators and references. 00852 */ 00853 iterator 00854 insert_after(const_iterator __pos, const _Tp& __val) 00855 { return iterator(this->_M_insert_after(__pos, __val)); } 00856 00857 /** 00858 * 00859 */ 00860 iterator 00861 insert_after(const_iterator __pos, _Tp&& __val) 00862 { return iterator(this->_M_insert_after(__pos, std::move(__val))); } 00863 00864 /** 00865 * @brief Inserts a number of copies of given data into the 00866 * %forward_list. 00867 * @param __pos An iterator into the %forward_list. 00868 * @param __n Number of elements to be inserted. 00869 * @param __val Data to be inserted. 00870 * @return An iterator pointing to the last inserted copy of 00871 * @a val or @a pos if @a n == 0. 00872 * 00873 * This function will insert a specified number of copies of the 00874 * given data after the location specified by @a pos. 00875 * 00876 * This operation is linear in the number of elements inserted and 00877 * does not invalidate iterators and references. 00878 */ 00879 iterator 00880 insert_after(const_iterator __pos, size_type __n, const _Tp& __val); 00881 00882 /** 00883 * @brief Inserts a range into the %forward_list. 00884 * @param __pos An iterator into the %forward_list. 00885 * @param __first An input iterator. 00886 * @param __last An input iterator. 00887 * @return An iterator pointing to the last inserted element or 00888 * @a __pos if @a __first == @a __last. 00889 * 00890 * This function will insert copies of the data in the range 00891 * [@a __first,@a __last) into the %forward_list after the 00892 * location specified by @a __pos. 00893 * 00894 * This operation is linear in the number of elements inserted and 00895 * does not invalidate iterators and references. 00896 */ 00897 template<typename _InputIterator, 00898 typename = std::_RequireInputIter<_InputIterator>> 00899 iterator 00900 insert_after(const_iterator __pos, 00901 _InputIterator __first, _InputIterator __last); 00902 00903 /** 00904 * @brief Inserts the contents of an initializer_list into 00905 * %forward_list after the specified iterator. 00906 * @param __pos An iterator into the %forward_list. 00907 * @param __il An initializer_list of value_type. 00908 * @return An iterator pointing to the last inserted element 00909 * or @a __pos if @a __il is empty. 00910 * 00911 * This function will insert copies of the data in the 00912 * initializer_list @a __il into the %forward_list before the location 00913 * specified by @a __pos. 00914 * 00915 * This operation is linear in the number of elements inserted and 00916 * does not invalidate iterators and references. 00917 */ 00918 iterator 00919 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) 00920 { return insert_after(__pos, __il.begin(), __il.end()); } 00921 00922 /** 00923 * @brief Removes the element pointed to by the iterator following 00924 * @c pos. 00925 * @param __pos Iterator pointing before element to be erased. 00926 * @return An iterator pointing to the element following the one 00927 * that was erased, or end() if no such element exists. 00928 * 00929 * This function will erase the element at the given position and 00930 * thus shorten the %forward_list by one. 00931 * 00932 * Due to the nature of a %forward_list this operation can be done 00933 * in constant time, and only invalidates iterators/references to 00934 * the element being removed. The user is also cautioned that 00935 * this function only erases the element, and that if the element 00936 * is itself a pointer, the pointed-to memory is not touched in 00937 * any way. Managing the pointer is the user's responsibility. 00938 */ 00939 iterator 00940 erase_after(const_iterator __pos) 00941 { return iterator(this->_M_erase_after(const_cast<_Node_base*> 00942 (__pos._M_node))); } 00943 00944 /** 00945 * @brief Remove a range of elements. 00946 * @param __pos Iterator pointing before the first element to be 00947 * erased. 00948 * @param __last Iterator pointing to one past the last element to be 00949 * erased. 00950 * @return @ __last. 00951 * 00952 * This function will erase the elements in the range 00953 * @a (__pos,__last) and shorten the %forward_list accordingly. 00954 * 00955 * This operation is linear time in the size of the range and only 00956 * invalidates iterators/references to the element being removed. 00957 * The user is also cautioned that this function only erases the 00958 * elements, and that if the elements themselves are pointers, the 00959 * pointed-to memory is not touched in any way. Managing the pointer 00960 * is the user's responsibility. 00961 */ 00962 iterator 00963 erase_after(const_iterator __pos, const_iterator __last) 00964 { return iterator(this->_M_erase_after(const_cast<_Node_base*> 00965 (__pos._M_node), 00966 const_cast<_Node_base*> 00967 (__last._M_node))); } 00968 00969 /** 00970 * @brief Swaps data with another %forward_list. 00971 * @param __list A %forward_list of the same element and allocator 00972 * types. 00973 * 00974 * This exchanges the elements between two lists in constant 00975 * time. Note that the global std::swap() function is 00976 * specialized such that std::swap(l1,l2) will feed to this 00977 * function. 00978 */ 00979 void 00980 swap(forward_list& __list) 00981 noexcept(_Node_alloc_traits::_S_nothrow_swap()) 00982 { 00983 std::swap(this->_M_impl._M_head._M_next, 00984 __list._M_impl._M_head._M_next); 00985 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), 00986 __list._M_get_Node_allocator()); 00987 } 00988 00989 /** 00990 * @brief Resizes the %forward_list to the specified number of 00991 * elements. 00992 * @param __sz Number of elements the %forward_list should contain. 00993 * 00994 * This function will %resize the %forward_list to the specified 00995 * number of elements. If the number is smaller than the 00996 * %forward_list's current number of elements the %forward_list 00997 * is truncated, otherwise the %forward_list is extended and the 00998 * new elements are default constructed. 00999 */ 01000 void 01001 resize(size_type __sz); 01002 01003 /** 01004 * @brief Resizes the %forward_list to the specified number of 01005 * elements. 01006 * @param __sz Number of elements the %forward_list should contain. 01007 * @param __val Data with which new elements should be populated. 01008 * 01009 * This function will %resize the %forward_list to the specified 01010 * number of elements. If the number is smaller than the 01011 * %forward_list's current number of elements the %forward_list 01012 * is truncated, otherwise the %forward_list is extended and new 01013 * elements are populated with given data. 01014 */ 01015 void 01016 resize(size_type __sz, const value_type& __val); 01017 01018 /** 01019 * @brief Erases all the elements. 01020 * 01021 * Note that this function only erases 01022 * the elements, and that if the elements themselves are 01023 * pointers, the pointed-to memory is not touched in any way. 01024 * Managing the pointer is the user's responsibility. 01025 */ 01026 void 01027 clear() noexcept 01028 { this->_M_erase_after(&this->_M_impl._M_head, 0); } 01029 01030 // 23.3.4.6 forward_list operations: 01031 01032 /** 01033 * @brief Insert contents of another %forward_list. 01034 * @param __pos Iterator referencing the element to insert after. 01035 * @param __list Source list. 01036 * 01037 * The elements of @a list are inserted in constant time after 01038 * the element referenced by @a pos. @a list becomes an empty 01039 * list. 01040 * 01041 * Requires this != @a x. 01042 */ 01043 void 01044 splice_after(const_iterator __pos, forward_list&& __list) 01045 { 01046 if (!__list.empty()) 01047 _M_splice_after(__pos, __list.before_begin(), __list.end()); 01048 } 01049 01050 void 01051 splice_after(const_iterator __pos, forward_list& __list) 01052 { splice_after(__pos, std::move(__list)); } 01053 01054 /** 01055 * @brief Insert element from another %forward_list. 01056 * @param __pos Iterator referencing the element to insert after. 01057 * @param __list Source list. 01058 * @param __i Iterator referencing the element before the element 01059 * to move. 01060 * 01061 * Removes the element in list @a list referenced by @a i and 01062 * inserts it into the current list after @a pos. 01063 */ 01064 void 01065 splice_after(const_iterator __pos, forward_list&& __list, 01066 const_iterator __i); 01067 01068 void 01069 splice_after(const_iterator __pos, forward_list& __list, 01070 const_iterator __i) 01071 { splice_after(__pos, std::move(__list), __i); } 01072 01073 /** 01074 * @brief Insert range from another %forward_list. 01075 * @param __pos Iterator referencing the element to insert after. 01076 * @param __list Source list. 01077 * @param __before Iterator referencing before the start of range 01078 * in list. 01079 * @param __last Iterator referencing the end of range in list. 01080 * 01081 * Removes elements in the range (__before,__last) and inserts them 01082 * after @a __pos in constant time. 01083 * 01084 * Undefined if @a __pos is in (__before,__last). 01085 */ 01086 void 01087 splice_after(const_iterator __pos, forward_list&&, 01088 const_iterator __before, const_iterator __last) 01089 { _M_splice_after(__pos, __before, __last); } 01090 01091 void 01092 splice_after(const_iterator __pos, forward_list&, 01093 const_iterator __before, const_iterator __last) 01094 { _M_splice_after(__pos, __before, __last); } 01095 01096 /** 01097 * @brief Remove all elements equal to value. 01098 * @param __val The value to remove. 01099 * 01100 * Removes every element in the list equal to @a __val. 01101 * Remaining elements stay in list order. Note that this 01102 * function only erases the elements, and that if the elements 01103 * themselves are pointers, the pointed-to memory is not 01104 * touched in any way. Managing the pointer is the user's 01105 * responsibility. 01106 */ 01107 void 01108 remove(const _Tp& __val); 01109 01110 /** 01111 * @brief Remove all elements satisfying a predicate. 01112 * @param __pred Unary predicate function or object. 01113 * 01114 * Removes every element in the list for which the predicate 01115 * returns true. Remaining elements stay in list order. Note 01116 * that this function only erases the elements, and that if the 01117 * elements themselves are pointers, the pointed-to memory is 01118 * not touched in any way. Managing the pointer is the user's 01119 * responsibility. 01120 */ 01121 template<typename _Pred> 01122 void 01123 remove_if(_Pred __pred); 01124 01125 /** 01126 * @brief Remove consecutive duplicate elements. 01127 * 01128 * For each consecutive set of elements with the same value, 01129 * remove all but the first one. Remaining elements stay in 01130 * list order. Note that this function only erases the 01131 * elements, and that if the elements themselves are pointers, 01132 * the pointed-to memory is not touched in any way. Managing 01133 * the pointer is the user's responsibility. 01134 */ 01135 void 01136 unique() 01137 { unique(std::equal_to<_Tp>()); } 01138 01139 /** 01140 * @brief Remove consecutive elements satisfying a predicate. 01141 * @param __binary_pred Binary predicate function or object. 01142 * 01143 * For each consecutive set of elements [first,last) that 01144 * satisfy predicate(first,i) where i is an iterator in 01145 * [first,last), remove all but the first one. Remaining 01146 * elements stay in list order. Note that this function only 01147 * erases the elements, and that if the elements themselves are 01148 * pointers, the pointed-to memory is not touched in any way. 01149 * Managing the pointer is the user's responsibility. 01150 */ 01151 template<typename _BinPred> 01152 void 01153 unique(_BinPred __binary_pred); 01154 01155 /** 01156 * @brief Merge sorted lists. 01157 * @param __list Sorted list to merge. 01158 * 01159 * Assumes that both @a list and this list are sorted according to 01160 * operator<(). Merges elements of @a __list into this list in 01161 * sorted order, leaving @a __list empty when complete. Elements in 01162 * this list precede elements in @a __list that are equal. 01163 */ 01164 void 01165 merge(forward_list&& __list) 01166 { merge(std::move(__list), std::less<_Tp>()); } 01167 01168 void 01169 merge(forward_list& __list) 01170 { merge(std::move(__list)); } 01171 01172 /** 01173 * @brief Merge sorted lists according to comparison function. 01174 * @param __list Sorted list to merge. 01175 * @param __comp Comparison function defining sort order. 01176 * 01177 * Assumes that both @a __list and this list are sorted according to 01178 * comp. Merges elements of @a __list into this list 01179 * in sorted order, leaving @a __list empty when complete. Elements 01180 * in this list precede elements in @a __list that are equivalent 01181 * according to comp(). 01182 */ 01183 template<typename _Comp> 01184 void 01185 merge(forward_list&& __list, _Comp __comp); 01186 01187 template<typename _Comp> 01188 void 01189 merge(forward_list& __list, _Comp __comp) 01190 { merge(std::move(__list), __comp); } 01191 01192 /** 01193 * @brief Sort the elements of the list. 01194 * 01195 * Sorts the elements of this list in NlogN time. Equivalent 01196 * elements remain in list order. 01197 */ 01198 void 01199 sort() 01200 { sort(std::less<_Tp>()); } 01201 01202 /** 01203 * @brief Sort the forward_list using a comparison function. 01204 * 01205 * Sorts the elements of this list in NlogN time. Equivalent 01206 * elements remain in list order. 01207 */ 01208 template<typename _Comp> 01209 void 01210 sort(_Comp __comp); 01211 01212 /** 01213 * @brief Reverse the elements in list. 01214 * 01215 * Reverse the order of elements in the list in linear time. 01216 */ 01217 void 01218 reverse() noexcept 01219 { this->_M_impl._M_head._M_reverse_after(); } 01220 01221 private: 01222 // Called by the range constructor to implement [23.3.4.2]/9 01223 template<typename _InputIterator> 01224 void 01225 _M_range_initialize(_InputIterator __first, _InputIterator __last); 01226 01227 // Called by forward_list(n,v,a), and the range constructor when it 01228 // turns out to be the same thing. 01229 void 01230 _M_fill_initialize(size_type __n, const value_type& __value); 01231 01232 // Called by splice_after and insert_after. 01233 iterator 01234 _M_splice_after(const_iterator __pos, const_iterator __before, 01235 const_iterator __last); 01236 01237 // Called by forward_list(n). 01238 void 01239 _M_default_initialize(size_type __n); 01240 01241 // Called by resize(sz). 01242 void 01243 _M_default_insert_after(const_iterator __pos, size_type __n); 01244 01245 // Called by operator=(forward_list&&) 01246 void 01247 _M_move_assign(forward_list&& __list, std::true_type) noexcept 01248 { 01249 clear(); 01250 std::swap(this->_M_impl._M_head._M_next, 01251 __list._M_impl._M_head._M_next); 01252 std::__alloc_on_move(this->_M_get_Node_allocator(), 01253 __list._M_get_Node_allocator()); 01254 } 01255 01256 // Called by operator=(forward_list&&) 01257 void 01258 _M_move_assign(forward_list&& __list, std::false_type) 01259 { 01260 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator()) 01261 _M_move_assign(std::move(__list), std::true_type()); 01262 else 01263 // The rvalue's allocator cannot be moved, or is not equal, 01264 // so we need to individually move each element. 01265 this->assign(std::__make_move_if_noexcept_iterator(__list.begin()), 01266 std::__make_move_if_noexcept_iterator(__list.end())); 01267 } 01268 01269 // Called by assign(_InputIterator, _InputIterator) if _Tp is 01270 // CopyAssignable. 01271 template<typename _InputIterator> 01272 void 01273 _M_assign(_InputIterator __first, _InputIterator __last, true_type) 01274 { 01275 auto __prev = before_begin(); 01276 auto __curr = begin(); 01277 auto __end = end(); 01278 while (__curr != __end && __first != __last) 01279 { 01280 *__curr = *__first; 01281 ++__prev; 01282 ++__curr; 01283 ++__first; 01284 } 01285 if (__first != __last) 01286 insert_after(__prev, __first, __last); 01287 else if (__curr != __end) 01288 erase_after(__prev, __end); 01289 } 01290 01291 // Called by assign(_InputIterator, _InputIterator) if _Tp is not 01292 // CopyAssignable. 01293 template<typename _InputIterator> 01294 void 01295 _M_assign(_InputIterator __first, _InputIterator __last, false_type) 01296 { 01297 clear(); 01298 insert_after(cbefore_begin(), __first, __last); 01299 } 01300 01301 // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable 01302 void 01303 _M_assign_n(size_type __n, const _Tp& __val, true_type) 01304 { 01305 auto __prev = before_begin(); 01306 auto __curr = begin(); 01307 auto __end = end(); 01308 while (__curr != __end && __n > 0) 01309 { 01310 *__curr = __val; 01311 ++__prev; 01312 ++__curr; 01313 --__n; 01314 } 01315 if (__n > 0) 01316 insert_after(__prev, __n, __val); 01317 else if (__curr != __end) 01318 erase_after(__prev, __end); 01319 } 01320 01321 // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable 01322 void 01323 _M_assign_n(size_type __n, const _Tp& __val, false_type) 01324 { 01325 clear(); 01326 insert_after(cbefore_begin(), __n, __val); 01327 } 01328 }; 01329 01330 /** 01331 * @brief Forward list equality comparison. 01332 * @param __lx A %forward_list 01333 * @param __ly A %forward_list of the same type as @a __lx. 01334 * @return True iff the elements of the forward lists are equal. 01335 * 01336 * This is an equivalence relation. It is linear in the number of 01337 * elements of the forward lists. Deques are considered equivalent 01338 * if corresponding elements compare equal. 01339 */ 01340 template<typename _Tp, typename _Alloc> 01341 bool 01342 operator==(const forward_list<_Tp, _Alloc>& __lx, 01343 const forward_list<_Tp, _Alloc>& __ly); 01344 01345 /** 01346 * @brief Forward list ordering relation. 01347 * @param __lx A %forward_list. 01348 * @param __ly A %forward_list of the same type as @a __lx. 01349 * @return True iff @a __lx is lexicographically less than @a __ly. 01350 * 01351 * This is a total ordering relation. It is linear in the number of 01352 * elements of the forward lists. The elements must be comparable 01353 * with @c <. 01354 * 01355 * See std::lexicographical_compare() for how the determination is made. 01356 */ 01357 template<typename _Tp, typename _Alloc> 01358 inline bool 01359 operator<(const forward_list<_Tp, _Alloc>& __lx, 01360 const forward_list<_Tp, _Alloc>& __ly) 01361 { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(), 01362 __ly.cbegin(), __ly.cend()); } 01363 01364 /// Based on operator== 01365 template<typename _Tp, typename _Alloc> 01366 inline bool 01367 operator!=(const forward_list<_Tp, _Alloc>& __lx, 01368 const forward_list<_Tp, _Alloc>& __ly) 01369 { return !(__lx == __ly); } 01370 01371 /// Based on operator< 01372 template<typename _Tp, typename _Alloc> 01373 inline bool 01374 operator>(const forward_list<_Tp, _Alloc>& __lx, 01375 const forward_list<_Tp, _Alloc>& __ly) 01376 { return (__ly < __lx); } 01377 01378 /// Based on operator< 01379 template<typename _Tp, typename _Alloc> 01380 inline bool 01381 operator>=(const forward_list<_Tp, _Alloc>& __lx, 01382 const forward_list<_Tp, _Alloc>& __ly) 01383 { return !(__lx < __ly); } 01384 01385 /// Based on operator< 01386 template<typename _Tp, typename _Alloc> 01387 inline bool 01388 operator<=(const forward_list<_Tp, _Alloc>& __lx, 01389 const forward_list<_Tp, _Alloc>& __ly) 01390 { return !(__ly < __lx); } 01391 01392 /// See std::forward_list::swap(). 01393 template<typename _Tp, typename _Alloc> 01394 inline void 01395 swap(forward_list<_Tp, _Alloc>& __lx, 01396 forward_list<_Tp, _Alloc>& __ly) 01397 { __lx.swap(__ly); } 01398 01399 _GLIBCXX_END_NAMESPACE_CONTAINER 01400 } // namespace std 01401 01402 #endif // _FORWARD_LIST_H