Std.PrefixTrie.PrefixTrie

type

This declaration introduces a public type.

What it does

Text keys held by their characters, so a prefix can be asked about.

Autocomplete, a routing table, a dictionary, every setting under

server.tls.: each of these asks for the entries whose key starts with

something. A Map can only answer by reading every key and testing it, so

returning five entries costs the whole map. SortedMap narrows that to a

range when the keys are text, which is better, and still compares whole keys

at each step.

Here a key is a path through the characters. Walking a prefix touches one

node per character of the prefix — not per entry in the trie — and everything

under that node is the answer. A prefix shared by a thousand keys is walked

once and stored once, which is the other thing this shape buys: the common

stem of server.tls.cert and server.tls.key exists one time.

The cost is that this holds text keys and nothing else, and that a key with

no shared prefix is a node per character with one child each. It is worth

reaching for when prefixes are asked about and keys overlap, and not

otherwise.

Read the signature

• This declaration has no value signature because it introduces a type or trait.