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