LinkedListPool¶
-
template<class
T
>
classLinkedListPool
¶ 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)¶
-
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.
-
class
ListIterator
¶ List iterator.
Iterators don’t get invalidated by adding items to list, but the items may be relocated.
Public Types
-
template<>
usingiterator_category
= std::forward_iterator_tag¶
-
template<>
usingvalue_type
= T¶
-
template<>
usingdifference_type
= size_t¶
-
template<>
usingpointer
= T *¶
-
template<>
usingreference
= T&¶
-
template<>
-