BaseList< T, NODE, HEAD, ALLOCATOR > Class Template Reference

#include <baselist.h>

Inheritance diagram for BaseList< T, NODE, HEAD, ALLOCATOR >:

Detailed Description

template<typename T, typename NODE = BaseListNode<T>, typename HEAD = BaseListHead<T, NODE>, typename ALLOCATOR = DefaultAllocator>
class maxon::BaseList< T, NODE, HEAD, ALLOCATOR >

Basic list template (double linked).

The BaseList implements the same methods as the arrays. Nonetheless it is highly recommended to use the iterator based methods instead of those taking an index or count as parameter because the latter perform poorly due to the nature of a list.

If you want to control the list nodes themselves or their memory layout you can specify the list node type with NODE instead of using the default template BaseListNode<T> (the same goes for the list head HEAD).

Performance characteristics: Random access to array elements is linear with the index n: O(n) Append or Pop (erase the last) an element is constant: O(1) Insert or Erase an element is constant: O(1)

Note
: Do not rely on the characteristics to pick the right type of collection. Always profile to check real life performance!
Template Parameters
TType of the list element content.
NODEA node that encapsulates the element content T and holds the pointers to the next and previous element (see BaseListNode for details).
HEADA list head for nodes of type NODE.
ALLOCATORClass for memory allocation.

Classes

class  IteratorTemplate
 

Public Types

using ValueType = T
 
using AllocatorType = ALLOCATOR
 
using Iterator = IteratorTemplate< false >
 
using ConstIterator = IteratorTemplate< true >
 

Public Member Functions

 BaseList ()
 
 BaseList (const ALLOCATOR &a)
 
 ~BaseList ()
 
 BaseList (BaseList &&src)
 
 MAXON_OPERATOR_MOVE_ASSIGNMENT (BaseList)
 
void Reset ()
 
void Flush ()
 
MAXON_ATTRIBUTE_FORCE_INLINE Bool IsEmpty () const
 
MAXON_ATTRIBUTE_FORCE_INLINE Bool IsPopulated () const
 
Int GetCount () const
 
const T & operator[] (Int idx) const
 
T & operator[] (Int idx)
 
ResultRef< T > Append ()
 
ResultRef< T > Append (const T &x)
 
ResultRef< T > Append (T &&x)
 
MAXON_ATTRIBUTE_FORCE_INLINE ResultPtr< T > Append (const Block< const T > &values)
 
ResultPtr< T > Append (const std::initializer_list< T > &values)
 
T * AppendNode (NODE *node)
 
ResultRef< T > Insert (Int position)
 
ResultMemT< IteratorInsert (Iterator position)
 
ResultRef< T > Insert (Int position, const T &x)
 
ResultMemT< IteratorInsert (Iterator position, const T &x)
 
ResultRef< T > Insert (Int position, T &&x)
 
ResultMemT< IteratorInsert (Iterator position, T &&x)
 
T * InsertNode (Iterator position, NODE *node)
 
ResultPtr< T > Insert (Int position, const Block< const T > &values)
 
ResultPtr< T > Insert (Int position, const std::initializer_list< T > &values)
 
ResultMemT< IteratorInsert (Iterator position, const Block< const T > &values)
 
ResultMemT< IteratorInsert (Iterator position, const std::initializer_list< T > &values)
 
ResultPtr< T > Erase (Int position, Int eraseCnt=1)
 
Iterator Erase (Iterator position, Int eraseCnt)
 
Iterator Erase (Iterator position)
 
ResultMem SwapErase (Int position, Int eraseCnt=1)
 
Iterator SwapErase (Iterator position, Int eraseCnt=1)
 
template<Bool STRIDED>
MAXON_ATTRIBUTE_FORCE_INLINE Iterator GetBlock (Iterator position, Block< T, STRIDED > &block)
 
template<Bool STRIDED>
MAXON_ATTRIBUTE_FORCE_INLINE Iterator GetBlock (Iterator position, Block< const T, STRIDED > &block) const
 
template<Bool STRIDED>
MAXON_ATTRIBUTE_FORCE_INLINE Int GetBlock (Int position, Block< T, STRIDED > &block)
 
template<Bool STRIDED>
MAXON_ATTRIBUTE_FORCE_INLINE Int GetBlock (Int position, Block< const T, STRIDED > &block) const
 
