Mappings¶

A mapping is melon's abstraction for "data indexed by something" — lengths per arc, distances per vertex, a boolean filter per element. Like the graph concepts, it is deliberately minimal: anything with an operator[] that can be read through a const access is a candidate, and the refinements say what more you can do with it. The concepts and the ownership views live in melon/mapping.hpp; the ready-made maps beyond maps::identity each have their own header under melon/maps/.

The concept¶

template <typename Map, typename Key>
concept mapping = detail::subscriptable_with<Map, Key> &&
                  !std::same_as<mapped_value_t<Map, Key>, void>;

Two requirements: the map is subscriptable by the key — detail::subscriptable_with is the named helper for that clause, checking m[k] on an lvalue map — and there is actually a value to read. The second clause carries more than it looks like it does — mapped_value_t is defined through a const access, so a mapping is a map you can read from a const object. That consequence is easy to miss and is covered below.

The associated aliases extract the value type. They are constrained on the subscript alone, not on mapping: mapped_reference_t stays usable on a map that fails the readability clause — a write-only map — while mapped_value_t goes through the const access, and its substitution failing on such a map is exactly what turns mapping false.

template <typename Map, typename Key>
    requires detail::subscriptable_with<Map, Key>
using mapped_reference_t = decltype(std::declval<Map &>()[std::declval<Key>()]);

template <typename Map, typename Key>
    requires detail::subscriptable_with<Map, Key>
using mapped_const_reference_t =
    decltype(std::declval<const Map &>()[std::declval<Key>()]);

template <typename Map, typename Key>
    requires detail::subscriptable_with<Map, Key>
using mapped_value_t = std::decay_t<mapped_const_reference_t<Map, Key>>;

mapped_reference_t is what a mutable access yields, mapped_const_reference_t what a const access yields, and mapped_value_t the decayed value behind it.

Writing, prefetching¶

template <typename Map, typename Key>
concept output_mapping =
    mapping<Map, Key> &&
    !std::same_as<mapped_reference_t<Map, Key>, mapped_value_t<Map, Key>> &&
    requires(Map & map, Key && key, mapped_value_t<Map, Key> & value) {
        map[std::forward<Key>(key)] = std::move(value);
    };

output_mapping adds assignment. A mapping that does not satisfy it is read-only. No return type is demanded of the write expression, which is what lets proxy references qualify — std::vector<bool> is a perfectly good output mapping alongside std::vector<double> and your own type, and so is a proxy following the C++23 const-assignable protocol whose assignment returns const proxy &, like static_filter_map's. The value is written from an rvalue, so move-only value types model the concept too.

The requirement also demands that a write actually lands: the subscript must return an lvalue reference into storage, or a proxy standing in for one — that is the disequality between mapped_reference_t and mapped_value_t. A map whose subscript returns a prvalue of the value type — a computed map, such as maps::function over a lambda returning by value — is readable but is not an output_mapping, because m[k] = v would assign into a temporary.

template <typename Map, typename Key>
concept contiguous_mapping =
    mapping<Map, Key> && std::integral<Key> && requires(Map & m) {
        { m.data() } -> std::convertible_to<
                            std::add_pointer_t<std::add_const_t<mapped_value_t<Map, Key>>>>;
    };

contiguous_mapping requires integral keys and a data() pointer to a flat block. This is not a micro-optimization detail: it is what lets the shortest-path algorithms issue explicit prefetches for the values they are about to touch, which is a large part of why they are fast on big graphs.

The ..._of refinements¶

mapping_of, output_mapping_of and contiguous_mapping_of add one requirement: the mapped value is exactly the given type.

template <typename Map, typename Key, typename Value>
concept mapping_of =
    mapping<Map, Key> && std::same_as<mapped_value_t<Map, Key>, Value>;

Use them when the value type is fixed by the problem rather than deduced from the map — output_mapping_of<F, arc_t<G>, bool> for an arc filter, for instance. Algorithms that infer their arithmetic from the map, such as Dijkstra, constrain their stored member on mapping_view<arc_t<Graph>> with no _of and let the length type follow — mapping_view is the view concept below.

What qualifies¶

Verified against the concepts as written:

† An output_mapping exactly when the callable, or the projection, hands back an lvalue reference into storage — the const-lambda spelling below. maps::element likewise writes through when the key is itself an lvalue: std::get on an lvalue tuple returns a reference into it.

std::map is not a mapping¶

std::map::operator[] is non-const — it inserts a default-constructed value when the key is absent, so it cannot be offered on a const map. A mapping must be readable through a const access, so mapping<std::map<K, V>, K> is false. The same holds for std::unordered_map.

