Library / Collections / Dictionaries / RedBlackTreeDictionary
RedBlackTreeDictionary
An ORDERED Dictionary[K, V, H] backed by a left-leaning red-black tree (Sedgewick LLRB), ARENA form. Guaranteed O(log n) lookup / insert / remove; iteration yields keys in Comparable order.
Fields 3
int64 rootIdxint64 countint64 freeHeadConstructors 4
INIT()INIT(Hasher[K] h)
INIT(GrowthHint hint, int64 initialCapacity)
INIT(Hasher[K] h, GrowthHint hint, int64 initialCapacity)
Methods 13
MODIFY METHOD insert(K key, V value) RETURNS STATUSmodifies
MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUSmodifies
METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE Vreads
METHOD lookupFast(REFERENCE K key) RETURNS booleanreads
Dictionary.lookupFast — the same descent as lookup, without the
STATUS that lookup must allocate on a miss.
MODIFY METHOD remove(REFERENCE K key) RETURNS | Kmodifies
Remove — hands back the STORED key and value (not the probe key, which is what the old key-only remove returned).
Like the SoA dictionaries and unlike ChainedHashDictionary, the halves are cloned rather than moved: the arena node is reached by index and a subscript read clones by rule (stmt_assign.py:149), and the LLRB delete rebalances the tree, so the node cannot simply be evicted first. Census pins this at one DUPLICATE per half.
METHOD contains(REFERENCE K key) RETURNS booleanreads
METHOD isEmpty() RETURNS booleanreads
METHOD size() RETURNS int64reads
Number of key-value pairs currently stored. Read-only, O(1).
MODIFY METHOD clear() RETURNS voidmodifies
METHOD keys() RETURNS LinkedList[K]reads
METHOD iterator() RETURNS ReferenceIterator[K]reads
METHOD clone() RETURNS Dictionary[K, V, H]reads
METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS booleanreads
for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.
Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so
two "equal" dictionaries would answer lookup(a) differently and neither
could stand in for the other — which is the whole point of an equivalence.
Keys-AND-values is what C++ (map and unordered_map), Rust, Swift,
Julia, Python and Java all specify. Keyset equality is a perfectly good
relation, but it is equality of the DOMAIN rather than of the dictionary,
and it deserves its own name (hasSameKeys) rather than this one.
Equal sizes plus a one-way walk is sufficient: with the counts already
equal, other cannot carry a key this one lacks unless this one also
carries a key other lacks — and the walk would have found that.