Contiguous dynamic array with N elements of inline storage. More...

#include <tpl_small_vector.H>

Inheritance diagram for Aleph::SmallVector< T, N >:

Collaboration diagram for Aleph::SmallVector< T, N >:

Public Types
using	Item_Type = T
	Aleph convention: element type.

using	value_type = T
	STL convention: value type.

using	size_type = size_t
	STL convention: size type.

using	iterator = T *
	Random-access iterator.

using	const_iterator = const T *
	Random-access const iterator.

Public Member Functions
	SmallVector () noexcept
	Construct an empty vector using the inline storage. Never allocates.

	SmallVector (const size_t n, const T &value)
	Construct with `n` copies of `value`.

	SmallVector (std::initializer_list< T > l)
	Construct from an initializer list.

template<std::input_iterator It>
	SmallVector (It first, It last)
	Construct from an iterator range.

	SmallVector (const SmallVector &v)
	Copy constructor (requires copyable `T`).

	SmallVector (SmallVector &&v) noexcept(std::is_nothrow_move_constructible_v< T >)
	Move constructor.

SmallVector &	operator= (const SmallVector &v)
	Copy assignment (requires copyable `T`).

SmallVector &	operator= (SmallVector &&v) noexcept(std::is_nothrow_move_constructible_v< T >)
	Move assignment. The source is left empty.

	~SmallVector ()

void	swap (SmallVector &v) noexcept(std::is_nothrow_move_constructible_v< T >)
	Swap contents with `v`.

size_t	size () const noexcept
	Return the number of stored elements. O(1).

size_t	capacity () const noexcept
	Return the current capacity (inline or heap). O(1).

bool	is_empty () const noexcept
	Return `true` if no elements are stored. O(1).

bool	is_small () const noexcept
	Return `true` while the elements still live in the inline buffer. O(1).

void	reserve (const size_t cap)
	Reserve capacity for at least `cap` elements.

void	empty () noexcept
	Destroy all elements (Aleph convention).

void	clear () noexcept
	Destroy all elements. Alias of `empty()`. Capacity is kept.

T &	operator[] (size_t i)
	Checked access to the i-th element.

const T &	operator[] (size_t i) const
	Checked const access to the i-th element (throws `std::out_of_range`).

T &	operator() (size_t i) noexcept
	Unchecked access to the i-th element (must be `< size()`).

const T &	operator() (size_t i) const noexcept
	Unchecked const access to the i-th element (must be `< size()`).

T &	get_first ()
	First element (checked).

const T &	get_first () const

T &	get_last ()
	Last element (checked).

const T &	get_last () const

T *	data () noexcept
	Pointer to the contiguous element storage. O(1).

const T *	data () const noexcept

template<class... Args>
T &	emplace_back (Args &&...args)
	Construct an element in place at the end.

T &	append (const T &item)
	Append a copy of `item`.

T &	append (T &&item)
	Append `item` by moving.

void	append_range (const T *first, const size_t count)
	Append `count` copies from `[first, first + count)`, in order.

T &	push_back (const T &item)
	STL-style alias of `append(const T &)`.

T &	push_back (T &&item)
	STL-style alias of `append(T &&)`.

T	remove_last ()
	Remove and return the last element.

void	pop_back ()
	Remove the last element (STL style).

T &	insert (size_t pos, T item)
	Insert an element at position `pos`, shifting the tail right.

void	erase (const size_t pos)
	Remove the element at position `pos`, shifting the tail left.

iterator	begin () noexcept
	Iterator to the first element. O(1).

iterator	end () noexcept
	Iterator past the last element. O(1).

const_iterator	begin () const noexcept
	Const iterator to the first element. O(1).

const_iterator	end () const noexcept
	Const iterator past the last element. O(1).

const_iterator	cbegin () const noexcept
	Const iterator to the first element. O(1).

const_iterator	cend () const noexcept
	Const iterator past the last element. O(1).

template<class Operation >
bool	traverse (Operation operation)
	Traverse elements in order while `operation` returns `true`.

template<class Operation >
bool	traverse (Operation operation) const
	Const traversal in order while `operation` returns `true`.

template<size_t M>
bool	operator== (const SmallVector< T, M > &v) const
	Equality: same size and pairwise equal elements.

