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

LinkedListPool(size_t initialCapacity)

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

Parameters
  • initialCapacity: number of elements to preallocate.

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.

Return

List containing single value value .

Parameters
  • value: value of element that will be inserted in the created list

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.

Return

Returns suffix of list.

Parameters
  • list: The list that needs to be split.

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

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

Split list and return first half.

Return

Returns prefix of list.

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 .

ListIterator head(const List &list)

Create list iterator from list.

Return

Iterator pointing to the first item in the list.

Parameters
  • list:

ListIterator end(const List &list)
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.

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
reference operator*()
pointer operator->()
ListIterator &operator++()
ListIterator operator++(int)
bool operator!=(const ListIterator &b) const
operator bool() const

Test if iterator points to valid value.