STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Functions
forward_list.h File Reference
#include <memory>

Go to the source code of this file.

Functions

namespace std _GLIBCXX_VISIBILITY (default)
 

Detailed Description

This is an internal header file, included by other library headers. Do not attempt to use it directly. {forward_list}

Function Documentation

namespace std _GLIBCXX_VISIBILITY ( default  )

A helper basic node class for forward_list. This is just a linked list with nothing inside it. There are purely list shuffling utility methods here.

A helper node class for forward_list. This is just a linked list with uninitialized storage for a data value in each node. There is a sorting utility method.

A forward_list::iterator.

All the functions are op overloads.

A forward_list::const_iterator.

All the functions are op overloads.

Forward list iterator equality comparison.

Forward list iterator inequality comparison.

Base class for forward_list.

A standard container with linear time access to elements, and fixed time insertion/deletion at any point in the sequence.

Template Parameters
_TpType of element.
_AllocAllocator type, defaults to allocator<_Tp>.

Meets the requirements of a container, a sequence, including the optional sequence requirements with the exception of at and operator[].

This is a singly linked list. Traversal up the list requires linear time, but adding and removing elements (or nodes) is done in constant time, regardless of where the change takes place. Unlike std::vector and std::deque, random-access iterators are not provided, so subscripting ( [] ) access is not allowed. For algorithms which only need sequential access, this lack makes no difference.

Also unlike the other standard containers, std::forward_list provides specialized algorithms unique to linked lists, such as splicing, sorting, and in-place reversal.

Creates a forward_list with no elements.

Parameters
__alAn allocator object.

Copy constructor with allocator argument.

Parameters
__listInput list to copy.
__alAn allocator object.

Move constructor with allocator argument.

Parameters
__listInput list to move.
__alAn allocator object.

Creates a forward_list with default constructed elements.

Parameters
__nThe number of elements to initially create.

This constructor creates the forward_list with __n default constructed elements.

Creates a forward_list with copies of an exemplar element.

Parameters
__nThe number of elements to initially create.
__valueAn element to copy.
__alAn allocator object.

This constructor fills the forward_list with __n copies of __value.

Builds a forward_list from a range.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__alAn allocator object.

Create a forward_list consisting of copies of the elements from [__first,__last). This is linear in N (where N is distance(__first,__last)).

The forward_list copy constructor.

Parameters
__listA forward_list of identical element and allocator types.

The forward_list move constructor.

Parameters
__listA forward_list of identical element and allocator types.

The newly-created forward_list contains the exact contents of __list. The contents of __list are a valid, but unspecified forward_list.

Builds a forward_list from an initializer_list

Parameters
__ilAn initializer_list of value_type.
__alAn allocator object.

Create a forward_list consisting of copies of the elements in the initializer_list __il. This is linear in __il.size().

The forward_list dtor.

The forward_list assignment operator.

Parameters
__listA forward_list of identical element and allocator types.

All the elements of __list are copied, but unlike the copy constructor, the allocator object is not copied.

The forward_list move assignment operator.

Parameters
__listA forward_list of identical element and allocator types.

The contents of __list are moved into this forward_list (without copying, if the allocators permit it). __list is a valid, but unspecified forward_list

The forward_list initializer list assignment operator.

Parameters
__ilAn initializer_list of value_type.

Replace the contents of the forward_list with copies of the elements in the initializer_list __il. This is linear in __il.size().

Assigns a range to a forward_list.

Parameters
__firstAn input iterator.
__lastAn input iterator.

This function fills a forward_list with copies of the elements in the range [__first,__last).

Note that the assignment completely changes the forward_list and that the number of elements of the resulting forward_list is the same as the number of elements assigned. Old data is lost.

Assigns a given value to a forward_list.

Parameters
__nNumber of elements to be assigned.
__valValue to be assigned.

This function fills a forward_list with __n copies of the given value. Note that the assignment completely changes the forward_list, and that the resulting forward_list has __n elements. Old data is lost.

Assigns an initializer_list to a forward_list.

Parameters
__ilAn initializer_list of value_type.

Replace the contents of the forward_list with copies of the elements in the initializer_list __il. This is linear in il.size().

Get a copy of the memory allocation object.

Returns a read/write iterator that points before the first element in the forward_list. Iteration is done in ordinary element order.

Returns a read-only (constant) iterator that points before the first element in the forward_list. Iteration is done in ordinary element order.

Returns a read/write iterator that points to the first element in the forward_list. Iteration is done in ordinary element order.

Returns a read-only (constant) iterator that points to the first element in the forward_list. Iteration is done in ordinary element order.

Returns a read/write iterator that points one past the last element in the forward_list. Iteration is done in ordinary element order.

Returns a read-only iterator that points one past the last element in the forward_list. Iteration is done in ordinary element order.

Returns a read-only (constant) iterator that points to the first element in the forward_list. Iteration is done in ordinary element order.

