pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout > Class Template Reference

Duplicate-preserving sorted view over owned vector payload and order. More...

#include <sorted_vector.h>

Public Types
using	permutation_type = Permutation<Index, StorageBits, Fanout, Layout>
	Underlying order-index type.
using	value_type = T
	Stored value type.
using	const_reference = const T&
	Immutable read result borrowing the owned vector.
using	size_type = std::size_t
	Count and position type.

Public Member Functions
	SortedPermutationVector (Compare compare={})
	Construct empty with a comparator.
	SortedPermutationVector (const SortedPermutationVector &)=delete
	Exclusive ownership disallows copying.
SortedPermutationVector &	operator= (const SortedPermutationVector &)=delete
	Exclusive ownership disallows copy assignment.
	SortedPermutationVector (SortedPermutationVector &&)=default
	Move vector payload, permutation, and comparator state.
SortedPermutationVector &	operator= (SortedPermutationVector &&)=default
	Replace vector payload, permutation, and comparator by move.
size_type	size () const noexcept
	Return the number of sorted values.
bool	empty () const noexcept
	Return whether this owner has no values.
const_reference	operator[] (size_type position) const
	Read one sorted zero-based value.
void	reserve (size_type count)
	Reserve append-only payload capacity.
template<class Key>
size_type	lower_bound_index (const Key &key) const
	Return the first position whose value is not ordered before key.
template<class Key>
size_type	upper_bound_index (const Key &key) const
	Return the first position whose value is ordered after key.
size_type	insert (T value)
	Insert a value before existing equivalent values.
size_type	memory_usage_bytes () const noexcept
	Return explicit requested bytes owned by this wrapper.

Static Public Member Functions
template<std::ranges::input_range Range> requires std:: constructible_from<T, std::ranges::range_rvalue_reference_t<Range>>
static SortedPermutationVector	from_range (Range &&range, Compare compare={})
	Build a sorted owner by consuming values one at a time.

Detailed Description

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>
class pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >

Duplicate-preserving sorted view over owned vector payload and order.

Values append physically to a std::vector while Permutation stores their sorted logical order. Insertion moves only order indices after the vector append, so it does not shift existing payloads. Reads return const T& into the vector; every vector reallocation invalidates those references. There is no contiguous storage promise in sorted order and no iterator interface. Bounds use predicate-guided search through the permutation tree.

Template Parameters

T	Non-bool, unqualified stored object type.
Compare	Strict weak ordering for T and lookup keys.
Index	Unsigned permutation index type with at most 64 value bits.
StorageBits	Local permutation block budget.
Fanout	Even permutation-tree fanout of at least four.
Layout	Permutation-tree child-length representation.

Constructor & Destructor Documentation

SortedPermutationVector()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::SortedPermutationVector ( Compare compare = {} )

inlineexplicit

Construct empty with a comparator.

Performs no value or permutation allocation.

Parameters

compare

Ordering relation for values and lookup keys.

Member Function Documentation

from_range()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

template<std::ranges::input_range Range>
requires std:: constructible_from<T, std::ranges::range_rvalue_reference_t<Range>>

static SortedPermutationVector pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::from_range ( Range && range, Compare compare = {} )

inlinestatic

Build a sorted owner by consuming values one at a time.

Equal incoming values are inserted before existing equivalent values. Input values append physically in input order; only the permutation describes sorted order.

Template Parameters

Range

Input range whose iterator-move result constructs T.

Parameters

range	Source consumed in iteration order.
compare	Ordering relation retained by the result.

Returns

Owner containing every input value in nondecreasing order.

Exceptions

Any	Exception from input iteration, value construction, comparison, vector growth, or permutation operations.

insert()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

size_type pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::insert ( T value )

inline

Insert a value before existing equivalent values.

The payload first appends at its next physical vector index. The permutation's atomic insert_at then places the new index at the lower-bound position. Existing payload objects are never shifted by sorted-order maintenance. If permutation insertion fails, the appended payload is removed; vector capacity and reference invalidation from its preceding growth are not rolled back.

Parameters

value

Value to own and insert.

Returns

Sorted position occupied by the new value.

Exceptions

std::length_error	If the next physical index exceeds Index.
Any	Exception from comparison, value construction, vector growth, or permutation insertion.

lower_bound_index()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

template<class Key>

size_type pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::lower_bound_index ( const Key & key ) const

inline

Return the first position whose value is not ordered before key.

Uses Compare(value,key) in the underlying permutation search. The result is in [0,size()]; size() means every stored value is before key.

Template Parameters

Key	Lookup type accepted by Compare.

Parameters

key	Lookup value; it is not stored or retained.

Returns

Lower-bound insertion position.

memory_usage_bytes()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

size_type pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::memory_usage_bytes ( ) const

inlinenoexcept

Return explicit requested bytes owned by this wrapper.

Includes wrapper/comparator bytes, vector payload capacity, and permutation allocations. Excludes allocator bookkeeping, RSS, and memory recursively owned by T. Arithmetic saturates at SIZE_MAX.

Returns

Total requested live bytes.

operator[]()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

const_reference pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::operator[] ( size_type position ) const

inline

Read one sorted zero-based value.

The result references the append-only vector payload. It remains valid until a vector reallocation or this wrapper's destruction.

Parameters

position

Position in [0,size()).

Returns

Const reference to the value at the sorted position.

Exceptions

std::out_of_range

If position >= size().

reserve()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

void pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::reserve ( size_type count )

inline

Reserve append-only payload capacity.

Does not alter sorted order. A vector reallocation invalidates all references previously returned by operator[].

Parameters

count

Minimum physical value capacity.

Exceptions

std::length_error	If count exceeds vector capacity limits.
std::bad_alloc	If vector allocation fails.

upper_bound_index()

template<class T = std::uint64_t, class Compare = std::less<>, class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

template<class Key>

size_type pixie::SortedPermutationVector< T, Compare, Index, StorageBits, Fanout, Layout >::upper_bound_index ( const Key & key ) const

inline

Return the first position whose value is ordered after key.

Uses Compare(key,value) in the underlying permutation search. The result is in [0,size()]; size() means no stored value is after key.

Template Parameters

Key	Lookup type accepted by Compare.

Parameters

key	Lookup value; it is not stored or retained.

Returns

Upper-bound position.

---

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

• include/pixie/permutations/sorted_vector.h