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