template<size_t M>
bool	operator!= (const SmallVector< T, M > &v) const
	Inequality: negation of `operator==`.

Private Member Functions
T *	inline_ptr () noexcept

const T *	inline_ptr () const noexcept

void	relocate (const size_t new_cap)

void	grow (const size_t min_cap)

void	steal (SmallVector &&o) noexcept(std::is_nothrow_move_constructible_v< T >)

void	release () noexcept

Static Private Member Functions
static T *	allocate (size_t m)

static void	deallocate (T *p, size_t m) noexcept

Private Attributes
std::byte	storage_ [N *sizeof(T)]

T *	ptr_

size_t	n_ = 0

size_t	cap_ = N

Detailed Description

template<typename T, size_t N = 8>
class Aleph::SmallVector< T, N >

Contiguous dynamic array with N elements of inline storage.

Elements live inside the object until the size exceeds N, at which point the contents move to a heap buffer that grows geometrically (factor 2). The container never returns to inline storage once spilled (even if it shrinks below N), so pointers into a heap-mode vector are only invalidated by growth.

Template Parameters

T	Element type. Must be move-constructible. Copy operations additionally require copy-constructible/assignable `T`.
N	Number of inline slots (must be positive). Choose it from the common-case size of the data, not the worst case.

Iterators: Plain pointers (T * / const T *): contiguous, random access. Growth reallocates and invalidates all iterators and references.

Aleph conventions: Following the library convention (see Array), empty() clears the container and is_empty() is the emptiness predicate. Both append and push_back names are provided.

Exception Safety: Growth offers the strong guarantee when T has a non-throwing move constructor or is copyable (std::move_if_noexcept semantics).

Thread Safety: Distinct instances may be used from distinct threads. Concurrent access to the same instance requires external synchronization.

Example: SmallVector<int, 8> v; // 8 slots inline, zero allocations

for (int i = 0; i < 8; ++i)

v.append(i); // still inline

v.append(8); // spills to heap

assert(not v.is_small());

Aleph::SmallVector
Contiguous dynamic array with N elements of inline storage.
Definition tpl_small_vector.H:118

Aleph::SmallVector::append
T & append(const T &item)
Append a copy of item.
Definition tpl_small_vector.H:555

Aleph::SmallVector::is_small
bool is_small() const noexcept
Return true while the elements still live in the inline buffer. O(1).
Definition tpl_small_vector.H:416

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466

Definition at line 117 of file tpl_small_vector.H.

Member Typedef Documentation

◆ const_iterator

template<typename T , size_t N = 8>

using Aleph::SmallVector< T, N >::const_iterator = const T *

Random-access const iterator.

Definition at line 240 of file tpl_small_vector.H.

◆ Item_Type

template<typename T , size_t N = 8>

using Aleph::SmallVector< T, N >::Item_Type = T

Aleph convention: element type.

Definition at line 236 of file tpl_small_vector.H.

◆ iterator

template<typename T , size_t N = 8>

using Aleph::SmallVector< T, N >::iterator = T *

Random-access iterator.

Definition at line 239 of file tpl_small_vector.H.

◆ size_type

template<typename T , size_t N = 8>

using Aleph::SmallVector< T, N >::size_type = size_t

STL convention: size type.

Definition at line 238 of file tpl_small_vector.H.

◆ value_type

template<typename T , size_t N = 8>

using Aleph::SmallVector< T, N >::value_type = T

STL convention: value type.

Definition at line 237 of file tpl_small_vector.H.

Constructor & Destructor Documentation

◆ SmallVector() [1/6]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::SmallVector ( )

inlinenoexcept

Construct an empty vector using the inline storage. Never allocates.

Definition at line 243 of file tpl_small_vector.H.

◆ SmallVector() [2/6]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::SmallVector	(	const size_t	n,
		const T &	value
	)

inline

Construct with n copies of value.

Parameters

n	Number of elements.
value	Value copied into each element.

Exceptions

std::bad_alloc if n > N and the heap buffer cannot be allocated.

Definition at line 251 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::grow(), Aleph::SmallVector< T, N >::n_, Aleph::SmallVector< T, N >::ptr_, Aleph::SmallVector< T, N >::release(), and value.

