pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes > Class Template Reference

Duplicate-preserving sorted sequence backed by PermutableSequence. More...

#include <sorted_sequence.h>

Public Types
using	sequence_type
	Underlying owning sequence type.
using	value_type = T
	Stored value type.
using	const_reference = typename sequence_type::const_reference
	Immutable indexed result inherited from the sequence policy.
using	size_type = std::size_t
	Count and position type.

Public Member Functions
	SortedPermutableSequence (Compare compare={})
	Construct empty with a comparator.
	SortedPermutableSequence (const SortedPermutableSequence &)=delete
	Exclusive ownership disallows copying.
SortedPermutableSequence &	operator= (const SortedPermutableSequence &)=delete
	Exclusive ownership disallows copy assignment.
	SortedPermutableSequence (SortedPermutableSequence &&)=default
	Move ownership and comparator state.
SortedPermutableSequence &	operator= (SortedPermutableSequence &&)=default
	Replace ownership and comparator state by move.
size_type	size () const noexcept
	Return the number of sorted values.
bool	empty () const noexcept
	Return whether this owner is empty.
const_reference	operator[] (size_type position) const
	Read one sorted zero-based value.
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 SortedPermutableSequence	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<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>
class pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >

Duplicate-preserving sorted sequence backed by PermutableSequence.

Values are in comparator order under Compare. insert() finds the first equivalent-or-greater position and atomically inserts the owned value there. Reads retain the underlying storage policy: packed values return by value and indirect values return stable const references. There is no contiguous storage or iterator interface. Bounds use the underlying tree's predicate-guided search.

Template Parameters

T	Stored object type accepted by PermutableSequence.
Compare	Strict weak ordering for T and lookup keys.
Storage	Compile-time payload storage policy.
StorageBits	Local sequence block budget.
Fanout	Even sequence-tree fanout of at least four.
Layout	Sequence-tree child-length representation.
ChunkBytes	Indirect payload target bytes per chunk.

Member Typedef Documentation

sequence_type

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

using pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::sequence_type

Initial value:

 
      PermutableSequence<T, Storage, StorageBits, Fanout, Layout, ChunkBytes>

Underlying owning sequence type.

Constructor & Destructor Documentation

SortedPermutableSequence()

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::SortedPermutableSequence ( Compare compare = {} )

inlineexplicit

Construct empty with a comparator.

Performs no sequence allocation. The comparator is used for every bound and insertion for this owner's lifetime.

Parameters

compare

Ordering relation for values and lookup keys.

Member Function Documentation

from_range()

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

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

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

inlinestatic

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

This preserves input-range support and the underlying payload requirements without materializing a sortable temporary vector. Equal incoming values are inserted before existing equivalent values.

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, or the underlying sequence operations.

insert()

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

size_type pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::insert ( T value )

inline

Insert a value before existing equivalent values.

Computes lower_bound_index(value) and delegates to the underlying sequence's atomic insert_at. The resulting sequence remains sorted on successful return.

Parameters

value

Value to own and insert.

Returns

Sorted position occupied by the new value.

Exceptions

Any	Exception from comparison, value construction, allocation, or the underlying insert operation.

lower_bound_index()

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

template<class Key>

size_type pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::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 tree 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<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

size_type pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::memory_usage_bytes ( ) const

inlinenoexcept

Return explicit requested bytes owned by this wrapper.

Includes wrapper and comparator storage, plus all underlying sequence storage. Excludes allocator bookkeeping, RSS, and allocations owned by stored values. Arithmetic saturates at SIZE_MAX.

Returns

Total requested live bytes.

operator[]()

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

const_reference pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::operator[] ( size_type position ) const

inline

Read one sorted zero-based value.

Packed storage returns T by value. Indirect storage returns const T& whose lifetime follows the underlying sequence's documented rules.

Parameters

position

Position in [0,size()).

Returns

Value at the sorted position.

Exceptions

std::out_of_range

If position >= size().

upper_bound_index()

template<class T = std::uint64_t, class Compare = std::less<>, ElementStorage Storage = ElementStorage::automatic, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative, std::size_t ChunkBytes = 4096>

template<class Key>

size_type pixie::SortedPermutableSequence< T, Compare, Storage, StorageBits, Fanout, Layout, ChunkBytes >::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 tree 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_sequence.h