Intrusive flat forward list container. More...

#include <iffl_list.h>

Public Types
using	value_type = T
	Element value type.

using	pointer = T *
	Pointer to element type.

using	const_pointer = T const *
	Pointer to const element type.

using	reference = T &
	Reference to the element type.

using	const_reference = T const &
	Reference to the const element type.

using	size_type = std::size_t
	Size type.

using	difference_type = std::ptrdiff_t
	Element pointers difference type.

using	traits = TT
	Element traits type.

using	traits_traits = flat_forward_list_traits_traits< T, TT >
	Element traits traits type.

using	range_t = typename traits_traits::range_t
	Vocabulary type used to describe buffer used by the element and how much of this buffer is used by the data. Type also includes information about required alignment.

using	size_with_padding_t = typename traits_traits::size_with_padding_t
	Vocabulary type used to describe size with padding.

using	offset_with_aligment_t = typename traits_traits::offset_with_aligment_t
	Vocabulary type used to describe size with alignment.

using	sizes_t = flat_forward_list_sizes< traits_traits::alignment >
	Vocabulary type that contains information about buffer size, and last element range.

using	allocator_type = typename std::allocator_traits< A >::template rebind_alloc< char >
	Type of allocator.

using	allocator_type_traits = std::allocator_traits< allocator_type >
	Type of allocator traits.

using	buffer_value_type = char
	Since we have variable size elements, and we cannot express it in the C++ type system we treat buffer with elements as a bag of chars and cast to the element type when necessary.

using	const_buffer_value_type = char const
	When we do not intend to modify buffer we can treat it as a bag of const characters.

using	buffer_pointer = char *
	Type used as a buffer pointer.

using	const_buffer_pointer = char const *
	Type used as a pointer to the const buffer.

using	iterator = flat_forward_list_iterator< T, TT >
	Type of iterator.

using	const_iterator = flat_forward_list_const_iterator< T, TT >
	Type of const iterator.

using	buffer_type = buffer_t< buffer_value_type >
	Pointers that describe buffer. More...

Public Member Functions
	flat_forward_list () noexcept
	Default constructor for container.

	flat_forward_list (allocator_type a) noexcept
	Constructs an empty container with an instance of provided allocator.

	flat_forward_list (flat_forward_list &&other) noexcept
	Move constructor. Moves allocator and content of other container to this container. More...

	flat_forward_list (flat_forward_list const &other)
	Copy constructor. Copies allocator if supported and copies content of other container to this container. More...

template<typename AA = allocator_type>
	flat_forward_list (attach_buffer, buffer_view const &other_buff, AA &&a=AA{}) noexcept
	Constructor that takes ownership of a buffer. More...

template<typename AA = allocator_type>
	flat_forward_list (buffer_view const &other_buff, AA &&a=AA{})
	Constructor that copies list from a buffer. More...

template<typename AA = allocator_type>
	flat_forward_list (attach_buffer, char buffer_begin, char last_element, char *buffer_end, AA &&a=AA{}) noexcept
	Constructor that takes ownership of a buffer. More...

template<typename AA = allocator_type>
	flat_forward_list (char const buffer_begin, char const last_element, char const *buffer_end, AA &&a=AA{})
	Constructor that copies list from a buffer. More...

template<typename AA = allocator_type>
	flat_forward_list (attach_buffer, char *buffer, size_t buffer_size, AA &&a=AA{}) noexcept
	Constructor that takes ownership of a buffer and attempts to find last element of the list. More...

template<typename AA = allocator_type>
	flat_forward_list (char const *buffer, size_t buffer_size, AA &&a=AA{})
	Constructor that checks if buffer contains a valid list and if it does then copies that list. More...

template<typename AA = allocator_type>
	flat_forward_list (const_iterator const &begin, const_iterator const &last, AA &&a=AA{})
	Copies element pointed by the iterators. More...

template<typename AA = allocator_type>
	flat_forward_list (flat_forward_list_view< T, TT > const &view, AA &&a=AA{})
	Copies element from the view. More...

flat_forward_list &	operator= (flat_forward_list &&other) noexcept(allocator_type_traits::propagate_on_container_move_assignment::value)
	Move assignment operator. More...

flat_forward_list &	operator= (flat_forward_list const &other)
	Copy assignment operator. More...

flat_forward_list &	operator= (buffer_view const &other_buff)
	Copy assignment operator. More...

	~flat_forward_list () noexcept
	Destructor. More...

buffer_ref	detach () noexcept
	Container releases ownership of the buffer. More...

void	attach (buffer_view const &other_buff)
	Takes ownership of a buffer. More...

void	attach (char buffer_begin, char last_element, char *buffer_end) noexcept
	Takes ownership of a buffer. More...

bool	attach (char *buffer, size_t buffer_size) noexcept
	Takes ownership of a buffer and attempts to find last element of the list. More...

void	assign (buffer_view const &other_buff)
	Copies list from a buffer. More...

void	assign (char const buffer_begin, char const last_element, char const *buffer_end)
	Copies list from a buffer. More...

bool	assign (char const buffer_begin, char const buffer_end)
	Checks if buffer contains a valid list and if it does then copies that list. More...

bool	assign (char const *buffer, size_type buffer_size)
	Checks if buffer contains a valid list and if it does then copies that list. More...

void	assign (const_iterator const &begin, const_iterator const &last)
	Copies element pointed by the iterators. More...

void	assign (flat_forward_list_view< T, TT > const &view)
	Copies elements from the view. More...

template<typename AA >
bool	is_compatible_allocator (AA const &other_allocator) const noexcept
	Compares if allocator used by container is equivalent to the other allocator. More...

allocator_type &	get_allocator () &noexcept
	Returns reference to the allocator used by this container. More...

allocator_type const &	get_allocator () const &noexcept
	Returns const reference to the allocator used by this container. More...

size_type	max_size () const noexcept
	Returns maximum size. More...

void	clear () noexcept
	Deallocated buffer owned by this container. More...

void	tail_shrink_to_fit ()
	Resizes buffer to the used capacity. More...

void	resize_buffer (size_type size)
	Resizes buffer. More...

void	push_back (size_type init_buffer_size, char const *init_buffer=nullptr)
	Adds new element to the end of the list. Element is initialized by copping provided buffer. More...

bool	try_push_back (size_type init_buffer_size, char const *init_buffer=nullptr)
	Adds new element to the end of the list. Element is initialized by copping provided buffer. More...

template<typename F >
void	emplace_back (size_type element_size, F const &fn)
	Constructs new element at the end of the list. More...

template<typename F >
bool	try_emplace_back (size_type element_size, F const &fn)
	Constructs new element at the end of the list if it fits in the existing free capacity. More...

void	pop_back () noexcept
	Removes last element from the list. More...

iterator	insert (iterator const &it, size_type init_buffer_size, char const *init_buffer=nullptr)
	Inserts new element at the position described by iterator. Element is initialized by copping provided buffer. More...

