urd¶

Say what your data is. urd picks the container and checks that it keeps its promises.

A Store is described by what it holds and how it is used, not by which container holds it:

#include <urd/store.hpp>
#include <urd/repr/values/indexed.hpp>            // the containers these Stores resolve to: an interner,
#include <urd/repr/maps/bidirectional_csr.hpp>  // a graph by index both ways,
#include <urd/repr/values/dense_set.hpp>          // a bitset,
#include <urd/repr/queues/queue.hpp>              // a queue,
#include <urd/repr/maps/index_map.hpp>          // a slot per index
using namespace urd;

struct User                                                             // an index: one integral member
{
    std::uint32_t id;
    static constexpr auto identifying_members() noexcept { return Members<&User::id> {}; }
};

using Names    = Store<set<std::string>, positional, monotone>;         // an interner: each name gets an index
using Follows  = Store<map<User, User>, multi, dense, frozen, bidirectional>;  // a frozen graph
using Seen     = Store<set<User>, dense>;                               // a bitset
using Frontier = Store<queue<User>, fifo>;                              // a queue
using Distance = Store<map<User, int>, dense, constant_clear>;   // cleared per search in O(1)

urd resolves each request at compile time to a container from the standard library, Boost, or its own urd::repr, and gives the Store exactly the interface those properties allow: a frozen Store has no insert, an unordered one no lower_bound, a queue no iteration. Every container urd can choose is checked against a reference model through thousands of random operations.

This documentation describes the Stores the way the standard library describes its containers: for each kind, its member types, its member functions grouped by what they do and by the properties that switch them on, and the complexity of each operation per representation.

Representations

Development

Benchmarks

Header-only C++20, GPL-3.0. Build: see Building and using.