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