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