Returns a read-only (constant) iterator that points before the first element in the forward_list. Iteration is done in ordinary element order.

Returns a read-only (constant) iterator that points one past the last element in the forward_list. Iteration is done in ordinary element order.

Returns true if the forward_list is empty. (Thus begin() would equal end().)

Returns the largest possible number of elements of forward_list.

Returns a read/write reference to the data at the first element of the forward_list.

Returns a read-only (constant) reference to the data at the first element of the forward_list.

Constructs object in forward_list at the front of the list.

Parameters
__argsArguments.

This function will insert an object of type Tp constructed with Tp(std::forward<Args>(args)...) at the front of the list Due to the nature of a forward_list this operation can be done in constant time, and does not invalidate iterators and references.

Add data to the front of the forward_list.

Parameters
__valData to be added.

This is a typical stack operation. The function creates an element at the front of the forward_list and assigns the given data to it. Due to the nature of a forward_list this operation can be done in constant time, and does not invalidate iterators and references.

Removes first element.

This is a typical stack operation. It shrinks the forward_list by one. Due to the nature of a forward_list this operation can be done in constant time, and only invalidates iterators/references to the element being removed.

Note that no data is returned, and if the first element's data is needed, it should be retrieved before pop_front() is called.

Constructs object in forward_list after the specified iterator.

Parameters
__posA const_iterator into the forward_list.
__argsArguments.
Returns
An iterator that points to the inserted data.

This function will insert an object of type T constructed with T(std::forward<Args>(args)...) after the specified location. Due to the nature of a forward_list this operation can be done in constant time, and does not invalidate iterators and references.

Inserts given value into forward_list after specified iterator.

Parameters
__posAn iterator into the forward_list.
__valData to be inserted.
Returns
An iterator that points to the inserted data.

This function will insert a copy of the given value after the specified location. Due to the nature of a forward_list this operation can be done in constant time, and does not invalidate iterators and references.

Inserts a number of copies of given data into the forward_list.

Parameters
__posAn iterator into the forward_list.
__nNumber of elements to be inserted.
__valData to be inserted.
Returns
An iterator pointing to the last inserted copy of val or pos if n == 0.

This function will insert a specified number of copies of the given data after the location specified by pos.

This operation is linear in the number of elements inserted and does not invalidate iterators and references.

Inserts a range into the forward_list.

Parameters
__posAn iterator into the forward_list.
__firstAn input iterator.
__lastAn input iterator.
Returns
An iterator pointing to the last inserted element or __pos if __first == __last.

This function will insert copies of the data in the range [__first,__last) into the forward_list after the location specified by __pos.

This operation is linear in the number of elements inserted and does not invalidate iterators and references.

Inserts the contents of an initializer_list into forward_list after the specified iterator.

Parameters
__posAn iterator into the forward_list.
__ilAn initializer_list of value_type.
Returns
An iterator pointing to the last inserted element or __pos if __il is empty.

This function will insert copies of the data in the initializer_list __il into the forward_list before the location specified by __pos.

This operation is linear in the number of elements inserted and does not invalidate iterators and references.

Removes the element pointed to by the iterator following pos.

Parameters
__posIterator pointing before element to be erased.
Returns
An iterator pointing to the element following the one that was erased, or end() if no such element exists.

This function will erase the element at the given position and thus shorten the forward_list by one.

Due to the nature of a forward_list this operation can be done in constant time, and only invalidates iterators/references to the element being removed. The user is also cautioned that this function only erases the element, and that if the element is itself a pointer, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Remove a range of elements.

Parameters
__posIterator pointing before the first element to be erased.
__lastIterator pointing to one past the last element to be erased.
Returns
@ __last.

This function will erase the elements in the range (__pos,__last) and shorten the forward_list accordingly.

This operation is linear time in the size of the range and only invalidates iterators/references to the element being removed. The user is also cautioned that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Swaps data with another forward_list.

Parameters
__listA forward_list of the same element and allocator types.

This exchanges the elements between two lists in constant time. Note that the global std::swap() function is specialized such that std::swap(l1,l2) will feed to this function.

Resizes the forward_list to the specified number of elements.

Parameters
__szNumber of elements the forward_list should contain.

This function will resize the forward_list to the specified number of elements. If the number is smaller than the forward_list's current number of elements the forward_list is truncated, otherwise the forward_list is extended and the new elements are default constructed.

Resizes the forward_list to the specified number of elements.

Parameters
__szNumber of elements the forward_list should contain.
__valData with which new elements should be populated.

This function will resize the forward_list to the specified number of elements. If the number is smaller than the forward_list's current number of elements the forward_list is truncated, otherwise the forward_list is extended and new elements are populated with given data.

Erases all the elements.

Note that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Insert contents of another forward_list.

Parameters
__posIterator referencing the element to insert after.
__listSource list.

