std::map

A hash map with open addressing. Keys need hash(this: K&) -> u64 and eq (std::compare).

Source: std/map.volt

Types

struct std::map

<K: type, V: type, Allocator: std::mem::allocator = std::mem::default_allocator> struct map

A hash map with open addressing: linear probing, and a removal shifts the entries after it back into the gap, so there are no removed markers and a probe stops at the first empty slot.

Field
`slots: std::map_slot<K, V>* = @cast<std::map_slot<K, V>*>(@alignof(std::map_slot<K, V>))`	slots and state are parallel arrays of cap slots; nothing is allocated until the first put. A key and its value share a slot, so a hit reads one place
`state: u8* = @cast<u8*>(1)`	per slot: 0 empty, else its key's tag (map_tag), so most probes that miss compare a byte instead of the key
`len: usize = 0`	the keys held
`cap: usize = 0`	the slots: 0, or a power of two (8, then doubling)
`allocator: Allocator = {}`	where the arrays come from

Methods

<K: type, V: type, A: std::mem::allocator> attach fn new_in(static this: std::map<K, V>, allocator: A) -> std::map<K, V, A>

an empty map that allocates from allocator

<K: type, V: type, A: std::mem::allocator> attach fn reserve(this: std::map<K, V, A>&, n: usize) -> std::mem::mem_error!void

room for n keys without growing: the slots double (at least 8) until n fit under 3/4 of them

<K: type, V: type, A: std::mem::allocator> attach fn put(this: std::map<K, V, A>&, key: K, value: V) -> void

set key to value (an old value for it is deleted)

<K: type, V: type, A: std::mem::allocator> attach fn get(this: std::map<K, V, A>&, key: K) -> V*

the value for key, if there is one

<K: type, V: type, A: std::mem::allocator> attach fn contains(this: std::map<K, V, A>&, key: K) -> bool

whether key has a value

<K: type, V: type, A: std::mem::allocator> attach fn remove(this: std::map<K, V, A>&, key: K) -> V?

take key's value out of the map

<K: type, V: type, A: std::mem::allocator> attach fn clear(this: std::map<K, V, A>&) -> void

deletes every key and value, keeping the slots

<K: type, V: type, A: std::mem::allocator> attach fn iter(this: std::map<K, V, A>&) -> std::map_iter<K, V>

for (e) in m.iter(): each entry, with e.value a reference into the map

<K: type, V: type, A: std::mem::allocator> attach fn copy(this: std::map<K, V, A>&) -> std::map<K, V, A>

a deep copy: a new map holding a copy of every key and value

<K: type, V: type, A: std::mem::allocator> attach fn delete(this: std::map<K, V, A>&) -> void

deletes every key and value, then frees the arrays

struct std::entry

<K: type, V: type> struct entry

a key and its value, as for (e) in m.iter() gives them (don't change the key: the map is ordered by it)

Field
`key: K&`
`value: V&`

struct std::map_iter

<K: type, V: type> struct map_iter

walks a map's entries in no particular order; changing the map while walking isn't allowed

Field
`slots: std::map_slot<K, V>*`
`state: u8*`
`cap: usize`
`i: usize = 0`	the next slot to look at

Methods

<K: type, V: type> attach fn next(this: std::map_iter<K, V>&) -> std::entry<K, V>?

the next full slot's entry

Functions

std::map_mix

fn map_mix(x: u64) -> u64

spreads the bits of an integer key (splitmix64's finalizer)

Methods on other types

Attached to built-in types, or to every type (T).

attach fn hash(this: str&) -> u64

FNV-1a hashes for the built-in key types; a key type K needs hash(this: K&) -> u64 and eq

attach fn hash(this: i32&) -> u64

integers: their bits spread by map_mix

attach fn hash(this: i64&) -> u64

attach fn hash(this: u32&) -> u64

attach fn hash(this: u64&) -> u64

attach fn hash(this: usize&) -> u64

attach fn hash(this: u8&) -> u64

attach fn hash(this: i8&) -> u64

attach fn hash(this: i16&) -> u64

attach fn hash(this: u16&) -> u64

attach fn hash(this: isize&) -> u64

attach fn hash(this: bool&) -> u64