29 #ifndef _FORWARD_LIST_H
30 #define _FORWARD_LIST_H 1
32 #pragma GCC system_header
34 #ifndef __GXX_EXPERIMENTAL_CXX0X__
42 _GLIBCXX_BEGIN_NAMESPACE(std)
44 using __gnu_cxx::__static_pointer_cast;
45 using __gnu_cxx::__const_pointer_cast;
52 template<typename _Alloc>
56 typedef typename _Alloc::template rebind<_Fwd_list_node_base<_Alloc> >
57 ::other::pointer _Pointer;
58 typedef typename _Alloc::template rebind<_Fwd_list_node_base<_Alloc> >
59 ::other::const_pointer _Const_pointer;
63 _Fwd_list_node_base() : _M_next(0) { }
66 swap(_Fwd_list_node_base& __x, _Fwd_list_node_base& __y)
67 { std::swap(__x._M_next, __y._M_next); }
70 _M_transfer_after(_Pointer __bbegin);
73 _M_transfer_after(_Pointer __bbegin, _Pointer __bend);
84 template<
typename _Tp,
typename _Alloc>
87 typedef typename _Alloc::template rebind<_Fwd_list_node<_Tp, _Alloc> >
88 ::other::pointer _Pointer;
90 template<
typename... _Args>
93 _M_value(std::forward<_Args>(__args)...) { }
95 template<
typename _Comp>
97 _M_sort_after(_Comp __comp);
107 template<
typename _Tp,
typename _Alloc>
114 typedef _Tp value_type;
115 typedef typename _Alloc::pointer pointer;
116 typedef typename _Alloc::reference reference;
117 typedef typename _Alloc::difference_type difference_type;
128 {
return __static_pointer_cast<
_Node*>(_M_node)->_M_value; }
132 {
return &__static_pointer_cast<
_Node*>(_M_node)->_M_value; }
137 _M_node = _M_node->_M_next;
145 _M_node = _M_node->_M_next;
151 {
return _M_node == __x._M_node; }
155 {
return _M_node != __x._M_node; }
166 typename _Node_base::_Pointer _M_node;
174 template<
typename _Tp,
typename _Alloc>
182 typedef _Tp value_type;
183 typedef typename _Alloc::const_pointer pointer;
184 typedef typename _Alloc::const_reference reference;
185 typedef typename _Alloc::difference_type difference_type;
195 : _M_node(__iter._M_node) { }
199 {
return __static_pointer_cast<
_Node*>(_M_node)->_M_value; }
203 {
return &__static_pointer_cast<
_Node*>(_M_node)->_M_value; }
208 _M_node = _M_node->_M_next;
216 _M_node = _M_node->_M_next;
222 {
return _M_node == __x._M_node; }
226 {
return _M_node != __x._M_node; }
237 typename _Node_base::_Const_pointer _M_node;
243 template<
typename _Tp,
typename _Alloc>
247 {
return __x._M_node == __y._M_node; }
252 template<
typename _Tp,
typename _Alloc>
256 {
return __x._M_node != __y._M_node; }
261 template<
typename _Tp,
typename _Alloc>
265 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
267 typedef typename _Alloc::template
268 rebind<_Fwd_list_node<_Tp, _Tp_alloc_type>>::other _Node_alloc_type;
270 struct _Fwd_list_impl
271 :
public _Node_alloc_type
276 : _Node_alloc_type(), _M_head()
279 _Fwd_list_impl(
const _Node_alloc_type& __a)
280 : _Node_alloc_type(__a), _M_head()
284 _Fwd_list_impl _M_impl;
294 _M_get_Node_allocator()
295 {
return *
static_cast<_Node_alloc_type*
>(&this->_M_impl); }
297 const _Node_alloc_type&
298 _M_get_Node_allocator()
const
299 {
return *
static_cast<const _Node_alloc_type*
>(&this->_M_impl); }
303 { this->_M_impl._M_head._M_next = 0; }
307 { this->_M_impl._M_head._M_next = 0; }
314 __lst._M_impl._M_head); }
317 : _M_impl(__lst._M_get_Node_allocator())
319 __lst._M_impl._M_head); }
322 { _M_erase_after(&_M_impl._M_head, 0); }
326 typename _Node::_Pointer
328 {
return _M_get_Node_allocator().allocate(1); }
330 template<
typename... _Args>
331 typename _Node::_Pointer
332 _M_create_node(_Args&&... __args)
334 typename _Node::_Pointer __node = this->_M_get_node();
337 _M_get_Node_allocator().construct(__node,
338 std::forward<_Args>(__args)...);
343 this->_M_put_node(__node);
344 __throw_exception_again;
349 template<
typename... _Args>
350 typename _Node_base::_Pointer
354 _M_put_node(
typename _Node::_Pointer __p)
355 { _M_get_Node_allocator().deallocate(__p, 1); }
357 typename _Node_base::_Pointer
358 _M_erase_after(
typename _Node_base::_Pointer __pos);
360 typename _Node_base::_Pointer
361 _M_erase_after(
typename _Node_base::_Pointer __pos,
362 typename _Node_base::_Pointer __last);
396 template<
typename _Tp,
typename _Alloc = allocator<_Tp> >
403 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
407 typedef _Tp value_type;
408 typedef typename _Tp_alloc_type::pointer pointer;
409 typedef typename _Tp_alloc_type::const_pointer const_pointer;
410 typedef typename _Tp_alloc_type::reference reference;
411 typedef typename _Tp_alloc_type::const_reference const_reference;
415 typedef std::size_t size_type;
416 typedef std::ptrdiff_t difference_type;
417 typedef _Alloc allocator_type;
436 :
_Base(__list, __al)
459 { _M_fill_initialize(__n, value_type()); }
471 const _Alloc& __al = _Alloc())
473 { _M_fill_initialize(__n, __value); }
485 template<
typename _InputIterator>
487 const _Alloc& __al = _Alloc())
491 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
492 _M_initialize_dispatch(__first, __last, _Integral());
504 :
_Base(__list.get_allocator())
505 { _M_initialize_dispatch(__list.
begin(), __list.
end(), __false_type()); }
528 const _Alloc& __al = _Alloc())
530 { _M_initialize_dispatch(__il.begin(), __il.end(), __false_type()); }
536 { _M_erase_after(&this->_M_impl._M_head, 0); }
596 template<
typename _InputIterator>
598 assign(_InputIterator __first, _InputIterator __last)
601 insert_after(cbefore_begin(), __first, __last);
618 insert_after(cbefore_begin(), __n, __val);
633 insert_after(cbefore_begin(), __il);
639 {
return this->_M_get_Node_allocator(); }
649 {
return iterator(&this->_M_impl._M_head); }
666 {
return iterator(this->_M_impl._M_head._M_next); }
728 {
return this->_M_impl._M_head._M_next == 0; }
735 {
return this->_M_get_Node_allocator().max_size(); }
747 __static_pointer_cast<
_Node*>(this->_M_impl._M_head._M_next);
748 return __front->_M_value;
759 __static_pointer_cast<
_Node*>(this->_M_impl._M_head._M_next);
760 return __front->_M_value;
776 template<
typename... _Args>
779 { this->_M_insert_after(cbefore_begin(),
780 std::forward<_Args>(__args)...); }
794 { this->_M_insert_after(cbefore_begin(), __val); }
800 push_front(_Tp&& __val)
801 { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
817 { this->_M_erase_after(&this->_M_impl._M_head); }
832 template<
typename... _Args>
835 {
return iterator(this->_M_insert_after(__pos,
836 std::forward<_Args>(__args)...)); }
852 {
return iterator(this->_M_insert_after(__pos, __val)); }
858 insert_after(const_iterator __pos, _Tp&& __val)
859 {
return iterator(this->_M_insert_after(__pos, std::move(__val))); }
878 this->splice_after(__pos,
std::move(__tmp));
894 template<
typename _InputIterator>
897 _InputIterator __first, _InputIterator __last)
899 forward_list __tmp(__first, __last, this->get_allocator());
900 this->splice_after(__pos,
std::move(__tmp));
920 this->splice_after(__pos,
std::move(__tmp));
944 return iterator(this->_M_erase_after(__tmp));
972 return iterator(this->_M_erase_after(__tmp, &*__last._M_node));
1002 { resize(__sz, _Tp()); }
1017 resize(size_type __sz, value_type __val);
1029 { this->_M_erase_after(&this->_M_impl._M_head, 0); }
1045 splice_after(const_iterator __pos,
forward_list&& __list);
1060 { this->splice_after(__pos, __list, __it, __it._M_next()); }
1076 splice_after(const_iterator __pos,
forward_list&& __list,
1077 const_iterator __before, const_iterator __last);
1091 remove(
const _Tp& __val);
1104 template<
typename _Pred>
1106 remove_if(_Pred __pred);
1134 template<
typename _BinPred>
1136 unique(_BinPred __binary_pred);
1162 template<
typename _Comp>
1175 _Node* __tmp = __static_pointer_cast<
_Node*>(&this->_M_impl._M_head);
1185 template<
typename _Comp>
1189 _Node* __tmp = __static_pointer_cast<
_Node*>(&this->_M_impl._M_head);
1200 { this->_M_impl._M_head._M_reverse_after(); }
1203 template<
typename _Integer>
1205 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1206 { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1209 template<
typename _InputIterator>
1211 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1217 _M_fill_initialize(size_type __n,
const value_type& __value);
1230 template<
typename _Tp,
typename _Alloc>
1232 operator==(
const forward_list<_Tp, _Alloc>& __lx,
1233 const forward_list<_Tp, _Alloc>& __ly);
1246 template<
typename _Tp,
typename _Alloc>
1248 operator<(const forward_list<_Tp, _Alloc>& __lx,
1251 __ly.cbegin(), __ly.cend()); }
1254 template<
typename _Tp,
typename _Alloc>
1258 {
return !(__lx == __ly); }
1261 template<
typename _Tp,
typename _Alloc>
1265 {
return (__ly < __lx); }
1268 template<
typename _Tp,
typename _Alloc>
1272 {
return !(__lx < __ly); }
1275 template<
typename _Tp,
typename _Alloc>
1277 operator<=(const forward_list<_Tp, _Alloc>& __lx,
1279 {
return !(__ly < __lx); }
1282 template<
typename _Tp,
typename _Alloc>
1286 { __lx.
swap(__ly); }
1289 template<
typename _Tp,
typename _Alloc>
1293 { __lx.swap(__ly); }
1296 template<
typename _Tp,
typename _Alloc>
1300 { __lx.
swap(__ly); }
1302 _GLIBCXX_END_NAMESPACE
1304 #endif // __GXX_EXPERIMENTAL_CXX0X__
1306 #endif // _FORWARD_LIST_H
const_iterator cbefore_begin() const
void swap(forward_list< _Tp, _Alloc > &__lx, forward_list< _Tp, _Alloc > &&__ly)
See std::forward_list::swap().
bool operator==(const forward_list< _Tp, _Alloc > &__lx, const forward_list< _Tp, _Alloc > &__ly)
Forward list equality comparison.
forward_list(const forward_list &__list, const _Alloc &__al)
Copy constructor with allocator argument.
bool operator>(const forward_list< _Tp, _Alloc > &__lx, const forward_list< _Tp, _Alloc > &__ly)
Based on operator<.
void assign(std::initializer_list< _Tp > __il)
Assigns an initializer_list to a forward_list.
A forward_list::iterator.
forward_list & operator=(std::initializer_list< _Tp > __il)
The forward_list initializer list assignment operator.
Base class for forward_list.
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a forward_list.
void _M_sort_after(_Comp __comp)
Sort the singly linked list starting after this node. This node is assumed to be an empty head node (...
A helper basic node class for forward_list. This is just a linked list with nothing inside it...
void sort(_Comp __comp)
Sort the forward_list using a comparison function.
void insert_after(const_iterator __pos, size_type __n, const _Tp &__val)
Inserts a number of copies of given data into the forward_list.
void swap(forward_list &&__list)
Swaps data with another forward_list.
~forward_list()
The forward_list dtor.
void splice_after(const_iterator __pos, forward_list &&__list, const_iterator __it)
Insert element from another forward_list.
void pop_front()
Removes first element.
forward_list & operator=(forward_list &&__list)
The forward_list move assignment operator.
const_iterator end() const
forward_list(size_type __n, const _Tp &__value, const _Alloc &__al=_Alloc())
Creates a forward_list with copies of an exemplar element.
iterator insert_after(const_iterator __pos, const _Tp &__val)
Inserts given value into forward_list after specified iterator.
void emplace_front(_Args &&...__args)
Constructs object in forward_list at the front of the list.
const_iterator begin() const
A forward_list::const_iterator.
forward_list(std::initializer_list< _Tp > __il, const _Alloc &__al=_Alloc())
Builds a forward_list from an initializer_list.
const_iterator before_begin() const
iterator erase_after(const_iterator __pos, iterator __last)
Remove a range of elements.
iterator erase_after(const_iterator __pos)
Removes the element pointed to by the iterator following pos.
forward_list(forward_list &&__list)
The forward_list move constructor.
_OI move(_II __first, _II __last, _OI __result)
Moves the range [first,last) into result.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
const_reference front() const
forward_list(const _Alloc &__al=_Alloc())
Creates a forward_list with no elements.
bool operator!=(const forward_list< _Tp, _Alloc > &__lx, const forward_list< _Tp, _Alloc > &__ly)
Based on operator==.
const_iterator cend() const
size_type max_size() const
void insert_after(const_iterator __pos, _InputIterator __first, _InputIterator __last)
Inserts a range into the forward_list.
void reverse()
Reverse the elements in list.
forward_list(const forward_list &__list)
The forward_list copy constructor.
void sort()
Sort the elements of the list.
void unique()
Remove consecutive duplicate elements.
forward_list(forward_list &&__list, const _Alloc &__al)
Move constructor with allocator argument.
void merge(forward_list &&__list)
Merge sorted lists.
void assign(size_type __n, const _Tp &__val)
Assigns a given value to a forward_list.
A helper node class for forward_list. This is just a linked list with a data value in each node...
allocator_type get_allocator() const
Get a copy of the memory allocation object.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs "dictionary" comparison on ranges.
forward_list(_InputIterator __first, _InputIterator __last, const _Alloc &__al=_Alloc())
Builds a forward_list from a range.
iterator emplace_after(const_iterator __pos, _Args &&...__args)
Constructs object in forward_list after the specified iterator.
void clear()
Erases all the elements.
const_iterator cbegin() const
void push_front(const _Tp &__val)
Add data to the front of the forward_list.
void insert_after(const_iterator __pos, std::initializer_list< _Tp > __il)
Inserts the contents of an initializer_list into forward_list after the specified iterator...
Forward iterators support a superset of input iterator operations.
forward_list(size_type __n)
Creates a forward_list with copies of the default element type.
void resize(size_type __sz)
Resizes the forward_list to the specified number of elements.
bool operator>=(const forward_list< _Tp, _Alloc > &__lx, const forward_list< _Tp, _Alloc > &__ly)
Based on operator<.
One of the comparison functors.
One of the comparison functors.