pw::containers::future::IntrusiveList< T > Class Template Reference

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