// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 2, or (at your option)
+// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
-// You should have received a copy of the GNU General Public License
-// along with this library; see the file COPYING. If not, write to
-// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
-// Boston, MA 02110-1301, USA.
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
-// As a special exception, you may use this file as part of a free software
-// library without restriction. Specifically, if other files instantiate
-// templates or use macros or inline functions from this file, or you compile
-// this file and link it with other files to produce an executable, this
-// file does not by itself cause the resulting executable to be covered by
-// the GNU General Public License. This exception does not however
-// invalidate any other reasons why the executable file might be covered by
-// the GNU General Public License.
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
/** @file forward_list.h
* This is a Standard C++ Library header.
using __gnu_cxx::__const_pointer_cast;
/**
- * @brief A helper basic node class for @forward_list.
+ * @brief 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.
*/
::other::pointer _Pointer;
typedef typename _Alloc::template rebind<_Fwd_list_node_base<_Alloc> >
::other::const_pointer _Const_pointer;
-
+
_Pointer _M_next;
-
+
_Fwd_list_node_base() : _M_next(0) { }
-
+
static void
swap(_Fwd_list_node_base& __x, _Fwd_list_node_base& __y)
{ std::swap(__x._M_next, __y._M_next); }
-
+
void
- _M_transfer_after(_Pointer __bbegin, _Pointer __bend)
- {
- _Pointer __keep = __bbegin->_M_next;
- if (__bend)
- {
- __bbegin->_M_next = __bend->_M_next;
- __bend->_M_next = this->_M_next;
- }
- else
- __bbegin->_M_next = 0;
- this->_M_next = __keep;
- }
-
+ _M_transfer_after(_Pointer __bbegin);
+
void
- _M_transfer_after(_Pointer __bbegin)
- {
- _Pointer __bend = __bbegin;
- while (__bend && __bend->_M_next)
- __bend = __bend->_M_next;
- _M_transfer_after(__bbegin, __bend);
- }
-
+ _M_transfer_after(_Pointer __bbegin, _Pointer __bend);
+
void
- _M_reverse_after()
- {
- _Pointer __tail = this->_M_next;
- if (!__tail)
- return;
- while (_Pointer __temp = __tail->_M_next)
- {
- _Pointer __keep = this->_M_next;
- this->_M_next = __temp;
- __tail->_M_next = __temp->_M_next;
- this->_M_next->_M_next = __keep;
- }
- }
+ _M_reverse_after();
};
/**
- * @brief A helper node class for @forward_list.
+ * @brief A helper node class for %forward_list.
* This is just a linked list with a data value in each node.
* There is a sorting utility method.
*/
- template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
+ template<typename _Tp, typename _Alloc>
struct _Fwd_list_node : public _Fwd_list_node_base<_Alloc>
{
typedef typename _Alloc::template rebind<_Fwd_list_node<_Tp, _Alloc> >
: _Fwd_list_node_base<_Alloc>(),
_M_value(std::forward<_Args>(__args)...) { }
- template<typename _Comp>
- void
- _M_sort_after(_Comp __comp);
-
_Tp _M_value;
};
*
* All the functions are op overloads.
*/
- template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
+ template<typename _Tp, typename _Alloc>
struct _Fwd_list_iterator
{
typedef _Fwd_list_iterator<_Tp, _Alloc> _Self;
reference
operator*() const
- { return __static_pointer_cast<_Node*>(this->_M_node)->_M_value; }
+ { return __static_pointer_cast<_Node*>(_M_node)->_M_value; }
pointer
operator->() const
- { return &__static_pointer_cast<_Node*>(this->_M_node)->_M_value; }
+ { return &__static_pointer_cast<_Node*>(_M_node)->_M_value; }
_Self&
operator++()
{
- this->_M_node = this->_M_node->_M_next;
+ _M_node = _M_node->_M_next;
return *this;
}
operator++(int)
{
_Self __tmp(*this);
- this->_M_node = this->_M_node->_M_next;
+ _M_node = _M_node->_M_next;
return __tmp;
}
bool
operator==(const _Self& __x) const
- { return this->_M_node == __x._M_node; }
+ { return _M_node == __x._M_node; }
bool
operator!=(const _Self& __x) const
- { return this->_M_node != __x._M_node; }
+ { return _M_node != __x._M_node; }
_Self
_M_next() const
{
if (_M_node)
- return _Fwd_list_iterator(this->_M_node->_M_next);
+ return _Fwd_list_iterator(_M_node->_M_next);
else
return _Fwd_list_iterator(0);
}
*
* All the functions are op overloads.
*/
- template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
+ template<typename _Tp, typename _Alloc>
struct _Fwd_list_const_iterator
{
typedef _Fwd_list_const_iterator<_Tp, _Alloc> _Self;
reference
operator*() const
- { return __static_pointer_cast<_Node*>(this->_M_node)->_M_value; }
+ { return __static_pointer_cast<_Node*>(_M_node)->_M_value; }
pointer
operator->() const
- { return &__static_pointer_cast<_Node*>(this->_M_node)->_M_value; }
+ { return &__static_pointer_cast<_Node*>(_M_node)->_M_value; }
_Self&
operator++()
{
- this->_M_node = this->_M_node->_M_next;
+ _M_node = _M_node->_M_next;
return *this;
}
operator++(int)
{
_Self __tmp(*this);
- this->_M_node = this->_M_node->_M_next;
+ _M_node = _M_node->_M_next;
return __tmp;
}
bool
operator==(const _Self& __x) const
- { return this->_M_node == __x._M_node; }
+ { return _M_node == __x._M_node; }
bool
operator!=(const _Self& __x) const
- { return this->_M_node != __x._M_node; }
+ { return _M_node != __x._M_node; }
_Self
_M_next() const
{
if (this->_M_node)
- return _Fwd_list_const_iterator(this->_M_node->_M_next);
+ return _Fwd_list_const_iterator(_M_node->_M_next);
else
return _Fwd_list_const_iterator(0);
}
/**
* @brief Forward list iterator equality comparison.
*/
- template<typename _Tp,class _Alloc>
+ template<typename _Tp, typename _Alloc>
inline bool
operator==(const _Fwd_list_iterator<_Tp, _Alloc>& __x,
const _Fwd_list_const_iterator<_Tp, _Alloc>& __y)
/**
* @brief Forward list iterator inequality comparison.
*/
- template<typename _Tp,class _Alloc>
+ template<typename _Tp, typename _Alloc>
inline bool
operator!=(const _Fwd_list_iterator<_Tp, _Alloc>& __x,
const _Fwd_list_const_iterator<_Tp, _Alloc>& __y)
{ return __x._M_node != __y._M_node; }
/**
- * @brief Base class for @forward_list.
+ * @brief Base class for %forward_list.
*/
- template<typename _Tp, typename _Alloc = allocator<_Tp> >
+ template<typename _Tp, typename _Alloc>
struct _Fwd_list_base
{
protected:
_M_put_node(typename _Node::_Pointer __p)
{ _M_get_Node_allocator().deallocate(__p, 1); }
- typename _Node_base::_Pointer
+ void
_M_erase_after(typename _Node_base::_Pointer __pos);
- typename _Node_base::_Pointer
+ void
_M_erase_after(typename _Node_base::_Pointer __pos,
typename _Node_base::_Pointer __last);
};
* @brief A standard container with linear time access to elements,
* and fixed time insertion/deletion at any point in the sequence.
*
- * @ingroup containers
* @ingroup sequences
*
* Meets the requirements of a <a href="tables.html#65">container</a>, a
* @brief The forward_list dtor.
*/
~forward_list()
- { _M_erase_after(&this->_M_impl._M_head, 0); }
+ { }
/**
* @brief The %forward_list assignment operator.
reference
front()
{
- _Node* __front = __static_pointer_cast<_Node*>(this->_M_impl._M_head._M_next);
+ _Node* __front =
+ __static_pointer_cast<_Node*>(this->_M_impl._M_head._M_next);
return __front->_M_value;
}
insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
{
forward_list __tmp(__n, __val, this->get_allocator());
- this->splice_after(__pos, std::move(__tmp));
+ splice_after(__pos, std::move(__tmp));
}
/**
_InputIterator __first, _InputIterator __last)
{
forward_list __tmp(__first, __last, this->get_allocator());
- this->splice_after(__pos, std::move(__tmp));
+ splice_after(__pos, std::move(__tmp));
}
/**
insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
{
forward_list __tmp(__il, this->get_allocator());
- this->splice_after(__pos, std::move(__tmp));
+ splice_after(__pos, std::move(__tmp));
}
/**
* @brief Removes the element pointed to by the iterator following
* @c pos.
- * @param pos Iterator pointing to element to be erased.
- * @return An iterator pointing to the next element (or end()).
+ * @param pos Iterator pointing before element to be erased.
*
* This function will erase the element at the given position and
* thus shorten the %forward_list by one.
* is itself a pointer, the pointed-to memory is not touched in
* any way. Managing the pointer is the user's responsibility.
*/
- iterator
+ void
erase_after(const_iterator __pos)
{
_Node_base* __tmp = __const_pointer_cast<_Node_base*>(__pos._M_node);
- if (__tmp)
- return iterator(this->_M_erase_after(__tmp));
- else
- return end();
+ this->_M_erase_after(__tmp);
}
/**
* erased.
* @param last Iterator pointing to one past the last element to be
* erased.
- * @return An iterator pointing to the element pointed to by @a last
- * prior to erasing (or end()).
*
* This function will erase the elements in the range @a
* (pos,last) and shorten the %forward_list accordingly.
* pointed-to memory is not touched in any way. Managing the pointer
* is the user's responsibility.
*/
- iterator
- erase_after(const_iterator __pos, iterator __last)
+ void
+ erase_after(const_iterator __pos, const_iterator __last)
{
- _Node_base* __tmp = __const_pointer_cast<_Node_base*>(__pos._M_node);
- return iterator(this->_M_erase_after(__tmp, &*__last._M_node));
+ _Node_base* __tmpp = __const_pointer_cast<_Node_base*>(__pos._M_node);
+ _Node_base* __tmpl = __const_pointer_cast<_Node_base*>(__last._M_node);
+ this->_M_erase_after(__tmpp, __tmpl);
}
/**
* function.
*/
void
- swap(forward_list&& __list)
+ swap(forward_list& __list)
{ _Node_base::swap(this->_M_impl._M_head, __list._M_impl._M_head); }
/**
* @brief Insert element from another %forward_list.
* @param pos Iterator referencing the element to insert after.
* @param list Source list.
- * @param it Iterator referencing the element before the element
+ * @param i Iterator referencing the element before the element
* to move.
*
* Removes the element in list @a list referenced by @a i and
*/
void
splice_after(const_iterator __pos, forward_list&& __list,
- const_iterator __it)
- { this->splice_after(__pos, __list, __it, __it._M_next()); }
+ const_iterator __i)
+ {
+ const_iterator __j = __i;
+ ++__j;
+ if (__pos == __i || __pos == __j)
+ return;
+
+ splice_after(__pos, std::move(__list), __i, __j);
+ }
/**
* @brief Insert range from another %forward_list.
*/
void
merge(forward_list&& __list)
- { this->merge(__list, std::less<_Tp>()); }
+ { this->merge(std::move(__list), std::less<_Tp>()); }
/**
* @brief Merge sorted lists according to comparison function.
*/
void
sort()
- {
- _Node* __tmp = __static_pointer_cast<_Node*>(&this->_M_impl._M_head);
- __tmp->_M_sort_after(std::less<_Tp>());
- }
+ { this->sort(std::less<_Tp>()); }
/**
* @brief Sort the forward_list using a comparison function.
*/
template<typename _Comp>
void
- sort(_Comp __comp)
- {
- _Node* __tmp = __static_pointer_cast<_Node*>(&this->_M_impl._M_head);
- __tmp->_M_sort_after(__comp);
- }
+ sort(_Comp __comp);
/**
* @brief Reverse the elements in list.
* Reverse the order of elements in the list in linear time.
*/
void
- reverse();
+ reverse()
+ { this->_M_impl._M_head._M_reverse_after(); }
private:
template<typename _Integer>
template<typename _Tp, typename _Alloc>
inline void
swap(forward_list<_Tp, _Alloc>& __lx,
- forward_list<_Tp, _Alloc>& __ly)
- { __lx.swap(__ly); }
-
- /// See std::forward_list::swap().
- template<typename _Tp, typename _Alloc>
- inline void
- swap(forward_list<_Tp, _Alloc>&& __lx,
- forward_list<_Tp, _Alloc>& __ly)
- { __lx.swap(__ly); }
-
- /// See std::forward_list::swap().
- template<typename _Tp, typename _Alloc>
- inline void
- swap(forward_list<_Tp, _Alloc>& __lx,
- forward_list<_Tp, _Alloc>&& __ly)
+ forward_list<_Tp, _Alloc>& __ly)
{ __lx.swap(__ly); }
_GLIBCXX_END_NAMESPACE // namespace std