Detailed Description

template<class T>
class frechet::data::LinkedList< T >

An intrusive double-linked list, similar to boost::intrusive.

Link references are stored inside the element objects.

Simplifies a few things:

small memory footprint (we don't need element container objects)
no iterators are needed: each element contains the information for iterating
concatenating two lists is easy

Major restrictions apply: each element can only be part of one list. Shallow copies are not allowed. The list takes ownership of elements and deletes them on removal.

The implementation is not thread-safe.

Iterator methods (first,next,prev,last) are type-safe. but insertions are not type-safe (contrary to boost::intrusive classes).

Optionally, LinkedList can be circular, i.e. the last element is directly linked to the first element. This property can be modified an run-time.

Simply use T* for an iterator:

for(T* i = list.first(); i; i = i->next())

...

Modifications to the underlying list do not break the iterator (except when deleting the current object).

Concurrently iterating and deleting should be done like this:

for(T* i = list.first(); i; ) {
    if (...)
        i = list.remove(i);
    else
        i = i->next();
}

Template Parameters

T	element type; must derive from BLinkedListElement

Author: Peter Schäfer

Definition at line 252 of file linkedlist.h.

#include <linkedlist.h>

Inherits frechet::data::BLinkedList.

Public Member Functions
	LinkedList ()
	empty constructor; creates an empty list More...

	LinkedList (LinkedList &&that)
	move constructor; takes ownership of another list More...

template<typename Cloner >
	LinkedList (const LinkedList &that, Cloner cloner)
	deep copy constructor More...

LinkedList &	operator= (LinkedList &&that)
	move assigment operator More...

T *	first () const

T *	last () const

T *	remove (T *el)

T *	operator[] (int i) const
	positional lookup (note: O(n), use with care) More...

void	swap (LinkedList< T > &that)
	exchange all elements with another list, taking ownership of the new elements More...

Public Member Functions inherited from frechet::data::BLinkedList
	BLinkedList (bool circular=false)
	default constructor; creates an empty list More...

	BLinkedList (BLinkedList &&that)
	move constructor More...

	~BLinkedList ()
	destructor; releases all element objects More...

bool	empty () const

int	size () const

bool	circular () const

void	setCircular (bool)
	update the circularity property of this list More...

BLinkedList &	operator= (BLinkedList &&that)
	move assigment operator More...

void	insert_first (BLinkedListElement *el)
	insert a new element at the beginning of the list; the list takes ownership of the element. Do not delete it yourself. More...

void	insert_last (BLinkedListElement *el)
	insert a new element at the end of the list; the list takes ownership of the element. Do not delete it yourself. More...

void	insert_before (BLinkedListElement el, BLinkedListElement before)
	insert a new element before a certain element of the list; the list takes ownership of the element. Do not delete it yourself. More...

void	insert_after (BLinkedListElement el, BLinkedListElement after)
	insert a new element after a certain element of the list; the list takes ownership of the element. Do not delete it yourself. More...

BLinkedListElement *	remove (BLinkedListElement *el)
	remove an element from the list and release its memory More...

void	clear ()
	release all elements More...

int	concat (BLinkedList &that)
	append all elements of another list, taking ownership of the new elements More...

int	swap (BLinkedList &that)
	exchange all elements with another list, taking ownership of the new elements More...

Private Member Functions
	BOOST_STATIC_ASSERT ((boost::is_base_of< BLinkedListElement, T >::value))

Additional Inherited Members
Protected Member Functions inherited from frechet::data::BLinkedList
BLinkedListElement *	operator[] (int i) const
	positional lookup (note: O(n), use with care) More...

Protected Attributes inherited from frechet::data::BLinkedList
BLinkedListElement *	_first
	the first element in the list (or nullptr) More...

BLinkedListElement *	_last
	the last element in the list (or nullptr) More...

int	_size
	current number of elements More...

bool	_circular
	if true, this is a circular list, i.e. the last element is connected to the first element More...

Constructor & Destructor Documentation

◆ LinkedList() [1/3]

template<class T>

frechet::data::LinkedList< T >::LinkedList ( )

inline

empty constructor; creates an empty list

Definition at line 256 of file linkedlist.h.

◆ LinkedList() [2/3]

template<class T>

frechet::data::LinkedList< T >::LinkedList ( LinkedList< T > && that )

inline

move constructor; takes ownership of another list

Parameters

that	list to move elements from; will be empty on return

Definition at line 259 of file linkedlist.h.

◆ LinkedList() [3/3]

template<class T>

template<typename Cloner >

frechet::data::LinkedList< T >::LinkedList	(	const LinkedList< T > &	that,
		Cloner	cloner
	)

inline

deep copy constructor

Parameters

that	list to copy from
cloner	a functor that creates deep copies of elements

Template Parameters

Cloner a functor class that creates deep copies of elements

Definition at line 268 of file linkedlist.h.

Member Function Documentation

◆ BOOST_STATIC_ASSERT()

template<class T>

frechet::data::LinkedList< T >::BOOST_STATIC_ASSERT ( (boost::is_base_of< BLinkedListElement, T >::value) )

private

◆ first()

template<class T>

T* frechet::data::LinkedList< T >::first ( ) const

inline

Returns: first element of the list (or nullptr if empty)

Definition at line 292 of file linkedlist.h.

◆ last()

template<class T>

T* frechet::data::LinkedList< T >::last ( ) const

inline

Returns: last element of the list (or nullptr if empty)

Definition at line 296 of file linkedlist.h.

◆ operator=()

template<class T>

LinkedList& frechet::data::LinkedList< T >::operator= ( LinkedList< T > && that )

inline

move assigment operator

Note that there is no copy assigment operator because we must prevent shallow copies; double-linked elements must not be part of two separate lists.

Parameters

that	list to move elements from; will be empty on return

Returns: this list, containing the elements from 'that'

Definition at line 284 of file linkedlist.h.

◆ operator[]()

template<class T>

T* frechet::data::LinkedList< T >::operator[] ( int i ) const

inline

positional lookup (note: O(n), use with care)

Parameters

i	index in list

Returns: the i-th element, or nullptr

Definition at line 305 of file linkedlist.h.

◆ remove()

template<class T>

T* frechet::data::LinkedList< T >::remove ( T * el )

inline

Definition at line 298 of file linkedlist.h.

◆ swap()

template<class T>

void frechet::data::LinkedList< T >::swap ( LinkedList< T > & that )

inline

exchange all elements with another list, taking ownership of the new elements

Parameters

that	list to move elements from

Returns: size of the list after swap

Definition at line 312 of file linkedlist.h.

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

include/data/linkedlist.h

Detailed Description

template<class T> class frechet::data::LinkedList< T >

Public Member Functions

Private Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ LinkedList() [1/3]

◆ LinkedList() [2/3]

◆ LinkedList() [3/3]

Member Function Documentation

◆ BOOST_STATIC_ASSERT()

◆ first()

◆ last()

◆ operator=()

◆ operator[]()

◆ remove()

◆ swap()

template<class T>
class frechet::data::LinkedList< T >