#include <list.hpp>

Collaboration diagram for List< T, TRecycling >:

Class Description

template<typename T, typename TRecycling>
class aworx::lib::monomem::List< T, TRecycling >

Implements a doubly linked list, likewise std::list does. Memory for inserted elements is allocated using the MonoAllocator provided with the constructor.

Elements that are erased from the list will be recycled with subsequent insert operations. With that, remove and insert operations do not lead to leaked memory in the monotonic allocator.

It is allowed to use different allocator objects with insertions. However, the life-cycle of the allocated memory and the objects stored in this container has to be kept in sync by the user of this object. For more information on this topic see methods Clear and Reset.

Template Parameters

T	The type of the contained objects.
TRecycling	Denotes the type of recycling that is to be performed. Possible values are Recycling::Private (the default), Recycling::Shared or Recycling::None.

Definition at line 57 of file monomem/fwds.hpp.

Public Types
using	ConstIterator = TIterator< const T >

using	ConstReverseIterator = std::reverse_iterator< ConstIterator >

using	Iterator = TIterator< T >

using	ReverseIterator = std::reverse_iterator< Iterator >

using	TSharedRecycler = lib::detail::SidiListHelper< Element >

Inner Classes
struct	TIterator

Public Methods
std::iterator_traits Interface

Iterator	begin ()

Iterator	end ()

ConstIterator	begin () const

ConstIterator	end () const

ConstIterator	cbegin () const

ConstIterator	cend () const

ReverseIterator	rbegin ()

ReverseIterator	rend ()

ConstReverseIterator	rbegin () const

ConstReverseIterator	rend () const

ConstReverseIterator	crbegin () const

ConstReverseIterator	crend () const

Construction/Destruction

	List (const List &copy)

	List (List &&move)

	List (MonoAllocator *pAllocator)

	List (MonoAllocator *pAllocator, TSharedRecycler &pRecycler)

	~List ()

Allocation

MonoAllocator *	GetAllocator () const

integer	RecyclablesCount () const

Size and Capacity

integer	Size () const

bool	IsEmpty () const

bool	IsNotEmpty () const

void	Clear ()

void	Reset ()

void	ReserveRecyclables (integer expectedSize)

List Start/End Access

T &	ElementAt (integer idx)

const T &	ElementAt (integer idx) const

T &	Front ()

const T &	Front () const

T &	Back ()

const T &	Back () const

Element Insertion

Iterator	Insert (ConstIterator position, const T &copy)

Iterator	Insert (ConstIterator position, T &&move)

T &	PushBack (const T &copy)

T &	PushBack (T &&move)

T &	PushFront (const T &copy)

T &	PushFront (T &&move)

template<typename... TArgs>
Iterator	Emplace (ConstIterator position, TArgs &&... args)

template<typename... TArgs>
T &	EmplaceBack (TArgs &&... args)

template<typename... TArgs>
T &	EmplaceFront (TArgs &&... args)

Element Removal

Iterator	Erase (ConstIterator position)

Iterator	Erase (ConstIterator first, ConstIterator last)

void	PopFront ()

void	PopBack ()

Protected Types
using	Element = detail::ListElement< T >

Protected Fields
MonoAllocator *	allocator

lib::detail::BidiListHelper< Element >	list

detail::ListRecycler< T, TRecycling >::type	recycler

Protected Methods
Element *	allocElement ()

Member Typedef Documentation

◆ ConstIterator

using ConstIterator = TIterator<const T>

The constant iterator exposed by this container.

Definition at line 245 of file list.hpp.

◆ ConstReverseIterator

using ConstReverseIterator = std::reverse_iterator<ConstIterator>

The constant iterator exposed by this container.

Definition at line 251 of file list.hpp.

◆ Element

using Element = detail::ListElement<T>

protected

The list element type.

Definition at line 76 of file list.hpp.

◆ Iterator

using Iterator = TIterator< T>

The mutable iterator exposed by this container.

Definition at line 248 of file list.hpp.

◆ ReverseIterator

using ReverseIterator = std::reverse_iterator<Iterator>

The mutable iterator exposed by this container.

Definition at line 254 of file list.hpp.

◆ TSharedRecycler

using TSharedRecycler = lib::detail::SidiListHelper<Element>

This type definition may be used to define an externally managed shared recycler, which can be passed to the alternative constructor of this class when template parameter TRecycling equals Recycling::Shared.

See also: Chapter 3.3 Shared Recycling of the Programmer's Manual for this ALib Module.

Definition at line 94 of file list.hpp.

Constructor & Destructor Documentation

◆ List() [1/4]

