Description:

template<typename T, typename TRecycling>
class alib::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 69 of file list.hpp.

#include <list.hpp>

Collaboration diagram for List< T, TRecycling >:

[legend]

Inner Type Index:
struct	TIterator

Public Type Index:
using	ConstIterator = TIterator<const T>

using	ConstReverseIterator = std::reverse_iterator<ConstIterator>

using	Iterator = TIterator< T>

using	ReverseIterator = std::reverse_iterator<Iterator>

using	TSharedRecycler = lang::SidiListHelper<Element>

Public Method Index:
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)

Element 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 ()

Type Definition Details:

◆ ConstIterator

template<typename T , typename TRecycling >

using ConstIterator = TIterator<const T>

The constant iterator exposed by this container.

Definition at line 244 of file list.hpp.

◆ ConstReverseIterator

template<typename T , typename TRecycling >

using ConstReverseIterator = std::reverse_iterator<ConstIterator>

The constant iterator exposed by this container.

Definition at line 250 of file list.hpp.

◆ Element

template<typename T , typename TRecycling >

using Element = detail::ListElement<T>

protected

The list element type.

Definition at line 76 of file list.hpp.

◆ Iterator

template<typename T , typename TRecycling >

using Iterator = TIterator< T>

The mutable iterator exposed by this container.

Definition at line 247 of file list.hpp.

◆ ReverseIterator

template<typename T , typename TRecycling >

using ReverseIterator = std::reverse_iterator<Iterator>

The mutable iterator exposed by this container.

Definition at line 253 of file list.hpp.

◆ TSharedRecycler

template<typename T , typename TRecycling >

using TSharedRecycler = lang::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.

Field Details:

◆ allocator

template<typename T , typename TRecycling >

MonoAllocator* allocator

protected

The allocator assigned.

Definition at line 79 of file list.hpp.

◆ list

template<typename T , typename TRecycling >

lang::BidiListHelper<Element> list

protected

The list.

Definition at line 82 of file list.hpp.

◆ recycler

template<typename T , typename TRecycling >

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

protected

The recycler. Its type depends on template parameter TRecycling .

Definition at line 85 of file list.hpp.

Constructor(s) / Destructor Details::

◆ List() [1/4]

template<typename T , typename TRecycling >

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 317 of file list.hpp.

Here is the call graph for this function:

◆ List() [2/4]

template<typename T , typename TRecycling >

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 331 of file list.hpp.

◆ List() [3/4]

template<typename T , typename TRecycling >

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 347 of file list.hpp.

◆ List() [4/4]

template<typename T , typename TRecycling >

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 365 of file list.hpp.

◆ ~List()

template<typename T , typename TRecycling >

~List ( )

inline

Destructor. Invokes Clear.

Definition at line 374 of file list.hpp.

Here is the call graph for this function:

Method Details:

◆ allocElement()

template<typename T , typename TRecycling >

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.

Here is the call graph for this function:

◆ Back() [1/2]

template<typename T , typename TRecycling >

T & Back ( )

inline

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

Returns: A mutable reference to T .

Definition at line 588 of file list.hpp.

◆ Back() [2/2]

template<typename T , typename TRecycling >

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 599 of file list.hpp.

◆ begin() [1/2]

template<typename T , typename TRecycling >

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 260 of file list.hpp.

◆ begin() [2/2]

template<typename T , typename TRecycling >

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 268 of file list.hpp.

◆ cbegin()

template<typename T , typename TRecycling >

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 276 of file list.hpp.

◆ cend()

template<typename T , typename TRecycling >

ConstIterator cend ( ) const

inline

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

Returns: The end of this list.

Definition at line 280 of file list.hpp.

◆ Clear()

template<typename T , typename TRecycling >

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 454 of file list.hpp.

◆ crbegin()

template<typename T , typename TRecycling >

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 300 of file list.hpp.

Here is the call graph for this function:

◆ crend()

template<typename T , typename TRecycling >

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 304 of file list.hpp.

Here is the call graph for this function:

◆ ElementAt() [1/2]

template<typename T , typename TRecycling >

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 526 of file list.hpp.

Here is the call graph for this function:

◆ ElementAt() [2/2]

template<typename T , typename TRecycling >

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 547 of file list.hpp.

Here is the call graph for this function:

◆ Emplace()

template<typename T , typename TRecycling >

template<typename... TArgs>

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 702 of file list.hpp.

