Map

A map is a collection of key–value pairs where each key is unique. In ribs, all map types mix in RMap<K, V>, which extends RIterable<(K, V)> — maps are iterable as (key, value) tuples — and adds foundational lookup operations: get(key), contains(key), keys, and values.

This page covers the four map types in ribs — two regular maps (one immutable, one mutable) and two multi-value maps — along with when to reach for each.

The Map Hierarchy

RMap<K, V>              key–value; iterable as (K, V) tuples; adds get/contains/keys/values
  ├── IMap<K, V>        immutable hash map; structural update returns a new IMap
  └── MMap<K, V>        mutable hash map; in-place put/remove

RMultiDict<K, V>        each key maps to a *set* of values
  ├── IMultiDict<K, V>  immutable multi-value map
  └── MMultiDict<K, V>  mutable multi-value map

RMap and RMultiDict are separate hierarchies. A multidict is not a map — each key can have multiple distinct values.

IMap

IMap<K, V> is a persistent immutable hash map backed by a CHAMP (Compressed Hash-Array Mapped Prefix-tree) trie. All structural operations return a new IMap; the original is never modified.

Structural properties:

get / contains — effectively O(1)
operator + / - (add/remove one entry) — effectively O(1)
mapValues / transform — O(n)
Unordered — iteration order reflects hash values, not insertion order

Construction:

IMap Constructors

final imapEmpty = IMap.empty<String, int>();
final imapFromLiteral = imap({'a': 1, 'b': 2, 'c': 3});
final imapFromDart = IMap.fromDart({'x': 10, 'y': 20});
final imapFromPairs = IMap.fromDartIterable([('a', 1), ('b', 2), ('c', 3)]);

For incremental construction, use IMap.builder<K, V>(). Call addOne with a (K, V) tuple for each entry, then result() to produce the final immutable map:

IMap Builder

IMap<String, int> buildMap() {
  final builder = IMap.builder<String, int>();
  for (var i = 0; i < 5; i++) {
    builder.addOne(('key$i', i));
  }
  return builder.result();
}

Core operations:

IMap Operations

final base = imap({'a': 1, 'b': 2, 'c': 3});

// operator + takes a (K, V) tuple and returns a new IMap
final withD = base + ('d', 4); // {'a':1,'b':2,'c':3,'d':4}
final overrideB = base + ('b', 99); // {'a':1,'b':99,'c':3}

// operator - takes a key and returns a new IMap
final withoutA = base - 'a'; // {'b':2,'c':3}

// get returns Some(value) or None — never throws
final valB = base.get('b'); // Some(2)
final valZ = base.get('z'); // None

// operator [] throws if key is absent
final direct = base['a']; // 1

// getOrElse provides a fallback
final orElse = base.getOrElse('z', () => 0); // 0

// updatedWith lets you modify or remove an entry in one step
final incremented = base.updatedWith('a', (Option<int> old) => old.map((v) => v + 1));
final inserted = base.updatedWith('d', (Option<int> old) => const Some(42));

// mapValues transforms every value, preserving keys
final doubled = base.mapValues((int v) => v * 2); // {'a':2,'b':4,'c':6}

// transform has access to both key and value
final labelled = base.transform(
  (String k, int v) => '$k=$v',
); // {'a':'a=1','b':'b=2','c':'c=3'}

// removedAll removes a set of keys at once
final pruned = base.removedAll(ilist(['a', 'c'])); // {'b':2}

Key distinctions:

get(key) returns Option<V> — never throws, never returns null.
operator [] throws if the key is absent; use get or getOrElse in production code.
operator + takes a (K, V) tuple. If the key already exists, the old value is replaced.
operator - takes a key and returns a new map with that key removed. If the key is absent, the map is returned unchanged.
updatedWith(key, fn) receives the current value as Option<V> and can insert, update, or remove an entry in a single step.

Use when:

You need fast key lookup and can tolerate no ordering
The map is shared across call sites or stored in state — immutability prevents unexpected mutation
You want structural updates without managing copies manually

Avoid when:

You are building a map incrementally in a local scope where immutability is not required — use MMap instead
Each key should map to multiple values — use IMultiDict

MMap

MMap<K, V> is a mutable hash map. Operations like put and remove modify the map in place and return Option<V> indicating the previous value. The assignment operator []= mutates silently, matching Dart's own Map API.

MMap Operations

