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