The elements of list are inserted in constant time after the element referenced by pos. list becomes an empty list.

Requires this != x.

Insert element from another forward_list.

Parameters
__posIterator referencing the element to insert after.
__listSource list.
__iIterator referencing the element before the element to move.

Removes the element in list list referenced by i and inserts it into the current list after pos.

Insert range from another forward_list.

Parameters
__posIterator referencing the element to insert after.
__listSource list.
__beforeIterator referencing before the start of range in list.
__lastIterator referencing the end of range in list.

Removes elements in the range (__before,__last) and inserts them after __pos in constant time.

Undefined if __pos is in (__before,__last).

Remove all elements equal to value.

Parameters
__valThe value to remove.

Removes every element in the list equal to __val. Remaining elements stay in list order. Note that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Remove all elements satisfying a predicate.

Parameters
__predUnary predicate function or object.

Removes every element in the list for which the predicate returns true. Remaining elements stay in list order. Note that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Remove consecutive duplicate elements.

For each consecutive set of elements with the same value, remove all but the first one. Remaining elements stay in list order. Note that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Remove consecutive elements satisfying a predicate.

Parameters
__binary_predBinary predicate function or object.

For each consecutive set of elements [first,last) that satisfy predicate(first,i) where i is an iterator in [first,last), remove all but the first one. Remaining elements stay in list order. Note that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

Merge sorted lists.

Parameters
__listSorted list to merge.

Assumes that both list and this list are sorted according to operator<(). Merges elements of __list into this list in sorted order, leaving __list empty when complete. Elements in this list precede elements in __list that are equal.

Merge sorted lists according to comparison function.

Parameters
__listSorted list to merge.
__compComparison function defining sort order.

Assumes that both __list and this list are sorted according to comp. Merges elements of __list into this list in sorted order, leaving __list empty when complete. Elements in this list precede elements in __list that are equivalent according to comp().

Sort the elements of the list.

Sorts the elements of this list in NlogN time. Equivalent elements remain in list order.

Sort the forward_list using a comparison function.

Sorts the elements of this list in NlogN time. Equivalent elements remain in list order.

Reverse the elements in list.

Reverse the order of elements in the list in linear time.

Forward list equality comparison.

Parameters
__lxA forward_list
__lyA forward_list of the same type as __lx.
Returns
True iff the elements of the forward lists are equal.

This is an equivalence relation. It is linear in the number of elements of the forward lists. Deques are considered equivalent if corresponding elements compare equal.

Forward list ordering relation.

Parameters
__lxA forward_list.
__lyA forward_list of the same type as __lx.
Returns
True iff __lx is lexicographically less than __ly.

This is a total ordering relation. It is linear in the number of elements of the forward lists. The elements must be comparable with <.

See std::lexicographical_compare() for how the determination is made.

Based on operator==

Based on operator<

Based on operator<

Based on operator<

See std::forward_list::swap().

