Line data Source code
1 : // <forward_list.h> -*- C++ -*-
2 :
3 : // Copyright (C) 2008-2013 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 3, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /** @file bits/forward_list.h
26 : * This is an internal header file, included by other library headers.
27 : * Do not attempt to use it directly. @headername{forward_list}
28 : */
29 :
30 : #ifndef _FORWARD_LIST_H
31 : #define _FORWARD_LIST_H 1
32 :
33 : #pragma GCC system_header
34 :
35 : #include <memory>
36 : #if __cplusplus >= 201103L
37 : #include <initializer_list>
38 : #endif
39 :
40 : namespace std _GLIBCXX_VISIBILITY(default)
41 : {
42 : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
43 :
44 : /**
45 : * @brief A helper basic node class for %forward_list.
46 : * This is just a linked list with nothing inside it.
47 : * There are purely list shuffling utility methods here.
48 : */
49 : struct _Fwd_list_node_base
50 : {
51 334618 : _Fwd_list_node_base() = default;
52 :
53 : _Fwd_list_node_base* _M_next = nullptr;
54 :
55 : _Fwd_list_node_base*
56 : _M_transfer_after(_Fwd_list_node_base* __begin,
57 : _Fwd_list_node_base* __end)
58 : {
59 : _Fwd_list_node_base* __keep = __begin->_M_next;
60 : if (__end)
61 : {
62 : __begin->_M_next = __end->_M_next;
63 : __end->_M_next = _M_next;
64 : }
65 : else
66 : __begin->_M_next = 0;
67 : _M_next = __keep;
68 : return __end;
69 : }
70 :
71 : void
72 : _M_reverse_after() noexcept
73 : {
74 : _Fwd_list_node_base* __tail = _M_next;
75 : if (!__tail)
76 : return;
77 : while (_Fwd_list_node_base* __temp = __tail->_M_next)
78 : {
79 : _Fwd_list_node_base* __keep = _M_next;
80 : _M_next = __temp;
81 : __tail->_M_next = __temp->_M_next;
82 : _M_next->_M_next = __keep;
83 : }
84 : }
85 : };
86 :
87 : /**
88 : * @brief A helper node class for %forward_list.
89 : * This is just a linked list with uninitialized storage for a
90 : * data value in each node.
91 : * There is a sorting utility method.
92 : */
93 : template<typename _Tp>
94 : struct _Fwd_list_node
95 : : public _Fwd_list_node_base
96 : {
97 334655 : _Fwd_list_node() = default;
98 :
99 : typename aligned_storage<sizeof(_Tp), alignment_of<_Tp>::value>::type
100 : _M_storage;
101 :
102 : _Tp*
103 1003200 : _M_valptr() noexcept
104 : {
105 1003200 : return static_cast<_Tp*>(static_cast<void*>(&_M_storage));
106 : }
107 :
108 : const _Tp*
109 : _M_valptr() const noexcept
110 : {
111 : return static_cast<const _Tp*>(static_cast<const void*>(&_M_storage));
112 : }
113 : };
114 :
115 : /**
116 : * @brief A forward_list::iterator.
117 : *
118 : * All the functions are op overloads.
119 : */
120 : template<typename _Tp>
121 : struct _Fwd_list_iterator
122 : {
123 : typedef _Fwd_list_iterator<_Tp> _Self;
124 : typedef _Fwd_list_node<_Tp> _Node;
125 :
126 : typedef _Tp value_type;
127 : typedef _Tp* pointer;
128 : typedef _Tp& reference;
129 : typedef ptrdiff_t difference_type;
130 : typedef std::forward_iterator_tag iterator_category;
131 :
132 : _Fwd_list_iterator()
133 : : _M_node() { }
134 :
135 : explicit
136 254674 : _Fwd_list_iterator(_Fwd_list_node_base* __n)
137 254674 : : _M_node(__n) { }
138 :
139 : reference
140 254676 : operator*() const
141 254676 : { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
142 :
143 : pointer
144 : operator->() const
145 : { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
146 :
147 : _Self&
148 : operator++()
149 : {
150 : _M_node = _M_node->_M_next;
151 : return *this;
152 : }
153 :
154 : _Self
155 : operator++(int)
156 : {
157 : _Self __tmp(*this);
158 : _M_node = _M_node->_M_next;
159 : return __tmp;
160 : }
161 :
162 : bool
163 : operator==(const _Self& __x) const
164 : { return _M_node == __x._M_node; }
165 :
166 : bool
167 : operator!=(const _Self& __x) const
168 : { return _M_node != __x._M_node; }
169 :
170 : _Self
171 : _M_next() const
172 : {
173 : if (_M_node)
174 : return _Fwd_list_iterator(_M_node->_M_next);
175 : else
176 : return _Fwd_list_iterator(0);
177 : }
178 :
179 : _Fwd_list_node_base* _M_node;
180 : };
181 :
182 : /**
183 : * @brief A forward_list::const_iterator.
184 : *
185 : * All the functions are op overloads.
186 : */
187 : template<typename _Tp>
188 : struct _Fwd_list_const_iterator
189 : {
190 : typedef _Fwd_list_const_iterator<_Tp> _Self;
191 : typedef const _Fwd_list_node<_Tp> _Node;
192 : typedef _Fwd_list_iterator<_Tp> iterator;
193 :
194 : typedef _Tp value_type;
195 : typedef const _Tp* pointer;
196 : typedef const _Tp& reference;
197 : typedef ptrdiff_t difference_type;
198 : typedef std::forward_iterator_tag iterator_category;
199 :
200 : _Fwd_list_const_iterator()
201 : : _M_node() { }
202 :
203 : explicit
204 334668 : _Fwd_list_const_iterator(const _Fwd_list_node_base* __n)
205 334668 : : _M_node(__n) { }
206 :
207 : _Fwd_list_const_iterator(const iterator& __iter)
208 : : _M_node(__iter._M_node) { }
209 :
210 : reference
211 : operator*() const
212 : { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
213 :
214 : pointer
215 : operator->() const
216 : { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
217 :
218 : _Self&
219 : operator++()
220 : {
221 : _M_node = _M_node->_M_next;
222 : return *this;
223 : }
224 :
225 : _Self
226 : operator++(int)
227 : {
228 : _Self __tmp(*this);
229 : _M_node = _M_node->_M_next;
230 : return __tmp;
231 : }
232 :
233 : bool
234 : operator==(const _Self& __x) const
235 : { return _M_node == __x._M_node; }
236 :
237 : bool
238 : operator!=(const _Self& __x) const
239 : { return _M_node != __x._M_node; }
240 :
241 : _Self
242 : _M_next() const
243 : {
244 : if (this->_M_node)
245 : return _Fwd_list_const_iterator(_M_node->_M_next);
246 : else
247 : return _Fwd_list_const_iterator(0);
248 : }
249 :
250 : const _Fwd_list_node_base* _M_node;
251 : };
252 :
253 : /**
254 : * @brief Forward list iterator equality comparison.
255 : */
256 : template<typename _Tp>
257 : inline bool
258 : operator==(const _Fwd_list_iterator<_Tp>& __x,
259 : const _Fwd_list_const_iterator<_Tp>& __y)
260 : { return __x._M_node == __y._M_node; }
261 :
262 : /**
263 : * @brief Forward list iterator inequality comparison.
264 : */
265 : template<typename _Tp>
266 : inline bool
267 : operator!=(const _Fwd_list_iterator<_Tp>& __x,
268 : const _Fwd_list_const_iterator<_Tp>& __y)
269 : { return __x._M_node != __y._M_node; }
270 :
271 : /**
272 : * @brief Base class for %forward_list.
273 : */
274 : template<typename _Tp, typename _Alloc>
275 : struct _Fwd_list_base
276 : {
277 : protected:
278 : typedef typename __gnu_cxx::__alloc_traits<_Alloc> _Alloc_traits;
279 : typedef typename _Alloc_traits::template rebind<_Tp>::other
280 : _Tp_alloc_type;
281 :
282 : typedef typename _Alloc_traits::template
283 : rebind<_Fwd_list_node<_Tp>>::other _Node_alloc_type;
284 :
285 : typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
286 :
287 22 : struct _Fwd_list_impl
288 : : public _Node_alloc_type
289 : {
290 : _Fwd_list_node_base _M_head;
291 :
292 : _Fwd_list_impl()
293 : : _Node_alloc_type(), _M_head()
294 : { }
295 :
296 22 : _Fwd_list_impl(const _Node_alloc_type& __a)
297 22 : : _Node_alloc_type(__a), _M_head()
298 22 : { }
299 :
300 : _Fwd_list_impl(_Node_alloc_type&& __a)
301 : : _Node_alloc_type(std::move(__a)), _M_head()
302 : { }
303 : };
304 :
305 : _Fwd_list_impl _M_impl;
306 :
307 : public:
308 : typedef _Fwd_list_iterator<_Tp> iterator;
309 : typedef _Fwd_list_const_iterator<_Tp> const_iterator;
310 : typedef _Fwd_list_node<_Tp> _Node;
311 :
312 : _Node_alloc_type&
313 1337755 : _M_get_Node_allocator() noexcept
314 1337755 : { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
315 :
316 : const _Node_alloc_type&
317 : _M_get_Node_allocator() const noexcept
318 : { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
319 :
320 : _Fwd_list_base()
321 : : _M_impl() { }
322 :
323 22 : _Fwd_list_base(const _Node_alloc_type& __a)
324 22 : : _M_impl(__a) { }
325 :
326 : _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a);
327 :
328 : _Fwd_list_base(_Fwd_list_base&& __lst)
329 : : _M_impl(std::move(__lst._M_get_Node_allocator()))
330 : {
331 : this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
332 : __lst._M_impl._M_head._M_next = 0;
333 : }
334 :
335 22 : ~_Fwd_list_base()
336 22 : { _M_erase_after(&_M_impl._M_head, 0); }
337 :
338 : protected:
339 :
340 : _Node*
341 334622 : _M_get_node()
342 334622 : { return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); }
343 :
344 : template<typename... _Args>
345 : _Node*
346 334673 : _M_create_node(_Args&&... __args)
347 : {
348 334673 : _Node* __node = this->_M_get_node();
349 : __try
350 : {
351 334675 : _Tp_alloc_type __a(_M_get_Node_allocator());
352 : typedef allocator_traits<_Tp_alloc_type> _Alloc_traits;
353 334675 : ::new ((void*)__node) _Node();
354 334675 : _Alloc_traits::construct(__a, __node->_M_valptr(),
355 669304 : std::forward<_Args>(__args)...);
356 : }
357 : __catch(...)
358 : {
359 : this->_M_put_node(__node);
360 : __throw_exception_again;
361 : }
362 334630 : return __node;
363 : }
364 :
365 : template<typename... _Args>
366 : _Fwd_list_node_base*
367 : _M_insert_after(const_iterator __pos, _Args&&... __args);
368 :
369 : void
370 334674 : _M_put_node(_Node* __p)
371 334674 : { _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
372 :
373 : _Fwd_list_node_base*
374 : _M_erase_after(_Fwd_list_node_base* __pos);
375 :
376 : _Fwd_list_node_base*
377 : _M_erase_after(_Fwd_list_node_base* __pos,
378 : _Fwd_list_node_base* __last);
379 : };
380 :
381 : /**
382 : * @brief A standard container with linear time access to elements,
383 : * and fixed time insertion/deletion at any point in the sequence.
384 : *
385 : * @ingroup sequences
386 : *
387 : * @tparam _Tp Type of element.
388 : * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
389 : *
390 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
391 : * <a href="tables.html#67">sequence</a>, including the
392 : * <a href="tables.html#68">optional sequence requirements</a> with the
393 : * %exception of @c at and @c operator[].
394 : *
395 : * This is a @e singly @e linked %list. Traversal up the
396 : * %list requires linear time, but adding and removing elements (or
397 : * @e nodes) is done in constant time, regardless of where the
398 : * change takes place. Unlike std::vector and std::deque,
399 : * random-access iterators are not provided, so subscripting ( @c
400 : * [] ) access is not allowed. For algorithms which only need
401 : * sequential access, this lack makes no difference.
402 : *
403 : * Also unlike the other standard containers, std::forward_list provides
404 : * specialized algorithms %unique to linked lists, such as
405 : * splicing, sorting, and in-place reversal.
406 : */
407 : template<typename _Tp, typename _Alloc = allocator<_Tp> >
408 : class forward_list : private _Fwd_list_base<_Tp, _Alloc>
409 : {
410 : private:
411 : typedef _Fwd_list_base<_Tp, _Alloc> _Base;
412 : typedef _Fwd_list_node<_Tp> _Node;
413 : typedef _Fwd_list_node_base _Node_base;
414 : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
415 : typedef typename _Base::_Node_alloc_type _Node_alloc_type;
416 : typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
417 : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
418 :
419 : public:
420 : // types:
421 : typedef _Tp value_type;
422 : typedef typename _Alloc_traits::pointer pointer;
423 : typedef typename _Alloc_traits::const_pointer const_pointer;
424 : typedef typename _Alloc_traits::reference reference;
425 : typedef typename _Alloc_traits::const_reference const_reference;
426 :
427 : typedef _Fwd_list_iterator<_Tp> iterator;
428 : typedef _Fwd_list_const_iterator<_Tp> const_iterator;
429 : typedef std::size_t size_type;
430 : typedef std::ptrdiff_t difference_type;
431 : typedef _Alloc allocator_type;
432 :
433 : // 23.3.4.2 construct/copy/destroy:
434 :
435 : /**
436 : * @brief Creates a %forward_list with no elements.
437 : * @param __al An allocator object.
438 : */
439 : explicit
440 22 : forward_list(const _Alloc& __al = _Alloc())
441 22 : : _Base(_Node_alloc_type(__al))
442 22 : { }
443 :
444 : /**
445 : * @brief Copy constructor with allocator argument.
446 : * @param __list Input list to copy.
447 : * @param __al An allocator object.
448 : */
449 : forward_list(const forward_list& __list, const _Alloc& __al)
450 : : _Base(_Node_alloc_type(__al))
451 : { _M_range_initialize(__list.begin(), __list.end()); }
452 :
453 : /**
454 : * @brief Move constructor with allocator argument.
455 : * @param __list Input list to move.
456 : * @param __al An allocator object.
457 : */
458 : forward_list(forward_list&& __list, const _Alloc& __al)
459 : noexcept(_Node_alloc_traits::_S_always_equal())
460 : : _Base(std::move(__list), _Node_alloc_type(__al))
461 : { }
462 :
463 : /**
464 : * @brief Creates a %forward_list with default constructed elements.
465 : * @param __n The number of elements to initially create.
466 : *
467 : * This constructor creates the %forward_list with @a __n default
468 : * constructed elements.
469 : */
470 : explicit
471 : forward_list(size_type __n, const _Alloc& __al = _Alloc())
472 : : _Base(_Node_alloc_type(__al))
473 : { _M_default_initialize(__n); }
474 :
475 : /**
476 : * @brief Creates a %forward_list with copies of an exemplar element.
477 : * @param __n The number of elements to initially create.
478 : * @param __value An element to copy.
479 : * @param __al An allocator object.
480 : *
481 : * This constructor fills the %forward_list with @a __n copies of
482 : * @a __value.
483 : */
484 : forward_list(size_type __n, const _Tp& __value,
485 : const _Alloc& __al = _Alloc())
486 : : _Base(_Node_alloc_type(__al))
487 : { _M_fill_initialize(__n, __value); }
488 :
489 : /**
490 : * @brief Builds a %forward_list from a range.
491 : * @param __first An input iterator.
492 : * @param __last An input iterator.
493 : * @param __al An allocator object.
494 : *
495 : * Create a %forward_list consisting of copies of the elements from
496 : * [@a __first,@a __last). This is linear in N (where N is
497 : * distance(@a __first,@a __last)).
498 : */
499 : template<typename _InputIterator,
500 : typename = std::_RequireInputIter<_InputIterator>>
501 : forward_list(_InputIterator __first, _InputIterator __last,
502 : const _Alloc& __al = _Alloc())
503 : : _Base(_Node_alloc_type(__al))
504 : { _M_range_initialize(__first, __last); }
505 :
506 : /**
507 : * @brief The %forward_list copy constructor.
508 : * @param __list A %forward_list of identical element and allocator
509 : * types.
510 : */
511 : forward_list(const forward_list& __list)
512 : : _Base(_Node_alloc_traits::_S_select_on_copy(
513 : __list._M_get_Node_allocator()))
514 : { _M_range_initialize(__list.begin(), __list.end()); }
515 :
516 : /**
517 : * @brief The %forward_list move constructor.
518 : * @param __list A %forward_list of identical element and allocator
519 : * types.
520 : *
521 : * The newly-created %forward_list contains the exact contents of @a
522 : * __list. The contents of @a __list are a valid, but unspecified
523 : * %forward_list.
524 : */
525 : forward_list(forward_list&& __list) noexcept
526 : : _Base(std::move(__list)) { }
527 :
528 : /**
529 : * @brief Builds a %forward_list from an initializer_list
530 : * @param __il An initializer_list of value_type.
531 : * @param __al An allocator object.
532 : *
533 : * Create a %forward_list consisting of copies of the elements
534 : * in the initializer_list @a __il. This is linear in __il.size().
535 : */
536 : forward_list(std::initializer_list<_Tp> __il,
537 : const _Alloc& __al = _Alloc())
538 : : _Base(_Node_alloc_type(__al))
539 : { _M_range_initialize(__il.begin(), __il.end()); }
540 :
541 : /**
542 : * @brief The forward_list dtor.
543 : */
544 22 : ~forward_list() noexcept
545 22 : { }
546 :
547 : /**
548 : * @brief The %forward_list assignment operator.
549 : * @param __list A %forward_list of identical element and allocator
550 : * types.
551 : *
552 : * All the elements of @a __list are copied, but unlike the copy
553 : * constructor, the allocator object is not copied.
554 : */
555 : forward_list&
556 : operator=(const forward_list& __list);
557 :
558 : /**
559 : * @brief The %forward_list move assignment operator.
560 : * @param __list A %forward_list of identical element and allocator
561 : * types.
562 : *
563 : * The contents of @a __list are moved into this %forward_list
564 : * (without copying, if the allocators permit it).
565 : * @a __list is a valid, but unspecified %forward_list
566 : */
567 : forward_list&
568 : operator=(forward_list&& __list)
569 : noexcept(_Node_alloc_traits::_S_nothrow_move())
570 : {
571 : constexpr bool __move_storage =
572 : _Node_alloc_traits::_S_propagate_on_move_assign()
573 : || _Node_alloc_traits::_S_always_equal();
574 : _M_move_assign(std::move(__list),
575 : integral_constant<bool, __move_storage>());
576 : return *this;
577 : }
578 :
579 : /**
580 : * @brief The %forward_list initializer list assignment operator.
581 : * @param __il An initializer_list of value_type.
582 : *
583 : * Replace the contents of the %forward_list with copies of the
584 : * elements in the initializer_list @a __il. This is linear in
585 : * __il.size().
586 : */
587 : forward_list&
588 : operator=(std::initializer_list<_Tp> __il)
589 : {
590 : assign(__il);
591 : return *this;
592 : }
593 :
594 : /**
595 : * @brief Assigns a range to a %forward_list.
596 : * @param __first An input iterator.
597 : * @param __last An input iterator.
598 : *
599 : * This function fills a %forward_list with copies of the elements
600 : * in the range [@a __first,@a __last).
601 : *
602 : * Note that the assignment completely changes the %forward_list and
603 : * that the number of elements of the resulting %forward_list is the
604 : * same as the number of elements assigned. Old data is lost.
605 : */
606 : template<typename _InputIterator,
607 : typename = std::_RequireInputIter<_InputIterator>>
608 : void
609 : assign(_InputIterator __first, _InputIterator __last)
610 : {
611 : typedef is_assignable<_Tp, decltype(*__first)> __assignable;
612 : _M_assign(__first, __last, __assignable());
613 : }
614 :
615 : /**
616 : * @brief Assigns a given value to a %forward_list.
617 : * @param __n Number of elements to be assigned.
618 : * @param __val Value to be assigned.
619 : *
620 : * This function fills a %forward_list with @a __n copies of the
621 : * given value. Note that the assignment completely changes the
622 : * %forward_list, and that the resulting %forward_list has __n
623 : * elements. Old data is lost.
624 : */
625 : void
626 : assign(size_type __n, const _Tp& __val)
627 : { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); }
628 :
629 : /**
630 : * @brief Assigns an initializer_list to a %forward_list.
631 : * @param __il An initializer_list of value_type.
632 : *
633 : * Replace the contents of the %forward_list with copies of the
634 : * elements in the initializer_list @a __il. This is linear in
635 : * il.size().
636 : */
637 : void
638 : assign(std::initializer_list<_Tp> __il)
639 : { assign(__il.begin(), __il.end()); }
640 :
641 : /// Get a copy of the memory allocation object.
642 : allocator_type
643 : get_allocator() const noexcept
644 : { return allocator_type(this->_M_get_Node_allocator()); }
645 :
646 : // 23.3.4.3 iterators:
647 :
648 : /**
649 : * Returns a read/write iterator that points before the first element
650 : * in the %forward_list. Iteration is done in ordinary element order.
651 : */
652 : iterator
653 : before_begin() noexcept
654 : { return iterator(&this->_M_impl._M_head); }
655 :
656 : /**
657 : * Returns a read-only (constant) iterator that points before the
658 : * first element in the %forward_list. Iteration is done in ordinary
659 : * element order.
660 : */
661 : const_iterator
662 : before_begin() const noexcept
663 : { return const_iterator(&this->_M_impl._M_head); }
664 :
665 : /**
666 : * Returns a read/write iterator that points to the first element
667 : * in the %forward_list. Iteration is done in ordinary element order.
668 : */
669 : iterator
670 254676 : begin() noexcept
671 254676 : { return iterator(this->_M_impl._M_head._M_next); }
672 :
673 : /**
674 : * Returns a read-only (constant) iterator that points to the first
675 : * element in the %forward_list. Iteration is done in ordinary
676 : * element order.
677 : */
678 : const_iterator
679 : begin() const noexcept
680 : { return const_iterator(this->_M_impl._M_head._M_next); }
681 :
682 : /**
683 : * Returns a read/write iterator that points one past the last
684 : * element in the %forward_list. Iteration is done in ordinary
685 : * element order.
686 : */
687 : iterator
688 : end() noexcept
689 : { return iterator(0); }
690 :
691 : /**
692 : * Returns a read-only iterator that points one past the last
693 : * element in the %forward_list. Iteration is done in ordinary
694 : * element order.
695 : */
696 : const_iterator
697 : end() const noexcept
698 : { return const_iterator(0); }
699 :
700 : /**
701 : * Returns a read-only (constant) iterator that points to the
702 : * first element in the %forward_list. Iteration is done in ordinary
703 : * element order.
704 : */
705 : const_iterator
706 : cbegin() const noexcept
707 : { return const_iterator(this->_M_impl._M_head._M_next); }
708 :
709 : /**
710 : * Returns a read-only (constant) iterator that points before the
711 : * first element in the %forward_list. Iteration is done in ordinary
712 : * element order.
713 : */
714 : const_iterator
715 334677 : cbefore_begin() const noexcept
716 334677 : { return const_iterator(&this->_M_impl._M_head); }
717 :
718 : /**
719 : * Returns a read-only (constant) iterator that points one past
720 : * the last element in the %forward_list. Iteration is done in
721 : * ordinary element order.
722 : */
723 : const_iterator
724 : cend() const noexcept
725 : { return const_iterator(0); }
726 :
727 : /**
728 : * Returns true if the %forward_list is empty. (Thus begin() would
729 : * equal end().)
730 : */
731 : bool
732 499099 : empty() const noexcept
733 499099 : { return this->_M_impl._M_head._M_next == 0; }
734 :
735 : /**
736 : * Returns the largest possible number of elements of %forward_list.
737 : */
738 : size_type
739 : max_size() const noexcept
740 : { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
741 :
742 : // 23.3.4.4 element access:
743 :
744 : /**
745 : * Returns a read/write reference to the data at the first
746 : * element of the %forward_list.
747 : */
748 : reference
749 80000 : front()
750 : {
751 80000 : _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
752 80000 : return *__front->_M_valptr();
753 : }
754 :
755 : /**
756 : * Returns a read-only (constant) reference to the data at the first
757 : * element of the %forward_list.
758 : */
759 : const_reference
760 : front() const
761 : {
762 : _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
763 : return *__front->_M_valptr();
764 : }
765 :
766 : // 23.3.4.5 modiļ¬ers:
767 :
768 : /**
769 : * @brief Constructs object in %forward_list at the front of the
770 : * list.
771 : * @param __args Arguments.
772 : *
773 : * This function will insert an object of type Tp constructed
774 : * with Tp(std::forward<Args>(args)...) at the front of the list
775 : * Due to the nature of a %forward_list this operation can
776 : * be done in constant time, and does not invalidate iterators
777 : * and references.
778 : */
779 : template<typename... _Args>
780 : void
781 : emplace_front(_Args&&... __args)
782 : { this->_M_insert_after(cbefore_begin(),
783 : std::forward<_Args>(__args)...); }
784 :
785 : /**
786 : * @brief Add data to the front of the %forward_list.
787 : * @param __val Data to be added.
788 : *
789 : * This is a typical stack operation. The function creates an
790 : * element at the front of the %forward_list and assigns the given
791 : * data to it. Due to the nature of a %forward_list this operation
792 : * can be done in constant time, and does not invalidate iterators
793 : * and references.
794 : */
795 : void
796 254677 : push_front(const _Tp& __val)
797 254677 : { this->_M_insert_after(cbefore_begin(), __val); }
798 :
799 : /**
800 : *
801 : */
802 : void
803 80000 : push_front(_Tp&& __val)
804 80000 : { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
805 :
806 : /**
807 : * @brief Removes first element.
808 : *
809 : * This is a typical stack operation. It shrinks the %forward_list
810 : * by one. Due to the nature of a %forward_list this operation can
811 : * be done in constant time, and only invalidates iterators/references
812 : * to the element being removed.
813 : *
814 : * Note that no data is returned, and if the first element's data
815 : * is needed, it should be retrieved before pop_front() is
816 : * called.
817 : */
818 : void
819 334676 : pop_front()
820 334676 : { this->_M_erase_after(&this->_M_impl._M_head); }
821 :
822 : /**
823 : * @brief Constructs object in %forward_list after the specified
824 : * iterator.
825 : * @param __pos A const_iterator into the %forward_list.
826 : * @param __args Arguments.
827 : * @return An iterator that points to the inserted data.
828 : *
829 : * This function will insert an object of type T constructed
830 : * with T(std::forward<Args>(args)...) after the specified
831 : * location. Due to the nature of a %forward_list this operation can
832 : * be done in constant time, and does not invalidate iterators
833 : * and references.
834 : */
835 : template<typename... _Args>
836 : iterator
837 : emplace_after(const_iterator __pos, _Args&&... __args)
838 : { return iterator(this->_M_insert_after(__pos,
839 : std::forward<_Args>(__args)...)); }
840 :
841 : /**
842 : * @brief Inserts given value into %forward_list after specified
843 : * iterator.
844 : * @param __pos An iterator into the %forward_list.
845 : * @param __val Data to be inserted.
846 : * @return An iterator that points to the inserted data.
847 : *
848 : * This function will insert a copy of the given value after
849 : * the specified location. Due to the nature of a %forward_list this
850 : * operation can be done in constant time, and does not
851 : * invalidate iterators and references.
852 : */
853 : iterator
854 : insert_after(const_iterator __pos, const _Tp& __val)
855 : { return iterator(this->_M_insert_after(__pos, __val)); }
856 :
857 : /**
858 : *
859 : */
860 : iterator
861 : insert_after(const_iterator __pos, _Tp&& __val)
862 : { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
863 :
864 : /**
865 : * @brief Inserts a number of copies of given data into the
866 : * %forward_list.
867 : * @param __pos An iterator into the %forward_list.
868 : * @param __n Number of elements to be inserted.
869 : * @param __val Data to be inserted.
870 : * @return An iterator pointing to the last inserted copy of
871 : * @a val or @a pos if @a n == 0.
872 : *
873 : * This function will insert a specified number of copies of the
874 : * given data after the location specified by @a pos.
875 : *
876 : * This operation is linear in the number of elements inserted and
877 : * does not invalidate iterators and references.
878 : */
879 : iterator
880 : insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
881 :
882 : /**
883 : * @brief Inserts a range into the %forward_list.
884 : * @param __pos An iterator into the %forward_list.
885 : * @param __first An input iterator.
886 : * @param __last An input iterator.
887 : * @return An iterator pointing to the last inserted element or
888 : * @a __pos if @a __first == @a __last.
889 : *
890 : * This function will insert copies of the data in the range
891 : * [@a __first,@a __last) into the %forward_list after the
892 : * location specified by @a __pos.
893 : *
894 : * This operation is linear in the number of elements inserted and
895 : * does not invalidate iterators and references.
896 : */
897 : template<typename _InputIterator,
898 : typename = std::_RequireInputIter<_InputIterator>>
899 : iterator
900 : insert_after(const_iterator __pos,
901 : _InputIterator __first, _InputIterator __last);
902 :
903 : /**
904 : * @brief Inserts the contents of an initializer_list into
905 : * %forward_list after the specified iterator.
906 : * @param __pos An iterator into the %forward_list.
907 : * @param __il An initializer_list of value_type.
908 : * @return An iterator pointing to the last inserted element
909 : * or @a __pos if @a __il is empty.
910 : *
911 : * This function will insert copies of the data in the
912 : * initializer_list @a __il into the %forward_list before the location
913 : * specified by @a __pos.
914 : *
915 : * This operation is linear in the number of elements inserted and
916 : * does not invalidate iterators and references.
917 : */
918 : iterator
919 : insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
920 : { return insert_after(__pos, __il.begin(), __il.end()); }
921 :
922 : /**
923 : * @brief Removes the element pointed to by the iterator following
924 : * @c pos.
925 : * @param __pos Iterator pointing before element to be erased.
926 : * @return An iterator pointing to the element following the one
927 : * that was erased, or end() if no such element exists.
928 : *
929 : * This function will erase the element at the given position and
930 : * thus shorten the %forward_list by one.
931 : *
932 : * Due to the nature of a %forward_list this operation can be done
933 : * in constant time, and only invalidates iterators/references to
934 : * the element being removed. The user is also cautioned that
935 : * this function only erases the element, and that if the element
936 : * is itself a pointer, the pointed-to memory is not touched in
937 : * any way. Managing the pointer is the user's responsibility.
938 : */
939 : iterator
940 : erase_after(const_iterator __pos)
941 : { return iterator(this->_M_erase_after(const_cast<_Node_base*>
942 : (__pos._M_node))); }
943 :
944 : /**
945 : * @brief Remove a range of elements.
946 : * @param __pos Iterator pointing before the first element to be
947 : * erased.
948 : * @param __last Iterator pointing to one past the last element to be
949 : * erased.
950 : * @return @ __last.
951 : *
952 : * This function will erase the elements in the range
953 : * @a (__pos,__last) and shorten the %forward_list accordingly.
954 : *
955 : * This operation is linear time in the size of the range and only
956 : * invalidates iterators/references to the element being removed.
957 : * The user is also cautioned that this function only erases the
958 : * elements, and that if the elements themselves are pointers, the
959 : * pointed-to memory is not touched in any way. Managing the pointer
960 : * is the user's responsibility.
961 : */
962 : iterator
963 : erase_after(const_iterator __pos, const_iterator __last)
964 : { return iterator(this->_M_erase_after(const_cast<_Node_base*>
965 : (__pos._M_node),
966 : const_cast<_Node_base*>
967 : (__last._M_node))); }
968 :
969 : /**
970 : * @brief Swaps data with another %forward_list.
971 : * @param __list A %forward_list of the same element and allocator
972 : * types.
973 : *
974 : * This exchanges the elements between two lists in constant
975 : * time. Note that the global std::swap() function is
976 : * specialized such that std::swap(l1,l2) will feed to this
977 : * function.
978 : */
979 : void
980 : swap(forward_list& __list)
981 : noexcept(_Node_alloc_traits::_S_nothrow_swap())
982 : {
983 : std::swap(this->_M_impl._M_head._M_next,
984 : __list._M_impl._M_head._M_next);
985 : _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
986 : __list._M_get_Node_allocator());
987 : }
988 :
989 : /**
990 : * @brief Resizes the %forward_list to the specified number of
991 : * elements.
992 : * @param __sz Number of elements the %forward_list should contain.
993 : *
994 : * This function will %resize the %forward_list to the specified
995 : * number of elements. If the number is smaller than the
996 : * %forward_list's current number of elements the %forward_list
997 : * is truncated, otherwise the %forward_list is extended and the
998 : * new elements are default constructed.
999 : */
1000 : void
1001 : resize(size_type __sz);
1002 :
1003 : /**
1004 : * @brief Resizes the %forward_list to the specified number of
1005 : * elements.
1006 : * @param __sz Number of elements the %forward_list should contain.
1007 : * @param __val Data with which new elements should be populated.
1008 : *
1009 : * This function will %resize the %forward_list to the specified
1010 : * number of elements. If the number is smaller than the
1011 : * %forward_list's current number of elements the %forward_list
1012 : * is truncated, otherwise the %forward_list is extended and new
1013 : * elements are populated with given data.
1014 : */
1015 : void
1016 : resize(size_type __sz, const value_type& __val);
1017 :
1018 : /**
1019 : * @brief Erases all the elements.
1020 : *
1021 : * Note that this function only erases
1022 : * the elements, and that if the elements themselves are
1023 : * pointers, the pointed-to memory is not touched in any way.
1024 : * Managing the pointer is the user's responsibility.
1025 : */
1026 : void
1027 : clear() noexcept
1028 : { this->_M_erase_after(&this->_M_impl._M_head, 0); }
1029 :
1030 : // 23.3.4.6 forward_list operations:
1031 :
1032 : /**
1033 : * @brief Insert contents of another %forward_list.
1034 : * @param __pos Iterator referencing the element to insert after.
1035 : * @param __list Source list.
1036 : *
1037 : * The elements of @a list are inserted in constant time after
1038 : * the element referenced by @a pos. @a list becomes an empty
1039 : * list.
1040 : *
1041 : * Requires this != @a x.
1042 : */
1043 : void
1044 : splice_after(const_iterator __pos, forward_list&& __list)
1045 : {
1046 : if (!__list.empty())
1047 : _M_splice_after(__pos, __list.before_begin(), __list.end());
1048 : }
1049 :
1050 : void
1051 : splice_after(const_iterator __pos, forward_list& __list)
1052 : { splice_after(__pos, std::move(__list)); }
1053 :
1054 : /**
1055 : * @brief Insert element from another %forward_list.
1056 : * @param __pos Iterator referencing the element to insert after.
1057 : * @param __list Source list.
1058 : * @param __i Iterator referencing the element before the element
1059 : * to move.
1060 : *
1061 : * Removes the element in list @a list referenced by @a i and
1062 : * inserts it into the current list after @a pos.
1063 : */
1064 : void
1065 : splice_after(const_iterator __pos, forward_list&& __list,
1066 : const_iterator __i);
1067 :
1068 : void
1069 : splice_after(const_iterator __pos, forward_list& __list,
1070 : const_iterator __i)
1071 : { splice_after(__pos, std::move(__list), __i); }
1072 :
1073 : /**
1074 : * @brief Insert range from another %forward_list.
1075 : * @param __pos Iterator referencing the element to insert after.
1076 : * @param __list Source list.
1077 : * @param __before Iterator referencing before the start of range
1078 : * in list.
1079 : * @param __last Iterator referencing the end of range in list.
1080 : *
1081 : * Removes elements in the range (__before,__last) and inserts them
1082 : * after @a __pos in constant time.
1083 : *
1084 : * Undefined if @a __pos is in (__before,__last).
1085 : */
1086 : void
1087 : splice_after(const_iterator __pos, forward_list&&,
1088 : const_iterator __before, const_iterator __last)
1089 : { _M_splice_after(__pos, __before, __last); }
1090 :
1091 : void
1092 : splice_after(const_iterator __pos, forward_list&,
1093 : const_iterator __before, const_iterator __last)
1094 : { _M_splice_after(__pos, __before, __last); }
1095 :
1096 : /**
1097 : * @brief Remove all elements equal to value.
1098 : * @param __val The value to remove.
1099 : *
1100 : * Removes every element in the list equal to @a __val.
1101 : * Remaining elements stay in list order. Note that this
1102 : * function only erases the elements, and that if the elements
1103 : * themselves are pointers, the pointed-to memory is not
1104 : * touched in any way. Managing the pointer is the user's
1105 : * responsibility.
1106 : */
1107 : void
1108 : remove(const _Tp& __val);
1109 :
1110 : /**
1111 : * @brief Remove all elements satisfying a predicate.
1112 : * @param __pred Unary predicate function or object.
1113 : *
1114 : * Removes every element in the list for which the predicate
1115 : * returns true. Remaining elements stay in list order. Note
1116 : * that this function only erases the elements, and that if the
1117 : * elements themselves are pointers, the pointed-to memory is
1118 : * not touched in any way. Managing the pointer is the user's
1119 : * responsibility.
1120 : */
1121 : template<typename _Pred>
1122 : void
1123 : remove_if(_Pred __pred);
1124 :
1125 : /**
1126 : * @brief Remove consecutive duplicate elements.
1127 : *
1128 : * For each consecutive set of elements with the same value,
1129 : * remove all but the first one. Remaining elements stay in
1130 : * list order. Note that this function only erases the
1131 : * elements, and that if the elements themselves are pointers,
1132 : * the pointed-to memory is not touched in any way. Managing
1133 : * the pointer is the user's responsibility.
1134 : */
1135 : void
1136 : unique()
1137 : { unique(std::equal_to<_Tp>()); }
1138 :
1139 : /**
1140 : * @brief Remove consecutive elements satisfying a predicate.
1141 : * @param __binary_pred Binary predicate function or object.
1142 : *
1143 : * For each consecutive set of elements [first,last) that
1144 : * satisfy predicate(first,i) where i is an iterator in
1145 : * [first,last), remove all but the first one. Remaining
1146 : * elements stay in list order. Note that this function only
1147 : * erases the elements, and that if the elements themselves are
1148 : * pointers, the pointed-to memory is not touched in any way.
1149 : * Managing the pointer is the user's responsibility.
1150 : */
1151 : template<typename _BinPred>
1152 : void
1153 : unique(_BinPred __binary_pred);
1154 :
1155 : /**
1156 : * @brief Merge sorted lists.
1157 : * @param __list Sorted list to merge.
1158 : *
1159 : * Assumes that both @a list and this list are sorted according to
1160 : * operator<(). Merges elements of @a __list into this list in
1161 : * sorted order, leaving @a __list empty when complete. Elements in
1162 : * this list precede elements in @a __list that are equal.
1163 : */
1164 : void
1165 : merge(forward_list&& __list)
1166 : { merge(std::move(__list), std::less<_Tp>()); }
1167 :
1168 : void
1169 : merge(forward_list& __list)
1170 : { merge(std::move(__list)); }
1171 :
1172 : /**
1173 : * @brief Merge sorted lists according to comparison function.
1174 : * @param __list Sorted list to merge.
1175 : * @param __comp Comparison function defining sort order.
1176 : *
1177 : * Assumes that both @a __list and this list are sorted according to
1178 : * comp. Merges elements of @a __list into this list
1179 : * in sorted order, leaving @a __list empty when complete. Elements
1180 : * in this list precede elements in @a __list that are equivalent
1181 : * according to comp().
1182 : */
1183 : template<typename _Comp>
1184 : void
1185 : merge(forward_list&& __list, _Comp __comp);
1186 :
1187 : template<typename _Comp>
1188 : void
1189 : merge(forward_list& __list, _Comp __comp)
1190 : { merge(std::move(__list), __comp); }
1191 :
1192 : /**
1193 : * @brief Sort the elements of the list.
1194 : *
1195 : * Sorts the elements of this list in NlogN time. Equivalent
1196 : * elements remain in list order.
1197 : */
1198 : void
1199 : sort()
1200 : { sort(std::less<_Tp>()); }
1201 :
1202 : /**
1203 : * @brief Sort the forward_list using a comparison function.
1204 : *
1205 : * Sorts the elements of this list in NlogN time. Equivalent
1206 : * elements remain in list order.
1207 : */
1208 : template<typename _Comp>
1209 : void
1210 : sort(_Comp __comp);
1211 :
1212 : /**
1213 : * @brief Reverse the elements in list.
1214 : *
1215 : * Reverse the order of elements in the list in linear time.
1216 : */
1217 : void
1218 : reverse() noexcept
1219 : { this->_M_impl._M_head._M_reverse_after(); }
1220 :
1221 : private:
1222 : // Called by the range constructor to implement [23.3.4.2]/9
1223 : template<typename _InputIterator>
1224 : void
1225 : _M_range_initialize(_InputIterator __first, _InputIterator __last);
1226 :
1227 : // Called by forward_list(n,v,a), and the range constructor when it
1228 : // turns out to be the same thing.
1229 : void
1230 : _M_fill_initialize(size_type __n, const value_type& __value);
1231 :
1232 : // Called by splice_after and insert_after.
1233 : iterator
1234 : _M_splice_after(const_iterator __pos, const_iterator __before,
1235 : const_iterator __last);
1236 :
1237 : // Called by forward_list(n).
1238 : void
1239 : _M_default_initialize(size_type __n);
1240 :
1241 : // Called by resize(sz).
1242 : void
1243 : _M_default_insert_after(const_iterator __pos, size_type __n);
1244 :
1245 : // Called by operator=(forward_list&&)
1246 : void
1247 : _M_move_assign(forward_list&& __list, std::true_type) noexcept
1248 : {
1249 : clear();
1250 : std::swap(this->_M_impl._M_head._M_next,
1251 : __list._M_impl._M_head._M_next);
1252 : std::__alloc_on_move(this->_M_get_Node_allocator(),
1253 : __list._M_get_Node_allocator());
1254 : }
1255 :
1256 : // Called by operator=(forward_list&&)
1257 : void
1258 : _M_move_assign(forward_list&& __list, std::false_type)
1259 : {
1260 : if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1261 : _M_move_assign(std::move(__list), std::true_type());
1262 : else
1263 : // The rvalue's allocator cannot be moved, or is not equal,
1264 : // so we need to individually move each element.
1265 : this->assign(std::__make_move_if_noexcept_iterator(__list.begin()),
1266 : std::__make_move_if_noexcept_iterator(__list.end()));
1267 : }
1268 :
1269 : // Called by assign(_InputIterator, _InputIterator) if _Tp is
1270 : // CopyAssignable.
1271 : template<typename _InputIterator>
1272 : void
1273 : _M_assign(_InputIterator __first, _InputIterator __last, true_type)
1274 : {
1275 : auto __prev = before_begin();
1276 : auto __curr = begin();
1277 : auto __end = end();
1278 : while (__curr != __end && __first != __last)
1279 : {
1280 : *__curr = *__first;
1281 : ++__prev;
1282 : ++__curr;
1283 : ++__first;
1284 : }
1285 : if (__first != __last)
1286 : insert_after(__prev, __first, __last);
1287 : else if (__curr != __end)
1288 : erase_after(__prev, __end);
1289 : }
1290 :
1291 : // Called by assign(_InputIterator, _InputIterator) if _Tp is not
1292 : // CopyAssignable.
1293 : template<typename _InputIterator>
1294 : void
1295 : _M_assign(_InputIterator __first, _InputIterator __last, false_type)
1296 : {
1297 : clear();
1298 : insert_after(cbefore_begin(), __first, __last);
1299 : }
1300 :
1301 : // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable
1302 : void
1303 : _M_assign_n(size_type __n, const _Tp& __val, true_type)
1304 : {
1305 : auto __prev = before_begin();
1306 : auto __curr = begin();
1307 : auto __end = end();
1308 : while (__curr != __end && __n > 0)
1309 : {
1310 : *__curr = __val;
1311 : ++__prev;
1312 : ++__curr;
1313 : --__n;
1314 : }
1315 : if (__n > 0)
1316 : insert_after(__prev, __n, __val);
1317 : else if (__curr != __end)
1318 : erase_after(__prev, __end);
1319 : }
1320 :
1321 : // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable
1322 : void
1323 : _M_assign_n(size_type __n, const _Tp& __val, false_type)
1324 : {
1325 : clear();
1326 : insert_after(cbefore_begin(), __n, __val);
1327 : }
1328 : };
1329 :
1330 : /**
1331 : * @brief Forward list equality comparison.
1332 : * @param __lx A %forward_list
1333 : * @param __ly A %forward_list of the same type as @a __lx.
1334 : * @return True iff the elements of the forward lists are equal.
1335 : *
1336 : * This is an equivalence relation. It is linear in the number of
1337 : * elements of the forward lists. Deques are considered equivalent
1338 : * if corresponding elements compare equal.
1339 : */
1340 : template<typename _Tp, typename _Alloc>
1341 : bool
1342 : operator==(const forward_list<_Tp, _Alloc>& __lx,
1343 : const forward_list<_Tp, _Alloc>& __ly);
1344 :
1345 : /**
1346 : * @brief Forward list ordering relation.
1347 : * @param __lx A %forward_list.
1348 : * @param __ly A %forward_list of the same type as @a __lx.
1349 : * @return True iff @a __lx is lexicographically less than @a __ly.
1350 : *
1351 : * This is a total ordering relation. It is linear in the number of
1352 : * elements of the forward lists. The elements must be comparable
1353 : * with @c <.
1354 : *
1355 : * See std::lexicographical_compare() for how the determination is made.
1356 : */
1357 : template<typename _Tp, typename _Alloc>
1358 : inline bool
1359 : operator<(const forward_list<_Tp, _Alloc>& __lx,
1360 : const forward_list<_Tp, _Alloc>& __ly)
1361 : { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
1362 : __ly.cbegin(), __ly.cend()); }
1363 :
1364 : /// Based on operator==
1365 : template<typename _Tp, typename _Alloc>
1366 : inline bool
1367 : operator!=(const forward_list<_Tp, _Alloc>& __lx,
1368 : const forward_list<_Tp, _Alloc>& __ly)
1369 : { return !(__lx == __ly); }
1370 :
1371 : /// Based on operator<
1372 : template<typename _Tp, typename _Alloc>
1373 : inline bool
1374 : operator>(const forward_list<_Tp, _Alloc>& __lx,
1375 : const forward_list<_Tp, _Alloc>& __ly)
1376 : { return (__ly < __lx); }
1377 :
1378 : /// Based on operator<
1379 : template<typename _Tp, typename _Alloc>
1380 : inline bool
1381 : operator>=(const forward_list<_Tp, _Alloc>& __lx,
1382 : const forward_list<_Tp, _Alloc>& __ly)
1383 : { return !(__lx < __ly); }
1384 :
1385 : /// Based on operator<
1386 : template<typename _Tp, typename _Alloc>
1387 : inline bool
1388 : operator<=(const forward_list<_Tp, _Alloc>& __lx,
1389 : const forward_list<_Tp, _Alloc>& __ly)
1390 : { return !(__ly < __lx); }
1391 :
1392 : /// See std::forward_list::swap().
1393 : template<typename _Tp, typename _Alloc>
1394 : inline void
1395 : swap(forward_list<_Tp, _Alloc>& __lx,
1396 : forward_list<_Tp, _Alloc>& __ly)
1397 : { __lx.swap(__ly); }
1398 :
1399 : _GLIBCXX_END_NAMESPACE_CONTAINER
1400 : } // namespace std
1401 :
1402 : #endif // _FORWARD_LIST_H
|