bool	try_insert (iterator const &it, size_type init_buffer_size, char const *init_buffer=nullptr)
	Inserts new element at the position described by iterator. Element is initialized by copping provided buffer. More...

template<typename F >
iterator	emplace (iterator const &it, size_type new_element_size, F const &fn)
	Constructs new element at the position described by iterator. Element is initialized with a help of the functor passed as a parameter. More...

template<typename F >
bool	try_emplace (iterator const &it, size_type new_element_size, F const &fn)
	Constructs new element at the position described by iterator. Element is initialized with a help of the functor passed as a parameter. More...

void	push_front (size_type init_buffer_size, char const *init_buffer=nullptr)
	Constructs new element at the beginning of the container. Element is initialized by copping provided buffer. More...

bool	try_push_front (size_type init_buffer_size, char const *init_buffer=nullptr)
	Constructs new element at the beginning of the container. Element is initialized by copping provided buffer. More...

template<typename F >
void	emplace_front (size_type element_size, F const &fn)
	Inserts new element at the beginning of the container. Element is initialized with a help of the functor passed as a parameter. More...

template<typename F >
bool	try_emplace_front (size_type element_size, F const &fn)
	Inserts new element at the beginning of the container. Element is initialized with a help of the functor passed as a parameter. More...

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

void	erase_after (iterator const &it) noexcept
	Erases element after the element pointed by the iterator. More...

void	erase_after_half_closed (iterator const &before_start, iterator const &last) noexcept
	Erases element in the range (before_start, last]. More...

void	erase_all_after (iterator const &it) noexcept
	Erases element in the range (before_start, end) More...

iterator	erase_all_from (iterator const &it) noexcept
	Erases element in the range [it, end) More...

void	erase_all () noexcept
	Erases all elements in the buffer without deallocating buffer.

iterator	erase (iterator const &it) noexcept
	Erases element pointed by iterator. More...

iterator	erase (iterator const &start, iterator const &end) noexcept
	Erases element in the range [start, end). More...

void	swap (flat_forward_list &other) noexcept(allocator_type_traits::propagate_on_container_swap::value\|\|allocator_type_traits::propagate_on_container_move_assignment::value)
	Swaps content of this container and the other container. More...

template<typename LESS_F >
void	sort (LESS_F const &fn)
	Sorts elements of container using comparator passed as a parameter. More...

void	reverse ()
	Reverses elements of the list. More...

template<class F >
void	merge (flat_forward_list &other, F const &fn)
	Merges two linked list ordering lists using comparison functor. More...

template<typename F >
void	unique (F const &fn) noexcept
	If there are multiple equivalent elements next to each other then first one is kept, and all other are deleted. More...

template<typename F >
void	remove_if (F const &fn) noexcept
	Removes all elements that satisfy predicate. More...

T &	front () noexcept

T const &	front () const noexcept

T &	back () noexcept

T const &	back () const noexcept

iterator	begin () noexcept

const_iterator	begin () const noexcept

iterator	last () noexcept

const_iterator	last () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

const_iterator	cbegin () const noexcept

const_iterator	clast () const noexcept

const_iterator	cend () const noexcept

char *	data () noexcept

char const *	data () const noexcept

bool	revalidate_data (size_type data_size=npos) noexcept
	Validates that buffer contains a valid list. More...

void	shrink_to_fit ()
	Removes unused padding of each element and at the tail. More...

void	shrink_to_fit (iterator const &first, iterator const &end)
	Removes unused padding of each element in the range [first, end). More...

void	shrink_to_fit (iterator const &it)
	Removes unused padding of an element. More...

iterator	element_add_size (iterator const &it, size_type size_to_add)
	Adds unused capacity to the element. More...

bool	try_element_add_size (iterator const &it, size_type size_to_add)
	Adds unused capacity to the element. More...

template<typename F >
iterator	element_resize (iterator const &it, size_type new_size, F const &fn)
	Resizes element. More...

template<typename F >
bool	try_element_resize (iterator const &it, size_type new_size, F const &fn)
	Resizes element. More...

size_type	required_size (const_iterator const &it) const noexcept
	Returns capacity used by the element's data. More...

size_type	used_size (const_iterator const &it) const noexcept

range_t	range (const_iterator const &it) const noexcept
	Information about the buffer occupied by an element. More...

range_t	closed_range (const_iterator const &begin, const_iterator const &last) const noexcept
	Information about the buffer occupied by elements in the range [begin, last]. More...

range_t	half_open_range (const_iterator const &begin, const_iterator const &end) const noexcept
	Information about the buffer occupied by elements in the range [begin, end). More...

bool	contains (const_iterator const &it, size_type position) const noexcept
	Tells if given offset in the buffer falls into a buffer used by the element. More...

iterator	find_element_before (size_type position) noexcept
	Searches for an element before the element that contains given position. More...

const_iterator	find_element_before (size_type position) const noexcept
	Searches for an element before the element that contains given position. More...

iterator	find_element_at (size_type position) noexcept
	Searches for an element that contains given position. More...

const_iterator	find_element_at (size_type position) const noexcept
	Searches for an element that contains given position. More...

iterator	find_element_after (size_type position) noexcept
	Searches for an element after the element that contains given position. More...

const_iterator	find_element_after (size_type position) const noexcept
	Searches for an element after the element that contains given position. More...

size_type	size () const noexcept
	Number of elements in the container. More...

bool	empty () const noexcept
	Tells if container contains no elements. More...

size_type	used_capacity () const noexcept

size_type	total_capacity () const noexcept

size_type	remaining_capacity () const noexcept

void	fill_padding (int fill_byte=0, bool zero_unused_capacity=true) noexcept
	Fills parts of the buffer not used by element data with fill_byte. More...

Static Public Attributes
static size_type const	npos = iffl::npos
	Constant that represents and invalid or non-existent position.

Friends
template<typename TU , typename TTU >
class	flat_forward_list_ref

Detailed Description

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>
class iffl::flat_forward_list< T, TT, A >

Intrusive flat forward list container.

Forward declaration of intrusive flat forward list container.

Template Parameters

T	- element type
TT	- element type traits
A	- allocator type that should be used for this container

TT is default initialized to specialization of flat_forward_list_traits for T A is default initialized to std::allocator for T Container is inherited from allocator to utilize Empty Base Class Optimization (EBCO).

Iterator invalidation notes: Begin iterator might get invalidated on any operation that causes buffer reallocation or erases last element of container Any other iterator, including an end iterator can get invalidated on any operation that causes buffer reallocation or adds, removes or resizes elements of container. Methods that take iterator as an input, and can invalidate it return new valid iterator as an output. Caller must refresh end iterator by explicitly calling [c]end().