That does not stop you passing one to an algorithm: map arguments are routed through maps::mapping_all, whose views dispatch each subscript to m[k], then m(k), then m.at(k) — with the constness the wrapped map carries.

std::map<unsigned int, double> lengths = ...;

for(auto && [v, d] : dijkstra(graph, std::as_const(lengths), s)) { ... }   // reads via at()

The constness matters. Wrapping the non-const lengths directly also compiles, but the resulting mapping_ref_view<std::map<...>> holds a non-const reference — its subscript still finds the inserting operator[] first, so a missing key silently default-inserts a value. The at() branch, which throws on a missing key instead, engages only for a const-qualified wrapped map: a reference view of a const map, as above, or a mapping_owning_view read through const.

Where it does bite is a static_assert, or a template of your own constrained on mapping. Assert on the wrapped type — that is what the algorithm will actually hold:

static_assert(!mapping<std::map<unsigned int, double>, unsigned int>);
static_assert(output_mapping_of<maps::mapping_all_t<std::map<unsigned int, double> &>,
                                unsigned int, double>);

Maps that come from the graph¶

Algorithms rarely take their scratch space from you; they ask the graph for it:

auto dist   = create_vertex_map<double>(g, 0.0);
auto in_cut = create_arc_map<bool>(g, false);

The resulting types are vertex_map_t<G, double> and arc_map_t<G, bool>, chosen by the graph implementation. For melon's containers they are static_maps, which are contiguous_mappings — so an algorithm that requires contiguity gets it, and one that does not still works when the graph hands back something else.

Mapping views¶

Just as graphs are wrapped by views::graph_all, mappings passed to an algorithm go through maps::mapping_all, which yields:

• mapping_ref_view — a non-owning reference, when the argument is an lvalue;
• mapping_owning_view — takes ownership, when it is an rvalue;
• the argument itself, unwrapped, when it is already a view — maps::identity, maps::constant, a transform_map_view, or a type of your own derived from mapping_view_base.

Two concepts name the two ends of that wrapping. mapping_view<M, K> is a mapping that is std::movable and opts in through mapping_view_base — what an algorithm requires of the member it stores, so that a stored map is always a view and never a raw container. mapping_for<M, Target> is the constructor-side counterpart: M is accepted wherever Target is constructible from maps::mapping_all_t<M>, which is how the same constructor takes a container by lvalue, by rvalue, or a lambda bare.

That is what makes both of these safe:

std::vector<double> length = ...;
dijkstra a(g, length, s);                       // ref view; `length` must outlive `a`
dijkstra b(g, std::move(length), s);            // owning view; `b` holds the vector

mapping_owning_view uses a std::ranges-style movable box, so an algorithm stays movable even when the mapping it owns is a capturing lambda.

maps::function¶

maps::function(f) wraps any callable into a mapping. You do not need it to pass a lambda to an algorithm — that wrapping happens automatically — but you do need it wherever a mapping is required as a type: a member of your own class, a static_assert, an explicit template argument.

// unit lengths, no storage
auto unit = maps::function([](auto &&) { return 1; });

// lengths derived from coordinates
auto euclidean = maps::function([&](arc_t<G> a) { return distance(pos[arc_source(g, a)],
                                                              pos[arc_target(g, a)]); });

std::vector<double> storage(n);
auto m = maps::function([&storage](arc_t<G> a) -> double & { return storage[a]; });

The ready-made maps¶

maps::identity ships with melon/mapping.hpp itself; the rest live in melon/maps/, one header each:

maps::constant's value is an NTTP, so the map is an empty type — only structural types qualify; a runtime constant is maps::function over a capturing lambda. maps::true_map is the default filter of views::subgraph — and since it is empty and stored with [[no_unique_address]], an unfiltered subgraph costs nothing and its vertices() is the underlying range itself rather than a filter_view. maps::identity and maps::element are how d_ary_heap is told where to find an entry's priority and identifier: maps::element<1> reads .second of a std::pair entry, maps::element<0> its .first.

maps::transform(m, f) routes its base through maps::mapping_all — an lvalue is referenced, an rvalue owned, a view passed through — and applies f to the mapped value, never to the key. With a value-returning projection the result is read-only; a projection handing back a real lvalue reference keeps the base's writability, and the mutable-lambda rule above applies to f exactly as it does to maps::function. The returned class is transform_map_view, in melon itself like the other view classes — take it by auto; its exact type depends on the projection's.

Next¶

• Undirected graphs — edges, and create_edge_map.
• Ownership and mapping views — the full mapping_all story.
• Maps, heaps and sets — static_map and static_filter_map in detail.