linked-elements.hpp File Reference

Intrusive single linked list with optional ownership. More...

Go to the source code of this file.

Description

Intrusive single linked list with optional ownership.

This helper template allows to attach a number of tightly integrated elements with low overhead. Typically, these elements are to be attached once and never changed. Optionally, elements can be created using a custom allocation scheme; the holder might also take ownership. These variations in functionality are controlled by policy templates.

The rationale for using this approach is

• variable number of elements
• explicit support for polymorphism
• no need to template the holder on the number of elements
• no heap allocations (contrast this to using std::vector)
• clear and expressive notation at the usage site
• convenient access through Lumiera Forward Iterators
• the need to integrate tightly with a custom allocator

Note

effectively, LinkedElements is „just a dressed-up pointer“; under the assumption that the allocator is a monostate, and exploiting empty-base-optimisation, footprint is minimal.

this linked list container is intrusive and thus needs the help of the element type, which must provide a pointer member next. Consequently, each such node element can not be member in several collections at the same time (unless they share all elements)

as usual, any iterator relies on the continued existence and unaltered state of the container. There is no sanity check.

Warning

this container is deliberately not threadsafe

be sure to understand the implications of taking ownership: When adding an existing node element (by pointer) to a LinkedElements list which takes ownership, the list will attempt to destroy or de-allocate this node element when going out of scope.

See also

LinkedElements_test

allocator-handle.hpp

ScopedCollection

itertools.hpp

Definition in file linked-elements.hpp.

#include "lib/error.hpp"
#include "lib/nocopy.hpp"
#include "lib/iter-adapter.hpp"
#include "lib/allocator-handle.hpp"
#include "lib/util.hpp"
#include <utility>
#include <memory>

Namespaces
namespace	lib
	Implementation namespace for support and library code.
namespace	lib::linked_elements

Typedefs
template<class N >
using	OwningHeapAllocated = OwningAllocated< std::allocator< N > >
	default policy: use standard heap allocation for new elements

Classes
struct	OwningAllocated< ALO >
	< allocation policies for the LinkedElements list container More...
struct	NoOwnership
	Policy for LinkedElements: never create or destroy any elements, only allow to add already existing nodes. More...
class	LinkedElements< N, ALO >
	Intrusive single linked list, possibly taking ownership of node elements. More...
struct	LinkedElements< N, ALO >::IterationState
	Iteration is just following the single linked list. More...

Functions
template<class N >
auto &	asLinkedElements (N *const &anchor)
	transiently reinterpret an element pointer as const LinkedElements, allowing to count, iterate or subscript a chain of elements