Debugging notes: Defining FFL_DBG_CHECK_ITERATOR_VALID will enable validation of that iterators passed in input parameters are valid and are pointing to an existing element. Cost of this validation is O(element count). Defining FFL_DBG_CHECK_DATA_VALID will enable validation of container after every method that modifies container data.

Iterator names notes: begin or first - first element in a half-open [first, end) or closed [first, last] range. last - refers to the last element in half-closed (before_begin, last] or closed [first, last] range. end - refers to an element pass the last element. It is used with half open [begin, end) or open (before_begin, end) range. before_beging or before_first - refers to an element preceding begin or first element. Is used in half-open (before_begin, last] or open (before_begin, end) range.

Security notes: One of the common directions for attack is to leak to the attacher some uninitialized data that might contain addresses that might guide attacker how to bypass protections like Address Space Layout Randomization (ASLR). To prevent that consider using fill_padding that will fill any unused space with given pattern making sure we are not leaking any unintended information in the element padding and in the buffer's unused tail.

Inter-op with C API notes: When passing pointer to container's buffer to an API that can modify it it will invalidate container invariants. For instance pointer to the last element will no longer be valid. User must call revalidate_data after this call to make sure invariants are fixed. The cal revalidate_data will rescan buffer for valid list as if it is a non-trusted buffer.

Allocator notes: COntainer supports adopting (attaching to) buffer that was allocated by someone else. This helps to minimize number of copies when inter-oping with C API. It is responsibility of user to make sure that container uses allocator that is compatible with how adopted buffer was allocated.

Member Typedef Documentation

◆ buffer_type

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iffl::flat_forward_list< T, TT, A >::buffer_type

Pointers that describe buffer.

Depending if T is const buffer uses char * or char const *

Constructor & Destructor Documentation

