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.