libboxes: boxes::LinkedVector< T, ChunkSizeV

Implements a vector-like container that uses a linked list of fixed-size chunks to store its elements. More...

#include <linked_vector.hpp>

Collaboration diagram for boxes::LinkedVector< T, ChunkSizeV >:

Public Member Functions
	LinkedVector ()
	Constructs an empty container. More...

	LinkedVector (LinkedVector< T, ChunkSizeV > &&other)
	Move constructor. More...

LinkedVector< T, ChunkSizeV > &	operator= (LinkedVector< T, ChunkSizeV > &&other)
	Move assignment operator. More...

void	swap (LinkedVector< T, ChunkSizeV > &other)
	Swaps the contents of this LinkedVector with another. More...

template<typename Arg >
void	push_front (Arg &&value)
	Pushes a new element to the front of the container. More...

template<typename Arg >
void	push_back (Arg &&value)
	Pushes a new element to the back of the container. More...

void	pop_front ()
	Removes the first element from the container. More...

void	pop_back ()
	Removes the last element from the container. More...

T &	front ()
	Returns a reference to the first element in the container. More...

const T &	front () const
	Returns a const reference to the first element in the container. More...

T &	back ()
	Returns a reference to the last element in the container. More...

const T &	back () const
	Returns a const reference to the last element in the container. More...

T &	operator[] (size_type pos)
	Provides access to the element at the specified position. More...

const T &	operator[] (size_type pos) const
	Returns a const reference to the element at the specified position. More...

T &	at (size_type pos)
	Returns a reference to the element at the specified position. More...

const T &	at (size_type pos) const
	Returns a const reference to the element at the specified position. More...

iterator	begin ()
	Returns an iterator to the first element of the container. More...

iterator	end ()
	Returns an iterator to the element following the last element of the container. More...

iterator	cbegin () const
	Returns a const iterator to the first element of the container. More...

iterator	cend () const
	Returns a const iterator to the element following the last element. More...

bool	operator== (const LinkedVector< T, ChunkSizeV > &other) const
	Returns true if the two containers are equal. More...

bool	operator!= (const LinkedVector< T, ChunkSizeV > &other) const
	Returns true if the two containers are not equal. More...

std::size_t	size () const BOXES_NOTHROW
	Returns the number of elements in the container. More...

std::size_t	capacity () const BOXES_NOTHROW
	Returns the maximum number of elements the container can hold without additional memory allocation. More...

void	clear ()
	Removes all elements from the container. More...

bool	empty () const BOXES_NOTHROW
	Returns true if the container is empty. More...

Detailed Description

template<typename T, std::size_t ChunkSizeV>
class boxes::LinkedVector< T, ChunkSizeV >

Implements a vector-like container that uses a linked list of fixed-size chunks to store its elements.

The LinkedVector class is a container that provides a similar interface to std::vector, but uses a linked list of fixed-size chunks to store its elements. This allows for efficient insertion and deletion at both ends of the container, as well as efficient memory usage for large containers.

Internally, the LinkedVector uses RingBuffer objects as chunks to store its elements.

To minimise the number of memory allocations, the LinkedVector maintains a list of discarded chunks that can be reused when new chunks are needed. When a chunk is no longer needed, it is moved to the list of discarded chunks rather than being deallocated.

Template Parameters

T	The type of the elements stored in the container.
ChunkSizeV	The size of the chunks used to store the elements.

Examples: linked_vector_example.cpp.

Definition at line 44 of file linked_vector.hpp.

Constructor & Destructor Documentation

◆ LinkedVector() [1/2]

template<typename T , std::size_t ChunkSizeV>

boxes::LinkedVector< T, ChunkSizeV >::LinkedVector ( )

inline

Constructs an empty container.

Note: By default, the LinkedVector is constructed with a single empty chunk.

Definition at line 112 of file linked_vector.hpp.

◆ LinkedVector() [2/2]

template<typename T , std::size_t ChunkSizeV>

boxes::LinkedVector< T, ChunkSizeV >::LinkedVector ( LinkedVector< T, ChunkSizeV > && other )

inline

Move constructor.

Parameters

Member Function Documentation

◆ at() [1/2]

template<typename T , std::size_t ChunkSizeV>

T & boxes::LinkedVector< T, ChunkSizeV >::at ( size_type pos )

inline

Returns a reference to the element at the specified position.

If pos is not within the range of the container, an exception of type std::out_of_range is thrown.

Parameters

pos	The position of the element to access

Returns: A reference to the element at the specified position

Definition at line 324 of file linked_vector.hpp.