◆ flat_forward_list() [1/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iffl::flat_forward_list< T, TT, A >::flat_forward_list ( flat_forward_list< T, TT, A > && other )

inlinenoexcept

Move constructor. Moves allocator and content of other container to this container.

Parameters

other - container we are moving from

◆ flat_forward_list() [2/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iffl::flat_forward_list< T, TT, A >::flat_forward_list ( flat_forward_list< T, TT, A > const & other )

inline

Copy constructor. Copies allocator if supported and copies content of other container to this container.

Parameters

other - container we are copying from

Exceptions

std::bad_alloc if buffer allocation fails

◆ flat_forward_list() [3/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	attach_buffer	,
		buffer_view const &	other_buff,
		AA &&	a = `AA{}`
	)

inlinenoexcept

Constructor that takes ownership of a buffer.

Template Parameters

A	- type of allocator.

Parameters

other_buff	- pointer to the start of the buffer that contains list.
a	- allocator that should be used by this container.

This constructor does not validate if this is a valid flat forward list. It assumes that caller validated buffer before using this constructor. The first parameter is an empty vocabulary type to help with overload resolution and code readability.

iffl::flat_forward_list<my_type> new_owner{iffl::attach_buffer{}, begin, last, end};

After this call container is responsible for deallocating the buffer. It is responsibility of the caller to make sure that buffer was allocated using method compatible with allocator used by this container.

◆ flat_forward_list() [4/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	buffer_view const &	other_buff,
		AA &&	a = `AA{}`
	)

inlineexplicit

Constructor that copies list from a buffer.

Template Parameters

AA	- type of allocator.

Parameters

other_buff	- pointer to the start of the buffer that contains list.
a	- allocator that should be used by this container.

Exceptions

std::bad_alloc if buffer allocation fails

This constructor does not validate if this is a valid flat forward list. It assumes that caller validated buffer before using this constructor.

◆ flat_forward_list() [5/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	attach_buffer	,
		char *	buffer_begin,
		char *	last_element,
		char *	buffer_end,
		AA &&	a = `AA{}`
	)

inlinenoexcept

Constructor that takes ownership of a buffer.

Template Parameters

AA	- type of allocator.

Parameters

buffer_begin	- pointer to the start of the buffer that contains list.
buffer_end	- pointer to the address right after last byte in the buffer.
last_element	- pointers to the last element of the list in the buffer. If buffer does not contain any elements then this parameter must be nullptr.
a	- allocator that should be used by this container.

This constructor does not validate if this is a valid flat forward list. It assumes that caller validated buffer before using this constructor. The first parameter is an empty vocabulary type to help with overload resolution and code reliability.

iffl::flat_forward_list<my_type> new_owner{iffl::attach_buffer{}, begin, last, end};

After this call container is responsible for deallocating the buffer. It is responsibility of the caller to make sure that buffer was allocated using method compatible with allocator used by this container.

◆ flat_forward_list() [6/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	char const *	buffer_begin,
		char const *	last_element,
		char const *	buffer_end,
		AA &&	a = `AA{}`
	)

inline

Constructor that copies list from a buffer.

Template Parameters

AA	- type of allocator.

Parameters

buffer_begin	- pointer to the start of the buffer that contains list.
buffer_end	- pointer to the address right after last byte in the buffer.
last_element	- pointers to the last element of the list in the buffer. If buffer does not contain any elements then this parameter must be nullptr.
a	- allocator that should be used by this container.

Exceptions

std::bad_alloc if buffer allocation fails

This constructor does not validate if this is a valid flat forward list. It assumes that caller validated buffer before using this constructor.

◆ flat_forward_list() [7/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	attach_buffer	,
		char *	buffer,
		size_t	buffer_size,
		AA &&	a = `AA{}`
	)

inlinenoexcept

Constructor that takes ownership of a buffer and attempts to find last element of the list.

Template Parameters

AA	- type of allocator.

Parameters

buffer	- pointer to the start of the buffer that might contains list.
buffer_size	- buffer size.
a	- allocator that should be used by this container.

This constructor adopts buffer, and searches for the last valid element in the buffer. If buffer validation fails then container will treat it as if it has no elements. The first parameter is an empty vocabulary type to help with overload resolution and code reliability.

iffl::flat_forward_list<my_type> new_owner{iffl::attach_buffer{}, begin, size};

After this call container is responsible for deallocating the buffer. It is responsibility of the caller to make sure that buffer was allocated using method compatible with allocator used by this container.

◆ flat_forward_list() [8/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	char const *	buffer,
		size_t	buffer_size,
		AA &&	a = `AA{}`
	)

inline

Constructor that checks if buffer contains a valid list and if it does then copies that list.

Template Parameters

AA	- type of allocator.

Parameters

buffer	- pointer to the start of the buffer that might contains list.
buffer_size	- buffer size.
a	- allocator that should be used by this container.

Exceptions

std::bad_alloc if buffer allocation fails

This constructor searches for the last valid element in the buffer, and is buffer is valid then it copies elements to the new buffer.

◆ flat_forward_list() [9/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	const_iterator const &	begin,
		const_iterator const &	last,
		AA &&	a = `AA{}`
	)

inline

Copies element pointed by the iterators.

Parameters

begin	- iterator for the buffer begin.
last	- last element that should be included in the view.
a	- allocator that should be used by this container.

Exceptions

std::bad_alloc if buffer allocation fails

◆ flat_forward_list() [10/10]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA = allocator_type>

iffl::flat_forward_list< T, TT, A >::flat_forward_list	(	flat_forward_list_view< T, TT > const &	view,
		AA &&	a = `AA{}`
	)

inline

Copies element from the view.

Parameters

view	- view over a flat forward list buffer.
a	- allocator that should be used by this container.

Exceptions

std::bad_alloc if buffer allocation fails

◆ ~flat_forward_list()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iffl::flat_forward_list< T, TT, A >::~flat_forward_list ( )

inlinenoexcept

Destructor.

Deallocates buffer owned by container.

Member Function Documentation

◆ assign() [1/6]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::assign ( buffer_view const & other_buff )

inline

Copies list from a buffer.

Parameters

other_buff - describes the other buffer.

Exceptions

std::bad_alloc if buffer allocation fails

This method does not validate if this is a valid flat forward list. It assumes that caller validated buffer before using this constructor.

◆ assign() [2/6]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::assign	(	char const *	buffer_begin,
		char const *	last_element,
		char const *	buffer_end
	)

inline

Copies list from a buffer.

Parameters

buffer_begin	- pointer to the start of the buffer that contains list.
buffer_end	- pointer to the address right after last byte in the buffer.
last_element	- pointers to the last element of the list in the buffer. If buffer does not contain any elements then this parameter must be nullptr.

Exceptions

std::bad_alloc if buffer allocation fails

This method does not validate if this is a valid flat forward list. It assumes that caller validated buffer before using this constructor.

◆ assign() [3/6]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::assign	(	char const *	buffer_begin,
		char const *	buffer_end
	)

inline

Checks if buffer contains a valid list and if it does then copies that list.

Parameters

buffer_begin	- pointer to the start of the buffer that might contains list.
buffer_end	- pointer to the buffer end.

Exceptions

std::bad_alloc if buffer allocation fails

This method searches for the last valid element in the buffer, and is buffer is valid then it copies elements to the new buffer.

◆ assign() [4/6]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::assign	(	char const *	buffer,
		size_type	buffer_size
	)

inline

Checks if buffer contains a valid list and if it does then copies that list.

Parameters

buffer	- pointer to the start of the buffer that might contains list.
buffer_size	- buffer size.

Exceptions

std::bad_alloc if buffer allocation fails

This method searches for the last valid element in the buffer, and is buffer is valid then it copies elements to the new buffer.

◆ assign() [5/6]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::assign	(	const_iterator const &	begin,
		const_iterator const &	last
	)

inline

Copies element pointed by the iterators.

Parameters

begin	- iterator for the buffer begin.
last	- last element that should be included in the view.

◆ assign() [6/6]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::assign ( flat_forward_list_view< T, TT > const & view )

inline

Copies elements from the view.

Parameters

view	- view over the flat forward list

◆ attach() [1/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::attach ( buffer_view const & other_buff )

inline

Takes ownership of a buffer.

Parameters

other_buff - describes the buffer we are attaching.

This method first clears existing content of the container. It does not validate if buffer contains a valid flat forward list. It assumes that caller validated buffer before using this constructor. After this call container is responsible for deallocating the buffer. It is responsibility of the caller to make sure that buffer was allocated using method compatible with allocator used by this container.

◆ attach() [2/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::attach	(	char *	buffer_begin,
		char *	last_element,
		char *	buffer_end
	)

inlinenoexcept

Takes ownership of a buffer.

Parameters

buffer_begin	- pointer to the start of the buffer that contains list.
buffer_end	- pointer to the address right after last byte in the buffer.
last_element	- pointers to the last element of the list in the buffer. If buffer does not contain any elements then this parameter must be nullptr.

This method first clears existing content of the container. It does not validate if buffer contains a valid flat forward list. It assumes that caller validated buffer before using this constructor. After this call container is responsible for deallocating the buffer. It is responsibility of the caller to make sure that buffer was allocated using method compatible with allocator used by this container.

◆ attach() [3/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::attach	(	char *	buffer,
		size_t	buffer_size
	)

inlinenoexcept

Takes ownership of a buffer and attempts to find last element of the list.

Parameters

buffer	- pointer to the start of the buffer that might contains list.
buffer_size	- buffer size.

This method adopts buffer, and searches for the last valid element in the buffer. If buffer validation fails then container will treat it as if it has no elements. After this call container is responsible for deallocating the buffer. It is responsibility of the caller to make sure that buffer was allocated using method compatible with allocator used by this container.

◆ back() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

T& iffl::flat_forward_list< T, TT, A >::back ( )

inlinenoexcept

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

Calling this method on a empty container will trigger fail-fast

◆ back() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

T const& iffl::flat_forward_list< T, TT, A >::back ( ) const

inlinenoexcept

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

Calling this method on a empty container will trigger fail-fast

◆ begin() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::begin ( )

inlinenoexcept

Returns: Returns an iterator pointing to the first element of container.

Calling on an empty container returns end iterator

◆ begin() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::begin ( ) const

inlinenoexcept

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

Calling on an empty container returns const end iterator

◆ cbegin()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::cbegin ( ) const

inlinenoexcept

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

Calling on an empty container returns const end iterator

◆ cend()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::cend ( ) const

inlinenoexcept

Returns: Returns an end const_iterator.

For types that support get_next_offset offset or when container is empty, the end iterator is const_iterator{}. For types that do not support get_next_offset an end iterator is pointing pass the last element of container

◆ clast()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::clast ( ) const

inlinenoexcept

Returns: Returns a const iterator pointing to the last element of container.

Calling on an empty container returns end iterator

◆ clear()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::clear ( )

inlinenoexcept

Deallocated buffer owned by this container.

After this call container is empty

◆ closed_range()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

range_t iffl::flat_forward_list< T, TT, A >::closed_range	(	const_iterator const &	begin,
		const_iterator const &	last
	)		const

inlinenoexcept

Information about the buffer occupied by elements in the range [begin, last].

Parameters

begin	- iterator pointing to the first element.
last	- iterator pointing to the last element in the range.

Returns

For any case, except when last element of range is last element of the collection, it returns:

start of the first element.
offset of the last element data end.
offset of the last element buffer end. If range last is last element of collection then data end and buffer end point to the same position.

All offsets values are relative to the buffer owned by the container.

◆ contains()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::contains	(	const_iterator const &	it,
		size_type	position
	)		const

inlinenoexcept

Tells if given offset in the buffer falls into a buffer used by the element.

Parameters

it	- iterator pointing to an element
position	- offset in the container's buffer.

Returns: True if position is in the element's buffer. and false otherwise. Element's buffer is retrieved using range(it). When iterator refers to container end or when position is npos the result will be false.

◆ data() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

char* iffl::flat_forward_list< T, TT, A >::data ( )

inlinenoexcept

Returns: Pointer to the begging of the buffer or nullptr container has if no allocated buffer.

◆ data() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

char const* iffl::flat_forward_list< T, TT, A >::data ( ) const

inlinenoexcept

Returns: Const pointer to the begging of the buffer or nullptr container has if no allocated buffer.

◆ detach()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

buffer_ref iffl::flat_forward_list< T, TT, A >::detach ( )

inlinenoexcept

Container releases ownership of the buffer.

After the call completes, container is empty.

Returns: Returns buffer information to the caller. Caller is responsible for deallocating returned buffer.

◆ element_add_size()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::element_add_size	(	iterator const &	it,
		size_type	size_to_add
	)

inline

Adds unused capacity to the element.

Parameters

it	- iterator that points to the element to grow.
size_to_add	- bytes to add to the current element size

Exceptions

std::bad_alloc if allocating new buffer fails.

This method also fixes alignment of element and adds missing padding. added capacity becomes unused capacity that is reserved for future use. Unused capacity is zero initialized.

◆ element_resize()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

iterator iffl::flat_forward_list< T, TT, A >::element_resize	(	iterator const &	it,
		size_type	new_size,
		F const &	fn
	)

inline

Resizes element.

Template Parameters

F	- type of functor user to update element.

Parameters

it	- iterator that points to the element that is being resized.
new_size	- new element size.
fn	- functor used to update element after it was resized.

Exceptions

std::bad_alloc if allocating new buffer fails.

Resizing to 0 will delete element. Resizing to size smaller than minimum_size will trigger fail-fast. Resizing to any other size also fixes alignment of element and adds missing padding.

◆ emplace()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

iterator iffl::flat_forward_list< T, TT, A >::emplace	(	iterator const &	it,
		size_type	new_element_size,
		F const &	fn
	)

inline

Constructs new element at the position described by iterator. Element is initialized with a help of the functor passed as a parameter.

Template Parameters

F	- type of a functor

Parameters

it	- iterator pointing to the position new element should be inserted to. Iterator value must be a valid iterator pointing to one of the elements or an end iterator. If iterator is pointing to an element that is not properly aligned then new element will not be properly aligned. When iterator in not then end then size is padded to make sure that if this element is properly aligned then next element is also property aligned.
new_element_size	- number of bytes required for the new element.
fn	- a functor used to construct new element.

Returns: Returns a pair of boolean that tells caller if element was inserted, and iterator to the position where it should be inserted in case of failure or was inserted in case of success.

Exceptions

std::bad_alloca if allocating new buffer fails. Any exceptions that might be raised by the functor. If functor raises then container remains in the state as if call did not happen

Constructed element does not have to use up the entire buffer unused space will become unused buffer capacity.

◆ emplace_back()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

void iffl::flat_forward_list< T, TT, A >::emplace_back	(	size_type	element_size,
		F const &	fn
	)

inline

Constructs new element at the end of the list.

Template Parameters

F	- type of a functor Element is initialized with a help of the functor passed as a parameter.

Parameters

element_size	- number of bytes required for the new element.
fn	- a functor used to construct new element.

Exceptions

std::bad_alloca if allocating new buffer fails. Any exceptions that might be raised by the functor. If functor raises then container remains in the state as if call did not happen

Constructed element does not have to use up the entire buffer unused space will become unused buffer capacity.

◆ emplace_front()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

void iffl::flat_forward_list< T, TT, A >::emplace_front	(	size_type	element_size,
		F const &	fn
	)

inline

Inserts new element at the beginning of the container. Element is initialized with a help of the functor passed as a parameter.

Template Parameters

F	- type of a functor

Parameters

element_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast. When container is not empty then size is padded to make sure that next element is also property aligned.
fn	- a functor used to construct new element.

Exceptions

std::bad_alloca if allocating new buffer fails. Any exceptions that might be raised by the functor. If functor raises then container remains in the state as if call did not happen

◆ empty()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::empty ( ) const

inlinenoexcept

Tells if container contains no elements.

Returns: False when container contains at least one element and true otherwise.

Both container with no buffer as well as container that has buffer that does not contain any valid elements will return true.

◆ end() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::end ( )

inlinenoexcept

Returns: Returns an end iterator.

An end iterator is pointing pass the last element of container

◆ end() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::end ( ) const

inlinenoexcept

Returns: Returns an end const_iterator.

An end iterator is pointing pass the last element of container

◆ erase() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::erase ( iterator const & it )

inlinenoexcept

Erases element pointed by iterator.

Parameters

it	- iterator pointing to the element being erased.

This gives us erase semantics everyone is used to, but algorithm complexity is O(element count) if we are erasing last element because we need to find element before the element being erased, and make it last.

◆ erase() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::erase	(	iterator const &	start,
		iterator const &	end
	)

inlinenoexcept

Erases element in the range [start, end).

Parameters

start	- first element to be erased.
end	- one pass the last element that is being erased.

This gives us erase semantics everyone is used to, but algorithm complexity is O(element count) if we are erasing all element till the end of container, because we need to find element before the element being erased, and make it last.

◆ erase_after()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::erase_after ( iterator const & it )

inlinenoexcept

Erases element after the element pointed by the iterator.

Parameters

it	- iterator pointing to an element before the element that will be erased. If iterator is pointing to the last element of container then it will trigger fail-fast.

◆ erase_after_half_closed()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::erase_after_half_closed	(	iterator const &	before_start,
		iterator const &	last
	)

inlinenoexcept

Erases element in the range (before_start, last].

Parameters

before_start	- iterator pointing to an element before the first element that will be erased. If iterator is pointing to the last element of container then it will trigger fail-fast.
last	- iterator pointing to the last element to be erased. if this iterator is end then it will erase all elements after before_start.

Usual pair of iterators define a half opened range [start, end) Note that in this case our range is (start, last]. In other words we will erase all elements after start, including last.

◆ erase_all_after()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::erase_all_after ( iterator const & it )

inlinenoexcept

Erases element in the range (before_start, end)

Parameters

it	- iterator pointing to an element before the first element that will be erased. If iterator is pointing to the last element of container then it will trigger fail-fast.

◆ erase_all_from()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::erase_all_from ( iterator const & it )

inlinenoexcept

Erases element in the range [it, end)

Parameters

it	- iterator to the first element to be erased

This algorithm has complexity O(element count) because to erase element pointed by it we need to locate element before and make it new last element.

◆ fill_padding()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::fill_padding	(	int	fill_byte = `0`,
		bool	zero_unused_capacity = `true`
	)

inlinenoexcept

Fills parts of the buffer not used by element data with fill_byte.

Parameters

fill_byte	- pattern to use
zero_unused_capacity	- also fill container unused capacity true by default.

◆ find_element_after() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::find_element_after ( size_type position )

inlinenoexcept

Searches for an element after the element that contains given position.

Parameters

position - offset in the container's buffer

Returns: Iterator to the found element, if it was found, and container's end iterator otherwise.

Cost of this algorithm is O(number of elements in container) because we have to performs linear search for an element from the start of container's buffer.

◆ find_element_after() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::find_element_after ( size_type position ) const

inlinenoexcept

Searches for an element after the element that contains given position.

Parameters

position - offset in the container's buffer

Returns: Const iterator to the found element, if it was found, and container's end const iterator otherwise.

Cost of this algorithm is O(number of elements in container) because we have to performs linear search for an element from the start of container's buffer.

◆ find_element_at() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::find_element_at ( size_type position )

inlinenoexcept

Searches for an element that contains given position.

Parameters

position - offset in the container's buffer

Returns: Iterator to the found element, if it was found, and container's end iterator otherwise.

Cost of this algorithm is O(number of elements in container) because we have to performs linear search for an element from the start of container's buffer.

◆ find_element_at() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::find_element_at ( size_type position ) const

inlinenoexcept

Searches for an element that contains given position.

Parameters

position - offset in the container's buffer

Returns: Const iterator to the found element, if it was found, and container's end const iterator otherwise.

Cost of this algorithm is O(number of elements in container) because we have to performs linear search for an element from the start of container's buffer.

◆ find_element_before() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::find_element_before ( size_type position )

inlinenoexcept

Searches for an element before the element that contains given position.

Parameters

position - offset in the container's buffer

Returns: Iterator to the found element, if it was found, and container's end iterator otherwise.

Cost of this algorithm is O(number of elements in container) because we have to perform linear search for an element from the start of container's buffer.

◆ find_element_before() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::find_element_before ( size_type position ) const

inlinenoexcept

Searches for an element before the element that contains given position.

Parameters

position - offset in the container's buffer

Returns: Const iterator to the found element, if it was found, and container's end const iterator otherwise.

Cost of this algorithm is O(number of elements in container) because we have to performs linear search for an element from the start of container's buffer.

◆ front() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

T& iffl::flat_forward_list< T, TT, A >::front ( )

inlinenoexcept

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

Calling this method on a empty container will trigger fail-fast

◆ front() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

T const& iffl::flat_forward_list< T, TT, A >::front ( ) const

inlinenoexcept

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

Calling this method on a empty container will trigger fail-fast

◆ get_allocator() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

allocator_type& iffl::flat_forward_list< T, TT, A >::get_allocator ( ) &

inlinenoexcept

Returns reference to the allocator used by this container.

Returns: Allocator reference.

◆ get_allocator() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

allocator_type const& iffl::flat_forward_list< T, TT, A >::get_allocator ( ) const &

inlinenoexcept

Returns const reference to the allocator used by this container.

Returns: Allocator const reference.

◆ half_open_range()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

range_t iffl::flat_forward_list< T, TT, A >::half_open_range	(	const_iterator const &	begin,
		const_iterator const &	end
	)		const

inlinenoexcept

Information about the buffer occupied by elements in the range [begin, end).

Parameters

begin	- iterator pointing to the first element.
end	- iterator pointing to the past last element in the range.

Returns

For any case, except when end element of range is the end element of the collection,

start of the first element.
offset of the element before end data end.
offset of the element before end buffer end. If range end is collection end then data end and buffer end point to the same position.

All offsets values are relative to the buffer owned by the container. Algorithm has complexity O(number of elements in collection) because to find element before end we have to scan buffer from beginning.

◆ insert()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::insert	(	iterator const &	it,
		size_type	init_buffer_size,
		char const *	init_buffer = `nullptr`
	)

inline

Inserts new element at the position described by iterator. Element is initialized by copping provided buffer.

Parameters

it	- iterator pointing to the position new element should be inserted to. Iterator value must be a valid iterator pointing to one of the elements or an end iterator. If iterator is pointing to an element that is not properly aligned then new element will not be properly aligned.
init_buffer_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast. When iterator in not then end then size is padded to make sure that if this element is properly aligned then next element is also property aligned.
init_buffer	- a pointer to the buffer. If pointer to the buffer is nullptr then element data are zero initialized.

Exceptions

std::bad_alloca if allocating new buffer fails.

New element becomes a new last element and, if set_next offset is supported, then it is called on the previous last element such that it points to the new one.

◆ is_compatible_allocator()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename AA >

bool iffl::flat_forward_list< T, TT, A >::is_compatible_allocator ( AA const & other_allocator ) const

inlinenoexcept

Compares if allocator used by container is equivalent to the other allocator.

Parameters

other_allocator - allocator we are comparing to

Returns: True if allocators are equivalent, and false otherwise.

◆ last() [1/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

iterator iffl::flat_forward_list< T, TT, A >::last ( )

inlinenoexcept

Returns: Returns an iterator pointing to the last element of container.

Calling on an empty container returns end iterator

◆ last() [2/2]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

const_iterator iffl::flat_forward_list< T, TT, A >::last ( ) const

inlinenoexcept

Returns: Returns a const iterator pointing to the last element of container.

Calling on an empty container returns end iterator

◆ max_size()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::max_size ( ) const

inlinenoexcept

Returns maximum size.

Returns: Maximum size.

For this container it is maximum number of bytes that can be allocated through allocator used by this container

◆ merge()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<class F >

void iffl::flat_forward_list< T, TT, A >::merge	(	flat_forward_list< T, TT, A > &	other,
		F const &	fn
	)

inline

Merges two linked list ordering lists using comparison functor.

Template Parameters

F	- type of comparison functor

Parameters

fn	- comparison functor
other	- the other list we are merging with

Exceptions

Might throw std::bad_alloc when allocation fails.

if both lists are sorted, and we are merging using the same compare functor, then merged list will be sorted.

◆ operator=() [1/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

flat_forward_list& iffl::flat_forward_list< T, TT, A >::operator= ( flat_forward_list< T, TT, A > && other )

inlinenoexcept

Move assignment operator.

Parameters

◆ operator=() [2/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

flat_forward_list& iffl::flat_forward_list< T, TT, A >::operator= ( flat_forward_list< T, TT, A > const & other )

inline

Copy assignment operator.

Parameters

◆ operator=() [3/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

flat_forward_list& iffl::flat_forward_list< T, TT, A >::operator= ( buffer_view const & other_buff )

inline

Copy assignment operator.

Parameters

other_buff - linked list we are copying from

Exceptions

std::bad_alloc when allocating buffer fails

This function first attempts to copy allocator, if it is supported, and after that allocates new buffer and copies all elements to the new buffer.

◆ pop_back()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::pop_back ( )

inlinenoexcept

Removes last element from the list.

This method has cost O(number of elements). Cost comes from scanning buffer from beginning to find element before the current last element. Since this is a single linked list we have no faster way to locate it. Element before current last element will become new last element.

◆ pop_front()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::pop_front ( )

inlinenoexcept

Removes first element from the container.

Calling on empty container will trigger fail-fast

◆ push_back()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::push_back	(	size_type	init_buffer_size,
		char const *	init_buffer = `nullptr`
	)

inline

Adds new element to the end of the list. Element is initialized by copping provided buffer.

Parameters

init_buffer_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast.
init_buffer	- a pointer to the buffer. If pointer to the buffer is nullptr then element data are zero initialized.

Exceptions

std::bad_alloca if allocating new buffer fails

New element becomes a new last element and, if set_next offset is supported, then it is called on the previous last element such that it points to the new one.

◆ push_front()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::push_front	(	size_type	init_buffer_size,
		char const *	init_buffer = `nullptr`
	)

inline

Constructs new element at the beginning of the container. Element is initialized by copping provided buffer.

Parameters

init_buffer_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast. When container is not empty then size is padded to make sure that next element is also property aligned.
init_buffer	- a pointer to the buffer. If pointer to the buffer is nullptr then element data are zero initialized.

Exceptions

std::bad_alloca if allocating new buffer fails.

◆ range()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

range_t iffl::flat_forward_list< T, TT, A >::range ( const_iterator const & it ) const

inlinenoexcept

Information about the buffer occupied by an element.

Parameters

it	- iterator pointing to an element.

Returns

For any element except the last, it returns:

start element offset.
offset of element data end.
offset of element buffer end. For the last element data end and buffer end point to the same position.

All offsets values are relative to the buffer owned by the container.

◆ remaining_capacity()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::remaining_capacity ( ) const

inlinenoexcept

Returns: Number of bytes in the buffer not used by the existing elements.

◆ remove_if()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

void iffl::flat_forward_list< T, TT, A >::remove_if ( F const & fn )

inlinenoexcept

Removes all elements that satisfy predicate.

Template Parameters

F	- type of predicate

Parameters

fn	- predicate functor

◆ required_size()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::required_size ( const_iterator const & it ) const

inlinenoexcept

Returns capacity used by the element's data.

Parameters

it	- iterator pointing to the element we are returning size for.

Returns: Returns size of the element without padding

◆ resize_buffer()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::resize_buffer ( size_type size )

inline

Resizes buffer.

Parameters

size	- new buffer size Passing 0 has same effect as clearing container Setting buffer size to the value smaller than first element size will produce empty list.

Exceptions

std::bad_alloca if allocating new buffer fails

Allocates new buffer of specified size, and copies all elements that can fit to the new buffer size. all other elements will be erased. Resizing buffer to the larger capacity will add unused capacity. This can help reduce buffer reallocations when adding new elements to the buffer. Resizing to capacity smaller than used capacity will end up erasing elements that do not fit to the new buffer size.

◆ revalidate_data()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::revalidate_data ( size_type data_size = npos )

inlinenoexcept

Validates that buffer contains a valid list.

Parameters

data_size - upper watermark for the valid data.

Returns: true if valid list was found and false otherwise.

You must call this method after passing pointer to container's buffer to a function that might change buffer content. If valid list of found then buff().last will be pointing to the element that was found. If no valid list was found then buff().last will be nullptr.

◆ reverse()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::reverse ( )

inline

Reverses elements of the list.

Exceptions

Might throw std::bad_alloc when allocation fails

◆ shrink_to_fit() [1/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::shrink_to_fit ( )

inline

Removes unused padding of each element and at the tail.

Exceptions

std::bad_alloc if allocating new buffer fails.

This method also fixes alignment of each element and adds missing padding, so at the end used capacity might grow. Once unused capacity of each element is removed, and missing padding added, this method reallocates buffer to remove any unused capacity at the tail.

◆ shrink_to_fit() [2/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::shrink_to_fit	(	iterator const &	first,
		iterator const &	end
	)

inline

Removes unused padding of each element in the range [first, end).

Parameters

first	- iterator that points to the first element to shrink.
end	- iterator that points past the last element.

Exceptions

std::bad_alloc if allocating new buffer fails.

This method also fixes alignment of each element and adds missing padding, so at the end used capacity might grow.

◆ shrink_to_fit() [3/3]

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::shrink_to_fit ( iterator const & it )

inline

Removes unused padding of an element.

Parameters

it	- iterator that points to the element to shrink.

Exceptions

std::bad_alloc if allocating new buffer fails.

This method also fixes alignment of element and adds missing padding, so at the end used capacity might grow.

◆ size()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::size ( ) const

inlinenoexcept

Number of elements in the container.

Returns: Number of elements in the container.

Cost of this algorithm is O(number of elements in container). Container does not actively cache/updates element count so we need to scan list to find number of elements.

◆ sort()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename LESS_F >

void iffl::flat_forward_list< T, TT, A >::sort ( LESS_F const & fn )

inline

Sorts elements of container using comparator passed as a parameter.

Template Parameters

LESS_F - type of comparator

Parameters

fn	- instance of comparator

Algorithm complexity is O(n*log(n)+2*n)

Exceptions

Might throw std::bad_alloc when allocation fails

◆ swap()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::swap ( flat_forward_list< T, TT, A > & other )

inlinenoexcept

Swaps content of this container and the other container.

Parameters

other - reference to the other container

Exceptions

might throw std::bad_alloc if allocator swap throws or if allocators do not support swap, and we need to make a copy of elements, which involves allocation.

◆ tail_shrink_to_fit()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

void iffl::flat_forward_list< T, TT, A >::tail_shrink_to_fit ( )

inline

Resizes buffer to the used capacity.

Allocates new buffer of exact size that is required to keep all elements, moves all elements there and deallocates old buffer. If buffer already has no unused capacity then this call is no-op.

◆ total_capacity()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::total_capacity ( ) const

inlinenoexcept

Returns: Buffer size.

◆ try_element_add_size()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::try_element_add_size	(	iterator const &	it,
		size_type	size_to_add
	)

inline

Adds unused capacity to the element.

Parameters

it	- iterator that points to the element to grow.
size_to_add	- bytes to add to the current element size

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

This method also fixes alignment of element and adds missing padding. added capacity becomes unused capacity that is reserved for future use. Unused capacity is zero initialized.

◆ try_element_resize()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

bool iffl::flat_forward_list< T, TT, A >::try_element_resize	(	iterator const &	it,
		size_type	new_size,
		F const &	fn
	)

inline

Resizes element.

Template Parameters

F	- type of functor user to update element.

Parameters

it	- iterator that points to the element that is being resized.
new_size	- new element size.
fn	- functor used to update element after it was resized.

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

Resizing to 0 will delete element. Resizing to size smaller than minimum_size will trigger fail-fast. Resizing to any other size also fixes alignment of element and adds missing padding.

◆ try_emplace()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

bool iffl::flat_forward_list< T, TT, A >::try_emplace	(	iterator const &	it,
		size_type	new_element_size,
		F const &	fn
	)

inline

Constructs new element at the position described by iterator. Element is initialized with a help of the functor passed as a parameter.

Template Parameters

F	- type of a functor

Parameters

it	- iterator pointing to the position new element should be inserted to. Iterator value must be a valid iterator pointing to one of the elements or an end iterator. If iterator is pointing to an element that is not properly aligned then new element will not be properly aligned. When iterator in not then end then size is padded to make sure that if this element is properly aligned then next element is also property aligned.
new_element_size	- number of bytes required for the new element.
fn	- a functor used to construct new element.

Returns: Returns a pair of boolean that tells caller if element was inserted, and iterator to the position where it should be inserted in case of failure or was inserted in case of success.; true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

Constructed element does not have to use up the entire buffer unused space will become unused buffer capacity.

◆ try_emplace_back()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

bool iffl::flat_forward_list< T, TT, A >::try_emplace_back	(	size_type	element_size,
		F const &	fn
	)

inline

Constructs new element at the end of the list if it fits in the existing free capacity.

Template Parameters

F	- type of a functor Element is initialized with a help of the functor passed as a parameter.

Parameters

element_size	- number of bytes required for the new element.
fn	- a functor used to construct new element.

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

Constructed element does not have to use up the entire buffer unused space will become unused buffer capacity.

◆ try_emplace_front()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

bool iffl::flat_forward_list< T, TT, A >::try_emplace_front	(	size_type	element_size,
		F const &	fn
	)

inline

Inserts new element at the beginning of the container. Element is initialized with a help of the functor passed as a parameter.

Template Parameters

F	- type of a functor

Parameters

element_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast. When container is not empty then size is padded to make sure that next element is also property aligned.
fn	- a functor used to construct new element.

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

◆ try_insert()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::try_insert	(	iterator const &	it,
		size_type	init_buffer_size,
		char const *	init_buffer = `nullptr`
	)

inline

Inserts new element at the position described by iterator. Element is initialized by copping provided buffer.

Parameters

it	- iterator pointing to the position new element should be inserted to. Iterator value must be a valid iterator pointing to one of the elements or an end iterator. If iterator is pointing to an element that is not properly aligned then new element will not be properly aligned.
init_buffer_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast. When iterator in not then end then size is padded to make sure that if this element is properly aligned then next element is also property aligned.
init_buffer	- a pointer to the buffer. If pointer to the buffer is nullptr then element data are zero initialized.

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

New element becomes a new last element and, if set_next offset is supported, then it is called on the previous last element such that it points to the new one.

◆ try_push_back()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::try_push_back	(	size_type	init_buffer_size,
		char const *	init_buffer = `nullptr`
	)

inline

Adds new element to the end of the list. Element is initialized by copping provided buffer.

Parameters

init_buffer_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast.
init_buffer	- a pointer to the buffer. If pointer to the buffer is nullptr then element data are zero initialized.

Exceptions

std::bad_alloca if allocating new buffer fails

New element becomes a new last element and, if set_next offset is supported, then it is called on the previous last element such that it points to the new one.

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

◆ try_push_front()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

bool iffl::flat_forward_list< T, TT, A >::try_push_front	(	size_type	init_buffer_size,
		char const *	init_buffer = `nullptr`
	)

inline

Constructs new element at the beginning of the container. Element is initialized by copping provided buffer.

Parameters

init_buffer_size	- size of the buffer that will be used for initialization size smaller than minimum element size will trigger a fail-fast. When container is not empty then size is padded to make sure that next element is also property aligned.
init_buffer	- a pointer to the buffer. If pointer to the buffer is nullptr then element data are zero initialized.

Returns: true if element was placed in the existing buffer and false if buffer does not have enough capacity for the new element.

◆ unique()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename F >

void iffl::flat_forward_list< T, TT, A >::unique ( F const & fn )

inlinenoexcept

If there are multiple equivalent elements next to each other then first one is kept, and all other are deleted.

Template Parameters

F	- type of comparison functor

Parameters

fn	- comparison functor

◆ used_capacity()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::used_capacity ( ) const

inlinenoexcept

Returns: Number of bytes in the buffer used by existing elements.

◆ used_size()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

size_type iffl::flat_forward_list< T, TT, A >::used_size ( const_iterator const & it ) const

inlinenoexcept

Parameters

it	- iterator pointing to the element we are returning size for.

Returns: For any element except last returns distance from element start to the start of the next element. For the last element it returns used_capacity

Friends And Related Function Documentation

◆ flat_forward_list_ref

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>

template<typename TU , typename TTU >

friend class flat_forward_list_ref

friend

Give flat_forward_list_ref friend permissins so it can initialize itself from the buffer

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

include/iffl_list.h

Public Types

Public Member Functions

Static Public Attributes

Friends

Detailed Description

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>> class iffl::flat_forward_list< T, TT, A >

Member Typedef Documentation

◆ buffer_type

Constructor & Destructor Documentation

◆ flat_forward_list() [1/10]

◆ flat_forward_list() [2/10]

◆ flat_forward_list() [3/10]

◆ flat_forward_list() [4/10]

◆ flat_forward_list() [5/10]

◆ flat_forward_list() [6/10]

◆ flat_forward_list() [7/10]

◆ flat_forward_list() [8/10]

◆ flat_forward_list() [9/10]

◆ flat_forward_list() [10/10]

◆ ~flat_forward_list()

Member Function Documentation

◆ assign() [1/6]

◆ assign() [2/6]

◆ assign() [3/6]

◆ assign() [4/6]

◆ assign() [5/6]

◆ assign() [6/6]

◆ attach() [1/3]

◆ attach() [2/3]

◆ attach() [3/3]

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clast()

◆ clear()

◆ closed_range()

◆ contains()

◆ data() [1/2]

◆ data() [2/2]

◆ detach()

◆ element_add_size()

◆ element_resize()

◆ emplace()

◆ emplace_back()

◆ emplace_front()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ erase_after()

◆ erase_after_half_closed()

◆ erase_all_after()

◆ erase_all_from()

◆ fill_padding()

◆ find_element_after() [1/2]

◆ find_element_after() [2/2]

◆ find_element_at() [1/2]

◆ find_element_at() [2/2]

◆ find_element_before() [1/2]

◆ find_element_before() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ get_allocator() [1/2]

◆ get_allocator() [2/2]

◆ half_open_range()

◆ insert()

◆ is_compatible_allocator()

◆ last() [1/2]

◆ last() [2/2]

◆ max_size()

◆ merge()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ pop_back()

◆ pop_front()

template<typename T, typename TT = flat_forward_list_traits<T>, typename A = std::allocator<T>>
class iffl::flat_forward_list< T, TT, A >