Std.SortedMap.SortedMap

type

SortedMap

This declaration introduces a public type.

A map whose keys are kept in an order the caller chose, and which can be

asked about a key's neighbours rather than only about the key itself.

Map answers one question well: what is stored under this exact key. A rate

table, a version range, a timeline, and a histogram bucket all ask a

different one — what is stored under the largest key not greater than this

— and Map can only answer it by reading every entry out and scanning, which

walks the whole map to find something an ordered structure walks a fraction

of. Map also orders by the runtime's own order on values, so sorting by a

record's field, by a case-insensitive spelling, or downwards is not

something a caller can ask for at all.

The entries are held in one array, sorted, and reached by halving the range

each step, so a lookup passes a handful of entries rather than all of them.

Insertion and removal move an element into or out of the middle of that

array, which the runtime's arrays do about as cheaply as they are read, so

keeping the order costs no more than looking through it.

The comparison is carried with the entries rather than passed to each call.

A map compared one way on Monday and another way on Tuesday is not a map,

and the operations below would each need the caller to remember which — so

the order is fixed when the map is created and every later operation reads

it from there.