◆ SmallVector() [3/6]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::SmallVector ( std::initializer_list< T > l )

inline

Construct from an initializer list.

Parameters

l	Elements to copy, in order.

Exceptions

std::bad_alloc if the heap buffer cannot be allocated.

Definition at line 273 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::grow(), l, Aleph::SmallVector< T, N >::n_, Aleph::SmallVector< T, N >::ptr_, Aleph::SmallVector< T, N >::release(), and Aleph::HTList::size().

◆ SmallVector() [4/6]

template<typename T , size_t N = 8>

template<std::input_iterator It>

Aleph::SmallVector< T, N >::SmallVector	(	It	first,
		It	last
	)

inline

Construct from an iterator range.

Template Parameters

It	Input iterator whose value type converts to `T`.

Parameters

first	Beginning of the range.
last	End of the range.

Exceptions

std::bad_alloc if the heap buffer cannot be allocated.

Definition at line 301 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::append(), and Aleph::SmallVector< T, N >::release().

◆ SmallVector() [5/6]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::SmallVector ( const SmallVector< T, N > & v )

inline

Copy constructor (requires copyable T).

Definition at line 316 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::grow(), Aleph::SmallVector< T, N >::n_, Aleph::SmallVector< T, N >::ptr_, and Aleph::SmallVector< T, N >::release().

◆ SmallVector() [6/6]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::SmallVector ( SmallVector< T, N > && v )

inlinenoexcept

Move constructor.

Heap-mode sources are stolen in O(1); inline-mode sources are moved element by element (O(n)). The source is left empty.

Definition at line 339 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::steal().

◆ ~SmallVector()

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::~SmallVector ( )

inline

Definition at line 369 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::release().

Member Function Documentation

◆ allocate()

template<typename T , size_t N = 8>

static T * Aleph::SmallVector< T, N >::allocate ( size_t m )

inlinestaticprivate

Definition at line 140 of file tpl_small_vector.H.

References m.

Referenced by Aleph::SmallVector< T, N >::relocate().

◆ append() [1/2]

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::append ( const T & item )

inline

Append a copy of item.

Parameters

item	Element to copy.

Returns: Mutable reference to the new element.

Exceptions

std::bad_alloc if a growing reallocation fails.

Note: Amortized O(1).

Definition at line 555 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::emplace_back().

