Intrusive doubly linked list. More...

Collaboration diagram for beast::List< T, Tag >:

[legend]

Public Types
using	Node = typename detail::ListNode< T, Tag >

using	value_type = T

using	pointer = value_type *

using	reference = value_type &

using	const_pointer = value_type const *

using	const_reference = value_type const &

using	size_type = std::size_t

using	difference_type = std::ptrdiff_t

using	iterator = detail::ListIterator< Node >

using	const_iterator = detail::ListIterator< Node const >

Public Member Functions
	List ()
	Create an empty list. More...

	List (List const &)=delete

List &	operator= (List const &)=delete

bool	empty () const noexcept
	Determine if the list is empty. More...

size_type	size () const noexcept
	Returns the number of elements in the list. More...

reference	front () noexcept
	Obtain a reference to the first element. More...

const_reference	front () const noexcept
	Obtain a const reference to the first element. More...

reference	back () noexcept
	Obtain a reference to the last element. More...

const_reference	back () const noexcept
	Obtain a const reference to the last element. More...

iterator	begin () noexcept
	Obtain an iterator to the beginning of the list. More...

const_iterator	begin () const noexcept
	Obtain a const iterator to the beginning of the list. More...

const_iterator	cbegin () const noexcept
	Obtain a const iterator to the beginning of the list. More...

iterator	end () noexcept
	Obtain a iterator to the end of the list. More...

const_iterator	end () const noexcept
	Obtain a const iterator to the end of the list. More...

const_iterator	cend () const noexcept
	Obtain a const iterator to the end of the list. More...

void	clear () noexcept
	Clear the list. More...

iterator	insert (iterator pos, T &element) noexcept
	Insert an element. More...

void	insert (iterator pos, List &other) noexcept
	Insert another list into this one. More...

iterator	erase (iterator pos) noexcept
	Remove an element. More...

iterator	push_front (T &element) noexcept
	Insert an element at the beginning of the list. More...

T &	pop_front () noexcept
	Remove the element at the beginning of the list. More...

iterator	push_back (T &element) noexcept
	Append an element at the end of the list. More...

T &	pop_back () noexcept
	Remove the element at the end of the list. More...

void	swap (List &other) noexcept
	Swap contents with another list. More...

iterator	prepend (List &list) noexcept
	Insert another list at the beginning of this list. More...

iterator	append (List &list) noexcept
	Append another list at the end of this list. More...

iterator	iterator_to (T &element) const noexcept
	Obtain an iterator from an element. More...

const_iterator	const_iterator_to (T const &element) const noexcept
	Obtain a const iterator from an element. More...

Private Member Functions
reference	element_from (Node *node) noexcept

const_reference	element_from (Node const *node) const noexcept

Private Attributes
size_type	m_size

Node	m_head

Node	m_tail

Detailed Description

template<typename T, typename Tag = void>
class beast::List< T, Tag >

Intrusive doubly linked list.

This intrusive List is a container similar in operation to std::list in the Standard Template Library (STL). Like all intrusive containers, List requires you to first derive your class from List<>::Node:

struct Object : List <Object>::Node
{
    explicit Object (int value) : m_value (value)
    {
    }
 
    int m_value;
};

Now we define the list, and add a couple of items.

List <Object> list;
 
list.push_back (* (new Object (1)));
list.push_back (* (new Object (2)));

For compatibility with the standard containers, push_back() expects a reference to the object. Unlike the standard container, however, push_back() places the actual object in the list and not a copy-constructed duplicate.

Iterating over the list follows the same idiom as the STL:

for (List <Object>::iterator iter = list.begin(); iter != list.end; ++iter)

std::cout << iter->m_value;

You can even use BOOST_FOREACH, or range based for loops:

BOOST_FOREACH (Object& object, list)  // boost only
    std::cout << object.m_value;
 
for (Object& object : list)           // C++11 only
    std::cout << object.m_value;