ResultMem Resize (Int newCnt, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::DEFAULT)
 
Bool Pop (T *dst=nullptr)
 
Bool PopNode (NODE **dst)
 
Int GetIndex (const T &x) const
 
template<typename SourceArray >
Result< void > CopyFrom (const SourceArray &src)
 
void Swap (Iterator a, Iterator b)
 
Int GetMemorySize () const
 
ConstIterator Begin () const
 
Iterator Begin ()
 
ConstIterator End () const
 
Iterator End ()
 
ALLOCATOR & GetAllocator ()
 

Static Public Member Functions

static NODE * RemoveNode (Iterator position)
 
static NODE * RemoveNode (T *x)
 

Private Member Functions

 MAXON_DISALLOW_COPY_AND_ASSIGN (BaseList)
 
NODE * AllocNode ()
 
void DeleteNode (NODE *node)
 

Private Attributes

HEAD _head
 

Additional Inherited Members

- Static Protected Member Functions inherited from DefaultAllocator
static Int ComputeArraySize (Int currentSize, Int increment, Int minChunkSize)
 
static MAXON_ATTRIBUTE_FORCE_INLINE void * Alloc (Int32 s, MAXON_SOURCE_LOCATION_DECLARATION)
 
static MAXON_ATTRIBUTE_FORCE_INLINE void * Alloc (Int64 s, MAXON_SOURCE_LOCATION_DECLARATION)
 
static MAXON_ATTRIBUTE_FORCE_INLINE void * AllocClear (Int32 s, MAXON_SOURCE_LOCATION_DECLARATION)
 
static MAXON_ATTRIBUTE_FORCE_INLINE void * AllocClear (Int64 s, MAXON_SOURCE_LOCATION_DECLARATION)
 
static MAXON_ATTRIBUTE_FORCE_INLINE void * Realloc (void *p, Int32 n, MAXON_SOURCE_LOCATION_DECLARATION)
 
static MAXON_ATTRIBUTE_FORCE_INLINE void * Realloc (void *p, Int64 n, MAXON_SOURCE_LOCATION_DECLARATION)
 
template<typename T >
static MAXON_ATTRIBUTE_FORCE_INLINE void Free (T *&p)
 
static MAXON_ATTRIBUTE_FORCE_INLINE Bool IsCompatibleWithDefaultAllocator (void *)
 
- Static Protected Attributes inherited from DefaultAllocator
static const UInt ALIGNMENT
 
static const UInt ALIGNMENT_MASK
 
static const UInt MIN_ALIGNMENT_MASK
 

Member Typedef Documentation

◆ ValueType

using ValueType = T

◆ AllocatorType

using AllocatorType = ALLOCATOR

◆ Iterator

using Iterator = IteratorTemplate<false>

◆ ConstIterator

Constructor & Destructor Documentation

◆ BaseList() [1/3]

BaseList ( )

Default constructor. Creates an empty list.

◆ BaseList() [2/3]

BaseList ( const ALLOCATOR &  a)
explicit

This constructor has to be used if a list should use a custom allocator with member variables.

◆ ~BaseList()

~BaseList ( )

Destructs the list. If there are still elements they will be deleted.

◆ BaseList() [3/3]

BaseList ( BaseList< T, NODE, HEAD, ALLOCATOR > &&  src)

Move constructor.

Member Function Documentation

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( BaseList< T, NODE, HEAD, ALLOCATOR >  )
private

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT ( BaseList< T, NODE, HEAD, ALLOCATOR >  )

Move assignment operator.

◆ Reset()

void Reset ( )

Deletes all elements (calls destructors and frees memory).

◆ Flush()

void Flush ( )

Deletes all elements (same as Reset() for the BaseList).

◆ IsEmpty()

Checks if the list is empty. This is the same as GetCount() == 0

Returns
True if the list does not contain any elements.

◆ IsPopulated()

MAXON_ATTRIBUTE_FORCE_INLINE Bool IsPopulated ( ) const

Checks if the list contains anything. This is the same as GetCount() != 0

Returns
True if the list contains any elements.

◆ GetCount()

Int GetCount ( ) const

Gets the number of list elements. This has to iterate over all list elements. You may better want to use iterators directly!

Returns
Number of list elements.

◆ operator[]() [1/2]

const T& operator[] ( Int  idx) const

Array (subscript) operator for const objects. This is very ineffective on a list - better use iterators!

