carb::container::IntrusiveList

Defined in carb/container/IntrusiveList.h

Classes

• carb::container::IntrusiveList::const_iterator: A LegacyBidirectionalIterator to const ValueType .

• carb::container::IntrusiveList::iterator: A LegacyBidirectionalIterator to ValueType .

template<class T, IntrusiveListLink<T> T::* U>
class IntrusiveList

IntrusiveList is very similar to std::list, but requires the tracking information to be contained within the stored type T, rather than built around it.

In other words, the tracking information is “intrusive” in the type T by way of the IntrusiveListLink type. IntrusiveList does no allocation of the T type; all allocation is done outside of the context of IntrusiveList, which allows stored items to be on the stack, grouped with other items, etc.

The impetus behind intrusive containers is specifically to allow the application to own the allocation patterns for a type, but still be able to store them in a container. For std::list, everything goes through an Allocator type, but in a real application some stored instances may be on the stack while others are on the heap, which makes using std::list impractical. Furthermore, a stored type may wish to be removed from one list and inserted into another. With std::list, this would require heap interaction to erase from one list and insert into another. With IntrusiveList, this operation would not require any heap interaction and would be done very quickly (O(1)).

Another example is a std::list of polymorphic types. For std::list the contained type would have to be a pointer or pointer-like type which is an inefficient use of space, cache, etc.

Since IntrusiveList doesn’t require any form of Allocator, the allocation strategy is completely left up to the application. This means that items could be allocated on the stack, pooled, or items mixed between stack and heap.

IntrusiveList matches std::list with the following exceptions:

• The iterator and initializer_list constructor variants are not present in IntrusiveList.

• The iterator and initializer_list insert() variants are not present in IntrusiveList.

• IntrusiveList cannot be copied (though may still be moved).

• IntrusiveList does not have erase() to erase an item from the list, but instead has remove() which will remove an item from the container. It is up to the caller to manage the memory for the item.

• Likewise, clear() functions as a “remove all” and does not destroy items in the container.

• IntrusiveList does not have any emplace functions as it is not responsible for construction of items.

• iter_from_value() is a new function that translates an item contained in IntrusiveList into an iterator.

Example:

// Given a class Waiter whose purpose is to wait until woken:
class Waiter {
public:
    void wait();
    IntrusiveListLink<Waiter> link;
};

IntrusiveList<Waiter, &Waiter::link> list;

Waiter w;
list.push_back(w);
w.wait();
list.remove(w);

// Since the Waiter instance is on the stack there is no heap used to track items in `list`.

Example 2:

// Intrusive list can be used to move items between multiple lists using the same link node without any heap
// usage.
class MyItem { public:
    // ...
    void process();
    IntrusiveListLink<MyItem> link;
};

using MyItemList = IntrusiveList<MyItem, &MyItem::link>;
MyItemList dirty;
MyItemList clean;

MyItemList::iter;
while (!dirty.empty())
{
    MyItem& item = dirty.pop_front();
    item.process();
    clean.push_back(item);
}

Template Parameters

• T – The contained object type.

• U – A pointer-to-member of T that must be of type IntrusiveListLink. This member will be used by the IntrusiveList for tracking the contained object.

Public Types

using ValueType = T

The type of the contained object.

using Link = IntrusiveListLink<T>

The type of the IntrusiveListLink that must be a member of ValueType.

using reverse_iterator = std::reverse_iterator<iterator>

Helper definition for std::reverse_iterator<iterator>

using const_reverse_iterator = std::reverse_iterator<const_iterator>

Helper definition for std::reverse_iterator<const_iterator>

Public Functions

inline constexpr IntrusiveList()

Constructor. Initializes *this to be empty().

inline IntrusiveList(IntrusiveList &&other) noexcept

Move-construct. Moves all entries to *this from other and leaves it empty.

Parameters

other – Another IntrusiveList to move entries from.

inline ~IntrusiveList()

Destructor. Implies clear().

inline IntrusiveList &operator=(IntrusiveList &&other) noexcept

Move-assign. Moves all entries from other and leaves other in a valid but possibly non-empty state.

Parameters

other – Another IntrusiveList to move entries from.

inline bool empty() const noexcept

Checks whether the container is empty.

Returns

true if *this is empty; false otherwise.

inline size_t size() const noexcept

Returns the number of elements contained.

Returns

The number of elements contained.

inline size_t max_size() const noexcept

Returns the maximum possible number of elements.

Returns

The maximum possible number of elements.

inline iterator begin() noexcept

Returns an iterator to the beginning.

Returns

An iterator to the beginning.

