#include <intrusive_list.h>

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::BidirectionalIterator< T, ItemBase >

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

using	reverse_iterator = std::reverse_iterator< iterator >

using	const_reverse_iterator = std::reverse_iterator< const_iterator >

Public Member Functions
	IntrusiveList (const IntrusiveList &)=delete

IntrusiveList &	operator= (const IntrusiveList &)=delete

	IntrusiveList (IntrusiveList &&)=default

IntrusiveList &	operator= (IntrusiveList &&)=default

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

	IntrusiveList (std::initializer_list< Item * > items)

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

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

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

T &	back ()
	Reference to the last element in the list. Undefined behavior if empty().

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

reverse_iterator	rbegin ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	crbegin () const

reverse_iterator	rend ()

const_reverse_iterator	rend () const

const_reverse_iterator	crend () const

bool	empty () const noexcept

size_t	size () const

constexpr size_type	max_size () const noexcept

void	clear ()
	Removes all items from the list.

iterator	insert (iterator pos, T &item)
	Inserts the given `item` before the given position, `pos`.

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

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

iterator	erase (T &item)
	Removes the given `item` from the list. The item is not destructed.

iterator	erase (iterator pos)

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

void	push_back (T &item)
	Inserts an element at the end of the list.

void	pop_back ()
	Removes the last item in the list. The list must not be empty.

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 (IntrusiveList< T > &other) noexcept

void	merge (IntrusiveList< T > &other)

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

void	splice (iterator pos, IntrusiveList< T > &other)

void	splice (iterator pos, IntrusiveList< T > &other, iterator it)

void	splice (iterator pos, IntrusiveList< 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)

Detailed Description

template<typename T>
class pw::containers::future::IntrusiveList< T >

A doubly-linked intrusive list.

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

As a doubly-linked list, operations such as removal are O(1) in time, and the list may be iterated in either direction. However, the overhead needed is 2*sizeof(T*).

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

Since items are not allocated by this class, the following methods have no analogue:
- std::list<T>::get_allocator
- std::list<T>::emplace
- std::list<T>::emplace_front
- std::list<T>::emplace_back
- std::list<T>::resize
Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:
- std::list<T>::(constructor)
- std::list<T>::assign
- std::list<T>::insert
There are no overloads corresponding to the following methods that take r-value references.:
- std::list<T>::insert
- std::list<T>::push_back
- std::list<T>::push_front
- std::list<T>::splice
Since modifying the list modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
- std::list<T>::insert
- std::list<T>::erase
- std::list<T>::splice
An additional overload of erase is provided that takes a direct reference to an item.
C++23 methods are not (yet) supported.

Template Parameters

T	Type of intrusive items stored in the list.

Constructor & Destructor Documentation

◆ IntrusiveList()

template<typename T >

pw::containers::future::IntrusiveList< T >::IntrusiveList ( IntrusiveList< T > && )

default

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

This is O(1).

Member Function Documentation

◆ clear()

template<typename T >

void pw::containers::future::IntrusiveList< T >::clear ( )

inline

Removes all items from the list.

◆ empty()

template<typename T >

bool pw::containers::future::IntrusiveList< T >::empty ( ) const

inlinenoexcept

◆ erase()

template<typename T >

iterator pw::containers::future::IntrusiveList< T >::erase ( iterator pos )

inline

Removes the item following pos from the list. The item is not destructed.

◆ insert() [1/2]

template<typename T >

template<typename Iterator >

iterator pw::containers::future::IntrusiveList< T >::insert	(	iterator	pos,
		Iterator	first,
		Iterator	last
	)

inline

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

◆ insert() [2/2]

template<typename T >

iterator pw::containers::future::IntrusiveList< T >::insert	(	iterator	pos,
		std::initializer_list< T * >	items
	)

inline

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

◆ max_size()

template<typename T >

constexpr size_type pw::containers::future::IntrusiveList< 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::containers::future::IntrusiveList< T >::merge ( IntrusiveList< 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::containers::future::IntrusiveList< T >::merge	(	IntrusiveList< 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 >

IntrusiveList & pw::containers::future::IntrusiveList< T >::operator= ( IntrusiveList< T > && )

default

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

This is O(1).

◆ remove()

template<typename T >

bool pw::containers::future::IntrusiveList< T >::remove ( const T & item )

inline

◆ remove_if()

template<typename T >

template<typename UnaryPredicate >

size_type pw::containers::future::IntrusiveList< 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::containers::future::IntrusiveList< T >::reverse ( )

inline

Reverses the order of items in the list.

◆ size()

template<typename T >

size_t pw::containers::future::IntrusiveList< T >::size ( ) const

inline

◆ sort() [1/2]

template<typename T >

void pw::containers::future::IntrusiveList< 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::containers::future::IntrusiveList< 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() [1/3]

template<typename T >

void pw::containers::future::IntrusiveList< T >::splice	(	iterator	pos,
		IntrusiveList< T > &	other
	)

inline

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

◆ splice() [2/3]

template<typename T >

void pw::containers::future::IntrusiveList< T >::splice	(	iterator	pos,
		IntrusiveList< T > &	other,
		iterator	first,
		iterator	last
	)

inline

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

◆ splice() [3/3]

template<typename T >

void pw::containers::future::IntrusiveList< T >::splice	(	iterator	pos,
		IntrusiveList< T > &	other,
		iterator	it
	)

inline

Moves the item pointed to by it from other to before pos in this list.

◆ swap()

template<typename T >

void pw::containers::future::IntrusiveList< T >::swap ( IntrusiveList< T > & other )

inlinenoexcept

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

This is O(1).

◆ unique() [1/2]

template<typename T >

size_type pw::containers::future::IntrusiveList< 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::containers::future::IntrusiveList< 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_list.h

Classes

Public Types

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ IntrusiveList()

Member Function Documentation

◆ clear()

◆ empty()

◆ erase()

◆ insert() [1/2]

◆ insert() [2/2]

◆ max_size()

◆ merge() [1/2]

◆ merge() [2/2]

◆ operator=()

◆ remove()

◆ remove_if()

◆ reverse()

◆ size()

◆ sort() [1/2]

◆ sort() [2/2]

◆ splice() [1/3]

◆ splice() [2/3]

◆ splice() [3/3]

◆ swap()

◆ unique() [1/2]

◆ unique() [2/2]