rw_forward_list< T, A > Class Template Reference

Maintains a collection of some type T implemented as a singly-linked, forward-iteration-only list. More...

#include <rw/stdex/forward_list.h>

Public Types
typedef std::allocator_traits< A >::template rebind_alloc< node_type >	allocator_type
typedef rw_forward_list_iterator< const T, const base_node_type, const node_type, difference_type >	const_iterator
typedef const value_type *	const_pointer
typedef const value_type &	const_reference
typedef std::allocator_traits< allocator_type >::difference_type	difference_type
typedef rw_forward_list_iterator< T, base_node_type, node_type, difference_type >	iterator
typedef value_type *	pointer
typedef value_type &	reference
typedef std::allocator_traits< allocator_type >::size_type	size_type
typedef T	value_type

Public Member Functions
	rw_forward_list ()
	rw_forward_list (const rw_forward_list< T, A > &x)
	rw_forward_list (rw_forward_list< T, A > &&x)
template<typename InputIterator >
	rw_forward_list (InputIterator first, InputIterator last)
	rw_forward_list (size_type n, const T &value)
	~rw_forward_list ()
template<typename InputIterator >
void	assign (InputIterator first, InputIterator last)
iterator	before_begin ()
const_iterator	before_begin () const
iterator	begin ()
const_iterator	begin () const
const_iterator	cbefore_begin () const
const_iterator	cbegin () const
const_iterator	cend () const
void	clear ()
bool	empty () const
iterator	end ()
const_iterator	end () const
iterator	erase_after (const_iterator position)
iterator	erase_after (const_iterator position, const_iterator last)
reference	front ()
const_reference	front () const
iterator	insert_after (const_iterator position, const T &x)
iterator	insert_after (const_iterator position, T &&x)
template<typename InputIterator >
iterator	insert_after (const_iterator position, InputIterator first, InputIterator last)
iterator	insert_after (const_iterator position, size_type n, const T &value)
size_type	max_size () const
void	merge (rw_forward_list< T, A > &x)
rw_forward_list< T, A > &	operator= (const rw_forward_list< T, A > &x)
rw_forward_list< T, A > &	operator= (rw_forward_list< T, A > &&x)
void	pop_front ()
void	push_front (const T &x)
void	push_front (T &&x)
void	remove (const T &value)
void	reverse ()
void	sort ()
template<typename Compare >
void	sort (Compare comp)
void	splice_after (const_iterator position, rw_forward_list< T, A > &x)
void	splice_after (const_iterator position, rw_forward_list< T, A > &x, const_iterator prev)
void	splice_after (const_iterator position, rw_forward_list< T, A > &x, const_iterator first, const_iterator last)
void	swap (rw_forward_list< T, A > &x)
void	unique ()

Related Functions
(Note that these are not member functions.)
template<typename T , typename A >
bool	operator!= (const rw_forward_list< T, A > &lhs, const rw_forward_list< T, A > &rhs)
template<typename T , typename A >
bool	operator< (const rw_forward_list< T, A > &lhs, const rw_forward_list< T, A > &rhs)
template<typename T , typename A >
bool	operator<= (const rw_forward_list< T, A > &lhs, const rw_forward_list< T, A > &rhs)
template<typename T , typename A >
bool	operator== (const rw_forward_list< T, A > &lhs, const rw_forward_list< T, A > &rhs)
template<typename T , typename A >
bool	operator> (const rw_forward_list< T, A > &lhs, const rw_forward_list< T, A > &rhs)
template<typename T , typename A >
bool	operator>= (const rw_forward_list< T, A > &lhs, const rw_forward_list< T, A > &rhs)

Detailed Description

template<typename T, typename A = std::allocator<T>>
class rw_forward_list< T, A >

Class rw_forward_list maintains a collection of T, implemented as a singly-linked list. Since this is a value-based list, objects are copied into and out of the links that make up the list.

Unlike classes that meet the ANSI sequence specification, rw_forward_list focuses primarily on minimizing the memory overhead of a linked-list by providing only forward iteration. This results in various functions that are similar to, but different from, other sequence containers.

Member Typedef Documentation

template<typename T, typename A = std::allocator<T>>

typedef std::allocator_traits<A>::template rebind_alloc<node_type> rw_forward_list< T, A >::allocator_type

A type representing the allocator type for the container.

template<typename T, typename A = std::allocator<T>>

typedef rw_forward_list_iterator<const T, const base_node_type, const node_type, difference_type> rw_forward_list< T, A >::const_iterator

