Skip to main content
Pigweed's logo Pigweed
code_xml
  1. Home
  2. Reference
  3. C/C++
  4. pw::IntrusiveForwardList< T > Class Template Reference
pw::IntrusiveForwardList< T > Class Template Reference

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
TType 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

constexpr IntrusiveForwardList ()=default
 Constructs an empty list.
 
 IntrusiveForwardList (const IntrusiveForwardList &)=delete
 
IntrusiveForwardList & operator= (const IntrusiveForwardList &)=delete
 
constexpr IntrusiveForwardList (IntrusiveForwardList &&)=default
 
constexpr IntrusiveForwardList & operator= (IntrusiveForwardList &&)=default
 
template<typename Iterator >
constexpr IntrusiveForwardList (Iterator first, Iterator last)
 
constexpr IntrusiveForwardList (std::initializer_list< Item * > items)
 Constructs a list from a std::initializer_list of pointers to items.
 
template<typename Iterator >
constexpr void assign (Iterator first, Iterator last)
 Replaces the contents of the list with the items in [first, last).
 
constexpr void assign (std::initializer_list< T * > items)
 Replaces the contents of the list with the pointers in items.
 
constexpr reference front ()
 Reference to the first element in the list. Undefined behavior if empty().
 
constexpr const_reference front () const
 
constexpr iterator before_begin () noexcept
 Returns an iterator to the position before the first element.
 
constexpr const_iterator before_begin () const noexcept
 Returns a const iterator to the position before the first element.
 
constexpr const_iterator cbefore_begin () const noexcept
 Returns a const iterator to the position before the first element.
 
constexpr iterator begin () noexcept
 Returns an iterator to the first element.
 
constexpr const_iterator begin () const noexcept
 Returns a const iterator to the first element.
 
constexpr const_iterator cbegin () const noexcept
 Returns a const iterator to the first element.
 
constexpr iterator end () noexcept
 Returns an iterator past the last element.
 
constexpr const_iterator end () const noexcept
 Returns a const iterator past the last element.
 
constexpr const_iterator cend () const noexcept
 Returns a const iterator past the last element.
 
constexpr bool empty () const noexcept
 
constexpr size_type max_size () const noexcept
 
constexpr void clear ()
 Removes all items from the list.
 
constexpr iterator insert_after (iterator pos, T &item)
 Inserts the given item after the given position, pos.
 
template<typename Iterator >
constexpr iterator insert_after (iterator pos, Iterator first, Iterator last)
 
constexpr iterator insert_after (iterator pos, std::initializer_list< T * > items)
 
constexpr iterator erase_after (iterator pos)
 Removes the item following pos from the list. The item is not destructed.
 
constexpr iterator erase_after (iterator first, iterator last)
 Removes the range of items from first (inclusive) to last (exclusive).
 
constexpr void push_front (T &item)
 Inserts an element at the beginning of the list.
 
constexpr void pop_front ()
 Removes the first item in the list. The list must not be empty.
 
void swap (IntrusiveForwardList< T > &other) noexcept
 
constexpr void merge (IntrusiveForwardList< T > &other)
 
template<typename Compare >
constexpr void merge (IntrusiveForwardList< T > &other, Compare comp)
 
constexpr void splice_after (iterator pos, IntrusiveForwardList< T > &other)
 
constexpr void splice_after (iterator pos, IntrusiveForwardList< T > &other, iterator it)
 
constexpr void splice_after (iterator pos, IntrusiveForwardList< T > &other, iterator first, iterator last)
 
constexpr bool remove (const T &item)
 
template<typename UnaryPredicate >
constexpr size_type remove_if (UnaryPredicate pred)
 
void reverse ()
 Reverses the order of items in the list.
 
constexpr size_type unique ()
 
template<typename BinaryPredicate >
constexpr size_type unique (BinaryPredicate pred)
 
void sort ()
 
template<typename Compare >
void sort (Compare comp)
 

Friends

template<typename >
class containers::internal::LegacyIntrusiveList
 
constexpr void containers::PushBackSlow (IntrusiveForwardList< T > &, T &)
 

Constructor & Destructor Documentation

◆ IntrusiveForwardList() [1/2]

template<typename T >
constexpr pw::IntrusiveForwardList< T >::IntrusiveForwardList ( IntrusiveForwardList< T > &&  )
constexprdefault

Moves the other list's contents into this list.

This is O(n).

◆ IntrusiveForwardList() [2/2]

template<typename T >
template<typename Iterator >
constexpr pw::IntrusiveForwardList< T >::IntrusiveForwardList ( Iterator  first,
Iterator  last 
)
inlineconstexpr

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 >
constexpr void pw::IntrusiveForwardList< T >::clear ( )
inlineconstexpr

Removes all items from the list.

◆ empty()

template<typename T >
constexpr bool pw::IntrusiveForwardList< T >::empty ( ) const
inlineconstexprnoexcept

◆ front()

template<typename T >
constexpr const_reference pw::IntrusiveForwardList< T >::front ( ) const
inlineconstexpr

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

◆ insert_after() [1/2]

template<typename T >
template<typename Iterator >
constexpr iterator pw::IntrusiveForwardList< T >::insert_after ( iterator  pos,
Iterator  first,
Iterator  last 
)
inlineconstexpr

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

◆ insert_after() [2/2]

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

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 >
constexpr void pw::IntrusiveForwardList< T >::merge ( IntrusiveForwardList< T > &  other)
inlineconstexpr

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 >
constexpr void pw::IntrusiveForwardList< T >::merge ( IntrusiveForwardList< T > &  other,
Compare  comp 
)
inlineconstexpr

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 >
constexpr IntrusiveForwardList & pw::IntrusiveForwardList< T >::operator= ( IntrusiveForwardList< T > &&  )
constexprdefault

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

This is O(n).

◆ pop_front()

template<typename T >
constexpr void pw::IntrusiveForwardList< T >::pop_front ( )
inlineconstexpr

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

◆ push_front()

template<typename T >
constexpr void pw::IntrusiveForwardList< T >::push_front ( T &  item)
inlineconstexpr

Inserts an element at the beginning of the list.

◆ remove()

template<typename T >
constexpr bool pw::IntrusiveForwardList< T >::remove ( const T &  item)
inlineconstexpr

◆ remove_if()

template<typename T >
template<typename UnaryPredicate >
constexpr size_type pw::IntrusiveForwardList< T >::remove_if ( UnaryPredicate  pred)
inlineconstexpr

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

Template Parameters
UnaryPredicateFunction 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
BinaryPredicateFunction 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
BinaryPredicateFunction with the signature bool(const Item&, const Item&)

◆ splice_after() [1/3]

template<typename T >
constexpr void pw::IntrusiveForwardList< T >::splice_after ( iterator  pos,
IntrusiveForwardList< T > &  other 
)
inlineconstexpr

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

◆ splice_after() [2/3]

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

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

◆ splice_after() [3/3]

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

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 >
constexpr size_type pw::IntrusiveForwardList< T >::unique ( )
inlineconstexpr

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

Template Parameters
BinaryPredicateFunction with the signature bool(const Item&, const Item&)

This overload uses T::operator==.

◆ unique() [2/2]

template<typename T >
template<typename BinaryPredicate >
constexpr size_type pw::IntrusiveForwardList< T >::unique ( BinaryPredicate  pred)
inlineconstexpr

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

Template Parameters
BinaryPredicateFunction with the signature bool(const Item&, const Item&)

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