List ( const List< T, TRecycling > & copy )

inline

Copy constructor. Invokes implementation dependent copy constructor of recycler, copies the pointer to the allocator and then copies each element.

Parameters

copy	The list to copy.

Definition at line 318 of file list.hpp.

◆ List() [2/4]

List ( List< T, TRecycling > && move )

inline

Move constructor. Invokes implementation dependent move constructor of recycler, moves the pointer to the allocator and then copies each element.

Parameters

move	The private recycler to move.

Definition at line 332 of file list.hpp.

◆ List() [3/4]

List ( MonoAllocator * pAllocator )

inline

Constructor accepting a pointer to the allocator.

Note: This cnstructor is not available if template argument TRecycling equals type Recycling::Shared.

Parameters

pAllocator The monotonic allocator to use.

Definition at line 348 of file list.hpp.

◆ List() [4/4]

List	(	MonoAllocator *	pAllocator,
		TSharedRecycler &	pRecycler
	)

inlineexplicit

Constructor taking a shared recycler.

Parameters

pAllocator	The monotonic allocator to use.
pRecycler	The shared recycler.

Definition at line 366 of file list.hpp.

◆ ~List()

~List ( )

inline

Destructor. Invokes Clear.

Definition at line 375 of file list.hpp.

Member Function Documentation

◆ allocElement()

Element* allocElement ( )

inlineprotected

Returns either a recycled or newly allocated element.

Returns: A pointer to the element created or recycled.

Definition at line 102 of file list.hpp.

◆ Back() [1/2]

T& Back ( )

inline

Returns a non-constant reference to the last object of the list.

Returns: A mutable reference to T.

Definition at line 589 of file list.hpp.

◆ Back() [2/2]

const T& Back ( ) const

inline

Returns a constant reference to the last object of the list.

Returns: A constant reference to T.

Definition at line 600 of file list.hpp.

◆ begin() [1/2]

Iterator begin ( )

inline

Returns an iterator pointing to a mutable value at the start of this list.

Returns: The start of this list.

Definition at line 261 of file list.hpp.

◆ begin() [2/2]

ConstIterator begin ( ) const

inline

Returns an iterator pointing to a constant value at the start of this list.

Returns: The start of this list.

Definition at line 269 of file list.hpp.

◆ cbegin()

ConstIterator cbegin ( ) const

inline

Returns an iterator pointing to a constant value at the start of this list.

Returns: The start of this list.

Definition at line 277 of file list.hpp.

◆ cend()

ConstIterator cend ( ) const

inline

Returns an iterator pointing to the first element behind this list.

Returns: The end of this list.

Definition at line 281 of file list.hpp.

◆ Clear()

void Clear ( )

inline

Invokes the destructor of all elements and empties the list. All allocated internal elements are kept for future recycling. Hence, the invocation of this method with this value implies that associated monotonic allocator is not reset.

As the life-cycle of the monotonic allocator(s) used for insertions is not under control of this object, it is the obligation of the caller to ensure that the monotonic allocator is kept in sync with this object.

Definition at line 455 of file list.hpp.

◆ crbegin()

ConstReverseIterator crbegin ( ) const

inline

Returns a reverse iterator pointing to a constant value at the end of this list.

Returns: The start of this list.

Definition at line 301 of file list.hpp.

◆ crend()

ConstReverseIterator crend ( ) const

inline

Returns a reverse iterator pointing to the first element behind the start of this list.

Returns: The end of this list.

Definition at line 305 of file list.hpp.

◆ ElementAt() [1/2]

T& ElementAt ( integer idx )

inline

Traverses the list to return the item with the given idx. (Executes in linear time O(N).)

Parameters

idx	The index of the element to retrieve.

Returns: A mutable reference to T.

Definition at line 527 of file list.hpp.

◆ ElementAt() [2/2]

const T& ElementAt ( integer idx ) const

inline

Traverses the list to return the item with the given idx. (Executes in linear time O(N).)

Parameters

idx	The index of the element to retrieve.

Returns: A constant reference to T.

Definition at line 548 of file list.hpp.

◆ Emplace()

Iterator Emplace	(	ConstIterator	position,
		TArgs &&...	args
	)

inline

Adds a new element before the given position.

Template Parameters

TArgs Types of variadic parameters given with parameter args.

Parameters

position	The position to emplace the new element.
args	Variadic parameters to be forwarded to constructor of type T.

Returns: A constant reference to the element added.

Definition at line 703 of file list.hpp.

◆ EmplaceBack()

T& EmplaceBack ( TArgs &&... args )

inline