◆ at() [2/2]

template<typename T , std::size_t ChunkSizeV>

const T & boxes::LinkedVector< T, ChunkSizeV >::at ( size_type pos ) const

inline

Returns a const reference to the element at the specified position.

If pos is not within the range of the container, an exception of type std::out_of_range is thrown.

Parameters

pos	The position of the element to access

Returns: A const reference to the element at the specified position

Definition at line 340 of file linked_vector.hpp.

◆ back() [1/2]

template<typename T , std::size_t ChunkSizeV>

T & boxes::LinkedVector< T, ChunkSizeV >::back ( )

inline

Returns a reference to the last element in the container.

If the container is empty, an exception of type std::out_of_range is thrown.

Returns: Reference to the last element in the container

Definition at line 264 of file linked_vector.hpp.

◆ back() [2/2]

template<typename T , std::size_t ChunkSizeV>

const T & boxes::LinkedVector< T, ChunkSizeV >::back ( ) const

inline

Returns a const reference to the last element in the container.

Returns: const T & A const reference to the last element in the container

Definition at line 277 of file linked_vector.hpp.

◆ begin()

template<typename T , std::size_t ChunkSizeV>

iterator boxes::LinkedVector< T, ChunkSizeV >::begin ( )

inline

Returns an iterator to the first element of the container.

Returns: an iterator to the first element of the container

Definition at line 349 of file linked_vector.hpp.

◆ capacity()

template<typename T , std::size_t ChunkSizeV>

std::size_t boxes::LinkedVector< T, ChunkSizeV >::capacity ( ) const

inline

Returns the maximum number of elements the container can hold without additional memory allocation.

The capacity of a LinkedVector is the maximum number of elements it can hold without additional memory allocation. This is the number of elements that can be stored in the currently allocated chunks.

Note: The capacity of a LinkedVector is always a multiple of the chunk size.

Returns: The maximum number of elements the container can hold without any additional memory allocation.

Definition at line 444 of file linked_vector.hpp.

◆ cbegin()

template<typename T , std::size_t ChunkSizeV>

iterator boxes::LinkedVector< T, ChunkSizeV >::cbegin ( ) const

inline

Returns a const iterator to the first element of the container.

Returns: an iterator to the first element of the container

Definition at line 365 of file linked_vector.hpp.

◆ cend()

template<typename T , std::size_t ChunkSizeV>

iterator boxes::LinkedVector< T, ChunkSizeV >::cend ( ) const

inline

Returns a const iterator to the element following the last element.

Returns: an iterator to the element following the last element of the container

Definition at line 373 of file linked_vector.hpp.

◆ clear()

template<typename T , std::size_t ChunkSizeV>

void boxes::LinkedVector< T, ChunkSizeV >::clear ( )

inline

Removes all elements from the container.

Definition at line 451 of file linked_vector.hpp.

◆ empty()

template<typename T , std::size_t ChunkSizeV>

bool boxes::LinkedVector< T, ChunkSizeV >::empty ( ) const

inline

Returns true if the container is empty.

Returns: true if the container is empty, false otherwise.

Examples: linked_vector_example.cpp.

Definition at line 462 of file linked_vector.hpp.

◆ end()

template<typename T , std::size_t ChunkSizeV>

iterator boxes::LinkedVector< T, ChunkSizeV >::end ( )

inline

Returns an iterator to the element following the last element of the container.

Returns: an iterator to the element following the last element of the container

Definition at line 358 of file linked_vector.hpp.

◆ front() [1/2]

template<typename T , std::size_t ChunkSizeV>

T & boxes::LinkedVector< T, ChunkSizeV >::front ( )

inline

Returns a reference to the first element in the container.

If the container is empty, an exception of type std::out_of_range is thrown.

Returns: Reference to the first element in the container

Examples: linked_vector_example.cpp.

Definition at line 238 of file linked_vector.hpp.

◆ front() [2/2]

template<typename T , std::size_t ChunkSizeV>

const T & boxes::LinkedVector< T, ChunkSizeV >::front ( ) const

inline

Returns a const reference to the first element in the container.

If the container is empty, an exception of type std::out_of_range is thrown.

Returns: const T & A const reference to the first element in the container

Definition at line 254 of file linked_vector.hpp.

◆ operator!=()

template<typename T , std::size_t ChunkSizeV>

bool boxes::LinkedVector< T, ChunkSizeV >::operator!= ( const LinkedVector< T, ChunkSizeV > & other ) const

inline

Returns true if the two containers are not equal.

Parameters

other The container to compare with