A type that provides a const forward iterator over the elements in the container.

template<typename T, typename A = std::allocator<T>>

typedef const value_type* rw_forward_list< T, A >::const_pointer

A type that provides a const pointer to an element in the container.

template<typename T, typename A = std::allocator<T>>

typedef const value_type& rw_forward_list< T, A >::const_reference

A type that provides a const reference to an element in the container.

template<typename T, typename A = std::allocator<T>>

typedef std::allocator_traits<allocator_type>::difference_type rw_forward_list< T, A >::difference_type

A signed integral type used to indicate the distance between two valid iterators on the same container.

template<typename T, typename A = std::allocator<T>>

typedef rw_forward_list_iterator<T, base_node_type, node_type, difference_type> rw_forward_list< T, A >::iterator

A type that provides a forward iterator over the elements in the container.

template<typename T, typename A = std::allocator<T>>

typedef value_type* rw_forward_list< T, A >::pointer

A type that provides a pointer to an element in the container.

template<typename T, typename A = std::allocator<T>>

typedef value_type& rw_forward_list< T, A >::reference

A type that provides a reference to an element in the container.

template<typename T, typename A = std::allocator<T>>

typedef std::allocator_traits<allocator_type>::size_type rw_forward_list< T, A >::size_type

An unsigned integral type used for counting the number of elements in the container.

template<typename T, typename A = std::allocator<T>>

typedef T rw_forward_list< T, A >::value_type

A type representing the value stored in the container.

Constructor & Destructor Documentation

template<typename T , typename A >

rw_forward_list< T, A >::rw_forward_list ( )

inline

Constructs an empty rw_forward_list.

template<typename T, typename A = std::allocator<T>>

rw_forward_list< T, A >::rw_forward_list

(

const rw_forward_list< T, A > &

x

)

Constructs an rw_forward_list that is a copy of x. Each element from x is copied into self.

template<typename T, typename A>

rw_forward_list< T, A >::rw_forward_list ( rw_forward_list< T, A > &&  x )

inline

Move constructor. The constructed list takes ownership of the data owned by x.

Condition:

This method is available only on platforms with rvalue reference support.

template<typename T, typename A = std::allocator<T>>

template<typename InputIterator >

rw_forward_list< T, A >::rw_forward_list	(	InputIterator	first,
		InputIterator	last
	)

Constructs an rw_forward_list containing a copy of each element in the range [first, last).

InputIterator is an input iterator type that points to elements that are convertible to value_type objects.

template<typename T, typename A>

rw_forward_list< T, A >::rw_forward_list ( size_type  n, const T &  value  )

inline

Constructs an rw_forward_list containing n instances of value.

template<typename T , typename A >

rw_forward_list< T, A >::~rw_forward_list ( )

inline

The destructor releases the memory used by the links.

Member Function Documentation

template<typename T , typename A >

template<typename InputIterator >

void rw_forward_list< T, A >::assign ( InputIterator  first, InputIterator  last  )

inline

Copies each element in the range [first, last) into self, replacing any existing elements.

InputIterator is an input iterator type that points to elements that are convertible to value_type objects.

Note

If first or last are iterators into this container, the behavior is undefined.

template<typename T , typename A >

rw_forward_list< T, A >::iterator rw_forward_list< T, A >::before_begin ( )

inline

Returns an iterator preceding the first element in the container. This iterator is intended for use with functions insert_after(), erase_after(), and splice_after(). Attempting to access this iterator results in undefined behavior. When the iterator returned by this function is incremented, it is equivalent to the iterator returned by begin().

template<typename T , typename A >

rw_forward_list< T, A >::const_iterator rw_forward_list< T, A >::before_begin ( ) const

inline

Returns an iterator preceding the first element in the container. This iterator is intended for use with functions insert_after(), erase_after(), and splice_after(). Attempting to access this iterator results in undefined behavior. When the iterator returned by this function is incremented, it is equivalent to the iterator returned by begin().

template<typename T , typename A >

rw_forward_list< T, A >::iterator rw_forward_list< T, A >::begin ( )

inline

Returns an iterator referring to the first element in the container.

If the container is empty, returns end().

template<typename T , typename A >

rw_forward_list< T, A >::const_iterator rw_forward_list< T, A >::begin ( ) const

inline

Returns an iterator referring to the first element in the container.

If the container is empty, returns end().

template<typename T , typename A >

rw_forward_list< T, A >::const_iterator rw_forward_list< T, A >::cbefore_begin ( ) const

inline

