Skip to Content
ReferenceLibrary

hashmap

Flat open-addressing hash map from Int keys to V, salted with splitmix64.

Generated from spec/std/hashmap.cp by cpl doc --format json.

FlatMap

pub struct FlatMap<V>

Flat open-addressing hash map from Int keys to V, salted with splitmix64. get, contains, set, remove, and get_or_insert are O(1) expected.

Source

FlatMap.new

fn new(default_val: V, cap: Int = 16) -> FlatMap<V>

[rename] Create an empty FlatMap<V> sized for at least cap entries (replaces with_capacity).

default_val fills the value slots that hold no entry; no method returns it, so any value of V works. The table is a power of two at least twice cap, so cap entries fit without a rehash; a cap below 1 gives the smallest table.

  • cost: O(cap)
  • traps: never

Examples:

  • var m: FlatMap<Int> = FlatMap(0); m.len == 0

Source

FlatMap.len

fn len(self) -> Int

Number of live key-value pairs.

  • cost: O(1)
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(1, 5); m.set(1, 6); m.len == 1

Source

FlatMap.is_empty

fn is_empty(self) -> Bool

Whether the map has no live entries.

  • cost: O(1)
  • traps: never

Examples:

  • FlatMap(0).is_empty == true

Source

FlatMap.clear

fn clear(mut self)

Remove all entries while keeping allocated capacity.

  • cost: O(capacity)
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(1, 5); m.clear(); m.get(1) == None

Source

FlatMap.slot

fn slot(self, k: Int) -> Int

Source

FlatMap.rehash

fn rehash(mut self, new_cap: Int)

Source

FlatMap.get

fn get(self, k: Int) -> ?V

Look up k, returning None if absent.

  • cost: O(1) expected
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(5, 50); m.get(5) == Some(50) and m.get(6) == None

Source

FlatMap.contains

fn contains(self, k: Int) -> Bool

Whether k is currently present.

  • cost: O(1) expected
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(-3, 1); m.contains(-3) and not m.contains(3)

Source

FlatMap.set

fn set(mut self, k: Int, v: V)

Insert or overwrite k -> v.

When the table would pass half full it doubles and every entry is rehashed.

  • cost: O(1) expected amortized
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(1, 5); m.set(1, 6); m.get(1) == Some(6)

Source

FlatMap.get_or_insert

fn get_or_insert(mut self, k: Int, v: V) -> V

Return the value for k, inserting v first if k is absent.

A present k keeps its value; v is then ignored.

  • cost: O(1) expected amortized
  • traps: never

Examples:

  • var m = FlatMap(0); m.get_or_insert(4, 7) == 7 and m.get_or_insert(4, 9) == 7

Source

FlatMap.remove

fn remove(mut self, k: Int) -> ?V

Remove k if present; returns its old value or None.

  • cost: O(1) expected
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(2, 9); m.remove(2) == Some(9) and m.remove(2) == None

Source

FlatMap.reserve

fn reserve(mut self, cap: Int)

Reserve space for at least cap entries without rehashing.

Entries are kept; a cap the table already fits does nothing.

  • cost: O(cap) when the table grows, O(1) otherwise
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(1, 2); m.reserve(1000); m.get(1) == Some(2)

Source

FlatMap.take

fn take(mut self) -> FlatMap<V>

Move the map's contents out in O(1), leaving self empty.

  • cost: O(1)
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(1, 2); let t = m.take(); m.is_empty and t.get(1) == Some(2)

Source

FlatMap.items

fn items(self) -> yields (Int, V)

O(1) to make. Yields every live (key, val) pair.

The order is the table's slot order, which depends on the per-map salt: it is fixed while the map is unchanged and agrees with keys and values, but no program should depend on it. Sort when the order matters.

  • cost: O(1) to make, O(capacity) to walk
  • empty: yields nothing
  • order: unspecified slot order, the same as keys and values while unchanged
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(2, 20); m.set(1, 10); m.items.sorted() == [(1, 10), (2, 20)]

Source

FlatMap.keys

