Keyed Structures

Keyed Structures

Map[K, V]
SortedMap.SortedMap[K, V]
LinkedMap.LinkedMap[K, V]

Status: eight purpose-specific keyed structures ship in Std beside the built-in ordered Map. They are persistent values: an update returns a new structure and leaves the original available.

The right structure is determined by the question a program asks, not by the fact that every one of them stores keys.

Structure	Use it when
Std.SortedMap	Keys need a caller-supplied order, ranges, neighbours, or rank.
Std.LinkedMap	Iteration must preserve insertion order.
Std.EnumMap	The key domain is fixed and every key has a value.
Std.BiMap	Either side of a one-to-one relation must find the other.
Std.MultiMap	One key owns zero or more values.
Std.MultiKeyMap	An entry has two keys and either key is an index.
Std.LruCache	A bounded map must evict the least recently used entry.
Std.PrefixTrie	Text keys are queried by prefix.

Ordered questions

Std.SortedMap stores the comparison function with the map. floor, ceiling, lower, and higher answer neighbouring entries; range and restrictRange operate on half-open key ranges.

import Std.SortedMap as SortedMap

let prices = SortedMap.fromPairs(
  &[(10, "low"), (30, "high")],
  fn(left: Int, right: Int) -> Bool => left < right
)

SortedMap.floor(&prices, 20)    // Some((10, "low"))
SortedMap.ceiling(&prices, 20)  // Some((30, "high"))

Std.LinkedMap answers a different ordering question. insert keeps a key's original position; touch moves it to the newest position. oldest and newest expose the ends of that order.

Total and relational maps

An EnumMap[K, V] is built from a domain. get returns V, not Option[V], for keys from that domain. Use find when a key came from outside the program and may not belong to it.

import Std.EnumMap as EnumMap

let enabled = EnumMap.filled(&["build", "test", "publish"], false)
let ready = EnumMap.set(&enabled, "build", true)
EnumMap.get(&ready, "build")  // true

BiMap keeps a bijection. insert displaces an old pairing on either side; insertChecked returns None instead when either side is already paired. MultiMap keeps many values under one key. MultiKeyMap[A, B, V] stores entries under pairs and maintains indexes for withFirst and withSecond.

Bounded and prefix lookup

An LruCache returns updated recency state with a successful read:

import Std.LruCache as LruCache

let cache = LruCache.put(&LruCache.withCapacity[Str, Int](2), "answer", 42)
let step = LruCache.get(&cache, "answer")
let found = step[0]
let updated = step[1]

peek reads without changing recency. put may evict, and a capacity of zero is a valid disabled cache that retains nothing.

PrefixTrie holds text keys as character paths. withPrefix returns the matching entries; longestPrefixOf answers the stored key that is the longest prefix of some input.

import Std.PrefixTrie as PrefixTrie

let routes = PrefixTrie.fromPairs(&[("/api", 1), ("/api/admin", 2), ("/help", 3)])
PrefixTrie.keysWithPrefix(&routes, "/api")  // ["/api", "/api/admin"]

Cost boundary

These modules state useful observations in their types, but they are Pudu source running through the interpreter. Their APIs do not promise native-language complexity bounds. SortedMap, for example, currently stores a sorted sequence; PrefixTrie.size collects its pairs. Choose them for semantic fit first and measure the current evaluator for workloads where cost matters.

Related

• Sets Maps And Sequences
• Standard Library
• Trees And Hierarchies
• Implementation Status