fennec::list< TypeT, Alloc >

Data Structure defining lists of elements. More...

#include <list.h>

Detailed Description

template<class TypeT, class Alloc = allocator<TypeT>>
struct fennec::list< TypeT, Alloc >

This data-structure behaves like a linked list, but does not use pointers. Instead, it is in-array. This creates the following properties:

Property	Value
stable	⛔
dynamic	✅
homogenous	✅
distinct	⛔
ordered	⛔
space	\(O(N)\)
linear	✅
access	\(O(1)\)
find	\(O(N)\)
insertion	\(O(N)\)
deletion	\(O(N)\)

Template Parameters

TypeT

value type

Classes
class	const_iterator
	Iterator Class for Const Access. More...
class	iterator
	Iterator Class. More...

Public Types
using	alloc_t = typename allocator_traits< Alloc >::template rebind< node >
	Alias for the allocator type, rebound to list nodes.
using	value_t = TypeT
	Alias for the value type.

Public Member Functions
Constructors & Destructor
Iterator type for forward iteration over a constant list
constexpr	list ()
	Default Constructor, initializes an empty list.
constexpr	list (const list &l)
	Copy Constructor, copies all elements in l with optimized layout.
constexpr	list (list &&l) noexcept
	Move Constructor, takes ownership of the list.
constexpr	~list ()
	Destructor, destructs all elements then releases the allocation.
Assignment
constexpr list &	operator= (const list &l)
	Copy Assignment Operator.
constexpr list &	operator= (list &&l) noexcept
	Move Assignment Operator.
Properties
constexpr size_t	size () const
constexpr size_t	capacity () const
constexpr bool	empty () const
Access
constexpr value_t &	operator[] (int i)
	Array Access Operator.
constexpr const value_t &	operator[] (int i) const
	Const Array Access Operator.
constexpr value_t &	front ()
	Access Front Element.
constexpr const value_t &	front () const
	Const Access Front Element.
constexpr value_t &	back ()
	Access Back Element.
constexpr const value_t &	back () const
	Const Access Back Element.
Modifiers
constexpr size_t	insert (const iterator &it, const value_t &x)
	Copy Insertion.
constexpr size_t	insert (const iterator &it, value_t &&x)
	Move Insertion.
constexpr size_t	insert (size_t i, const value_t &x)
	Copy Insertion.
constexpr size_t	insert (size_t i, value_t &&x)
	Move Insertion.
template<typename... ArgsT>
constexpr size_t	emplace (size_t i, ArgsT &&...args)
	Emplace Insertion.
constexpr size_t	push_front (const value_t &x)
	Push Front Copy.
constexpr size_t	push_front (value_t &&x)
	Push Front Move.
template<typename... ArgsT>
constexpr size_t	emplace_front (ArgsT &&...args)
	Emplace Front.
constexpr size_t	push_back (const value_t &x)
	Push Back Copy.
constexpr size_t	push_back (value_t &&x)
	Push Back Move.
template<typename... ArgsT>
constexpr size_t	emplace_back (ArgsT &&...args)
	Emplace Back.
constexpr void	erase (size_t i)
	Erase Element.
constexpr void	erase (const iterator &it)
	Erase Element.
constexpr void	pop_front ()
	Pop Front, erases first element.
constexpr void	pop_back ()
	Pop Back, erases first element.
constexpr void	clear ()
	Clears the list, destructing all elements in order.
Iteration
constexpr iterator	begin ()
	C++ Iterator Specification begin()
constexpr iterator	end ()
	C++ Iterator Specification end()
constexpr const_iterator	begin () const
	Const C++ Iterator Specification begin()
constexpr const_iterator	end () const
	Const C++ Iterator Specification end()

Static Public Attributes
static constexpr size_t	npos = -1
	Constant representing a non-existant position.

Constructor & Destructor Documentation

list() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr fennec::list< TypeT, Alloc >::list ( const list< TypeT, Alloc > &  l )

inlineconstexpr

Parameters

l	The list to copy

list() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr fennec::list< TypeT, Alloc >::list ( list< TypeT, Alloc > &&  l )

inlineconstexprnoexcept

Parameters

l	The list to move

Member Function Documentation

operator=() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr list & fennec::list< TypeT, Alloc >::operator= ( const list< TypeT, Alloc > &  l )

inlineconstexpr

Parameters

l	the list to copy

Returns

this after having copied all elements of l

operator=() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr list & fennec::list< TypeT, Alloc >::operator= ( list< TypeT, Alloc > &&  l )

inlineconstexprnoexcept

Parameters

l	the list to copy

Returns

this after having taken ownership over the contents of l