Parameters
[in]idxElement index (if it's out of bounds you will get an error in debug code only, otherwise it will crash).
Returns
List element.

◆ operator[]() [2/2]

T& operator[] ( Int  idx)

Array (subscript) operator for non-const objects. This is very ineffective on a list - better use iterators!

Parameters
[in]idxElement index (if it's out of bounds you will get an error in debug code only, otherwise it will crash).
Returns
List element.

◆ Append() [1/5]

ResultRef<T> Append ( )

Adds a new element at the end of the list.

Returns
Element reference or OutOfMemoryError if the allocation failed.

◆ Append() [2/5]

ResultRef<T> Append ( const T &  x)

Adds a new element at the end of the list and initializes it with a copy of x.

Parameters
[in]xValue to be copied.
Returns
Element reference or OutOfMemoryError if the allocation failed.

◆ Append() [3/5]

ResultRef<T> Append ( T &&  x)

Adds a new element at the end of the list and moves the content of x to it.

Parameters
[in]xValue to be moved.
Returns
Element reference or OutOfMemoryError if the allocation failed.

◆ Append() [4/5]

MAXON_ATTRIBUTE_FORCE_INLINE ResultPtr<T> Append ( const Block< const T > &  values)

Appends new elements at the end of the list.

Parameters
[in]valuesBlock with values to be copied. If the block points to nullptr, only its count is used, and you have to call the constructor of the new elements manually.
Returns
Element pointer or OutOfMemoryError if the allocation failed.

◆ Append() [5/5]

ResultPtr<T> Append ( const std::initializer_list< T > &  values)

Appends new elements at the end of the list.

Parameters
[in]valuesInitializer list with values to be copied.
Returns
Element pointer or OutOfMemoryError if the allocation failed.

◆ AppendNode()

T* AppendNode ( NODE *  node)

BaseList specific: Adds a new list node at the end of the list.

Parameters
[in]nodePointer to new list node (BaseList will take ownership of it).
Returns
Pointer to the appended node's data.

◆ Insert() [1/10]

ResultRef<T> Insert ( Int  position)

Inserts a new default element at index position. Use the iterator based Insert() below! This is compatible to the arrays but slow because Insert() has to iterate over the list to find the element corresponding to the index position.

Parameters
[in]positionInsert index.
Returns
Element reference or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [2/10]

ResultMemT<Iterator> Insert ( Iterator  position)

Inserts a new default element at iterator position.

Parameters
[in]positionInsert position.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position out of boundaries).

◆ Insert() [3/10]

ResultRef<T> Insert ( Int  position,
const T &  x 
)

Inserts a new element at index position and initializes it with a copy of x. Use the iterator based Insert() below! This is compatible to the arrays but slow because Insert() has to iterate over the list.

Parameters
[in]positionInsert index.
[in]xValue to be copied.
Returns
Element reference or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [4/10]

ResultMemT<Iterator> Insert ( Iterator  position,
const T &  x 
)

Inserts a new element at iterator position and initializes it with a copy of x.

Parameters
[in]positionInsert position.
[in]xValue to be copied.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [5/10]

ResultRef<T> Insert ( Int  position,
T &&  x 
)

Inserts a new element at index position and moves the content of x to it. Use the iterator based Insert() below! This is compatible to the arrays but slow because Insert() has to iterate over the list.

Parameters
[in]positionInsert index.
[in]xValue to be moved.
Returns
Element reference or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [6/10]

ResultMemT<Iterator> Insert ( Iterator  position,
T &&  x 
)

Inserts a new element at iterator position and moves the content of x to it.

Parameters
[in]positionInsert position.
[in]xValue to be moved.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ InsertNode()

T* InsertNode ( Iterator  position,
NODE *  node 
)

BaseList specific: Inserts a new list node at iterator position.

Parameters
[in]positionInsert position.
[in]nodePointer to new list node (BaseList will take ownership of it).
Returns
Pointer to the inserted node's data.

◆ Insert() [7/10]

ResultPtr<T> Insert ( Int  position,
const Block< const T > &  values 
)

Inserts new elements at index position. Use the iterator based Insert() below! This is compatible to the arrays but slow because Insert() has to iterate over the list.

Parameters
[in]positionInsert index.
[in]valuesBlock with values to be copied. If the block points to nullptr, only its count is used, and you have to call the constructor of the new elements manually.
Returns
Element pointer or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [8/10]

ResultPtr<T> Insert ( Int  position,
const std::initializer_list< T > &  values 
)

Inserts new elements at index position. Use the iterator based Insert() below! This is compatible to the arrays but slow because Insert() has to iterate over the list.

Parameters
[in]positionInsert index.
[in]valuesInitializer list with values to be copied.
Returns
Element pointer or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [9/10]

ResultMemT<Iterator> Insert ( Iterator  position,
const Block< const T > &  values 
)

Inserts new elements at iterator position (all elements from position on are moved by the the count of values).

Parameters
[in]positionInsert position.
[in]valuesBlock with values to be copied. If the block points to nullptr, only its count is used, and you have to call the constructor of the new elements manually.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [10/10]

ResultMemT<Iterator> Insert ( Iterator  position,
const std::initializer_list< T > &  values 
)

Inserts new elements at iterator position (all elements from position on are moved by the the count of values).

Parameters
[in]positionInsert position.
[in]valuesInitializer list with values to be copied.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Erase() [1/3]

ResultPtr<T> Erase ( Int  position,
Int  eraseCnt = 1 
)

Erases (removes and deletes) elements. Use the iterator based Erase() below! This is compatible to the arrays but slow because Erase() has to iterate over the list.

Parameters
[in]positionErase index (Erase() will fail if out of bounds and return nullptr).
[in]eraseCntNumber of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) a nullptr will be returned.
Returns
Pointer to the element that is now at position. If position equals the number of elements after Erase() a valid pointer is returned but you are not allowed to access it. OutOfMemoryError is only returned on failure (position was out of bounds).

