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