LinkedListPool

template<class T>
class LinkedListPool

Pool of singly linked lists.

Should not be used as general purpose container. Use only for algorithms that require linked lists ability to split and concatenate them. All the data is owned by LinkedListPool.

In contrast to std::list and std::forward_list doesn’t allocate each node separately. LinkedListPool can reserve all the memory for multiple lists during construction. Uses std::vector as backing container.

Public Functions

inline LinkedListPool(size_t initialCapacity)

Create a linked list pool with capacity for initialCapacity list items.

Parameters:

initialCapacity – number of elements to preallocate.

inline List makeList(const T &value)

Create a list containing single item.

Does not invalidate any iterators, but may cause item relocation when initialCapacity is exceeded.

Parameters:

value – value of element that will be inserted in the created list

Returns:

List containing single value value .

inline List splitTail(const List &list, const ListIterator &head)

Split list and return second half.

After performing the operation, list passed as argument and return list point to the same items. Modifying them will affect both lists.

Parameters:

• list – The list that needs to be split.

• head – Iterator to the first item in new list. Needs to be within list .

Returns:

Returns suffix of list.

inline List splitHead(const List &list, const ListIterator &end)

Split list and return first half.

Parameters:

• list – The list that needs to be split.

• end – Iterator to the first item that should not be included in returned list. Needs to be within list .

Returns:

Returns prefix of list.

inline ListIterator head(const List &list)

Create list iterator from list.

Parameters:

list –

Returns:

Iterator pointing to the first item in the list.

inline ListIterator end(const List &list)

inline List append(const List &head, const List &tail)

class List

Single list within LinkedListPool.

List only refers to chain of elements. Copying it doesn’t copy any element. Item data is owned by LinkedListPool.

Use LinkedListPool::makeList to create non-empty list.

Public Functions

List() = default

Create an empty list.

inline bool isEmpty() const

class ListIterator

List iterator.

Iterators don’t get invalidated by adding items to list, but the items may be relocated.

Public Types

using iterator_category = std::forward_iterator_tag

using value_type = T

using difference_type = size_t

using pointer = T*

using reference = T&

Public Functions

ListIterator() = default

inline reference operator*()

inline pointer operator->()

inline ListIterator &operator++()

inline ListIterator operator++(int)

inline bool operator!=(const ListIterator &b) const

inline explicit operator bool() const

Test if iterator points to valid value.