◆ Erase() [2/3]

Iterator Erase ( Iterator  position,
Int  eraseCnt 
)

Erases (removes and deletes) elements.

Parameters
[in]positionErase position.
[in]eraseCntNumber of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) an invalid iterator will be returned.
Returns
Iterator for the element that is now at position (its operator Bool() will return false if something failed).

◆ Erase() [3/3]

Iterator Erase ( Iterator  position)

Erases (removes and deletes) an element.

Parameters
[in]positionErase position.
Returns
Iterator for the element that is now at position (its operator Bool() will return false if something failed).

◆ SwapErase() [1/2]

ResultMem SwapErase ( Int  position,
Int  eraseCnt = 1 
)

For a list this is exactly the same as Erase().

Parameters
[in]positionErase index (Erase() will fail if out of bounds and return nullptr).
[in]eraseCntNumber of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) false will be returned.
Returns
False if position was out of bounds.

◆ SwapErase() [2/2]

Iterator SwapErase ( Iterator  position,
Int  eraseCnt = 1 
)

For a list this is exactly the same as Erase().

Parameters
[in]positionErase position.
[in]eraseCntNumber of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) an invalid iterator will be returned.
Returns
Iterator for the element that is now at position (its operator Bool() will return false if something failed).

◆ GetBlock() [1/4]

MAXON_ATTRIBUTE_FORCE_INLINE Iterator GetBlock ( Iterator  position,
Block< T, STRIDED > &  block 
)

Determines a contiguous block of array elements which contains the element at position. For a BaseArray, this yields the whole array as a block.

Parameters
[in]positionElement position.
[out]blockBlock which contains the element at position.
Returns
Start iterator of the block. The requested element can be found within the block at index position - start iterator.

◆ GetBlock() [2/4]

MAXON_ATTRIBUTE_FORCE_INLINE Iterator GetBlock ( Iterator  position,
Block< const T, STRIDED > &  block 
) const

Determines a contiguous block of array elements which contains the element at position. For a BaseArray, this yields the whole array as a block.

Parameters
[in]positionElement position.
[out]blockBlock which contains the element at position.
Returns
Start iterator of the block. The requested element can be found within the block at index position - start iterator.

◆ GetBlock() [3/4]

MAXON_ATTRIBUTE_FORCE_INLINE Int GetBlock ( Int  position,
Block< T, STRIDED > &  block 
)

Determines a contiguous block of array elements which contains the element at position. For a BaseArray, this yields the whole array as a block.

Parameters
[in]positionElement index.
[out]blockBlock which contains the element at position.
Returns
Start index of the block. The requested element can be found within the block at position - start index.

◆ GetBlock() [4/4]

