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