size()

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::size ( ) const

inlineconstexpr

Returns

The size of the list in elements.

capacity()

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::capacity ( ) const

inlineconstexpr

Returns

The capacity of the list in elements.

empty()

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr bool fennec::list< TypeT, Alloc >::empty ( ) const

inlineconstexpr

Returns

true when the list is empty, false otherwise.

operator[]() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr value_t & fennec::list< TypeT, Alloc >::operator[] ( int  i )

inlineconstexpr

Parameters

i	Index to access

Returns

A reference to the element at i

\(O(N)\)

operator[]() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr const value_t & fennec::list< TypeT, Alloc >::operator[] ( int  i ) const

inlineconstexpr

Parameters

i	Index to access

Returns

A const-qualified reference to the element at i

\(O(N)\)

front() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr value_t & fennec::list< TypeT, Alloc >::front ( )

inlineconstexpr

Returns

A reference to the first element in the list

front() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr const value_t & fennec::list< TypeT, Alloc >::front ( ) const

inlineconstexpr

Returns

A const-qualified reference to the first element in the list

back() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr value_t & fennec::list< TypeT, Alloc >::back ( )

inlineconstexpr

Returns

A reference to the last element in the list

back() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr const value_t & fennec::list< TypeT, Alloc >::back ( ) const

inlineconstexpr

Returns

A const-qualified reference to the last element in the list

insert() [1/4]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::insert ( const iterator &  it, const value_t &  x  )

inlineconstexpr

Parameters

it	Location to insert at
x	value to copy

\(O(1)\)

insert() [2/4]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::insert ( const iterator &  it, value_t &&  x  )

inlineconstexpr

Parameters

it	Location to insert at
x	value to move

\(O(1)\)

insert() [3/4]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::insert ( size_t  i, const value_t &  x  )

inlineconstexpr

Parameters

i	Index to insert at
x	value to copy

\(O(N)\)

insert() [4/4]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::insert ( size_t  i, value_t &&  x  )

inlineconstexpr

Parameters

i	Index to insert at
x	value to move

\(O(N)\)

emplace()

template<class TypeT , class Alloc = allocator<TypeT>>

template<typename... ArgsT>

constexpr size_t fennec::list< TypeT, Alloc >::emplace ( size_t  i, ArgsT &&...  args  )

inlineconstexpr

Template Parameters

ArgsT

Argument types

Parameters

i	Index to insert at
args	Arguments to construct with

\(O(N)\)

push_front() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::push_front ( const value_t &  x )

inlineconstexpr

Parameters

x	Value to copy

push_front() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::push_front ( value_t &&  x )

inlineconstexpr

Parameters

x	Value to move

emplace_front()

template<class TypeT , class Alloc = allocator<TypeT>>

template<typename... ArgsT>

constexpr size_t fennec::list< TypeT, Alloc >::emplace_front ( ArgsT &&...  args )

inlineconstexpr

Parameters

args	Arguments to construct with

Template Parameters

ArgsT

Argument types

push_back() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::push_back ( const value_t &  x )

inlineconstexpr

Parameters

x	Value to copy

push_back() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr size_t fennec::list< TypeT, Alloc >::push_back ( value_t &&  x )

inlineconstexpr

Parameters

x	Value to move

emplace_back()

template<class TypeT , class Alloc = allocator<TypeT>>

template<typename... ArgsT>

constexpr size_t fennec::list< TypeT, Alloc >::emplace_back ( ArgsT &&...  args )

inlineconstexpr

Parameters

args	Arguments to construct with

Template Parameters

ArgsT

Argument types

erase() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr void fennec::list< TypeT, Alloc >::erase ( size_t  i )

inlineconstexpr

Parameters

i	Index to erase

erase() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr void fennec::list< TypeT, Alloc >::erase ( const iterator &  it )

inlineconstexpr

Parameters

it	Location to Erase

begin() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr iterator fennec::list< TypeT, Alloc >::begin ( )

inlineconstexpr

Returns

An iterator for the first element in the list

end() [1/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr iterator fennec::list< TypeT, Alloc >::end ( )

inlineconstexpr

Returns

An iterator for the end of the list

begin() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr const_iterator fennec::list< TypeT, Alloc >::begin ( ) const

inlineconstexpr

Returns

A const iterator for the first element in the list

end() [2/2]

template<class TypeT , class Alloc = allocator<TypeT>>

constexpr const_iterator fennec::list< TypeT, Alloc >::end ( ) const

inlineconstexpr

Returns

A const iterator for the end of the list

---

The documentation for this struct was generated from the following file:

• include/fennec/containers/list.h