MAXON_ATTRIBUTE_FORCE_INLINE Int GetBlock ( Int  position,
Block< const T, STRIDED > &  block 
) const

Determines a contiguous block of array elements which contains the element at position. For a BaseArray, this yields the whole array as a block.

Parameters
[in]positionElement index.
[out]blockBlock which contains the element at position.
Returns
Start index of the block. The requested element can be found within the block at position - start index.

◆ Resize()

Resizes the list to contain newCnt elements. If newCnt is smaller than GetCount() all extra elements are being deleted. If it is greater the list is expanded and the default constructor is called for new elements.

Parameters
[in]newCntNew list size.
[in]resizeFlagsSee COLLECTION_RESIZE_FLAGS (flags other than ON_GROW_UNINITIALIZED/POD_UNINITIALIZED result in default behaviour).
Returns
False if allocation failed.

◆ Pop()

Bool Pop ( T *  dst = nullptr)

Deletes the last element.

Parameters
[out]dstNullptr or pointer to return value.
Returns
True if there was at least one element.

◆ PopNode()

Bool PopNode ( NODE **  dst)

BaseList specific: Removes the last node and returns the pointer to it.

Parameters
[out]dstUsed to return pointer to the last node (must not be null), the caller will take ownership of the node.
Returns
True if successful.

◆ GetIndex()

Int GetIndex ( const T &  x) const

Gets the index of element. The element must be part of the list, otherwise (e.g. if x is a copy of a list element) InvalidArrayIndex will be returned. This is compatible to the arrays but slow because GetIndex() has to iterate over the list.

Returns
Index of element or InvalidArrayIndex (not element of this).

◆ RemoveNode() [1/2]

static NODE* RemoveNode ( Iterator  position)
static

BaseList specific: Removes the node and returns a pointer to it.

Parameters
[in]positionPosition of the element to be removed.
Returns
Node pointer or null, the caller will take ownership of it.

◆ RemoveNode() [2/2]

static NODE* RemoveNode ( T *  x)
static

BaseList specific: Removes the node and returns a pointer to it.

Parameters
[in]xThe element to be removed.
Returns
Node pointer or null, the caller will take ownership of it.

◆ CopyFrom()

Result<void> CopyFrom ( const SourceArray &  src)

Copies an array or list.

Parameters
[in]srcSource list or array.
Returns
OK on success.

◆ Swap()

void Swap ( Iterator  a,
Iterator  b 
)

Swaps elements a and b (just changes the pointers, more efficient than global Swap(list[a], list[b]).

Parameters
[in]aPosition of element to be swapped.
[in]bPosition of element to be swapped.

◆ GetMemorySize()

Int GetMemorySize ( ) const

Calculates the memory usage for this array. The array element class must have a public member GetMemorySize that returns an element's size.

Returns
Memory size in bytes.

◆ Begin() [1/2]

ConstIterator Begin ( ) const

Gets an iterator for the first element. When you modify the list Begin() will change, it is not a constant value.

Returns
Iterator for the first element (equal to End() if the list is empty).

◆ Begin() [2/2]

Iterator Begin ( )

Gets an iterator for the first element. When you modify the list Begin() will change, it is not a constant value.

Returns
Iterator for the first element (equal to End() if the list is empty).

◆ End() [1/2]

ConstIterator End ( ) const

Gets an iterator for the end (End() - 1 is the last element if the list is not empty). For the BaseList End() is in fact a constant value, it won't change even if you insert or remove elements. That's different from all arrays (where End() will change when you modify the array).

Returns
Iterator for the list end (this is behind the last element).

◆ End() [2/2]

Iterator End ( )

Gets an iterator for the end (End() - 1 is the last element if the list is not empty). For the BaseList End() is in fact a constant value, it won't change even if you insert or remove elements. That's different from all arrays (where End() will change when you modify the array).

Returns
Iterator for the list end (this is behind the last element).

◆ GetAllocator()

ALLOCATOR& GetAllocator ( )

Returns the allocator as reference. Typically this is used by the arrays and other base classes when multiple of them are "stiched" together as one big object all shall use one main allocator.

Returns
Allocator reference.

◆ AllocNode()

NODE* AllocNode ( )
private

◆ DeleteNode()

void DeleteNode ( NODE *  node)
private

Member Data Documentation

◆ _head

HEAD _head
private