Because List is mostly STL compliant, it can be passed into STL algorithms: e.g. std::for_each() or std::find_first_of().

In general, objects placed into a List should be dynamically allocated although this cannot be enforced at compile time. Since the caller provides the storage for the object, the caller is also responsible for deleting the object. An object still exists after being removed from a List, until the caller deletes it. This means an element can be moved from one List to another with practically no overhead.

Unlike the standard containers, an object may only exist in one list at a time, unless special preparations are made. The Tag template parameter is used to distinguish between different list types for the same object, allowing the object to exist in more than one list simultaneously.

For example, consider an actor system where a global list of actors is maintained, so that they can each be periodically receive processing time. We wish to also maintain a list of the subset of actors that require a domain-dependent update. To achieve this, we declare two tags, the associated list types, and the list element thusly:

struct Actor;         // Forward declaration required
 
struct ProcessTag { };
struct UpdateTag { };
 
using ProcessList = List <Actor, ProcessTag>;
using UpdateList = List <Actor, UpdateTag>;
 
// Derive from both node types so we can be in each list at once.
//
struct Actor : ProcessList::Node, UpdateList::Node
{
    bool process ();    // returns true if we need an update
    void update ();
};

Template Parameters

T	The base type of element which the list will store pointers to.
Tag	An optional unique type name used to distinguish lists and nodes, when the object can exist in multiple lists simultaneously.

Definition at line 29 of file List.h.

Member Typedef Documentation

◆ Node

template<typename T , typename Tag = void>

using beast::List< T, Tag >::Node = typename detail::ListNode<T, Tag>

Definition at line 282 of file List.h.

◆ value_type

template<typename T , typename Tag = void>

using beast::List< T, Tag >::value_type = T

Definition at line 284 of file List.h.

◆ pointer

template<typename T , typename Tag = void>

using beast::List< T, Tag >::pointer = value_type*

Definition at line 285 of file List.h.

◆ reference

template<typename T , typename Tag = void>

using beast::List< T, Tag >::reference = value_type&

Definition at line 286 of file List.h.

◆ const_pointer

template<typename T , typename Tag = void>

using beast::List< T, Tag >::const_pointer = value_type const*

Definition at line 287 of file List.h.

◆ const_reference

template<typename T , typename Tag = void>

using beast::List< T, Tag >::const_reference = value_type const&

Definition at line 288 of file List.h.

◆ size_type

template<typename T , typename Tag = void>

using beast::List< T, Tag >::size_type = std::size_t

Definition at line 289 of file List.h.

◆ difference_type

template<typename T , typename Tag = void>

using beast::List< T, Tag >::difference_type = std::ptrdiff_t

Definition at line 290 of file List.h.

◆ iterator

template<typename T , typename Tag = void>

using beast::List< T, Tag >::iterator = detail::ListIterator<Node>

Definition at line 292 of file List.h.

◆ const_iterator

template<typename T , typename Tag = void>

using beast::List< T, Tag >::const_iterator = detail::ListIterator<Node const>

Definition at line 293 of file List.h.

Constructor & Destructor Documentation

◆ List() [1/2]

template<typename T , typename Tag = void>

beast::List< T, Tag >::List ( )

Create an empty list.

Definition at line 296 of file List.h.

◆ List() [2/2]

template<typename T , typename Tag = void>

beast::List< T, Tag >::List ( List< T, Tag > const & )

delete

Member Function Documentation

◆ operator=()

template<typename T , typename Tag = void>

List& beast::List< T, Tag >::operator= ( List< T, Tag > const & )

delete

◆ empty()

template<typename T , typename Tag = void>

bool beast::List< T, Tag >::empty ( ) const

noexcept

Determine if the list is empty.

Returns: true if the list is empty.

Definition at line 311 of file List.h.

◆ size()

template<typename T , typename Tag = void>

size_type beast::List< T, Tag >::size ( ) const

noexcept

Returns the number of elements in the list.

Definition at line 318 of file List.h.

