Semantics¶
Leaving out a tag you need is a bug: the program relies on something nobody keeps.
What holds of the elements. Most of these the container keeps (a guarantee: sorted, stable_refs); a few
you keep about your data (a demand: dense), and urd picks a container that relies on it, so state one only
where it holds. Each tag’s card says which. Saying less buys cheaper containers: leave a question open where nothing
reads the answer.
Question |
Tags |
Kinds |
|---|---|---|
|
set, map, multiset, sequence, pool, slots, partition |
|
|
queue |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, queue, pool, slots, partition |
|
|
map, multiset |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
map |
|
|
sequence |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
pool |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
Design by contract: guarantees the supplier keeps, preconditions the client keeps (Meyer, 1992).
What you promise about your data¶
Question |
Tags |
Kinds |
|---|---|---|
|
set, map, multiset, sequence, pool, slots, partition |
|
|
queue |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
Which keys?¶
Category any_keys, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, pool, slots, partition.
Keys are indices 0..n-1 (urd::index_of), stored by position; or few in their range.
dense¶
The keys are 0..n-1, or nearly so: indices filling their range.
Role: a demand: you promise it about the data.
In plain words: ids, indices, vertices numbered 0..n-1, small key range.
Kept by: you, about your data.
Instead of:
sparse(one answer per question).Shortest served request:
Store<set<Id>, dense>.
sparse¶
The keys are few compared to their range.
Role: a demand: you promise it about the data.
In plain words: few keys in a large range, scattered keys, arbitrary keys.
Kept by: you, about your data.
Instead of:
dense(one answer per question).Shortest served request: none in What a request resolves to.
How do priorities move?¶
Category any_priority, which promises nothing: a request that leaves the question open gets it. Asked of: queue.
A priority queue (queue<V>, by_priority) never pushed below the last popped: integral priorities go to buckets.
monotone_priority¶
A priority queue never pushed below the last popped.
Role: a demand: you promise it about the data.
In plain words: dijkstra, non-negative lengths, event simulation.
Kept by: you, about your data.
Shortest served request:
Store<queue<int>, by_priority, monotone_priority>.
What compares the elements?¶
Category any_comparison, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
order_by<C>: a sorted Store, or a by_priority queue, compared by comparator C instead of
urd::Less (in a map, over its keys). The order is C and nothing else: elements it does not separate
are equivalent, so a unique Store keeps one of them. urd::by<P> compares by P(element).
order_by¶
Ordered by the given comparator (in a map, over its keys), not urd::Less.
Role: a demand: you promise it about the data.
In plain words: order by, comparator, priority function.
Kept by: you, about your data.
Shortest served request:
Store<set<int>, sorted, order_by>.
What holds¶
Question |
Tags |
Kinds |
|---|---|---|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, queue, pool, slots, partition |
|
|
map, multiset |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
In which order is it iterated?¶
Category any_order, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Iteration ascending by urd::Less, or in the order elements first came. sorted adds
lower_bound, upper_bound, equal_range and operator<=>; either adds rbegin, rend. To order
by something else, see order_by<C> in How the language is organized.
sorted¶
Iterated in ascending order by urd::Less.
Role: a guarantee: the container keeps it.
In plain words: sorted, in order, ordered by key, range queries.
Kept by: the container.
Instead of:
insertion_ordered(one answer per question).Shortest served request:
Store<set<Id>, sorted>.
insertion_ordered¶
Iterated in the order elements were first inserted.
Role: a guarantee: the container keeps it.
In plain words: insertion order, first come first listed, keeps the order added.
Kept by: the container.
Instead of:
sorted(one answer per question).Shortest served request:
Store<set<Id>, insertion_ordered>.
Reached by position?¶
Category by_key, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Elements identified by position: sequences, and sets with positions (an interner with monotone). Such
containers also declare it, which selection reads.
positional¶
Identified by position 0..n-1, in order.
Role: a guarantee: the container keeps it.
In plain words: by position, numbered as inserted, interner.
Kept by: the container.
Shortest served request:
Store<set<Id>, positional>.
Duplicates allowed?¶
Category duplicates, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, queue, pool, slots, partition.
No two elements equal. Implied for sets, and for maps without multi; stated for pools that intern.
unique¶
No two elements are equal.
Role: a guarantee: the container keeps it.
In plain words: no duplicates, distinct, each at most once.
Kept by: the container.
Shortest served request:
Store<map<Id, Store<set<Id>, unique>>>.
Values per key?¶
Category any_multiplicity, which promises nothing: a request that leaves the question open gets it. Asked of: map, multiset.
One value per key, or many (a multimap).
multi¶
Any number of values per key: a multimap.
Role: a request: only a request states it.
In plain words: multimap, many values per key, adjacency lists.
Kept by: the container.
Shortest served request:
Store<map<Id, Id>, multi>.
Does it change after building?¶
Category may_change, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Only grows until cleared (monotone_until_clear: no erase or pop_back; clear empties it at once,
and with retains refilling allocates nothing), only grows (monotone: no clear either), or changes only
by assign(first, last), a rebuild in the storage held where the container can; a frozen Store is read by any
number of threads between rebuilds. Each is the one before with less: monotone_until_clear ⊃ monotone ⊃
frozen. A monotone queue keeps pop: pop is how a queue is consumed, and monotone takes only clear
away.
monotone_until_clear¶
Only grows until cleared: elements are only added; clear() empties it at once.
Role: a request: only a request states it.
In plain words: append only until cleared, cleared, never erased, refilled after clear.
Kept by: the container.
Instead of:
monotone,frozen(one answer per question).Shortest served request:
Store<set<Id>, monotone_until_clear>.
monotone¶
Only grows: nothing is ever removed.
Role: a request: only a request states it.
In plain words: append only, only grows, never erased.
Kept by: the container.
Promises at least:
monotone_until_clear.Instead of:
frozen(one answer per question).Shortest served request:
Store<set<Id>, monotone>.
frozen¶
No change after construction; assign rebuilds it whole.
Role: a request: only a request states it.
In plain words: built once, read only, immutable after building.
Kept by: the container.
Promises at least:
monotone_until_clear,monotone.Shortest served request:
Store<set<Id>, frozen>.
Can it be empty?¶
Category maybe_empty, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
At least one element: no default constructor, and construction from elements asserts one; a fixed-shape Store asserts a row. A promise about iterated elements: sets, maps and sequences only.
nonempty¶
At least one element.
Role: a request: only a request states it.
In plain words: never empty, nonempty.
Kept by: the container.
Shortest served request:
Store<set<Id>, nonempty>.
Do references stay valid?¶
Category moving_refs, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
A reference to a stored element stays valid until that element is removed, by whichever path hands it out: an
iterator’s element, a map’s value (at, operator[], update, an entry’s .second), a sequence’s
operator[], a queue’s front or top, a pool’s [handle]. Insert moves no other element; erase and
clear end only the references to what they remove.
stable_refs¶
A reference to an element stays valid until that element is removed.
Role: a guarantee: the container keeps it.
In plain words: pointers stay valid, stable addresses, references survive inserts.
Kept by: the container.
Shortest served request:
Store<set<Id>, stable_refs>.
Same contents, same bytes?¶
Category any_representation, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Equal contents have equal representations (a bitset); such a Store is hashable by its contents.
canonical¶
Equal contents have equal representations.
Role: a guarantee: the container keeps it.
In plain words: canonical, same contents same bytes, hashable by contents.
Kept by: the container.
Shortest served request: none in What a request resolves to.
What more it can do¶
Question |
Tags |
Kinds |
|---|---|---|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
map |
|
|
sequence |
Nested scopes?¶
Category any_scope, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Changes undone by pop_scope.
scoped¶
push_scope and pop_scope: popping undoes every change since the matching push.
Role: a guarantee: the container keeps it.
In plain words: nested scopes, undo on backtrack, symbol table.
Kept by: the container.
Shortest served request:
Store<map<Id, Id>, scoped>.
Layered over a parent?¶
Category any_layering, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Lookups fall through to a parent; on pools, indices continue after the parent’s.
layered¶
layer_over(parent): lookups find the parent’s elements too, which it neither owns nor changes.
Role: a guarantee: the container keeps it.
In plain words: falls through to a parent, overlay, phase over phase.
Kept by: the container.
Shortest served request:
Store<map<int, int>, dense, layered>.
Looked up both ways?¶
Category any_direction, which promises nothing: a request that leaves the question open gets it. Asked of: map.
A map answering keys(value) too.
bidirectional¶
A map that answers by value too: keys(v) gives the keys that map to v.
Role: a guarantee: the container keeps it.
In plain words: predecessors, reverse edges, inverse map.
Kept by: the container.
Shortest served request:
Store<map<Id, Id>, multi, dense, frozen, bidirectional>.
Rows of a fixed shape?¶
Category any_shape, which promises nothing: a request that leaves the question open gets it. Asked of: sequence.
Rows whose number and lengths are set at construction (urd::row_lengths, or one per row for rows
of rows); their contents change in place, and reset() sets them back to defaults (with proportional_clear,
only rows handed out to change since).
fixed_shape¶
Rows whose number and lengths are set at construction; only their contents change.
Role: a guarantee: the container keeps it.
In plain words: fixed rows, matrix, table of known shape.
Kept by: the container.
Shortest served request:
Store<sequence<Store<set<int>, unique, dense>>, fixed_shape>.
How it hands out memory¶
Question |
Tags |
Kinds |
|---|---|---|
|
set, map, multiset, sequence, queue, pool, slots, partition |
|
|
pool |
|
|
set, map, multiset, sequence, queue, pool, slots, partition |
One array?¶
Category any_layout, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Elements lie next to each other in memory: data().
contiguous¶
The elements lie next to each other in memory.
Role: a guarantee: the container keeps it.
In plain words: contiguous, cache friendly, as a span, one array.
Kept by: the container.
Shortest served request:
Store<sequence<int>, contiguous>.
Records packed flat?¶
Category any_packing, which promises nothing: a request that leaves the question open gets it. Asked of: pool.
Each record of an interning pool is one self-contained block of bytes (trivially copyable, or serialized by
cista), frozen once stored and read by urd::index.
flat¶
Each record is one self-contained block of bytes, frozen once stored and read by index.
Role: a guarantee: the container keeps it.
In plain words: flat records, serialized, one block per record.
Kept by: the container.
Shortest served request:
Store<pool<Id>, flat>.
Elements stored whole, or in fewer bits?¶
Category word, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.
Unsigned elements may take fewer bits than their type: with bit, each in the bit width the Store is built
with (urd::bit_width); with by_column_widths, each row by the widths of its columns
(urd::column_widths). Such a Store hands out values, not references to its elements.
bit¶
Every element fits in the bit width given at construction (urd::bit_width).
Role: a demand: you promise it about the data.
In plain words: bit packed, packed integers, few bits per element.
Kept by: you, about your data.
Instead of:
by_column_widths(one answer per question).Shortest served request:
Store<pool<Store<sequence<index<Id>>, stable_refs, frozen, positional>>, monotone, bit, layered>.
by_column_widths¶
Rows are stored by the column widths given at construction (urd::column_widths).
Role: a demand: you promise it about the data.
In plain words: column widths, unsigned columns, columns in given bits.
Kept by: you, about your data.
Instead of:
bit(one answer per question).Shortest served request: none in What a request resolves to.