Sequences

template<typename T, typename... Properties>
using Sequence = Store<sequence<T>, Properties...>;   // written out as Store<sequence<T>, ...> in code

class Sequence

A sequence: Store<sequence<T>, Properties...>. The name Sequence stands for the resolved Store type on this page.

A sequence identifies its elements by position: positions are 0..n-1. With sorted it keeps its elements in order and takes insert instead of push_back.

Request	Representation
Store<sequence<T>>	std::vector
Store<multiset<T>, sorted>	boost::container::flat_multiset
Store<sequence<T>, stable_refs>	SegmentedVector (thread-safe with concurrent, which implies stable_refs). A sequence with stable references changes at its end only: pop_back, clear and a shrinking resize, no erase or insert at a position, which would move the elements after; with monotone, not even those.
Store<sequence<Store<sequence<T>, frozen>>>	Jagged (compressed rows, any depth)
Store<sequence<Store<...>>, fixed_shape>	Jagged built from row_lengths
Store<sequence<Row>, retains> with a retains row	RowPool

Template parameters

T

Any type; orderable with sorted. A Store as element is a row (Rows: Stores as values and elements).

P

What addresses the positions, sequence<T, P>: std::size_t by default, or an index (urd::index<U>, any indexable key). Store<sequence<Node, index<Vertex>>> is a sequence parallel to the vertices another Store numbers: operator[] and at take a vertex’s index, position gives one; it holds an element at every position below its size (no presence, unlike a dense map), and grows by push_back and resize as any sequence.

Member types

value_type is T; iterator and reference are the representation’s and are mutable where the elements change in place: a sequence that is not frozen (a monotone one included: it only never removes), not a multiset (which places elements by value), and not rows handed out as views.

Member functions

Construction, capacity (size, empty, reserve), iterators (begin, end, rbegin, rend) and comparison (==, <=>) are as for Sets.

Element access

reference operator[](P pos)

const_reference operator[](P pos) const

reference at(P pos)

const_reference at(P pos) const

reference front()

reference back()

P position(const_iterator it) const

P is std::size_t but in a sequence<T, P>; at throws std::out_of_range past the end and for what is no index (index<U>(), none). position(end()) is the position after the last.

auto data()

A pointer to the elements, with contiguous.

Modifiers

Growable (not frozen, not fixed_shape):

void push_back(const value_type &element)

void push_back(value_type &&element)

template<typename ...Args>
reference emplace_back(Args&&... args)

Sequences (the appending facet). The new element, changeable in place where the elements are.

iterator insert(const value_type &element)

template<typename ...Args>
iterator emplace(Args&&... args)

Multisets (the insertion facet): into place, by value.

iterator insert(const_iterator pos, const value_type &element)

template<typename ...Args>
iterator emplace(const_iterator pos, Args&&... args)

Sequences, at a position (not monotone).

Shrinkable (neither frozen nor monotone; monotone_until_clear keeps clear only):

iterator erase(const_iterator pos)

iterator erase(const_iterator first, const_iterator last)

void pop_back()

void clear()

friend std::size_t erase(Sequence &store, const value_type &element)

template<typename Pred>
friend std::size_t erase_if(Sequence &store, Pred pred)

As std::erase and std::erase_if.

Shape (fixed_shape)

explicit Sequence(const row_lengths &lengths)

Rows of these lengths, empty: a fixed-shape Store’s only shape. Rows of rows take a vector of row lengths per row, at any depth. With nonempty, at least one row (a row of length 0 is a row), asserted.

void reset()

Every element back to its default, every bit unset; with proportional_clear, in the rows handed out to change since the last reset only.

Complexity

Representation	ordered lookup	access	iterate	lookup	insert	erase	clear	memory	holds
vector: std::vector	—	O(1)	O(n)	—	O(1)*	O(n)	O(n)	O(n), 1.5 words	one array; retains
flat_multiset: boost::container::flat_multiset (sorted vector)	O(log n)	O(1)	O(n)	O(log n)	O(n)	O(n)	O(n)	O(n), 1.5 words	n elements in one array; retains
segmented_vector: segmented vector (elements never move)	—	O(1)	O(n)	—	O(1)*	O(1)	O(n)	O(n), 1.5 words	doubling segments; stable references
concurrent_segmented_vector: segmented vector, thread-safe appends	—	O(1)	O(n)	—	O(1)*	O(1)	O(n)	O(n), 1.6 words	doubling segments; stable references; appends from threads
row_pool: row pool (cleared rows are kept for reuse)	—	O(1)	O(n)	—	O(1)*	O(1)	O(n)	O(n), 4 words	rows kept with their storage
jagged: jagged array (CSR: offsets + one data array)	—	O(1)	O(n)	—	O(r)	O(n)	O(n)	O(n), 1.2 words	one offsets array per level
fixed_jagged: jagged array of rows changed in place (fixed shape: offsets + one data array)	—	O(1)	O(n)	—	—	—	—	O(n), 1.2 words	one offsets array per level
tracked_jagged: jagged rows that track the rows handed out to change	—	O(1)	O(n)	—	—	—	—	O(n), 1.3 words	one array, + the rows handed out to change

* amortized, ~ expected; n elements, U the key range, r a row’s length, k a delta’s changes. Memory is the heap it holds (urd::memory_usage): what it grows in, and per element (or key, or slot) at most so many words, each the size of an element and at least a machine word. The declared costs; what they measure to is in Benchmarks.

Example

using Log = Store<sequence<Event>, monotone>;                       // only grows
using Rows = Store<sequence<Store<sequence<int>, frozen>>>;             // compressed rows: one array, one of offsets
auto rows = Rows { { 1, 2, 3 }, { 4 } };
std::span<const int> first = rows[0];
using Bits = Store<sequence<Store<set<Vertex>, dense>>, fixed_shape>;   // a bit matrix
auto bits = Bits(row_lengths { 8, 8, 8 });
bits[1].insert(Vertex { 3 });