Here is the call graph for this function:

◆ EmplaceBack()

template<typename T , typename TRecycling >

template<typename... TArgs>

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 718 of file list.hpp.

Here is the call graph for this function:

◆ EmplaceFront()

template<typename T , typename TRecycling >

template<typename... TArgs>

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 734 of file list.hpp.

Here is the call graph for this function:

◆ end() [1/2]

template<typename T , typename TRecycling >

Iterator end ( )

inline

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

Returns: The end of this list.

Definition at line 264 of file list.hpp.

◆ end() [2/2]

template<typename T , typename TRecycling >

ConstIterator end ( ) const

inline

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

Returns: The end of this list.

Definition at line 272 of file list.hpp.

◆ Erase() [1/2]

template<typename T , typename TRecycling >

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 779 of file list.hpp.

Here is the call graph for this function:

◆ Erase() [2/2]

template<typename T , typename TRecycling >

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 756 of file list.hpp.

Here is the call graph for this function:

◆ Front() [1/2]

template<typename T , typename TRecycling >

T & Front ( )

inline

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

Returns: A mutable reference to T .

Definition at line 565 of file list.hpp.

◆ Front() [2/2]

template<typename T , typename TRecycling >

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 577 of file list.hpp.

◆ GetAllocator()

template<typename T , typename TRecycling >

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 391 of file list.hpp.

◆ Insert() [1/2]

template<typename T , typename TRecycling >

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 615 of file list.hpp.

Here is the call graph for this function:

◆ Insert() [2/2]

template<typename T , typename TRecycling >

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 630 of file list.hpp.

Here is the call graph for this function:

◆ IsEmpty()

template<typename T , typename TRecycling >

bool IsEmpty ( ) const

inline

Tests this container for emptiness.

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

Definition at line 430 of file list.hpp.

◆ IsNotEmpty()

template<typename T , typename TRecycling >

bool IsNotEmpty ( ) const

inline

Tests this container for emptiness.

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

Definition at line 439 of file list.hpp.

◆ PopBack()

template<typename T , typename TRecycling >

void PopBack ( )

inline

Removes the last element.

Definition at line 816 of file list.hpp.

Here is the call graph for this function:

◆ PopFront()

template<typename T , typename TRecycling >

void PopFront ( )

inline

Removes the first element.

Definition at line 805 of file list.hpp.

Here is the call graph for this function:

◆ PushBack() [1/2]

template<typename T , typename TRecycling >

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 644 of file list.hpp.

Here is the call graph for this function:

◆ PushBack() [2/2]

template<typename T , typename TRecycling >

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 658 of file list.hpp.

Here is the call graph for this function:

◆ PushFront() [1/2]

template<typename T , typename TRecycling >

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 672 of file list.hpp.

Here is the call graph for this function:

◆ PushFront() [2/2]

template<typename T , typename TRecycling >

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 685 of file list.hpp.

Here is the call graph for this function:

◆ rbegin() [1/2]

template<typename T , typename TRecycling >

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 284 of file list.hpp.

Here is the call graph for this function:

◆ rbegin() [2/2]

template<typename T , typename TRecycling >

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 292 of file list.hpp.

Here is the call graph for this function:

◆ RecyclablesCount()

template<typename T , typename TRecycling >

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 408 of file list.hpp.

◆ rend() [1/2]

template<typename T , typename TRecycling >

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 288 of file list.hpp.

Here is the call graph for this function:

◆ rend() [2/2]

template<typename T , typename TRecycling >

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 296 of file list.hpp.

Here is the call graph for this function:

◆ ReserveRecyclables()

template<typename T , typename TRecycling >

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 500 of file list.hpp.

Here is the call graph for this function:

◆ Reset()

template<typename T , typename TRecycling >

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 480 of file list.hpp.

Here is the call graph for this function:

◆ Size()

template<typename T , typename TRecycling >

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 421 of file list.hpp.

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

Description:

Inner Type Index:

Public Type Index:

Public Method Index:

Type Definition Details:

◆ ConstIterator

◆ ConstReverseIterator

◆ Element

◆ Iterator

◆ ReverseIterator

◆ TSharedRecycler

Field Details:

◆ allocator

◆ list

◆ recycler

Constructor(s) / Destructor Details::

◆ List() [1/4]

◆ List() [2/4]

◆ List() [3/4]

◆ List() [4/4]

◆ ~List()

Method Details:

◆ 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()