◆ front() [1/2]

template<typename T , typename Tag = void>

reference beast::List< T, Tag >::front ( )

noexcept

Obtain a reference to the first element.

Invariant: The list may not be empty.

Returns: A reference to the first element.

Definition at line 328 of file List.h.

◆ front() [2/2]

template<typename T , typename Tag = void>

const_reference beast::List< T, Tag >::front ( ) const

noexcept

Obtain a const reference to the first element.

Invariant: The list may not be empty.

Returns: A const reference to the first element.

Definition at line 338 of file List.h.

◆ back() [1/2]

template<typename T , typename Tag = void>

reference beast::List< T, Tag >::back ( )

noexcept

Obtain a reference to the last element.

Invariant: The list may not be empty.

Returns: A reference to the last element.

Definition at line 348 of file List.h.

◆ back() [2/2]

template<typename T , typename Tag = void>

const_reference beast::List< T, Tag >::back ( ) const

noexcept

Obtain a const reference to the last element.

Invariant: The list may not be empty.

Returns: A const reference to the last element.

Definition at line 358 of file List.h.

◆ begin() [1/2]

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::begin ( )

noexcept

Obtain an iterator to the beginning of the list.

Returns: An iterator pointing to the beginning of the list.

Definition at line 367 of file List.h.

◆ begin() [2/2]

template<typename T , typename Tag = void>

const_iterator beast::List< T, Tag >::begin ( ) const

noexcept

Obtain a const iterator to the beginning of the list.

Returns: A const iterator pointing to the beginning of the list.

Definition at line 376 of file List.h.

◆ cbegin()

template<typename T , typename Tag = void>

const_iterator beast::List< T, Tag >::cbegin ( ) const

noexcept

Obtain a const iterator to the beginning of the list.

Returns: A const iterator pointing to the beginning of the list.

Definition at line 385 of file List.h.

◆ end() [1/2]

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::end ( )

noexcept

Obtain a iterator to the end of the list.

Returns: An iterator pointing to the end of the list.

Definition at line 394 of file List.h.

◆ end() [2/2]

template<typename T , typename Tag = void>

const_iterator beast::List< T, Tag >::end ( ) const

noexcept

Obtain a const iterator to the end of the list.

Returns: A constiterator pointing to the end of the list.

Definition at line 403 of file List.h.

◆ cend()

template<typename T , typename Tag = void>

const_iterator beast::List< T, Tag >::cend ( ) const

noexcept

Obtain a const iterator to the end of the list.

Returns: A constiterator pointing to the end of the list.

Definition at line 412 of file List.h.

◆ clear()

template<typename T , typename Tag = void>

void beast::List< T, Tag >::clear ( )

noexcept

Clear the list.

Note: This does not free the elements.

Definition at line 421 of file List.h.

◆ insert() [1/2]

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::insert	(	iterator	pos,
		T &	element
	)

noexcept

Insert an element.

Invariant: The element must not already be in the list.

Parameters

pos	The location to insert after.
element	The element to insert.

Returns: An iterator pointing to the newly inserted element.

Definition at line 435 of file List.h.

◆ insert() [2/2]

template<typename T , typename Tag = void>

void beast::List< T, Tag >::insert	(	iterator	pos,
		List< T, Tag > &	other
	)

noexcept

Insert another list into this one.

The other list is cleared.

Parameters

pos	The location to insert after.
other	The list to insert.

Definition at line 452 of file List.h.

◆ erase()

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::erase ( iterator pos )

noexcept

Remove an element.

Invariant: The element must exist in the list.

Parameters

pos	An iterator pointing to the element to remove.

Returns: An iterator pointing to the next element after the one removed.

Definition at line 472 of file List.h.

◆ push_front()

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::push_front ( T & element )

noexcept

Insert an element at the beginning of the list.

Invariant: The element must not exist in the list.

Parameters

element The element to insert.

Definition at line 487 of file List.h.

◆ pop_front()

template<typename T , typename Tag = void>