inline iterator end() noexcept

Returns an iterator to the end.

Returns

An iterator to the end.

inline const_iterator cbegin() const noexcept

Returns a const_iterator to the beginning.

Returns

A const_iterator to the beginning.

inline const_iterator cend() const noexcept

Returns a const_iterator to the end.

Returns

A const_iterator to the end.

inline const_iterator begin() const noexcept

Returns a const_iterator to the beginning.

Returns

A const_iterator to the beginning.

inline const_iterator end() const noexcept

Returns a const_iterator to the end.

Returns

A const_iterator to the end.

inline reverse_iterator rbegin() noexcept

Returns a reverse_iterator to the beginning.

Returns

A reverse_iterator to the beginning.

inline reverse_iterator rend() noexcept

Returns a reverse_iterator to the end.

Returns

A reverse_iterator to the end.

inline const_reverse_iterator crbegin() const noexcept

Returns a const_reverse_iterator to the beginning.

Returns

A const_reverse_iterator to the beginning.

inline const_reverse_iterator crend() const noexcept

Returns a const_reverse_iterator to the end.

Returns

A const_reverse_iterator to the end.

inline const_reverse_iterator rbegin() const noexcept

Returns a const_reverse_iterator to the beginning.

Returns

A const_reverse_iterator to the beginning.

inline const_reverse_iterator rend() const noexcept

Returns a const_reverse_iterator to the end.

Returns

A const_reverse_iterator to the end.

inline iterator locate(T &value) noexcept

Returns an iterator to the given value if it is contained in *this, otherwise returns end(). O(n).

Parameters

value – [in] The value to check for.

Returns

An iterator to value if contained in *this; end() otherwise.

inline const_iterator locate(T &value) const noexcept

Returns an iterator to the given value if it is contained in *this, otherwise returns end(). O(n).

Parameters

value – [in] The value to check for.

Returns

A const_iterator to value if contained in *this; end() otherwise.

inline iterator iter_from_value(T &value)

Naively produces an IntrusiveList::iterator for value within *this.

Warning

Undefined behavior results if value is not contained within *this. Use find() to safely check.

Parameters

value – The value to convert.

Returns

An iterator to value.

inline const_iterator iter_from_value(T &value) const

Naively produces an IntrusiveList::iterator for value within *this.

Warning

Undefined behavior results if value is not contained within *this. Use find() to safely check.

Parameters

value – The value to convert.

Returns

A const_iterator to value.

inline T &front()

Accesses the first element.

Warning

Undefined behavior if *this is empty().

Returns

A reference to the first element.

inline const T &front() const

Accesses the first element.

Warning

Undefined behavior if *this is empty().

Returns

A const reference to the first element.

inline T &back()

Accesses the last element.

Warning

Undefined behavior if *this is empty().

Returns

A reference to the last element.

inline const T &back() const

Accesses the last element.

Warning

Undefined behavior if *this is empty().

Returns

A const reference to the last element.

inline T &push_front(T &value)

Inserts an element at the beginning of the list.

Note

Precondition: value must not be contained (via U) in *this or any other IntrusiveList.

Parameters

value – The value to insert.

Returns

value for convenience.

inline T &pop_front()

Removes the first element.

Note

Precondition: *this must not be empty().

Returns

The prior first element in the list, which is now no longer contained in the list.

inline T &push_back(T &value)

Inserts an element at the end of the list.

Note

Precondition: value must not be contained (via U) in *this or any other IntrusiveList.

Parameters

value – The value to insert.

Returns

value for convenience.

inline T &pop_back()

Removes the last element.

Note

Precondition: *this must not be empty().

Returns

The prior last element in the list, which is now no longer contained in the list.

inline void clear()

Removes all elements from the list.

Note

Postcondition: *this is empty().

inline iterator insert(const_iterator pos, T &value)

Inserts an element before pos.

Note

Precondition: pos must be a valid const_iterator of *this; value must not be contained (via U) in this or any other IntrusiveList.

Parameters

• pos – A const_iterator indicating the insertion position. value will be inserted before pos.

• value – The value to insert.

Returns

An iterator to the newly-inserted value.

inline iterator remove(const_iterator pos)

Removes an element by iterator.

Note

Precondition: pos must be a valid const_iterator of *this and may not be end().

Parameters

pos – A const_iterator to the element to remove.

Returns

A iterator to the element immediately following pos, or end() if no elements followed it.

inline T &remove(T &value)

Removes an element by reference.

Note

Precondition: value must be contained in *this.

Parameters

value – The element to remove.

Returns

value for convenience.

