Reference

std/collections/map

std/collections/src/map.trb

Keys mapped to values: Map, its default implementation TrieMap, and the flat HashMap.

Map<Key, Value> is the type of the literal ["a": 1, "b": 2]; a Set is the same idea with no value at all. Both iterate in insertion order and compare regardless of it.

Related

trait Map

trait Map<Key, Value> with Iterate<(key: Key, value: Value)>, Length, MutableIndexed<Key, Value>

Mapping from keys to values. This is the type of the literal ["a": 1, "b": 2].

Iterated, it consists of (key, value) tuples. The trait asks nothing of Key - what a key has to be able to do is a matter of the implementation (TrieMap and HashMap need Hash, a sorted map would need Compare), so only the factories carry a bound.

Every implementation iterates in insertion order, and removing an entry does not reorder the rest. The order reaches the output through Show (an empty map shows as [:]), so it is a rule of the language and not of the implementation.

Examples

var ages = ["Ada": 36]
ages["Grace"] = 45
for (name, age) in ages {
  print "{name} is {age}"
}

A verb needs a var path; its participle answers a changed copy and works on a const map too:

const ages: Map<String, Int> = ["Ada": 36]
const older = ages.updated "Ada", 37
print older

map[key] is itself a var path, so a value is changed in place without reading it out first:

type Counter {
  var count: Int = 0
  var fn increment() {
    count = count + 1
  }
}

var scores: Map<String, Counter> = ["Ada": Counter()]
scores["Ada"].increment()
print scores["Ada"].count

Pitfalls

  • A binding read out of the map copies the value there and then: var mine = scores["Ada"] takes a copy of the counter above, so changing mine afterward never touches scores. See MutableIndexed for the rule.
  • map[key] panics if the key is absent; map.get(key) answers an Option instead.

Related

  • Set - the same idea without a value.
  • Iterate - the pipeline vocabulary (map, filter, fold, ...) every map has, over its entries.

fn of

static fn of(...entries: (Key, Value)): Self where Self: From<Iterate<(Key, Value)>>, Key: Hash

Builds a map from its arguments: Map.of(("a", 1), ("b", 2)). Answers Self.

fn remove

var fn remove(key: Key): Value?

Removes the entry for key and answers its value, or None if there was none.

fn clear

var fn clear()

Removes every entry, in place.

fn getOrInsert

var fn getOrInsert(key: Key, fallback: lazy Value): Value

The value for key, storing fallback first where there is none. The fallback is lazy, so a value that costs something is only built on a miss.

This is what other languages spell entry().or_default(), with the replacement written out: there is no Default trait, so what an absent key becomes stands at the call.

Examples

var counts: Map<String, Int> = [:]
print counts.getOrInsert("a", 0)

Pitfalls

  • The answer is a copy, as every value is. groups.getOrInsert(city, []).append(user) changes nothing and the compiler says so ("a temporary is not a var path"): a method cannot answer a place, because a place is a path and not a value. Map.update is the one that changes what is stored.

Related

  • Map.update - the same insert, with the stored value changed in place.

fn update

var fn update(key: Key, fallback: lazy Value, change: (var Value) => Void)

Changes the value for key in place, storing fallback first where there is none. This is the grouping loop:

var groups: Map<String, List<String>> = [:]
groups.update("north", []) { names => names.append("Ada") }
print groups

The fallback is lazy, so it is only built on a miss.

Related

  • Map.getOrInsert - the same insert, answering the value instead of changing it.

fn updated

fn updated(key: Key, value: Value): Self

The participle of set is set, so this one is called updated.

fn removed

fn removed(key: Key): Self

The participle of Map.remove: a changed copy with the entry for key gone.

fn count

fn count(): Int

How many entries there are. A map knows its size, so counting it does not walk it.

fn containsKey

fn containsKey(key: Key): Bool

Whether there is an entry for key.

fn keys

fn keys(): Iterate<Key>

Every key, in insertion order.

fn values

fn values(): Iterate<Value>

Every value, in insertion order.

fn mapValues

fn mapValues<Output>(transform: Transform<Value, Output>): Map<Key, Output> where Key: Hash

Transforms every value, keeping the keys: ages.mapValues { age => age + 1 }.

extend Map<Key, Value> with From<Iterate<(Key, Value)>>

extend<Key: Hash, Value> Map<Key, Value> with From<Iterate<(Key, Value)>>

The factory picks the default implementation. This is what makes Map.from and the literal ["a": 1] work.

fn from

static fn from(entries: Iterate<(Key, Value)>): Map<Key, Value>

extend Map<Key, Value> with Show

extend<Key: Show, Value: Show> Map<Key, Value> with Show

["a": 1, "b": 2], and [:] when it is empty - the format of the literal.