Adds a new element at the end of the list.

Template Parameters

TArgs Types of variadic parameters given with parameter args.

Parameters

args	Variadic parameters to be forwarded to constructor of type T.

Returns: A reference to the element added.

Definition at line 719 of file list.hpp.

◆ EmplaceFront()

T& EmplaceFront ( TArgs &&... args )

inline

Adds a new element at the end of the list.

Template Parameters

TArgs Types of variadic parameters given with parameter args.

Parameters

args	Variadic parameters to be forwarded to constructor of type T.

Returns: A reference to the element added.

Definition at line 735 of file list.hpp.

◆ end() [1/2]

Iterator end ( )

inline

Returns an iterator pointing to the first element behind this list.

Returns: The end of this list.

Definition at line 265 of file list.hpp.

◆ end() [2/2]

ConstIterator end ( ) const

inline

Returns an iterator pointing to the first element behind this list.

Returns: The end of this list.

Definition at line 273 of file list.hpp.

◆ Erase() [1/2]

Iterator Erase	(	ConstIterator	first,
		ConstIterator	last
	)

inline

Removes a range of elements defined by iterators first and last.

Parameters

first	The start of the range to remove.
last	The first element behind the range to remove.

Returns: A mutable iterator referring to the given last.

Definition at line 780 of file list.hpp.

◆ Erase() [2/2]

Iterator Erase ( ConstIterator position )

inline

Removes an element at the given position.

Parameters

position A constant iterator pointing to the element to be removed. Mutable iterators are inherently converted with the invocation of this method.

Returns: A mutable iterator pointing behind the removed element. If position refers to the last element of the list, iterator end() is returned.

Definition at line 757 of file list.hpp.

◆ Front() [1/2]

T& Front ( )

inline

Returns a non-constant reference to the first object of the list.

Returns: A mutable reference to T.

Definition at line 566 of file list.hpp.

◆ Front() [2/2]

const T& Front ( ) const

inline

Returns a constant reference to the first object of the list.

Returns: A constant reference to T.

Definition at line 578 of file list.hpp.

◆ GetAllocator()

MonoAllocator* GetAllocator ( ) const

inline

Returns the allocator of this object. Usually the allocator might be used to perform allocations in respect to data found in objects stored in this object. However, such allowance is dependent on the use case and not part of this class's contract.

Returns: The allocator that was provided in the constructor.

Definition at line 392 of file list.hpp.

◆ Insert() [1/2]

Iterator Insert	(	ConstIterator	position,
		const T &	copy
	)

inline

Adds a new element before the given position.

Parameters

position	The position to emplace the new element.
copy	The value to copy and insert.

Returns: A constant reference to the element added.

Definition at line 616 of file list.hpp.

◆ Insert() [2/2]

Iterator Insert	(	ConstIterator	position,
		T &&	move
	)

inline

Moves a value into this container before the given position.

Parameters

position	The position to emplace the new element.
move	The value to move into this container.

Returns: A constant reference to the element moved.

Definition at line 631 of file list.hpp.

◆ IsEmpty()

bool IsEmpty ( ) const

inline

Tests this container for emptiness.

Returns: true if this list is empty, false otherwise.

Definition at line 431 of file list.hpp.

◆ IsNotEmpty()

bool IsNotEmpty ( ) const

inline

Tests this container for emptiness.

Returns: true if this list is empty, false otherwise.

Definition at line 440 of file list.hpp.

◆ PopBack()

void PopBack ( )

inline

Removes the last element.

Definition at line 817 of file list.hpp.

◆ PopFront()

void PopFront ( )

inline

Removes the first element.

Definition at line 806 of file list.hpp.

◆ PushBack() [1/2]

T& PushBack ( const T & copy )

inline

Adds a new element at the end of the list.

Parameters

copy	The value to copy and insert.

Returns: A reference to the element added.

Definition at line 645 of file list.hpp.

◆ PushBack() [2/2]

T& PushBack ( T && move )

inline

Moves a value to the end of this list.

Parameters

move	The value to move into this container.

Returns: A reference to the element moved.

Definition at line 659 of file list.hpp.

◆ PushFront() [1/2]

T& PushFront ( const T & copy )

inline

Adds a new element at the start of the list.

Parameters

copy	The value to copy and insert.

Returns: A reference to the element added.

Definition at line 673 of file list.hpp.

◆ PushFront() [2/2]

T& PushFront ( T && move )

inline

Moves a value to the start of this list.

Parameters

move	The value to move into this container.

Returns: A reference to the element moved.

Definition at line 686 of file list.hpp.

◆ rbegin() [1/2]