fn keys(self) -> yields Int
  • cost: O(1) to make, O(capacity) to walk
  • empty: yields nothing
  • order: unspecified slot order, the same as items
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(2, 20); m.set(1, 10); m.keys.sorted() == [1, 2]

Source

FlatMap.values

fn values(self) -> yields V
  • cost: O(1) to make, O(capacity) to walk
  • empty: yields nothing
  • order: unspecified slot order, the same as items
  • traps: never

Examples:

  • var m = FlatMap(0); m.set(2, 20); m.set(1, 10); m.values.sorted() == [10, 20]

Source

FlatMap.absorb

fn absorb(mut self, mut other: FlatMap<V>, join: ?((V, V) -> V) = None)

Merge all entries from other into self (emptying other), combining collisions with join or overwriting.

For a key in both maps the result is join(self's value, other's value), or other's value when join is None. The smaller map is drained into the larger, so the argument order of join and the overwrite rule hold whichever side is moved.

  • cost: O(min(|self|, |other|)) expected
  • empty: an empty other leaves self unchanged
  • traps: never

Examples:

  • var a = FlatMap(0); a.set(1, 10); var b = FlatMap(0); b.set(1, 5); b.set(2, 7); a.absorb(mut b, join: (x, y) => x + y); a.get(1) == Some(15) and a.get(2) == Some(7) and b.is_empty
  • var a = FlatMap(0); a.set(1, 10); var b = FlatMap(0); b.set(1, 5); a.absorb(mut b); a.get(1) == Some(5)

Source

Counter

pub struct Counter<K, V = Int>

Default-valued frequency / weight map over hashable keys K. Counter<K> counts with Int (V = Int) and is a Track<K> (std.window): push(k) adds 1, pop(k) takes 1 away. c[k] reads init without inserting; add, get, set, remove, and contains are O(1) expected.

Invariant: no stored entry equals init. A write that leaves a key at init (add, set, absorb) removes it, so len is the number of keys whose value differs from init and contains(k) is get(k) != init.

Source

Counter.new

fn new(init: V) -> Counter<K, V>

Create an empty Counter<K, V> whose missing keys read as init.

  • cost: O(1)
  • traps: never

Examples:

  • var c: Counter<Char, Int> = Counter(0); c.get('z') == 0 and c.len == 0

Source

Counter.of

fn of(xs: List<K>) -> Counter<K, Int>

Count occurrences of each element in xs.

The result has init 0, so a key that never occurs reads 0.

  • cost: O(n) expected
  • empty: an empty counter
  • traps: never

Examples:

  • let c = Counter.of(['a', 'b', 'a']); c.get('a') == 2 and c.get('c') == 0

Source

Counter.len

fn len(self) -> Int

Number of keys with a stored entry.

  • cost: O(1)
  • traps: never

Examples:

  • Counter.of([3, 1, 3]).len == 2

Source

Counter.is_empty

fn is_empty(self) -> Bool

Whether no keys are stored.

  • cost: O(1)
  • traps: never

Examples:

  • Counter.of([1]).is_empty == false

Source

Counter.get

fn get(self, k: K) -> V

Value stored for k, or init if absent (does not insert).

c[k] calls this.

  • cost: O(1) expected
  • traps: never

Examples:

  • let c = Counter.of([5, 5]); c[5] == 2 and c[6] == 0 and c.len == 1

Source

Counter.contains

fn contains(self, k: K) -> Bool

Whether k currently has a stored entry.

  • cost: O(1) expected
  • traps: never

Examples:

  • let c = Counter.of([5]); c.contains(5) and not c.contains(6)

Source

Counter.set

fn set(mut self, k: K, v: V)

Set k to v (W8 IndexSet backing c[k] = v).

Setting a key to init removes it.

  • cost: O(1) expected amortized
  • traps: never

Examples:

  • var c = Counter.of(['a']); c['a'] = 4; c['a'] == 4
  • var c = Counter.of(['a']); c['a'] = 0; c.contains('a') == false

Source

Counter.add

fn add(mut self, k: K, delta: V)

