Overview

template<typename T>
class pw::IntrusiveForwardList< T >

A singly-list intrusive list.

IntrusiveForwardList<T> is a handle to access and manipulate the list, and IntrusiveForwardList<T>::Item is the type from which the base class items must derive.

As a singly-linked list, the overhead required is only sizeof(T*). However, operations such as removal may require O(n) time to walk the length of the list.

This class is modeled on std::forward_list, with the following differences:

Since items are not allocated by this class, the following methods have no analogue:
- std::forward_list<T>::get_allocator
- std::forward_list<T>::emplace_after
- std::forward_list<T>::emplace_front
- std::forward_list<T>::resize
Methods corresponding to the following take initializer lists of pointer to items rather than the itenms themselves:
- std::forward_list<T>::(constructor)
- std::forward_list<T>::assign
- std::forward_list<T>::insert_after
There are no overloads corresponding to the following methods that take r-value references.:
- std::forward_list<T>::insert_after
- std::forward_list<T>::push_front
- std::forward_list<T>::splice_after
Since modifying the list modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
- std::forward_list<T>::insert_after
- std::forward_list<T>::erase_after
- std::forward_list<T>::splice_after
C++23 methods are not (yet) supported.

Template Parameters

T	Type of intrusive items stored in the list.

Classes
class	Item

Public Types
using	element_type = T

using	value_type = std::remove_cv_t< element_type >

using	size_type = std::size_t

using	difference_type = std::ptrdiff_t

using	reference = value_type &

using	const_reference = const value_type &

using	pointer = element_type *

using	const_pointer = const element_type *

using	iterator = typename ::pw::containers::internal::ForwardIterator< T, ItemBase >

using	const_iterator = typename ::pw::containers::internal::ForwardIterator< std::add_const_t< T >, const ItemBase >

Public Member Functions
	IntrusiveForwardList (const IntrusiveForwardList &)=delete

IntrusiveForwardList &	operator= (const IntrusiveForwardList &)=delete

	IntrusiveForwardList (IntrusiveForwardList &&)=default

IntrusiveForwardList &	operator= (IntrusiveForwardList &&)=default

template<typename Iterator >
	IntrusiveForwardList (Iterator first, Iterator last)

	IntrusiveForwardList (std::initializer_list< Item * > items)
	Constructs a list from a std::initializer_list of pointers to items.

template<typename Iterator >
void	assign (Iterator first, Iterator last)

void	assign (std::initializer_list< T * > items)

reference	front ()
	Reference to the first element in the list. Undefined behavior if empty().

const_reference	front () const

iterator	before_begin () noexcept

const_iterator	before_begin () const noexcept

const_iterator	cbefore_begin () const noexcept

iterator	begin () noexcept

const_iterator	begin () const noexcept

const_iterator	cbegin () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

const_iterator	cend () const noexcept

bool	empty () const noexcept

constexpr size_type	max_size () const noexcept

void	clear ()
	Removes all items from the list.

iterator	insert_after (iterator pos, T &item)
	Inserts the given `item` after the given position, `pos`.

template<typename Iterator >
iterator	insert_after (iterator pos, Iterator first, Iterator last)

iterator	insert_after (iterator pos, std::initializer_list< T * > items)

iterator	erase_after (iterator pos)
	Removes the item following pos from the list. The item is not destructed.

iterator	erase_after (iterator first, iterator last)
	Removes the range of items from `first` (inclusive) to `last` (exclusive).

void	push_front (T &item)
	Inserts an element at the beginning of the list.

void	pop_front ()
	Removes the first item in the list. The list must not be empty.

void	swap (IntrusiveForwardList< T > &other) noexcept

void	merge (IntrusiveForwardList< T > &other)

template<typename Compare >
void	merge (IntrusiveForwardList< T > &other, Compare comp)

void	splice_after (iterator pos, IntrusiveForwardList< T > &other)

void	splice_after (iterator pos, IntrusiveForwardList< T > &other, iterator it)

void	splice_after (iterator pos, IntrusiveForwardList< T > &other, iterator first, iterator last)

bool	remove (const T &item)

template<typename UnaryPredicate >
size_type	remove_if (UnaryPredicate pred)

void	reverse ()
	Reverses the order of items in the list.

size_type	unique ()

template<typename BinaryPredicate >
size_type	unique (BinaryPredicate pred)

void	sort ()

template<typename Compare >
void	sort (Compare comp)

Friends
template<typename >
class	containers::internal::LegacyIntrusiveList

void	containers::PushBackSlow (IntrusiveForwardList< T > &, T &)

Constructor & Destructor Documentation

◆ IntrusiveForwardList() [1/2]

template<typename T >

pw::IntrusiveForwardList< T >::IntrusiveForwardList ( IntrusiveForwardList< T > && )

default

Moves the other list's contents into this list.

This is O(n).

◆ IntrusiveForwardList() [2/2]

template<typename T >

template<typename Iterator >

pw::IntrusiveForwardList< T >::IntrusiveForwardList	(	Iterator	first,
		Iterator	last
	)

inline

Constructs a list from an iterator over items. The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

Member Function Documentation

◆ clear()

template<typename T >

void pw::IntrusiveForwardList< T >::clear ( )

inline

Removes all items from the list.

◆ empty()

template<typename T >

bool pw::IntrusiveForwardList< T >::empty ( ) const

inlinenoexcept

◆ insert_after() [1/2]

template<typename T >

template<typename Iterator >

iterator pw::IntrusiveForwardList< T >::insert_after	(	iterator	pos,
		Iterator	first,
		Iterator	last
	)

inline

Inserts the range of items from first (inclusive) to last (exclusive) after the given position, pos.

