Elements: identity, hashing, order, indices¶

What a container needs of its elements comes from three function objects, with nothing in namespace std:

template<typename T> struct Hash¶: hash_t operator()(const T&) const: a deterministic 64-bit hash (scalars as themselves, Boost.ContainerHash mixing for composites). Given for arithmetic types, enums, strings and string views, the standard’s composites (pair, tuple, array, vector, set, map, optional, variant, span), any Identifiable type, urd::index, the views (urd::index_view and the record views), the flat containers of urd/elements/flat.hpp, any range whose elements in order are its value (urd::value_range<R> = true: hashed, compared and ordered as its elements), and Stores whose contents fix their order (sorted, canonical, sequences). There is deliberately no fallback to std::hash.

template<typename T> struct EqualTo¶: bool operator()(const T&, const T&) const: equality agreeing with Hash; for floating point, NaN equals NaN. Given for any iterable Store (equal contents, as its == compares them).

template<typename T> struct Less¶: bool operator()(const T&, const T&) const: a strict weak order agreeing with EqualTo, lexicographic over members and ranges. Given for Stores iterated in an order their request fixes (sorted, insertion_ordered, sequences), so such a Store can be a sorted key.

Which of the three a Store has is decided by its request, never by its representation: a Store named as another Store’s element is resolved before its representation is defined.

A type names its identity once and is then hashable, comparable and ordered, in member order:

template<auto... Ms> struct Members¶: The identifying members of a record, as member pointers.

struct Edge
{
    Vertex from, to;
    static constexpr auto identifying_members() noexcept { return Members<&Edge::from, &Edge::to> {}; }
};
using Edges = Store<set<Edge>>;                    // hashed by (from, to)

template<typename T> concept MemberIdentified¶: T::identifying_members() gives a Members.

template<typename T> concept Identifiable¶: T is MemberIdentified, or its identifying_members() gives its identity as a value (a view gives a tuple). Hash, EqualTo and Less of T are those of that identity.

template<typename T> concept hashable¶: Hash and EqualTo apply to T: what an unordered key needs.

template<typename T> concept orderable¶: Less and EqualTo apply to T: what a sorted key or a by_priority element needs.

template<typename K> concept indexable¶: index_of applies to K: what a dense key needs.

template<typename K> struct index_of¶: How a key is an index 0..n-1: is_index(key) (a negative integer, or urd::index’s none, is no index, and a lookup of one finds nothing), to_index(key) and from_index(std::size_t). Given for non-negative integers, enums, types identified by one integral member, and urd::index; specialize it for others.

Prehashed keys¶

A key hashed once can be looked up, and inserted into an interner, without being hashed again: the standard’s way to pass a precomputed hash. C++20 had dedicated overloads for it (P0920) and dropped them (P1661) for heterogeneous lookup by a key that carries its hash, which is what urd offers; there are no *_with_hash members.

template<typename T> struct prehashed¶: const T& key and hash_t hash, Hash’s of key. It refers to key, which must outlive it.

template<typename T> prehashed<T> prehash(const T &key)¶: key with its hash. Not of a temporary (that overload is deleted): the result would refer to it once it is gone.

A hashed Store’s find, contains and count take a prehashed<T> wherever they take a T (the hash sets and maps, the parallel ones, the positional sets, the record, value and arena interners), and an interner’s insert(key) and insert(key, make) do too. An interner hashes a new element once, its insert included: the lookup’s hash goes into the table with the new index.

Indices and views¶

template<typename T> struct index¶

The index of a T in the Store that numbers T’s (urd/elements/index.hpp): a positional set mints one on first insert, and a pool’s handles are indices. One 32-bit integer (value) with a none value (is_none()), a different type per T that converts to no other, hashable, orderable, and a dense key. Write it urd::index: the C library declares a function index in the global namespace.

value_type value¶: The number; none_value by default.

static constexpr value_type none_value¶: The none value: the largest value_type. A default-built index is none.

bool is_none() const noexcept¶

struct layer¶

The number of a Store that hands out indices for views (a pool of records, a positional set): such a Store is built from it first, Atoms(urd::layer { 3 }), and answers it as layer(). Who builds the Store gives it, and Stores whose views must differ get different numbers; a layer gets its own, as its parent does.

std::size_t number¶

A T is read through a context C that resolves the indices in its record (resolves), by one of four views (urd/elements/view.hpp), which differ only in how they hold the record. Each borrows its context as a const C*, which must outlive it, and has the same surface: context(), data(), member<&T::m>(), the accessors of its view_mixin, value_type (T), and an identity (what identifies the record, and the context’s number) that ==, <=>, EqualTo, Hash and Less compare by. A positional set and a pool of records resolve their own type; any type that gives the record, its number and the view of an index serves.

template<typename T, typename C = typename context_of<T>::type> class index_view¶

Holds an index<T>, read through the context as context[index] (a T, or its stored record data<T>) and identified by it: what a context makes of its indices, context.view(index). Two views of one element from one context are equal and hash equally, wherever they were made; views from differently numbered contexts are not.

index_view(index<T> at, const C *context) noexcept¶

index<T> index() const noexcept¶: Only an index_view names its index; a view of a record names none, so that the record’s mixin may.

template<typename T, typename C = typename context_of<T>::type, typename R = data<T>> class borrowed_view¶

Points at a record R (data<T>, a builder<T>, or another form of T) held outside the context, which must outlive the view; read and identified by the record. What resolve() makes of a record or builder held in place (never of a temporary).

borrowed_view(const R *record, const C *context)¶