Add delta to k's value, removing k if the result equals init.

An absent key starts from init. c[k] += d is c.add(k, d).

  • cost: O(1) expected amortized
  • traps: never (overflow wraps in release, traps in debug)

Examples:

  • var c: Counter<Char, Int> = Counter(0); c.add('x', 2); c['x'] == 2
  • var c: Counter<Char, Int> = Counter(0); c.add('x', 2); c.add('x', -2); c.len == 0

Source

Counter.remove

fn remove(mut self, k: K) -> ?V

Remove k and return its previous value, or None if absent.

  • cost: O(1) expected
  • traps: never

Examples:

  • var c = Counter.of(['a', 'a']); c.remove('a') == Some(2) and c.remove('a') == None

Source

Counter.reserve

fn reserve(mut self, cap: Int)

Reserve space for at least cap keys.

  • cost: O(cap) when the table grows, O(1) otherwise
  • traps: never

Examples:

  • var c = Counter.of([1]); c.reserve(100); c[1] == 1

Source

Counter.clear

fn clear(mut self)

Remove all entries.

  • cost: O(n)
  • traps: never

Examples:

  • var c = Counter.of([1, 2]); c.clear(); c.len == 0 and c[1] == 0

Source

Counter.take

fn take(mut self) -> Counter<K, V>

Move contents out in O(1), leaving self empty.

The init of self is unchanged.

  • cost: O(1)
  • traps: never

Examples:

  • var c = Counter.of([1]); let d = c.take(); c.is_empty and d[1] == 1

Source

Counter.absorb

fn absorb(mut self, mut other: Counter<K, V>)

Merge all entries from other into self by adding values (emptying other).

Stored values are added: a key stored in both ends at the sum of the two, a key stored in one keeps that value, and a sum equal to init is removed. Absent keys contribute nothing (not init), which keeps the result the same whichever side is drained.

  • cost: O(min(|self|, |other|)) expected
  • empty: an empty other leaves self unchanged
  • traps: never (overflow wraps in release, traps in debug)

Examples:

  • var a = Counter.of(['x', 'y']); var b = Counter.of(['y', 'z']); a.absorb(mut b); a['y'] == 2 and a.len == 3 and b.len == 0

Source

Counter.total

fn total(self) -> V

Sum of all stored values.

Only stored entries count; init is not added for absent keys.

  • cost: O(n)
  • empty: V.zero
  • traps: never (overflow wraps in release, traps in debug)

Examples:

  • Counter.of([1, 1, 2]).total() == 3

Source

Counter.most_common

fn most_common(self, k: Int) -> List<(K, V)>

Top k entries sorted by descending value.

A k at least len returns every entry.

  • cost: O(n log n)
  • empty: []
  • ties: equal values in ascending key order
  • order: descending value; a new List, keyed from 0
  • traps: when k < 0

Examples:

  • Counter.of([3, 1, 3, 2, 1, 3]).most_common(2) == [(3, 3), (1, 2)]
  • Counter.of(['b', 'a']).most_common(5) == [('a', 1), ('b', 1)]

Source

Counter.items

fn items(self) -> yields (K, V)

O(1) to make. Yields every stored (key, val) pair.

  • cost: O(1) to make, O(1) per step
  • empty: yields nothing
  • order: unspecified hash order, the same as keys and values while unchanged
  • traps: never

Examples:

  • Counter.of([2, 1, 2]).items.sorted() == [(1, 1), (2, 2)]

Source

Counter.keys

fn keys(self) -> yields K
  • cost: O(1) to make, O(1) per step
  • empty: yields nothing
  • order: unspecified hash order, the same as items
  • traps: never

Examples:

  • Counter.of([2, 1, 2]).keys.sorted() == [1, 2]

Source

Counter.values

fn values(self) -> yields V
  • cost: O(1) to make, O(1) per step
  • empty: yields nothing
  • order: unspecified hash order, the same as items
  • traps: never

Examples:

  • Counter.of([2, 1, 2]).values.sorted() == [1, 2]

Source

On this page