inline void swap(IntrusiveList &other) noexcept

Swaps the contents of *this with another IntrusiveList.

Parameters

other – The other IntrusiveList to swap with.

template<class Compare>
inline void merge(IntrusiveList &other, Compare comp)

Merges two sorted lists.

Note

Precondition: *this and other must be sorted using comp.

Note

This operation is stable: for equivalent elements in the two lists elements from *this shall always precede the elements from other. The order of equivalent elements within *this and other will not change.

Parameters

• other – [inout] Another IntrusiveList to merge with. Must be sorted via comp. Will be empty after this call.

• comp – The comparator predicate, such as std::less.

template<class Compare>
inline void merge(IntrusiveList &&other, Compare comp)

Merges two sorted lists.

See also

merge(IntrusiveList& other, Compare comp)

Parameters

• other – [inout] Another IntrusiveList to merge with. Must be sorted via comp. Will be empty after this call.

• comp – The comparator predicate, such as std::less.

inline void merge(IntrusiveList &other)

Merges two sorted lists via std::less.

See also

merge(IntrusiveList& other, Compare comp)

Parameters

other – [inout] Another IntrusiveList to merge with. Must be sorted via comp. Will be empty after this call.

inline void merge(IntrusiveList &&other)

Merges two sorted lists via std::less.

See also

merge(IntrusiveList& other, Compare comp)

Parameters

other – [inout] Another IntrusiveList to merge with. Must be sorted via comp. Will be empty after this call.

inline void splice(const_iterator pos, IntrusiveList &other)

Transfers elements from another IntrusiveList into *this.

Note

Precondition: pos must be a valid const_iterator of *this.

Parameters

• pos – The position before which to insert elements from other.

• other – Another IntrusiveList to splice from. Will be empty after this call.

inline void splice(const_iterator pos, IntrusiveList &&other)

Transfers elements from another IntrusiveList into *this.

Note

Precondition: pos must be a valid const_iterator of *this.

Parameters

• pos – The position before which to insert elements from other.

• other – Another IntrusiveList to splice from. Will be empty after this call.

inline void splice(const_iterator pos, IntrusiveList &other, iterator it)

Transfers an element from another IntrusiveList into *this.

Note

Precondition: pos must be a valid const_iterator of *this. it must be a valid iterator of other and may not be other.end().

Parameters

• pos – The position before which to insert the element from other.

• other – The IntrusiveList that it is from.

• it – An iterator to an element from other. Will be removed from other and transferred to *this.

inline void splice(const_iterator pos, IntrusiveList &&other, iterator it)

Transfers an element from another IntrusiveList into *this.

Note

Precondition: pos must be a valid const_iterator of *this. it must be a valid iterator of other and may not be other.end().

Parameters

• pos – The position before which to insert the element from other.

• other – The IntrusiveList that it is from.

• it – An iterator to an element from other. Will be removed from other and transferred to *this.

inline void splice(const_iterator pos, IntrusiveList &other, const_iterator first, const_iterator end)

Transfers a range of elements from another IntrusiveList into *this.

Note

Precondition: pos must be a valid const_iterator of *this. first and end must be a valid iterator range of other. pos must not be in the range [first, end).

Parameters

• pos – The position before which to insert the element(s) from other.

• other – The IntrusiveList that first and end are from.

• first – Combined with end describes a range of elements from other that will be moved to pos.

• end – Combined with first describes a range of elements from other that will be moved to pos.

inline void splice(const_iterator pos, IntrusiveList &&other, const_iterator first, const_iterator end)

Transfers a range of elements from another IntrusiveList into *this.

Note

Precondition: pos must be a valid const_iterator of *this. first and end must be a valid iterator range of other. pos must not be in the range [first, end).

Parameters

• pos – The position before which to insert the element(s) from other.

• other – The IntrusiveList that first and end are from.

• first – Combined with end describes a range of elements from other that will be moved to pos.

• end – Combined with first describes a range of elements from other that will be moved to pos.

inline void reverse() noexcept

Reverses the order of the elements.

template<class Compare>
inline void sort(Compare comp)

Sorts the contained elements by the specified comparator function.

Parameters

comp – The comparator function, such as std::less.

inline void sort()

Sorts the contained elements by the specified comparator function.

class const_iterator

A LegacyBidirectionalIterator to const ValueType.

See also

LegacyBidirectionalIterator

Subclassed by carb::container::IntrusiveList< T, U >::iterator

class iterator : public carb::container::IntrusiveList<T, U>::const_iterator

A LegacyBidirectionalIterator to ValueType.

See also

LegacyBidirectionalIterator