Returns: true if the two containers are not equal, false otherwise

Definition at line 405 of file linked_vector.hpp.

◆ operator=()

template<typename T , std::size_t ChunkSizeV>

LinkedVector< T, ChunkSizeV > & boxes::LinkedVector< T, ChunkSizeV >::operator= ( LinkedVector< T, ChunkSizeV > && other )

inline

Move assignment operator.

Parameters

◆ operator==()

template<typename T , std::size_t ChunkSizeV>

bool boxes::LinkedVector< T, ChunkSizeV >::operator== ( const LinkedVector< T, ChunkSizeV > & other ) const

inline

Returns true if the two containers are equal.

The two containers are considered equal if they have the same number of elements and all the elements, compared in order, are equal.

Parameters

other The container to compare with

Returns: true if the two containers are equal, false otherwise

Definition at line 384 of file linked_vector.hpp.

◆ operator[]() [1/2]

template<typename T , std::size_t ChunkSizeV>

T & boxes::LinkedVector< T, ChunkSizeV >::operator[] ( size_type pos )

inline

Provides access to the element at the specified position.

No bounds checking is performed.

Parameters

pos	The position of the element to access

Returns: A reference to the element at the specified position

Definition at line 287 of file linked_vector.hpp.

◆ operator[]() [2/2]

template<typename T , std::size_t ChunkSizeV>

const T & boxes::LinkedVector< T, ChunkSizeV >::operator[] ( size_type pos ) const

inline

Returns a const reference to the element at the specified position.

No bounds checking is performed.

Parameters

pos	The position of the element to access

Returns: A const reference to the element at the specified position

Definition at line 311 of file linked_vector.hpp.

◆ pop_back()

template<typename T , std::size_t ChunkSizeV>

void boxes::LinkedVector< T, ChunkSizeV >::pop_back ( )

inline

Removes the last element from the container.

The time complexity of this operation is O(1).

If the back chunk becomes empty after the removal, it is moved to the pool of discarded chunks. No deallocation is performed.

Definition at line 221 of file linked_vector.hpp.

◆ pop_front()

template<typename T , std::size_t ChunkSizeV>

void boxes::LinkedVector< T, ChunkSizeV >::pop_front ( )

inline

Removes the first element from the container.

The time complexity of this operation is O(1).

If the front chunk becomes empty after the removal, it is moved to the pool of discarded chunks. No deallocation is performed.

Examples: linked_vector_example.cpp.

Definition at line 204 of file linked_vector.hpp.

◆ push_back()

template<typename T , std::size_t ChunkSizeV>

template<typename Arg >

void boxes::LinkedVector< T, ChunkSizeV >::push_back ( Arg && value )

inline

Pushes a new element to the back of the container.

Newly inserted element is retrievable with back method.

The time complexity of this operation is O(1).

May incur a chunk allocation if the back chunk is full and the pool of discarded chunks is empty.

Template Parameters

Arg	The type of the argument to push

Parameters

value The value to push to the back of the container

Examples: linked_vector_example.cpp.

Definition at line 191 of file linked_vector.hpp.

◆ push_front()

template<typename T , std::size_t ChunkSizeV>

template<typename Arg >

void boxes::LinkedVector< T, ChunkSizeV >::push_front ( Arg && value )

inline

Pushes a new element to the front of the container.

Newly inserted element is retrievable with front method.

The time complexity of this operation is O(1).

May incur a chunk allocation if the front chunk is full and the pool of discarded chunks is empty.

Template Parameters

Arg	The type of the argument to push

Parameters

value The value to push to the front of the container

Definition at line 173 of file linked_vector.hpp.

◆ size()

template<typename T , std::size_t ChunkSizeV>

std::size_t boxes::LinkedVector< T, ChunkSizeV >::size ( ) const

inline

Returns the number of elements in the container.

Returns: The number of elements in the container

Definition at line 414 of file linked_vector.hpp.

◆ swap()

template<typename T , std::size_t ChunkSizeV>

void boxes::LinkedVector< T, ChunkSizeV >::swap ( LinkedVector< T, ChunkSizeV > & other )

inline

Swaps the contents of this LinkedVector with another.

Note: The pool of discarded chunks is swapped as well.

Parameters

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LinkedVector() [1/2]

◆ LinkedVector() [2/2]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ begin()

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ empty()

◆ end()

◆ front() [1/2]

◆ front() [2/2]

◆ operator!=()

◆ operator=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop_back()

◆ pop_front()

◆ push_back()

◆ push_front()

◆ size()

◆ swap()