Returns an iterator preceding the first element in the container. This iterator is intended for use with functions insert_after(), erase_after(), and splice_after(). Dereferencing the iterator returned by this function results in undefined behavior. When the iterator returned by this function is incremented, it is equivalent to the iterator returned by cbegin().

template<typename T , typename A >

rw_forward_list< T, A >::const_iterator rw_forward_list< T, A >::cbegin ( ) const

inline

Returns an iterator referring to the first element in the container.

If the container is empty, returns cend().

template<typename T , typename A >

rw_forward_list< T, A >::const_iterator rw_forward_list< T, A >::cend ( ) const

inline

Returns an iterator referring to the element after the last element in the container.

Dereferencing the iterator returned by this function results in undefined behavior.

template<typename T , typename A >

void rw_forward_list< T, A >::clear ( )

inline

Removes all elements from self.

template<typename T , typename A >

bool rw_forward_list< T, A >::empty ( ) const

inline

Returns true if self is empty.

template<typename T , typename A >

rw_forward_list< T, A >::iterator rw_forward_list< T, A >::end ( )

inline

Returns an iterator referring to the element after the last element in the container.

Dereferencing the iterator returned by this function results in undefined behavior.

template<typename T , typename A >

rw_forward_list< T, A >::const_iterator rw_forward_list< T, A >::end ( ) const

inline

Returns an iterator referring to the element after the last element in the container.

Dereferencing the iterator returned by this function results in undefined behavior.

template<typename T, typename A = std::allocator<T>>

iterator rw_forward_list< T, A >::erase_after

(

const_iterator

position

)

Removes from self the element following position. If position does not reference an actual element contained in self, the behavior is undefined. Returns an iterator referencing the location just after the erased element.

template<typename T, typename A = std::allocator<T>>

iterator rw_forward_list< T, A >::erase_after	(	const_iterator	position,
		const_iterator	last
	)

Removes from self the elements referenced by the range following position and bounded by last. Returns an iterator referencing a position just after the last erased element. If position does not reference an element in self, the behavior is undefined.

template<typename T , typename A >

rw_forward_list< T, A >::reference rw_forward_list< T, A >::front ( )

inline

Returns a reference to the first element in self. If self is empty, the behavior is undefined.

template<typename T , typename A >

rw_forward_list< T, A >::const_reference rw_forward_list< T, A >::front ( ) const

inline

Returns a const_reference to the first element in self. If self is empty, the behavior is undefined.

template<typename T, typename A = std::allocator<T>>

iterator rw_forward_list< T, A >::insert_after	(	const_iterator	position,
		const T &	x
	)

Inserts x after the element referenced by position. Returns an iterator referencing the newly inserted element.

template<typename T, typename A = std::allocator<T>>

iterator rw_forward_list< T, A >::insert_after	(	const_iterator	position,
		T &&	x
	)

Inserts x after the element referenced by position. Returns an iterator referencing the newly inserted element.

Condition:

This method is available only on platforms with rvalue reference support.

template<typename T, typename A = std::allocator<T>>

template<typename InputIterator >

iterator rw_forward_list< T, A >::insert_after	(	const_iterator	position,
		InputIterator	first,
		InputIterator	last
	)

Inserts a copy of each element in the range [first, last) into self, after the element referenced by position. Returns an iterator referencing the last inserted element.

InputIterator is an input iterator type that points to elements that are convertible to value_type objects.

Note

If first or last are iterators into this container, the behavior is undefined.

template<typename T, typename A = std::allocator<T>>

iterator rw_forward_list< T, A >::insert_after	(	const_iterator	position,
		size_type	n,
		const T &	value
	)

Inserts n copies of value into self, after the element referenced by position. Returns an iterator to the last inserted element, or position if no items are inserted.

template<typename T , typename A >

rw_forward_list< T, A >::size_type rw_forward_list< T, A >::max_size ( ) const

inline

Returns the maximum number of elements the container could hold.

Note

This is a theoretical limit. The actual limit may be constrained by system resources.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::merge

(

rw_forward_list< T, A > &

x

)

Assuming both x and self are sorted, moves every element from x into self, leaving x empty, and self sorted. If either list is unsorted, the move takes place, but the result may not be sorted. This method does not copy or destroy the elements in x, but re-links list nodes into self.

template<typename T, typename A>

rw_forward_list< T, A > & rw_forward_list< T, A >::operator= ( const rw_forward_list< T, A > &  x )

inline

Copy assignment. Constructs an rw_forward_list containing a copy of each element in x.