◆ insert_after() [2/2]

template<typename T >

iterator pw::IntrusiveForwardList< T >::insert_after	(	iterator	pos,
		std::initializer_list< T * >	items
	)

inline

Inserts the range of items from first (inclusive) to last (exclusive) after the given position, pos.

◆ max_size()

template<typename T >

constexpr size_type pw::IntrusiveForwardList< T >::max_size ( ) const

inlineconstexprnoexcept

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

◆ merge() [1/2]

template<typename T >

void pw::IntrusiveForwardList< T >::merge ( IntrusiveForwardList< T > & other )

inline

Merges the given other list into this one.

After the call, the list will be sorted according to comp. The sort is stable, and equivalent items in each list will remain in the same order relative to each other.

This overload uses T::operator<.

◆ merge() [2/2]

template<typename T >

template<typename Compare >

void pw::IntrusiveForwardList< T >::merge	(	IntrusiveForwardList< T > &	other,
		Compare	comp
	)

inline

Merges the given other list into this one.

After the call, the list will be sorted according to comp. The sort is stable, and equivalent items in each list will remain in the same order relative to each other.

◆ operator=()

template<typename T >

IntrusiveForwardList & pw::IntrusiveForwardList< T >::operator= ( IntrusiveForwardList< T > && )

default

Clears this list and moves the other list's contents into it.

This is O(n).

◆ pop_front()

template<typename T >

void pw::IntrusiveForwardList< T >::pop_front ( )

inline

Removes the first item in the list. The list must not be empty.

◆ push_front()

template<typename T >

void pw::IntrusiveForwardList< T >::push_front ( T & item )

inline

Inserts an element at the beginning of the list.

◆ remove()

template<typename T >

bool pw::IntrusiveForwardList< T >::remove ( const T & item )

inline

◆ remove_if()

template<typename T >

template<typename UnaryPredicate >

size_type pw::IntrusiveForwardList< T >::remove_if ( UnaryPredicate pred )

inline

Removes any item for which the given unary predicate function p evaluates to true when passed that item.

Template Parameters

UnaryPredicate Function with the signature bool(const Item&)

Returns: The number of items removed.

◆ reverse()

template<typename T >

void pw::IntrusiveForwardList< T >::reverse ( )

inline

Reverses the order of items in the list.

◆ sort() [1/2]

template<typename T >

void pw::IntrusiveForwardList< T >::sort ( )

inline

Rearranges the items in the list such that the given comparison function comp evaluates to true for each pair of successive items.

Template Parameters

BinaryPredicate Function with the signature bool(const Item&, const Item&)

This overload uses T::operator<.

◆ sort() [2/2]

template<typename T >

template<typename Compare >

void pw::IntrusiveForwardList< T >::sort ( Compare comp )

inline

Rearranges the items in the list such that the given comparison function comp evaluates to true for each pair of successive items.

Template Parameters

BinaryPredicate Function with the signature bool(const Item&, const Item&)

◆ splice_after() [1/3]

template<typename T >

void pw::IntrusiveForwardList< T >::splice_after	(	iterator	pos,
		IntrusiveForwardList< T > &	other
	)

inline

Inserts the items of other to after pos in this list. Upon returning, other will be empty.

◆ splice_after() [2/3]

template<typename T >

void pw::IntrusiveForwardList< T >::splice_after	(	iterator	pos,
		IntrusiveForwardList< T > &	other,
		iterator	first,
		iterator	last
	)

inline

Moves the items exclusively between first and last from other to after pos in this list.

◆ splice_after() [3/3]

template<typename T >

void pw::IntrusiveForwardList< T >::splice_after	(	iterator	pos,
		IntrusiveForwardList< T > &	other,
		iterator	it
	)

inline

Moves the item pointed to by the iterator following it from other to after pos in this list.

◆ swap()

template<typename T >

void pw::IntrusiveForwardList< T >::swap ( IntrusiveForwardList< T > & other )

inlinenoexcept

Exchanges this list's items with the other list's items.

This is O(n), where "n" is the number of items in the range.

◆ unique() [1/2]

template<typename T >

size_type pw::IntrusiveForwardList< T >::unique ( )

inline

Removes consecutive ietms that are equivalent accroding to the given binary predicate p, leaving only the first item in the list.

Template Parameters

BinaryPredicate Function with the signature bool(const Item&, const Item&)

This overload uses T::operator==.

◆ unique() [2/2]

template<typename T >

template<typename BinaryPredicate >

size_type pw::IntrusiveForwardList< T >::unique ( BinaryPredicate pred )

inline

Removes consecutive ietms that are equivalent accroding to the given binary predicate p, leaving only the first item in the list.

Template Parameters

BinaryPredicate Function with the signature bool(const Item&, const Item&)

The documentation for this class was generated from the following file:

pw_containers/public/pw_containers/intrusive_forward_list.h

Overview

Classes

Public Types

Public Member Functions

Friends

Constructor & Destructor Documentation

◆ IntrusiveForwardList() [1/2]

◆ IntrusiveForwardList() [2/2]

Member Function Documentation

◆ clear()

◆ empty()

◆ insert_after() [1/2]

◆ insert_after() [2/2]

◆ max_size()

◆ merge() [1/2]

◆ merge() [2/2]

◆ operator=()

◆ pop_front()

◆ push_front()

◆ remove()

◆ remove_if()

◆ reverse()

◆ sort() [1/2]

◆ sort() [2/2]

◆ splice_after() [1/3]

◆ splice_after() [2/3]

◆ splice_after() [3/3]

◆ swap()

◆ unique() [1/2]

◆ unique() [2/2]