41 {
42 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
43 
49  struct _Fwd_list_node_base
50  {
51  _Fwd_list_node_base() = default;
52 
53  _Fwd_list_node_base* _M_next = nullptr;
54 
55  _Fwd_list_node_base*
56  _M_transfer_after(_Fwd_list_node_base* __begin,
57  _Fwd_list_node_base* __end)
58  {
59  _Fwd_list_node_base* __keep = __begin->_M_next;
60  if (__end)
61  {
62  __begin->_M_next = __end->_M_next;
63  __end->_M_next = _M_next;
64  }
65  else
66  __begin->_M_next = 0;
67  _M_next = __keep;
68  return __end;
69  }
70 
71  void
72  _M_reverse_after() noexcept
73  {
74  _Fwd_list_node_base* __tail = _M_next;
75  if (!__tail)
76  return;
77  while (_Fwd_list_node_base* __temp = __tail->_M_next)
78  {
79  _Fwd_list_node_base* __keep = _M_next;
80  _M_next = __temp;
81  __tail->_M_next = __temp->_M_next;
82  _M_next->_M_next = __keep;
83  }
84  }
85  };
86 
93  template<typename _Tp>
94  struct _Fwd_list_node
95  : public _Fwd_list_node_base
96  {
97  _Fwd_list_node() = default;
98 
99  typename aligned_storage<sizeof(_Tp), alignment_of<_Tp>::value>::type
100  _M_storage;
101 
102  _Tp*
103  _M_valptr() noexcept
104  {
105  return static_cast<_Tp*>(static_cast<void*>(&_M_storage));
106  }
107 
108  const _Tp*
109  _M_valptr() const noexcept
110  {
111  return static_cast<const _Tp*>(static_cast<const void*>(&_M_storage));
112  }
113  };
114 
120  template<typename _Tp>
121  struct _Fwd_list_iterator
122  {
123  typedef _Fwd_list_iterator<_Tp> _Self;
124  typedef _Fwd_list_node<_Tp> _Node;
125 
126  typedef _Tp value_type;
127  typedef _Tp* pointer;
128  typedef _Tp& reference;
129  typedef ptrdiff_t difference_type;
130  typedef std::forward_iterator_tag iterator_category;
131 
132  _Fwd_list_iterator()
133  : _M_node() { }
134 
135  explicit
136  _Fwd_list_iterator(_Fwd_list_node_base* __n)
137  : _M_node(__n) { }
138 
139  reference
140  operator*() const
141  { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
142 
143  pointer
144  operator->() const
145  { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
146 
147  _Self&
148  operator++()
149  {
150  _M_node = _M_node->_M_next;
151  return *this;
152  }
153 
154  _Self
155  operator++(int)
156  {
157  _Self __tmp(*this);
158  _M_node = _M_node->_M_next;
159  return __tmp;
160  }
161 
162  bool
163  operator==(const _Self& __x) const
164  { return _M_node == __x._M_node; }
165 
166  bool
167  operator!=(const _Self& __x) const
168  { return _M_node != __x._M_node; }
169 
170  _Self
171  _M_next() const
172  {
173  if (_M_node)
174  return _Fwd_list_iterator(_M_node->_M_next);
175  else
176  return _Fwd_list_iterator(0);
177  }
178 
179  _Fwd_list_node_base* _M_node;
180  };
181 
187  template<typename _Tp>
188  struct _Fwd_list_const_iterator
189  {
190  typedef _Fwd_list_const_iterator<_Tp> _Self;
191  typedef const _Fwd_list_node<_Tp> _Node;
192  typedef _Fwd_list_iterator<_Tp> iterator;
193 
194  typedef _Tp value_type;
195  typedef const _Tp* pointer;
196  typedef const _Tp& reference;
197  typedef ptrdiff_t difference_type;
198  typedef std::forward_iterator_tag iterator_category;
199 
200  _Fwd_list_const_iterator()
201  : _M_node() { }
202 
203  explicit
204  _Fwd_list_const_iterator(const _Fwd_list_node_base* __n)
205  : _M_node(__n) { }
206 
207  _Fwd_list_const_iterator(const iterator& __iter)
208  : _M_node(__iter._M_node) { }
209 
210  reference
211  operator*() const
212  { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
213 
214  pointer
215  operator->() const
216  { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
217 
218  _Self&
219  operator++()
220  {
221  _M_node = _M_node->_M_next;
222  return *this;
223  }
224 
225  _Self
226  operator++(int)
227  {
228  _Self __tmp(*this);
229  _M_node = _M_node->_M_next;
230  return __tmp;
231  }
232 
233  bool
234  operator==(const _Self& __x) const
235  { return _M_node == __x._M_node; }
236 
237  bool
238  operator!=(const _Self& __x) const
239  { return _M_node != __x._M_node; }
240 
241  _Self
242  _M_next() const
243  {
244  if (this->_M_node)
245  return _Fwd_list_const_iterator(_M_node->_M_next);
246  else
247  return _Fwd_list_const_iterator(0);
248  }
249 
250  const _Fwd_list_node_base* _M_node;
251  };
252 
256  template<typename _Tp>
257  inline bool
258  operator==(const _Fwd_list_iterator<_Tp>& __x,
259  const _Fwd_list_const_iterator<_Tp>& __y)
260  { return __x._M_node == __y._M_node; }
261 
265  template<typename _Tp>
266  inline bool
267  operator!=(const _Fwd_list_iterator<_Tp>& __x,
268  const _Fwd_list_const_iterator<_Tp>& __y)
269  { return __x._M_node != __y._M_node; }
270 
274  template<typename _Tp, typename _Alloc>
275  struct _Fwd_list_base
276  {
277  protected:
278  typedef typename __gnu_cxx::__alloc_traits<_Alloc> _Alloc_traits;
279  typedef typename _Alloc_traits::template rebind<_Tp>::other
280  _Tp_alloc_type;
281 
282  typedef typename _Alloc_traits::template
283  rebind<_Fwd_list_node<_Tp>>::other _Node_alloc_type;
284 
285  typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
286 
287  struct _Fwd_list_impl
288  : public _Node_alloc_type
289  {
290  _Fwd_list_node_base _M_head;
291 
292  _Fwd_list_impl()
293  : _Node_alloc_type(), _M_head()
294  { }
295 
296  _Fwd_list_impl(const _Node_alloc_type& __a)
297  : _Node_alloc_type(__a), _M_head()
298  { }
299 
300  _Fwd_list_impl(_Node_alloc_type&& __a)
301  : _Node_alloc_type(std::move(__a)), _M_head()
302  { }
303  };
304 
305  _Fwd_list_impl _M_impl;
306 
307  public:
308  typedef _Fwd_list_iterator<_Tp> iterator;
309  typedef _Fwd_list_const_iterator<_Tp> const_iterator;
310  typedef _Fwd_list_node<_Tp> _Node;
311 
312  _Node_alloc_type&
313  _M_get_Node_allocator() noexcept
314  { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
315 
316  const _Node_alloc_type&
317  _M_get_Node_allocator() const noexcept
318  { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
319 
320  _Fwd_list_base()
321  : _M_impl() { }
322 
323  _Fwd_list_base(const _Node_alloc_type& __a)
324  : _M_impl(__a) { }
325 
326  _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a);
327 
328  _Fwd_list_base(_Fwd_list_base&& __lst)
329  : _M_impl(std::move(__lst._M_get_Node_allocator()))
330  {
331  this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
332  __lst._M_impl._M_head._M_next = 0;
333  }
334 
335  ~_Fwd_list_base()
336  { _M_erase_after(&_M_impl._M_head, 0); }
337 
338  protected:
339 
340  _Node*
341  _M_get_node()
342  { return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); }
343 
344  template<typename... _Args>
345  _Node*
346  _M_create_node(_Args&&... __args)
347  {
348  _Node* __node = this->_M_get_node();
349  __try
350  {
351  _Tp_alloc_type __a(_M_get_Node_allocator());
352  typedef allocator_traits<_Tp_alloc_type> _Alloc_traits;
353  ::new ((void*)__node) _Node();
354  _Alloc_traits::construct(__a, __node->_M_valptr(),
355  std::forward<_Args>(__args)...);
356  }
357  __catch(...)
358  {
359  this->_M_put_node(__node);
360  __throw_exception_again;
361  }
362  return __node;
363  }
364 
365  template<typename... _Args>
366  _Fwd_list_node_base*
367  _M_insert_after(const_iterator __pos, _Args&&... __args);
368 
369  void
370  _M_put_node(_Node* __p)
371  { _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
372 
373  _Fwd_list_node_base*
374  _M_erase_after(_Fwd_list_node_base* __pos);
375 
376  _Fwd_list_node_base*
377  _M_erase_after(_Fwd_list_node_base* __pos,
378  _Fwd_list_node_base* __last);
379  };
380 
407  template<typename _Tp, typename _Alloc = allocator<_Tp> >
408  class forward_list : private _Fwd_list_base<_Tp, _Alloc>
409  {
410  private:
411  typedef _Fwd_list_base<_Tp, _Alloc> _Base;
412  typedef _Fwd_list_node<_Tp> _Node;
413  typedef _Fwd_list_node_base _Node_base;
414  typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
415  typedef typename _Base::_Node_alloc_type _Node_alloc_type;
416  typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
417  typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
418 
419  public:
420  // types:
421  typedef _Tp value_type;
422  typedef typename _Alloc_traits::pointer pointer;
423  typedef typename _Alloc_traits::const_pointer const_pointer;
424  typedef typename _Alloc_traits::reference reference;
425  typedef typename _Alloc_traits::const_reference const_reference;
426 
427  typedef _Fwd_list_iterator<_Tp> iterator;
428  typedef _Fwd_list_const_iterator<_Tp> const_iterator;
429  typedef std::size_t size_type;
430  typedef std::ptrdiff_t difference_type;
431  typedef _Alloc allocator_type;
432 
433  // 23.3.4.2 construct/copy/destroy:
434 
439  explicit
440  forward_list(const _Alloc& __al = _Alloc())
441  : _Base(_Node_alloc_type(__al))
442  { }
443 
449  forward_list(const forward_list& __list, const _Alloc& __al)
450  : _Base(_Node_alloc_type(__al))
451  { _M_range_initialize(__list.begin(), __list.end()); }
452 
458  forward_list(forward_list&& __list, const _Alloc& __al)
459  noexcept(_Node_alloc_traits::_S_always_equal())
460  : _Base(std::move(__list), _Node_alloc_type(__al))
461  { }
462 
470  explicit
471  forward_list(size_type __n, const _Alloc& __al = _Alloc())
472  : _Base(_Node_alloc_type(__al))
473  { _M_default_initialize(__n); }
474 
484  forward_list(size_type __n, const _Tp& __value,
485  const _Alloc& __al = _Alloc())
486  : _Base(_Node_alloc_type(__al))
487  { _M_fill_initialize(__n, __value); }
488 
499  template<typename _InputIterator,
500  typename = std::_RequireInputIter<_InputIterator>>
501  forward_list(_InputIterator __first, _InputIterator __last,
502  const _Alloc& __al = _Alloc())
503  : _Base(_Node_alloc_type(__al))
504  { _M_range_initialize(__first, __last); }
505 
511  forward_list(const forward_list& __list)
512  : _Base(_Node_alloc_traits::_S_select_on_copy(
513  __list._M_get_Node_allocator()))
514  { _M_range_initialize(__list.begin(), __list.end()); }
515 
525  forward_list(forward_list&& __list) noexcept
526  : _Base(std::move(__list)) { }
527 
536  forward_list(std::initializer_list<_Tp> __il,
537  const _Alloc& __al = _Alloc())
538  : _Base(_Node_alloc_type(__al))
539  { _M_range_initialize(__il.begin(), __il.end()); }
540 
544  ~forward_list() noexcept
545  { }
546 
555  forward_list&
556  operator=(const forward_list& __list);
557 
567  forward_list&
568  operator=(forward_list&& __list)
569  noexcept(_Node_alloc_traits::_S_nothrow_move())
570  {
571  constexpr bool __move_storage =
572  _Node_alloc_traits::_S_propagate_on_move_assign()
573  || _Node_alloc_traits::_S_always_equal();
574  _M_move_assign(std::move(__list),
575  integral_constant<bool, __move_storage>());
576  return *this;
577  }
578 
587  forward_list&
588  operator=(std::initializer_list<_Tp> __il)
589  {
590  assign(__il);
591  return *this;
592  }
593 
606  template<typename _InputIterator,
607  typename = std::_RequireInputIter<_InputIterator>>
608  void
609  assign(_InputIterator __first, _InputIterator __last)
610  {
611  typedef is_assignable<_Tp, decltype(*__first)> __assignable;
612  _M_assign(__first, __last, __assignable());
613  }
614 
625  void
626  assign(size_type __n, const _Tp& __val)
627  { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); }
628 
637  void
638  assign(std::initializer_list<_Tp> __il)
639  { assign(__il.begin(), __il.end()); }
640 
642  allocator_type
643  get_allocator() const noexcept
644  { return allocator_type(this->_M_get_Node_allocator()); }
645 
646  // 23.3.4.3 iterators:
647 
652  iterator
653  before_begin() noexcept
654  { return iterator(&this->_M_impl._M_head); }
655 
661  const_iterator
662  before_begin() const noexcept
663  { return const_iterator(&this->_M_impl._M_head); }
664 
669  iterator
670  begin() noexcept
671  { return iterator(this->_M_impl._M_head._M_next); }
672 
678  const_iterator
679  begin() const noexcept
680  { return const_iterator(this->_M_impl._M_head._M_next); }
681 
687  iterator
688  end() noexcept
689  { return iterator(0); }
690 
696  const_iterator
697  end() const noexcept
698  { return const_iterator(0); }
699 
705  const_iterator
706  cbegin() const noexcept
707  { return const_iterator(this->_M_impl._M_head._M_next); }
708 
714  const_iterator
715  cbefore_begin() const noexcept
716  { return const_iterator(&this->_M_impl._M_head); }
717 
723  const_iterator
724  cend() const noexcept
725  { return const_iterator(0); }
726 
731  bool
732  empty() const noexcept
733  { return this->_M_impl._M_head._M_next == 0; }
734 
738  size_type
739  max_size() const noexcept
740  { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
741 
742  // 23.3.4.4 element access:
743 
748  reference
749  front()
750  {
751  _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
752  return *__front->_M_valptr();
753  }
754 
759  const_reference
760  front() const
761  {
762  _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
763  return *__front->_M_valptr();
764  }
765 
766  // 23.3.4.5 modiļ¬ers:
767 
779  template<typename... _Args>
780  void
781  emplace_front(_Args&&... __args)
782  { this->_M_insert_after(cbefore_begin(),
783  std::forward<_Args>(__args)...); }
784 
795  void
796  push_front(const _Tp& __val)
797  { this->_M_insert_after(cbefore_begin(), __val); }
798 
802  void
803  push_front(_Tp&& __val)
804  { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
805 
818  void
819  pop_front()
820  { this->_M_erase_after(&this->_M_impl._M_head); }
821 
835  template<typename... _Args>
836  iterator
837  emplace_after(const_iterator __pos, _Args&&... __args)
838  { return iterator(this->_M_insert_after(__pos,
839  std::forward<_Args>(__args)...)); }
840 
853  iterator
854  insert_after(const_iterator __pos, const _Tp& __val)
855  { return iterator(this->_M_insert_after(__pos, __val)); }
856 
860  iterator
861  insert_after(const_iterator __pos, _Tp&& __val)
862  { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
863 
879  iterator
880  insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
881 
897  template<typename _InputIterator,
898  typename = std::_RequireInputIter<_InputIterator>>
899  iterator
900  insert_after(const_iterator __pos,
901  _InputIterator __first, _InputIterator __last);
902 
918  iterator
919  insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
920  { return insert_after(__pos, __il.begin(), __il.end()); }
921 
939  iterator
940  erase_after(const_iterator __pos)
941  { return iterator(this->_M_erase_after(const_cast<_Node_base*>
942  (__pos._M_node))); }
943 
962  iterator
963  erase_after(const_iterator __pos, const_iterator __last)
964  { return iterator(this->_M_erase_after(const_cast<_Node_base*>
965  (__pos._M_node),
966  const_cast<_Node_base*>
967  (__last._M_node))); }
968 
979  void
980  swap(forward_list& __list)
981  noexcept(_Node_alloc_traits::_S_nothrow_swap())
982  {
983  std::swap(this->_M_impl._M_head._M_next,
984  __list._M_impl._M_head._M_next);
985  _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
986  __list._M_get_Node_allocator());
987  }
988 
1000  void
1001  resize(size_type __sz);
1002 
1015  void
1016  resize(size_type __sz, const value_type& __val);
1017 
1026  void
1027  clear() noexcept
1028  { this->_M_erase_after(&this->_M_impl._M_head, 0); }
1029 
1030  // 23.3.4.6 forward_list operations:
1031 
1043  void
1044  splice_after(const_iterator __pos, forward_list&& __list)
1045  {
1046  if (!__list.empty())
1047  _M_splice_after(__pos, __list.before_begin(), __list.end());
1048  }
1049 
1050  void
1051  splice_after(const_iterator __pos, forward_list& __list)
1052  { splice_after(__pos, std::move(__list)); }
1053 
1064  void
1065  splice_after(const_iterator __pos, forward_list&& __list,
1066  const_iterator __i);
1067 
1068  void
1069  splice_after(const_iterator __pos, forward_list& __list,
1070  const_iterator __i)
1071  { splice_after(__pos, std::move(__list), __i); }
1072 
1086  void
1087  splice_after(const_iterator __pos, forward_list&&,
1088  const_iterator __before, const_iterator __last)
1089  { _M_splice_after(__pos, __before, __last); }
1090 
1091  void
1092  splice_after(const_iterator __pos, forward_list&,
1093  const_iterator __before, const_iterator __last)
1094  { _M_splice_after(__pos, __before, __last); }
1095 
1107  void
1108  remove(const _Tp& __val);
1109 
1121  template<typename _Pred>
1122  void
1123  remove_if(_Pred __pred);
1124 
1135  void
1136  unique()
1137  { unique(std::equal_to<_Tp>()); }
1138 
1151  template<typename _BinPred>
1152  void
1153  unique(_BinPred __binary_pred);
1154 
1164  void
1165  merge(forward_list&& __list)
1166  { merge(std::move(__list), std::less<_Tp>()); }
1167 
1168  void
1169  merge(forward_list& __list)
1170  { merge(std::move(__list)); }
1171 
1183  template<typename _Comp>
1184  void
1185  merge(forward_list&& __list, _Comp __comp);
1186 
1187  template<typename _Comp>
1188  void
1189  merge(forward_list& __list, _Comp __comp)
1190  { merge(std::move(__list), __comp); }
1191 
1198  void
1199  sort()
1200  { sort(std::less<_Tp>()); }
1201 
1208  template<typename _Comp>
1209  void
1210  sort(_Comp __comp);
1211 
1217  void
1218  reverse() noexcept
1219  { this->_M_impl._M_head._M_reverse_after(); }
1220 
1221  private:
1222  // Called by the range constructor to implement [23.3.4.2]/9
1223  template<typename _InputIterator>
1224  void
1225  _M_range_initialize(_InputIterator __first, _InputIterator __last);
1226 
1227  // Called by forward_list(n,v,a), and the range constructor when it
1228  // turns out to be the same thing.
1229  void
1230  _M_fill_initialize(size_type __n, const value_type& __value);
1231 
1232  // Called by splice_after and insert_after.
1233  iterator
1234  _M_splice_after(const_iterator __pos, const_iterator __before,
1235  const_iterator __last);
1236 
1237  // Called by forward_list(n).
1238  void
1239  _M_default_initialize(size_type __n);
1240 
1241  // Called by resize(sz).
1242  void
1243  _M_default_insert_after(const_iterator __pos, size_type __n);
1244 
1245  // Called by operator=(forward_list&&)
1246  void
1247  _M_move_assign(forward_list&& __list, std::true_type) noexcept
1248  {
1249  clear();
1250  std::swap(this->_M_impl._M_head._M_next,
1251  __list._M_impl._M_head._M_next);
1252  std::__alloc_on_move(this->_M_get_Node_allocator(),
1253  __list._M_get_Node_allocator());
1254  }
1255 
1256  // Called by operator=(forward_list&&)
1257  void
1258  _M_move_assign(forward_list&& __list, std::false_type)
1259  {
1260  if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator())
1261  _M_move_assign(std::move(__list), std::true_type());
1262  else
1263  // The rvalue's allocator cannot be moved, or is not equal,
1264  // so we need to individually move each element.
1265  this->assign(std::__make_move_if_noexcept_iterator(__list.begin()),
1266  std::__make_move_if_noexcept_iterator(__list.end()));
1267  }
1268 
1269  // Called by assign(_InputIterator, _InputIterator) if _Tp is
1270  // CopyAssignable.
1271  template<typename _InputIterator>
1272  void
1273  _M_assign(_InputIterator __first, _InputIterator __last, true_type)
1274  {
1275  auto __prev = before_begin();
1276  auto __curr = begin();
1277  auto __end = end();
1278  while (__curr != __end && __first != __last)
1279  {
1280  *__curr = *__first;
1281  ++__prev;
1282  ++__curr;
1283  ++__first;
1284  }
1285  if (__first != __last)
1286  insert_after(__prev, __first, __last);
1287  else if (__curr != __end)
1288  erase_after(__prev, __end);
1289  }
1290 
1291  // Called by assign(_InputIterator, _InputIterator) if _Tp is not
1292  // CopyAssignable.
1293  template<typename _InputIterator>
1294  void
1295  _M_assign(_InputIterator __first, _InputIterator __last, false_type)
1296  {
1297  clear();
1298  insert_after(cbefore_begin(), __first, __last);
1299  }
1300 
1301  // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable
1302  void
1303  _M_assign_n(size_type __n, const _Tp& __val, true_type)
1304  {
1305  auto __prev = before_begin();
1306  auto __curr = begin();
1307  auto __end = end();
1308  while (__curr != __end && __n > 0)
1309  {
1310  *__curr = __val;
1311  ++__prev;
1312  ++__curr;
1313  --__n;
1314  }
1315  if (__n > 0)
1316  insert_after(__prev, __n, __val);
1317  else if (__curr != __end)
1318  erase_after(__prev, __end);
1319  }
1320 
1321  // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable
1322  void
1323  _M_assign_n(size_type __n, const _Tp& __val, false_type)
1324  {
1325  clear();
1326  insert_after(cbefore_begin(), __n, __val);
1327  }
1328  };
1329 
1340  template<typename _Tp, typename _Alloc>
1341  bool
1342  operator==(const forward_list<_Tp, _Alloc>& __lx,
1343  const forward_list<_Tp, _Alloc>& __ly);
1344 
1357  template<typename _Tp, typename _Alloc>
1358  inline bool
1359  operator<(const forward_list<_Tp, _Alloc>& __lx,
1360  const forward_list<_Tp, _Alloc>& __ly)
1361  { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(),
1362  __ly.cbegin(), __ly.cend()); }
1363 
1365  template<typename _Tp, typename _Alloc>
1366  inline bool
1367  operator!=(const forward_list<_Tp, _Alloc>& __lx,
1368  const forward_list<_Tp, _Alloc>& __ly)
1369  { return !(__lx == __ly); }
1370 
1372  template<typename _Tp, typename _Alloc>
1373  inline bool
1374  operator>(const forward_list<_Tp, _Alloc>& __lx,
1375  const forward_list<_Tp, _Alloc>& __ly)
1376  { return (__ly < __lx); }
1377 
1379  template<typename _Tp, typename _Alloc>
1380  inline bool
1381  operator>=(const forward_list<_Tp, _Alloc>& __lx,
1382  const forward_list<_Tp, _Alloc>& __ly)
1383  { return !(__lx < __ly); }
1384 
1386  template<typename _Tp, typename _Alloc>
1387  inline bool
1388  operator<=(const forward_list<_Tp, _Alloc>& __lx,
1389  const forward_list<_Tp, _Alloc>& __ly)
1390  { return !(__ly < __lx); }
1391 
1393  template<typename _Tp, typename _Alloc>
1394  inline void
1395  swap(forward_list<_Tp, _Alloc>& __lx,
1396  forward_list<_Tp, _Alloc>& __ly)
1397  { __lx.swap(__ly); }
1398 
1399 _GLIBCXX_END_NAMESPACE_CONTAINER
1400 } // namespace std
__gnu_debug::operator>=
bool operator>=(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:644
std::__exception_ptr::operator==
bool operator==(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
__try
#define __try
Definition: exception_defines.h:35
__throw_exception_again
#define __throw_exception_again
Definition: exception_defines.h:37
__gnu_debug::operator>
bool operator>(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:612
std::__exception_ptr::operator!=
bool operator!=(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
size_t
__SIZE_TYPE__ size_t
Definition: stddef.h:212
__gnu_pbds::detail::true_type
std::tr1::integral_constant< int, 1 > true_type
Definition: type_utils.hpp:70
__catch
#define __catch(X)
Definition: exception_defines.h:36
ptrdiff_t
__PTRDIFF_TYPE__ ptrdiff_t
Definition: stddef.h:147
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
__gnu_pbds::detail::false_type
std::tr1::integral_constant< int, 0 > false_type
Definition: type_utils.hpp:71
Generated on Sat Jul 22 2017 14:41:13 for STLdoc by   doxygen 1.8.6