ReverseIterator rbegin ( )

inline

Returns a reverse iterator pointing to a mutable value at the end of this list.

Returns: The start of this list.

Definition at line 285 of file list.hpp.

◆ rbegin() [2/2]

ConstReverseIterator rbegin ( ) const

inline

Returns a reverse iterator pointing to a constant value at the end of this list.

Returns: The start of this list.

Definition at line 293 of file list.hpp.

◆ RecyclablesCount()

integer RecyclablesCount ( ) const

inline

Counts the number of currently allocated but unused (not contained) list elements that will be recycled with upcoming insertions.

Note: This method is provided for completeness and unit-testing. It should not be of relevance for common usage.
Furthermore, this method is not available (aka does not compile) with instantiations that specify template parameter TRecycling as Recycling::None.

Returns: The number of removed and not yet recycled elements.

Definition at line 409 of file list.hpp.

◆ rend() [1/2]

ReverseIterator rend ( )

inline

Returns a reverse iterator pointing to the first element behind the start of this list.

Returns: The end of this list.

Definition at line 289 of file list.hpp.

◆ rend() [2/2]

ConstReverseIterator rend ( ) const

inline

Returns a reverse iterator pointing to the first element behind the start of this list.

Returns: The end of this list.

Definition at line 297 of file list.hpp.

◆ ReserveRecyclables()

void ReserveRecyclables ( integer expectedSize )

inline

Allocates the required memory for the number of additional elements expected.

This method may be helpful if the definite number of stored elements that is never exceeded is known. In this case, a snapshot of the monotonic allocator could be taken after the invocation of this method and then used to reset the monotonic allocator with preserving the memory used by this container.

Note: This method is not available (aka does not compile) with instantiations that specify template parameter TRecycling as Recycling::None.

Parameters

expectedSize The expected number of elements to be stored in the hash table.

Definition at line 501 of file list.hpp.

◆ Reset()

void Reset ( )

inline

Invokes Clear and in case of private recycling disposes all previously allocated recyclable instances of internal element type.

Hence, the invocation of this method with this value usually implies that the monotonic allocator used is reset as well.

As the life-cycle of the monotonic allocator(s) used for insertions is not under control of this object, it is the obligation of the caller to ensure that the monotonic allocator is kept in sync with this object.

Definition at line 481 of file list.hpp.

◆ Size()

integer Size ( ) const

inline

Evaluates the size of the list by traversing all elements.

Returns: The number of elements contained in this listed.

Definition at line 422 of file list.hpp.

Member Data Documentation

◆ allocator

MonoAllocator* allocator

protected

The allocator assigned.

Definition at line 79 of file list.hpp.

◆ list

lib::detail::BidiListHelper<Element> list

protected

The list.

Definition at line 82 of file list.hpp.

◆ recycler

detail::ListRecycler<T, TRecycling>::type recycler

protected

The recycler. Its type depends on template parameter TRecycling.

Definition at line 85 of file list.hpp.

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

Class Description

template<typename T, typename TRecycling> class aworx::lib::monomem::List< T, TRecycling >

Public Types

Inner Classes

Public Methods

Protected Types

Protected Fields

Protected Methods

Member Typedef Documentation

◆ ConstIterator

◆ ConstReverseIterator

◆ Element

◆ Iterator

◆ ReverseIterator

◆ TSharedRecycler

Constructor & Destructor Documentation

◆ List() [1/4]

◆ List() [2/4]

◆ List() [3/4]

◆ List() [4/4]

◆ ~List()

Member Function Documentation

◆ allocElement()

◆ Back() [1/2]

◆ Back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ Clear()

◆ crbegin()

◆ crend()

◆ ElementAt() [1/2]

◆ ElementAt() [2/2]

◆ Emplace()

◆ EmplaceBack()

◆ EmplaceFront()

◆ end() [1/2]

◆ end() [2/2]

◆ Erase() [1/2]

◆ Erase() [2/2]

◆ Front() [1/2]

◆ Front() [2/2]

◆ GetAllocator()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ IsEmpty()

◆ IsNotEmpty()

◆ PopBack()

◆ PopFront()

◆ PushBack() [1/2]

◆ PushBack() [2/2]

◆ PushFront() [1/2]

◆ PushFront() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ RecyclablesCount()

◆ rend() [1/2]

◆ rend() [2/2]

◆ ReserveRecyclables()

◆ Reset()

◆ Size()

Member Data Documentation

◆ allocator

◆ list

◆ recycler

template<typename T, typename TRecycling>
class aworx::lib::monomem::List< T, TRecycling >