T& beast::List< T, Tag >::pop_front ( )

noexcept

Remove the element at the beginning of the list.

Invariant: The list must not be empty.

Returns: A reference to the popped element.

Definition at line 497 of file List.h.

◆ push_back()

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::push_back ( T & element )

noexcept

Append an element at the end of the list.

Invariant: The element must not exist in the list.

Parameters

element The element to append.

Definition at line 509 of file List.h.

◆ pop_back()

template<typename T , typename Tag = void>

T& beast::List< T, Tag >::pop_back ( )

noexcept

Remove the element at the end of the list.

Invariant: The list must not be empty.

Returns: A reference to the popped element.

Definition at line 519 of file List.h.

◆ swap()

template<typename T , typename Tag = void>

void beast::List< T, Tag >::swap ( List< T, Tag > & other )

noexcept

Swap contents with another list.

Definition at line 528 of file List.h.

◆ prepend()

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::prepend ( List< T, Tag > & list )

noexcept

Insert another list at the beginning of this list.

The other list is cleared.

Parameters

list	The other list to insert.

Definition at line 541 of file List.h.

◆ append()

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::append ( List< T, Tag > & list )

noexcept

Append another list at the end of this list.

The other list is cleared.

Parameters

list	the other list to append.

Definition at line 551 of file List.h.

◆ iterator_to()

template<typename T , typename Tag = void>

iterator beast::List< T, Tag >::iterator_to ( T & element ) const

noexcept

Obtain an iterator from an element.

Invariant: The element must exist in the list.

Parameters

element The element to obtain an iterator for.

Returns: An iterator to the element.

Definition at line 562 of file List.h.

◆ const_iterator_to()

template<typename T , typename Tag = void>

const_iterator beast::List< T, Tag >::const_iterator_to ( T const & element ) const

noexcept

Obtain a const iterator from an element.

Invariant: The element must exist in the list.

Parameters

element The element to obtain an iterator for.

Returns: A const iterator to the element.

Definition at line 573 of file List.h.

◆ element_from() [1/2]

template<typename T , typename Tag = void>

reference beast::List< T, Tag >::element_from ( Node * node )

privatenoexcept

Definition at line 580 of file List.h.

◆ element_from() [2/2]

template<typename T , typename Tag = void>

const_reference beast::List< T, Tag >::element_from ( Node const * node ) const

privatenoexcept

Definition at line 586 of file List.h.

Member Data Documentation

◆ m_size

template<typename T , typename Tag = void>

size_type beast::List< T, Tag >::m_size

private

Definition at line 592 of file List.h.

◆ m_head

template<typename T , typename Tag = void>

Node beast::List< T, Tag >::m_head

private

Definition at line 593 of file List.h.

◆ m_tail

template<typename T , typename Tag = void>

Node beast::List< T, Tag >::m_tail

private

Definition at line 594 of file List.h.

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename T, typename Tag = void> class beast::List< T, Tag >

Member Typedef Documentation

◆ Node

◆ value_type

◆ pointer

◆ reference

◆ const_pointer

◆ const_reference

◆ size_type

◆ difference_type

◆ iterator

◆ const_iterator

Constructor & Destructor Documentation

◆ List() [1/2]

◆ List() [2/2]

Member Function Documentation

◆ operator=()

◆ empty()

◆ size()

◆ front() [1/2]

◆ front() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ end() [1/2]

◆ end() [2/2]

◆ cend()

◆ clear()

◆ insert() [1/2]

◆ insert() [2/2]

◆ erase()

◆ push_front()

◆ pop_front()

◆ push_back()

◆ pop_back()

◆ swap()

◆ prepend()

◆ append()

◆ iterator_to()

◆ const_iterator_to()

◆ element_from() [1/2]

◆ element_from() [2/2]

Member Data Documentation

◆ m_size

◆ m_head

◆ m_tail

template<typename T, typename Tag = void>
class beast::List< T, Tag >