template<typename T, typename C = typename context_of<T>::type, typename R = data<T>> class owning_view¶

Holds a record R by value: one computed rather than stored. Read and identified by the record.

owning_view(R record, const C *context)¶

template<typename T, typename C = typename context_of<T>::type, typename R = data<T>> class shared_view¶

Shares a record R (std::shared_ptr<const R>), released with the last copy. Read and identified by the record.

shared_view(std::shared_ptr<const R> record, const C *context)¶

What all four give:

const C &context() const noexcept¶

decltype(auto) data() const¶

The record: for an index_view as the context holds it, else the record held.

template<auto Member>
decltype(auto) get() const¶

A member of the record resolved through the context (resolve()): an index<U> becomes the index_view<U, C> the context makes, pointing at the layer that owns the element; a range of indices a range of views; a variant the variant of its alternatives resolved; an optional the optional of its value resolved; a pair the pair of its members resolved; a stored record held in the record its borrowed_view; anything else stays as it is.

static constexpr auto identifying_members() noexcept¶

The identity: the index, or the record, and the context’s number (layer); only where the context has a number.

template<typename C, typename T> concept resolves¶: context[index<T>] is convertible to const T&, or is the stored record data<T> (the slot of urd/elements/data.hpp, which must be Serializable); context.layer() is its number; context.view(index<T>) gives the index_view<T, C> of the index, through the context that owns it (a layer points it at the layer that owns the element; a context made of several Stores writes one per type).

template<typename M, typename C> decltype(auto) resolve(M &&member, const C &context)¶: A record’s member as a view sees it: resolution<M>::of(member, context), the member passed on as given (so that a record or builder, which its resolution borrows, is refused as a temporary); see index_view::get().

template<typename M> struct resolution¶: How a member of type M resolves: as it is, unless specialized. Given for indices (index<U>: the context’s view), ranges of indices (a range of views), and variants, optionals and pairs, std’s and cista’s alike (their contents resolved; urd/elements/view.hpp, by the concepts variant_value, optional_value and pair_value). A new member type resolves by specializing it.

template<std::ranges::input_range R, std::copy_constructible F> class transformed_range¶

template<std::ranges::input_range R, typename F> transformed_range<std::remove_cvref_t<R>, std::decay_t<F>> transform(R &&range, F &&function)¶: range read through function: each element x read as function(x), a borrowed std::views::transform. It holds range’s iterators and the function, and so do its iterators: unlike std::views::transform’s, they do not point into the range object and outlive it, so it is a std::ranges::borrowed_range (a function may return it, Python may iterate it after the call). It traverses as range does (random access, sized where it is), ends at range’s sentinel where it has one, and has base(), function() and a checked at(position). range must outlive it unless it is a borrowed view (iota, a span, the set bits of a bitset); a view that is not borrowed is refused, and transform takes an rvalue only where it is borrowed. The function is a small copy-constructible function object: a lambda (capturing by value what it reads through, such as a view) or a struct holding it (a pointer). It is held in a box, as std::views::transform holds it, so that the range and its iterators stay default-constructible and assignable; each iterator holds its own copy. It owns nothing else. Where what it reads is a value range (urd::value_range) or a view, it is a value range itself.

template<typename M, typename C> using resolved_range = transformed_range<M, resolver<C>>¶: A range of resolving elements read through a context: the transformed_range of M whose function, resolver<C> ({ &context }), resolves each element (resolve()) through the context, which it borrows; what resolution makes of a range of indices. context() gives the context. It can be spelled while C is still incomplete.

template<typename T> struct context_of¶: Names a record type’s default context once (template<> struct urd::context_of<Atom> { using type = Repository; };), so that index_view<Atom> needs no second argument.

template<typename T, typename V> struct view_mixin¶: Where a library adds the named accessors of a record’s views, one line each over member<>: template<typename V> struct urd::view_mixin<Atom, V> { auto predicate() const { return static_cast<const V&>(*this).template member<&urd::record_of<V>::predicate>(); } };, where record_of<V> is the record the view reads (named through V, so it may be incomplete where the mixin is declared). The mixin is keyed on what the view reads: views of an index and of a record of T share T’s mixin; views of a builder use builder<T>’s, which is T’s unless specialized. The view’s member<&T::m>() hides any member a mixin would declare.

Children of a record¶

urd/elements/children.hpp walks the handles a record holds: its children, every index<U> with U in a type list Types, found in its cista members directly, in (nested) flat vectors, as a variant’s alternative, in an optional or a pair, or in a nested record. U may be the record’s own type T: only a direct member of type index<T>, the record’s own handle, is no child. An index of a type not in Types is neither handed out nor walked into.

template<typename Types, typename T, typename R, typename C, typename F> void for_each_child(const R &record, const C &context, F f)¶: Calls f(context.view(child)) for each child, in member order.

template<typename Types, typename T, typename R, typename C, typename F> R map_children(R record, const C &context, F f)¶: The record with each child c replaced by to_stored(f(context.view(c))): f returns an index of c’s type or a view of one. A variant keeps its alternative.

template<typename Types, typename T, typename R, typename C, typename F> R map_variant_children(R record, const C &context, F f)¶: map_children, but each flat_variant slot not inside another variant (whatever its alternatives) is replaced whole, by to_stored(f(resolve(slot, context))): f gets the std::variant of the slot’s alternatives resolved and may return another alternative (a not becoming an or), as a view, an index or the variant. The walk does not enter a slot: the children inside it are f’s to map. Children outside variants are replaced as map_children replaces them, so f takes both views and resolved variants (an overload set, or a generic callback).