fn show

fn show(): String

extend Map<Key, Value> with Equals

extend<Key, Value: Equals> Map<Key, Value> with Equals

Equal when they hold the same entries, regardless of insertion order.

fn equals

fn equals(other: Self): Bool

extend Map<Key, Value> with Hash

extend<Key: Hash, Value: Hash> Map<Key, Value> with Hash

Order-independent, unlike List.hash: entries are combined with bitwiseExclusiveOr, so insertion order never changes the hash of equal maps.

Hash requires Equals, and the Equals implementation above satisfies that: Value: Hash implies Value: Equals.

fn hash

fn hash(): Int

fn describedKey

fn describedKey<Key>(key: Key): String

the key "Alan": a key as the message of a missing one names it - what map[key] panics with.

The key is shown as it shows inside of another value (showNested, so a text is quoted), cut after 60 characters. Whether its type has Show is a question about the type and not about the value, and a generic Key has no bound that answers it: so the compiler writes this call where it knows the type of the key, as describedShownKey of the shown key, and the body below is what is left for a key whose type has no Show - the words the key alone.

fn describedShownKey

fn describedShownKey(shown: String): String

the key "Alan" for the text a key shows as, with everything after its 60th character cut off as ....

type TrieMap

native type TrieMap<Key: Hash, Value> with Map<Key, Value>, From<Iterate<(Key, Value)>>

Hash array mapped trie - the default. A write to a shared map copies one path (O(log n)), so keeping many versions of a big map is cheap. Iterates in insertion order.

Until the trie exists, this name is a documented alias of HashMap. Only performance differs: iteration order and Show are the same either way.

fn from

static fn from(entries: Iterate<(Key, Value)>): TrieMap<Key, Value>

Ordinary TorbScript, and it cannot be a function of the runtime: entries is a trait-typed value of the program, so reading it means calling iterate and next through a witness table. withCapacity builds the empty table, and it is the one native the lowering answers itself - the element descriptors a table needs are a function of the language and no declaration can name one.

fn withCapacity

native static fn withCapacity(capacity: Int): TrieMap<Key, Value>

The empty table, with room for capacity entries before it has to grow again.

fn length

native fn length(): Int

How many entries there are.

fn get

native fn get(key: Key): Value?

The value for key, or None if there is none. map[key] panics instead; see TrieMap.at.

fn at

fn at(key: Key): Value

The value for key. This is map[key].

Panics

When there is no entry for key, with the key "Alan" is not in the map: the key as it shows inside of another value, cut after 60 characters, or the key alone where its type has no Show (describedKey). TrieMap.get is the same question with an Option for an answer.

fn iterate

fn iterate(): Iterator<(key: Key, value: Value)>

Ordinary TorbScript over entryAfter: see MapIterator.

fn entryAfter

native fn entryAfter(var cursor: Int): (key: Key, value: Value)?

The entry at or after cursor in the storage's own insertion order, with cursor left one past it. The one native a table needs beyond get and set: the tombstones a removal leaves are the storage's business and nothing else can skip them.

fn set

native var fn set(key: Key, value: Value)

Changes the value for key, or adds a new entry if there was none, in place. map[key] = value goes through this; see MutableIndexed.set.

fn remove

native var fn remove(key: Key): Value?

Removes the entry for key and answers its value, or None if there was none.

fn clear

native var fn clear()

Removes every entry, in place.

type HashMap

native type HashMap<Key: Hash, Value> with Map<Key, Value>, From<Iterate<(Key, Value)>>

Flat hash table: the fastest lookups and writes, but a write to a shared table copies all of it. The one for caches and indexes that are never copied. Iterates in insertion order.

fn from

static fn from(entries: Iterate<(Key, Value)>): HashMap<Key, Value>

Same as TrieMap.from.

fn withCapacity

native static fn withCapacity(capacity: Int): HashMap<Key, Value>

Same as TrieMap.withCapacity.

fn length

native fn length(): Int

Same as TrieMap.length.

fn get

native fn get(key: Key): Value?

Same as TrieMap.get.

fn at

fn at(key: Key): Value

Same as TrieMap.at.

Panics

When there is no entry for key, with the message of TrieMap.at.

fn iterate

fn iterate(): Iterator<(key: Key, value: Value)>

A cursor over the entries, in insertion order; see HashMapIterator.

fn entryAfter

native fn entryAfter(var cursor: Int): (key: Key, value: Value)?

Same as TrieMap.entryAfter.

fn set

native var fn set(key: Key, value: Value)

Same as TrieMap.set.

fn remove

native var fn remove(key: Key): Value?

Same as TrieMap.remove.

fn clear

native var fn clear()

Same as TrieMap.clear.