void mmapExample() {
  final m = MMap.empty<String, int>();

  // operator []= mutates in place (like a Dart Map)
  m['a'] = 1;
  m['b'] = 2;

  // put returns the previous value as Option
  final prev = m.put('a', 99); // Some(1)

  // get returns Some(value) or None
  final val = m.get('b'); // Some(2)

  // remove returns the removed value as Option
  final removed = m.remove('b'); // Some(2)

  // getOrElseUpdate inserts and returns a default if absent
  final guaranteed = m.getOrElseUpdate('c', () => 100); // 100; 'c'->100 inserted

  // updateWith applies a remapper; returning None removes the entry
  m.updateWith('a', (Option<int> old) => old.map((v) => v + 1));

  // removeAll removes several keys at once
  m.removeAll(ilist(['a', 'c']));

  // filterInPlace removes entries that do not satisfy the predicate
  m['x'] = 5;
  m['y'] = 15;
  m.filterInPlace(((String, int) kv) => kv.$2 > 10); // only 'y' remains

  // clear empties the map
  m.clear();
}

Key distinctions from IMap:

put(key, val) returns Some(oldValue) if the key existed, None if it was newly inserted — useful when you need to know whether an insert was actually an update.
remove(key) returns Some(removedValue) or None if absent.
getOrElseUpdate(key, fn) atomically inserts a default and returns it if the key is missing — useful for memoisation or lazy initialisation.
updateWith(key, fn) receives Option<V> and can insert, update, or delete an entry in one call; returning None removes the key.
filterInPlace(p) removes all entries that do not satisfy p, mutating the map in place.

Use when:

Building a map incrementally in a local scope (e.g. grouping, counting)
The return value of put/remove matters to the algorithm
You need getOrElseUpdate for lazy initialisation or memoisation

Avoid when:

The map will be shared across call sites or stored in state — use IMap to prevent unexpected mutation

IMultiDict

IMultiDict<K, V> maps each key to a set of values. Unlike IMap, a single key can have multiple distinct values associated with it.

Internally, it is backed by an IMap<K, ISet<V>>, which is exposed via the sets property. This means that adding the same (key, value) pair twice is idempotent — duplicates within a key's value set are ignored.

Construction:

IMultiDict Constructors

final mdEmpty = IMultiDict.empty<String, int>();

// Each (key, value) pair is added as a separate entry under the same key
final mdFromLiteral = imultidict([('a', 1), ('a', 2), ('b', 3)]);

Core operations:

IMultiDict Operations

final md = imultidict([('a', 1), ('a', 2), ('b', 3), ('b', 4)]);

// get returns the set of values for a key, or an empty set
final valuesForA = md.get('a'); // ISet {1, 2}
final valuesForZ = md.get('z'); // ISet {} (empty)

// operator + adds a single (key, value) entry; use explicit typed record to avoid
// Dart parsing ('c', 99) as two separate operator arguments
const (String, int) entryC = ('c', 99);
const (String, int) entryA3 = ('a', 3);
final mdWithC = md + entryC; // 'c' -> {99}
final mdWithExtraA = md + entryA3; // 'a' -> {1, 2, 3}

// sets exposes the underlying IMap<K, ISet<V>>
final setsMap = md.sets; // IMap {'a': ISet{1,2}, 'b': ISet{3,4}}

final hasKeyA = md.containsKey('a'); // true
final hasKeyZ = md.containsKey('z'); // false
final hasEntry = md.containsEntry(('a', 1)); // true
final hasValue = md.containsValue(3); // true

Key distinctions from IMap:

get(key) returns RSet<V> — the full set of values for that key — rather than Option<V>. An absent key returns an empty set.
operator + takes a (K, V) tuple and adds one entry to the key's value set. Adding an already-present entry is a no-op.
containsEntry(entry) takes a (K, V) tuple and checks for an exact key–value pair.
sets exposes the full IMap<K, ISet<V>> backing structure, which can be iterated, filtered, and transformed like any other map.

Use when:

One key naturally corresponds to multiple values (e.g. tags on documents, roles per user, HTTP headers with multiple values)
You want automatic deduplication of values under each key

Avoid when:

A key should have exactly one value — use IMap
You need mutable in-place updates — use MMultiDict

MMultiDict

MMultiDict<K, V> is the mutable counterpart to IMultiDict. The same key-to-set semantics apply, but add mutates in place and returns this for chaining.

Use the same construction functions as IMultiDict, substituting MMultiDict.empty<K, V>() or mmultidict(iterable) as the entry point. Call add(key, val) or operator + to add entries and get(key) to retrieve the value set.

Use when:

You are building up a multi-value map incrementally in a local scope

Avoid when:

The map will be shared or stored in state — use IMultiDict

Choosing a Map Type

Requirement	Recommended type
Immutable, one value per key	`IMap`
Mutable, local accumulation or counting	`MMap`
Immutable, multiple values per key	`IMultiDict`
Mutable multi-value accumulation	`MMultiDict`

The Map Hierarchy​

IMap​

MMap​

IMultiDict​

MMultiDict​

Choosing a Map Type​

The Map Hierarchy

IMap

MMap

IMultiDict

MMultiDict

Choosing a Map Type