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