Referenced by Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::push_back(), Aleph::SmallVector< T, N >::push_back(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ append() [2/2]

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::append ( T && item )

inline

Append item by moving.

Parameters

item	Element to move in.

Returns: Mutable reference to the new element.

Exceptions

std::bad_alloc if a growing reallocation fails.

Note: Amortized O(1).

Definition at line 567 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::emplace_back().

◆ append_range()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::append_range	(	const T *	first,
		const size_t	count
	)

inline

Append count copies from [first, first + count), in order.

Parameters

first	Pointer to the first source element. May be `nullptr` only when `count == 0` (nothing is read from it then).
count	Number of elements to copy.

Precondition: [first, first + count) is a valid range of live T objects (readable, not past-the-end of their own storage).; [first, first + count) does not overlap this vector's own element storage (i.e. first is not itself data() or a pointer derived from it), including across a reallocation this very call might trigger: if count grows the vector past capacity(), grow() relocates to a new buffer and frees the old one before any copying happens, so a first that pointed into the old buffer would already be dangling by the time it is read. Like std::memcpy, this does not support appending a vector's own elements to itself.

Exceptions

std::invalid_argument	if `first == nullptr` and `count > 0`.
std::bad_alloc	if a growing reallocation fails.
std::overflow_error	if `count` would overflow `size_t` when added to the current `size()`, or if growing the capacity to fit the result would overflow (see `grow()`'s own capacity-doubling guard).

Note: Equivalent to calling append(first[i]) for i in [0, count), in order, but faster: when T is trivially copyable, the whole range is copied with a single std::uninitialized_copy_n call instead of count individual placement-new calls (safe because a trivially copyable type's copy can never throw and has no observable side effects beyond the bytes themselves; standard library implementations lower this to a single memcpy for such types). For any other copy-constructible T, this still grows at most once for the whole range (rather than up to count times) before placement-constructing each element, with the same strong exception guarantee as append: if a mid-range copy throws, only the newly-appended elements are unwound and size() is left exactly as it was before the call.; Complexity: O(count), or O(size() + count) on the occasions this triggers a growing reallocation.; Not thread-safe: as with every other mutating method (see the class-level @par Thread Safety), concurrent calls on the same instance require external synchronization.

Definition at line 613 of file tpl_small_vector.H.

References ah_invalid_argument_if, ah_overflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::count(), Aleph::SmallVector< T, N >::grow(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by Aleph::Rope< Char, LeafSize >::build_from_view(), Aleph::Rope< Char, LeafSize >::slice(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::Rope< Char, LeafSize >::try_absorb_left(), and Aleph::Rope< Char, LeafSize >::try_absorb_right().

◆ begin() [1/2]

template<typename T , size_t N = 8>

const_iterator Aleph::SmallVector< T, N >::begin ( ) const

inlinenoexcept

Const iterator to the first element. O(1).

Definition at line 754 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

◆ begin() [2/2]

template<typename T , size_t N = 8>

iterator Aleph::SmallVector< T, N >::begin ( )

inlinenoexcept

Iterator to the first element. O(1).

Definition at line 742 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST().

◆ capacity()

template<typename T , size_t N = 8>

size_t Aleph::SmallVector< T, N >::capacity ( ) const

inlinenoexcept

Return the current capacity (inline or heap). O(1).

Definition at line 404 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::cap_.

Referenced by TEST(), TEST(), and TEST().

◆ cbegin()

template<typename T , size_t N = 8>

const_iterator Aleph::SmallVector< T, N >::cbegin ( ) const

inlinenoexcept

Const iterator to the first element. O(1).

Definition at line 766 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

◆ cend()

template<typename T , size_t N = 8>

const_iterator Aleph::SmallVector< T, N >::cend ( ) const

inlinenoexcept

Const iterator past the last element. O(1).

Definition at line 772 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

◆ clear()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::clear ( )

inlinenoexcept

Destroy all elements. Alias of empty(). Capacity is kept.

Definition at line 442 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::empty().

Referenced by TEST().

◆ data() [1/2]

template<typename T , size_t N = 8>

const T * Aleph::SmallVector< T, N >::data ( ) const

inlinenoexcept

Definition at line 520 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

◆ data() [2/2]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::data ( )

inlinenoexcept

Pointer to the contiguous element storage. O(1).

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 514 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ deallocate()

template<typename T , size_t N = 8>

static void Aleph::SmallVector< T, N >::deallocate	(	T *	p,
		size_t	m
	)

inlinestaticprivatenoexcept

Definition at line 145 of file tpl_small_vector.H.

References m.

Referenced by Aleph::SmallVector< T, N >::release(), and Aleph::SmallVector< T, N >::relocate().

◆ emplace_back()

template<typename T , size_t N = 8>

template<class... Args>

T & Aleph::SmallVector< T, N >::emplace_back ( Args &&... args )

inline

Construct an element in place at the end.

Template Parameters

Args	Argument types forwarded to `T`'s constructor.

Parameters

args	Arguments forwarded to `T`'s constructor.

Returns: Mutable reference to the new element.

Exceptions

std::bad_alloc if a growing reallocation fails.

Note: Amortized O(1). Safe even when args reference elements of this vector (the element is built before any reallocation).

Definition at line 536 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::grow(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by Aleph::SmallVector< T, N >::append(), Aleph::SmallVector< T, N >::append(), TEST(), and TEST().

◆ empty()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::empty ( )

inlinenoexcept

Destroy all elements (Aleph convention).

Capacity is kept.

Note: Following the Aleph container convention (see Array::empty()), this mutates the vector; use is_empty() to test emptiness.

Definition at line 435 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by Aleph::SmallVector< T, N >::clear(), and TEST().

◆ end() [1/2]

template<typename T , size_t N = 8>

const_iterator Aleph::SmallVector< T, N >::end ( ) const

inlinenoexcept

Const iterator past the last element. O(1).

Definition at line 760 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

◆ end() [2/2]

template<typename T , size_t N = 8>

iterator Aleph::SmallVector< T, N >::end ( )

inlinenoexcept

Iterator past the last element. O(1).

Definition at line 748 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST().

◆ erase()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::erase ( const size_t pos )

inline

Remove the element at position pos, shifting the tail left.

Parameters

pos	Position of the element to remove, in `[0, size())`.

Exceptions

std::out_of_range if pos >= size().

Note: O(n - pos) moves.

Definition at line 730 of file tpl_small_vector.H.

References ah_out_of_range_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST().

◆ get_first() [1/2]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::get_first ( )

inline

First element (checked).

Returns: Mutable reference to the first element.

Exceptions

std::underflow_error if the vector is empty.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 483 of file tpl_small_vector.H.

References ah_underflow_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST(), and TEST().

◆ get_first() [2/2]

template<typename T , size_t N = 8>

const T & Aleph::SmallVector< T, N >::get_first ( ) const

inline

Definition at line 490 of file tpl_small_vector.H.

References ah_underflow_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

◆ get_last() [1/2]

template<typename T , size_t N = 8>

Aleph::SmallVector< T, N >::get_last ( )

inline

Last element (checked).

Returns: Mutable reference to the last element.

Exceptions

std::underflow_error if the vector is empty.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 500 of file tpl_small_vector.H.

References ah_underflow_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST(), and TEST().

◆ get_last() [2/2]

template<typename T , size_t N = 8>

const T & Aleph::SmallVector< T, N >::get_last ( ) const

inline

Definition at line 507 of file tpl_small_vector.H.

References ah_underflow_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

◆ grow()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::grow ( const size_t min_cap )

inlineprivate

Definition at line 175 of file tpl_small_vector.H.

References ah_overflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, and Aleph::SmallVector< T, N >::relocate().

Referenced by Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::append_range(), Aleph::SmallVector< T, N >::emplace_back(), Aleph::SmallVector< T, N >::insert(), Aleph::SmallVector< T, N >::operator=(), and Aleph::SmallVector< T, N >::reserve().

◆ inline_ptr() [1/2]

template<typename T , size_t N = 8>

const T * Aleph::SmallVector< T, N >::inline_ptr ( ) const

inlineprivatenoexcept

Definition at line 135 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::storage_.

◆ inline_ptr() [2/2]

template<typename T , size_t N = 8>

T * Aleph::SmallVector< T, N >::inline_ptr ( )

inlineprivatenoexcept

Definition at line 130 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::storage_.

Referenced by Aleph::SmallVector< T, N >::is_small(), and Aleph::SmallVector< T, N >::release().

◆ insert()

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::insert	(	size_t	pos,
		T	item
	)

inline

Insert an element at position pos, shifting the tail right.

Parameters

pos	Insertion position in `[0, size()]`.
item	Element to insert (taken by value: pass rvalues to move).

Returns: Mutable reference to the inserted element.

Exceptions

std::out_of_range	if `pos > size()`.
std::bad_alloc	if a growing reallocation fails.

Note: O(n - pos) moves.

Definition at line 706 of file tpl_small_vector.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::grow(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST().

◆ is_empty()

template<typename T , size_t N = 8>

bool Aleph::SmallVector< T, N >::is_empty ( ) const

inlinenoexcept

Return true if no elements are stored. O(1).

Definition at line 410 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::n_.

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ is_small()

template<typename T , size_t N = 8>

bool Aleph::SmallVector< T, N >::is_small ( ) const

inlinenoexcept

Return true while the elements still live in the inline buffer. O(1).

Definition at line 416 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::inline_ptr(), and Aleph::SmallVector< T, N >::ptr_.

Referenced by Aleph::SmallVector< T, N >::release(), Aleph::SmallVector< T, N >::relocate(), Aleph::SmallVector< T, N >::swap(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ operator!=()

template<typename T , size_t N = 8>

template<size_t M>

bool Aleph::SmallVector< T, N >::operator!= ( const SmallVector< T, M > & v ) const

inline

Inequality: negation of operator==.

Definition at line 829 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()() [1/2]

template<typename T , size_t N = 8>

const T & Aleph::SmallVector< T, N >::operator() ( size_t i ) const

inlinenoexcept

Unchecked const access to the i-th element (must be < size()).

Definition at line 474 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

◆ operator()() [2/2]

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::operator() ( size_t i )

inlinenoexcept

Unchecked access to the i-th element (must be < size()).

Definition at line 468 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::ptr_.

◆ operator=() [1/2]

template<typename T , size_t N = 8>

SmallVector & Aleph::SmallVector< T, N >::operator= ( const SmallVector< T, N > & v )

inline

Copy assignment (requires copyable T).

Definition at line 346 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::grow(), Aleph::SmallVector< T, N >::n_, Aleph::SmallVector< T, N >::ptr_, and Aleph::SmallVector< T, N >::release().

◆ operator=() [2/2]

template<typename T , size_t N = 8>

SmallVector & Aleph::SmallVector< T, N >::operator= ( SmallVector< T, N > && v )

inlinenoexcept

Move assignment. The source is left empty.

Definition at line 360 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::release(), and Aleph::SmallVector< T, N >::steal().

◆ operator==()

template<typename T , size_t N = 8>

template<size_t M>

bool Aleph::SmallVector< T, N >::operator== ( const SmallVector< T, M > & v ) const

inline

Equality: same size and pairwise equal elements.

Parameters

v	Vector to compare against (any inline capacity).

Returns: true if both vectors hold equal elements in the same order.

Note: Complexity: O(n). Requires T equality comparable.

Definition at line 817 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::n_, Aleph::SmallVector< T, N >::ptr_, and Aleph::SmallVector< T, N >::size().

◆ operator[]() [1/2]

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::operator[] ( size_t i )

inline

Checked access to the i-th element.

Parameters

i	Zero-based index.

Returns: Mutable reference to the element.

Exceptions

std::out_of_range if i >= size().

Definition at line 454 of file tpl_small_vector.H.

References ah_out_of_range_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

◆ operator[]() [2/2]

template<typename T , size_t N = 8>

const T & Aleph::SmallVector< T, N >::operator[] ( size_t i ) const

inline

Checked const access to the i-th element (throws std::out_of_range).

Definition at line 461 of file tpl_small_vector.H.

References ah_out_of_range_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

◆ pop_back()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::pop_back ( )

inline

Remove the last element (STL style).

Exceptions

std::underflow_error if the vector is empty.

Note: O(1).

Definition at line 692 of file tpl_small_vector.H.

References ah_underflow_error_if, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST(), and TEST().

◆ push_back() [1/2]

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::push_back ( const T & item )

inline

STL-style alias of append(const T &).

Definition at line 663 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::append().

◆ push_back() [2/2]

template<typename T , size_t N = 8>

T & Aleph::SmallVector< T, N >::push_back ( T && item )

inline

STL-style alias of append(T &&).

Definition at line 670 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::append().

◆ release()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::release ( )

inlineprivatenoexcept

Definition at line 225 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::deallocate(), Aleph::SmallVector< T, N >::inline_ptr(), Aleph::SmallVector< T, N >::is_small(), N, Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::SmallVector(), Aleph::SmallVector< T, N >::~SmallVector(), Aleph::SmallVector< T, N >::operator=(), Aleph::SmallVector< T, N >::operator=(), and Aleph::SmallVector< T, N >::steal().

◆ relocate()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::relocate ( const size_t new_cap )

inlineprivate

Definition at line 152 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::allocate(), Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::deallocate(), Aleph::SmallVector< T, N >::is_small(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by Aleph::SmallVector< T, N >::grow().

◆ remove_last()

template<typename T , size_t N = 8>

T Aleph::SmallVector< T, N >::remove_last ( )

inline

Remove and return the last element.

Returns: The removed element, moved out.

Exceptions

std::underflow_error if the vector is empty.

Note: O(1). The storage never shrinks back to inline mode.

Definition at line 680 of file tpl_small_vector.H.

References ah_underflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST(), and TEST().

◆ reserve()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::reserve ( const size_t cap )

inline

Reserve capacity for at least cap elements.

Parameters

cap	Desired capacity. Values `<= capacity()` are no-ops.

Exceptions

std::bad_alloc if the heap buffer cannot be allocated.

Definition at line 425 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::cap_, and Aleph::SmallVector< T, N >::grow().

Referenced by TEST(), and TEST().

◆ size()

template<typename T , size_t N = 8>

size_t Aleph::SmallVector< T, N >::size ( ) const

inlinenoexcept

Return the number of stored elements. O(1).

Definition at line 398 of file tpl_small_vector.H.

References Aleph::SmallVector< T, N >::n_.

Referenced by Aleph::Rope< Char, LeafSize >::make_leaf(), Aleph::SmallVector< T, N >::operator==(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ steal()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::steal ( SmallVector< T, N > && o )

inlineprivatenoexcept

Definition at line 188 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, N, Aleph::SmallVector< T, N >::n_, Aleph::SmallVector< T, N >::ptr_, and Aleph::SmallVector< T, N >::release().

Referenced by Aleph::SmallVector< T, N >::SmallVector(), and Aleph::SmallVector< T, N >::operator=().

◆ swap()

template<typename T , size_t N = 8>

void Aleph::SmallVector< T, N >::swap ( SmallVector< T, N > & v )

inlinenoexcept

Swap contents with v.

O(1) when both vectors are in heap mode; otherwise elements are moved individually (O(n + m)).

Parameters

v	Vector to swap with.

Definition at line 381 of file tpl_small_vector.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::cap_, Aleph::SmallVector< T, N >::is_small(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST().

◆ traverse() [1/2]

template<typename T , size_t N = 8>

template<class Operation >

bool Aleph::SmallVector< T, N >::traverse ( Operation operation )

inline

Traverse elements in order while operation returns true.

Aleph-style bounded traversal: operation receives each element in index order; returning false stops the walk.

Template Parameters

Operation Callable bool(T &).

Parameters

operation Operation to apply.

Returns: true if all elements were visited, false if stopped early.

Definition at line 787 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Referenced by TEST().

◆ traverse() [2/2]

template<typename T , size_t N = 8>

template<class Operation >

bool Aleph::SmallVector< T, N >::traverse ( Operation operation ) const

inline

Const traversal in order while operation returns true.

Template Parameters

Operation Callable bool(const T &).

Parameters

operation Operation to apply.

Returns: true if all elements were visited, false if stopped early.

Definition at line 801 of file tpl_small_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::SmallVector< T, N >::n_, and Aleph::SmallVector< T, N >::ptr_.

Member Data Documentation

◆ cap_

◆ n_

template<typename T , size_t N = 8>

size_t Aleph::SmallVector< T, N >::n_ = 0

private

Definition at line 127 of file tpl_small_vector.H.

◆ ptr_

template<typename T , size_t N = 8>

T* Aleph::SmallVector< T, N >::ptr_

private

Definition at line 126 of file tpl_small_vector.H.

◆ storage_

template<typename T , size_t N = 8>

std::byte Aleph::SmallVector< T, N >::storage_[N *sizeof(T)]

private

Definition at line 125 of file tpl_small_vector.H.

Referenced by Aleph::SmallVector< T, N >::inline_ptr(), and Aleph::SmallVector< T, N >::inline_ptr().

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

tpl_small_vector.H

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ Item_Type

◆ iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ SmallVector() [1/6]

◆ SmallVector() [2/6]

◆ SmallVector() [3/6]

◆ SmallVector() [4/6]

◆ SmallVector() [5/6]

◆ SmallVector() [6/6]

◆ ~SmallVector()

Member Function Documentation

◆ allocate()

◆ append() [1/2]

◆ append() [2/2]

◆ append_range()

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ data() [1/2]

◆ data() [2/2]

◆ deallocate()

◆ emplace_back()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ get_first() [1/2]

◆ get_first() [2/2]

◆ get_last() [1/2]

◆ get_last() [2/2]

◆ grow()

◆ inline_ptr() [1/2]

◆ inline_ptr() [2/2]

◆ insert()

◆ is_empty()

◆ is_small()

◆ operator!=()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop_back()

◆ push_back() [1/2]

◆ push_back() [2/2]

◆ release()

◆ relocate()

◆ remove_last()

◆ reserve()

◆ size()

◆ steal()

◆ swap()

◆ traverse() [1/2]

◆ traverse() [2/2]

Member Data Documentation

◆ cap_

◆ n_

◆ ptr_

◆ storage_