template<typename T, typename A>

rw_forward_list< T, A > & rw_forward_list< T, A >::operator= ( rw_forward_list< T, A > &&  x )

inline

Move assignment. Self takes ownership of the data owned by x.

Condition:

This method is available only on platforms with rvalue reference support.

template<typename T , typename A >

void rw_forward_list< T, A >::pop_front ( )

inline

Erases the first element of self. If self is empty, the behavior is undefined.

template<typename T, typename A >

void rw_forward_list< T, A >::push_front ( const T &  x )

inline

Inserts x as the first element of the list.

template<typename T, typename A >

void rw_forward_list< T, A >::push_front ( T &&  x )

inline

Inserts x as the first element of the list.

Condition:

This method is available only on platforms with rvalue reference support.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::remove

(

const T &

value

)

Removes all elements in self that compare equal (T::operator==() or equivalent) to value.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::reverse

(

)

Reverses the order of the nodes containing the elements in self.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::sort

(

)

Sorts self according to T::operator<(T) or equivalent. Runs in time proportional to N log(N), where N is the number of elements. This method does not copy or destroy any of the elements exchanged during the sort, but adjusts the order of the links in the list.

template<typename T, typename A = std::allocator<T>>

template<typename Compare >

void rw_forward_list< T, A >::sort

(

Compare

comp

)

Sorts self according to a comparison object of type Compare. Compare must induce a total ordering on elements of type T via an equality function of type comp, which takes two arguments convertible to type T and returns a value of type bool.

Runs in time proportional to N log(N), where N is the number of elements. This method does not copy or destroy any of the elements exchanged during the sort, but adjusts the order of the links in the list.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::splice_after	(	const_iterator	position,
		rw_forward_list< T, A > &	x
	)

Inserts the entire contents of x into self, after the element referenced by position, leaving x empty. This method does not copy or destroy any of the elements moved, but re-links the list nodes from x into self.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::splice_after	(	const_iterator	position,
		rw_forward_list< T, A > &	x,
		const_iterator	prev
	)

Inserts the element referenced by i into self, after the element referenced by position. The element referenced by i is removed from x. This method does not copy or destroy the element moved, but re-links the node from x into self. If i is not an iterator into x, the behavior is undefined.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::splice_after	(	const_iterator	position,
		rw_forward_list< T, A > &	x,
		const_iterator	first,
		const_iterator	last
	)

Inserts the elements in the range (first, last) after the element referenced by position. The elements in the range (first, last) are removed from x. This method does not copy or destroy any of the elements moved, but re-links the list nodes from x into self. If i is not an iterator into x, the behavior is undefined.

template<typename T, typename A>

void rw_forward_list< T, A >::swap ( rw_forward_list< T, A > &  x )

inline

Exchanges the contents of self with x, retaining the ordering of each. This method does not copy or destroy any of the elements exchanged, but re-links the lists.

template<typename T, typename A = std::allocator<T>>

void rw_forward_list< T, A >::unique

(

)

Removes all consecutive duplicate elements from the container. Only the first element in each group is retained. Elements are considered duplicates if they compare equal (T::operator==() or equivalent).

Friends And Related Function Documentation

template<typename T , typename A >

bool operator!= ( const rw_forward_list< T, A > &  lhs, const rw_forward_list< T, A > &  rhs  )

related

Equivalent to !(lhs == rhs).

template<typename T , typename A >

bool operator< ( const rw_forward_list< T, A > &  lhs, const rw_forward_list< T, A > &  rhs  )

related

Returns the result of calling:

lexicographical_compare(lhs.begin(), lhs.end(),
                        rhs.begin(), rhs.end());

template<typename T , typename A >

bool operator<= ( const rw_forward_list< T, A > &  lhs, const rw_forward_list< T, A > &  rhs  )

related

Equivalent to !(rhs < lhs).

template<typename T , typename A >

bool operator== ( const rw_forward_list< T, A > &  lhs, const rw_forward_list< T, A > &  rhs  )

related

Returns true if lhs and rhs have the same number of elements and each element of rhs tests equal (T::operator==() or equivalent) to the corresponding element of lhs.

template<typename T , typename A >

bool operator> ( const rw_forward_list< T, A > &  lhs, const rw_forward_list< T, A > &  rhs  )

related

Equivalent to (rhs < lhs).

template<typename T , typename A >

bool operator>= ( const rw_forward_list< T, A > &  lhs, const rw_forward_list< T, A > &  rhs  )

related

Equivalent to !(lhs < rhs).