Struct StackMap 

pub struct StackMap<K, V, const N: usize> { /* private fields */ }

A fixed-capacity hash map that can be stored on the stack.

StackMap is designed as an alternative to HashMap for cases where:

• Collection size is small and known at compile time
• Heap allocations should be avoided
• Cache locality is important for performance

Type Parameters:

• K: Key type, must implement PartialEq
• V: Value type, must implement Clone, when using take
• N: Capacity of the map (const generic parameter)

Implementations

impl<K, V, const N: usize> StackMap<K, V, N>

where K: PartialEq,

pub fn new() -> Self

Creates a new empty StackMap with the capacity specified by the const generic parameter N.

Time Complexity: O(1)

Examples

let map = StackMap::<i32, String, 16>::new();
assert!(map.is_empty());
assert_eq!(map.capacity(), 16);

pub fn insert_or_update( &mut self, key: K, value: V, ) -> Result<(), StackMapError>

Inserts a key-value pair into the map or updates an existing entry.

This method will:

1. Update the value if the key already exists
2. Insert into the first available slot (empty or previously deleted)
3. Return an error if the map is at full capacity

Time Complexity: O(N) in the worst case (linear scan through entries)

Parameters

• key: The key to insert or update
• value: The value to associate with the key

Returns

• Ok(()) if the operation was successful (either inserted or updated)
• Err(StackMapError::MapFull) if the map is full and a new entry couldn’t be added

Examples

let mut map = StackMap::<i32, &str, 4>::new();

// Insert new entries
map.insert_or_update(1, "one").unwrap();
map.insert_or_update(2, "two").unwrap();

// Update existing entry
map.insert_or_update(1, "ONE").unwrap();
assert_eq!(map.get(&1), Some(&"ONE"));

// Fill the map to capacity
map.insert_or_update(3, "three").unwrap();
map.insert_or_update(4, "four").unwrap();

// This will return an error because the map is full
assert_eq!(map.insert_or_update(5, "five"), Err(StackMapError::MapFull));

pub fn get(&self, key: &K) -> Option<&V>

Retrieves a reference to the value associated with the given key.

Time Complexity: O(N) in the worst case (linear scan through entries)

Parameters

• key: The key to look up

Returns

• Some(&V) if the key exists in the map
• None if the key does not exist

Examples

let mut map = StackMap::<&str, i32, 8>::new();
map.insert_or_update("apple", 42).unwrap();

assert_eq!(map.get(&"apple"), Some(&42));
assert_eq!(map.get(&"banana"), None);

pub fn remove(&mut self, key: &K) -> bool

Removes a key from the map, returning whether a value has been found. See take for when you are interested in the actual value (which requires V: Clone)

This method uses a logical deletion approach (setting a deleted flag) rather than physically removing the entry. This preserves the probing sequence for future lookups.

Time Complexity: O(N) in the worst case (linear scan through entries)

Parameters

• key: The key to remove

Returns

• Some(V) with the value if the key was found and removed
• None if the key was not in the map

Examples

let mut map = StackMap::<&str, i32, 8>::new();
map.insert_or_update("apple", 42).unwrap();

assert_eq!(map.remove(&"apple"), true);
assert_eq!(map.len(), 0);
assert_eq!(map.remove(&"apple"), false); // Already removed

pub fn len(&self) -> usize

Returns the number of elements currently in the map.

This only counts non-deleted entries.

Time Complexity: O(1)

Returns

• The number of key-value pairs in the map

Examples

let mut map = StackMap::<i32, &str, 8>::new();
assert_eq!(map.len(), 0);

map.insert_or_update(1, "one").unwrap();
map.insert_or_update(2, "two").unwrap();
assert_eq!(map.len(), 2);

map.remove(&1);
assert_eq!(map.len(), 1);

pub fn is_empty(&self) -> bool

Checks if the map is empty (contains no key-value pairs).

Time Complexity: O(1)

Returns

• true if the map contains no elements
• false if the map contains at least one element

Examples

let mut map = StackMap::<i32, &str, 8>::new();
assert!(map.is_empty());

map.insert_or_update(1, "one").unwrap();
assert!(!map.is_empty());

map.remove(&1);
assert!(map.is_empty());

pub fn capacity(&self) -> usize

Returns the total capacity of the map (maximum number of entries it can hold).

This is determined by the const generic parameter N specified when creating the map.

Time Complexity: O(1)

Returns

• The maximum number of entries the map can hold

Examples

let map = StackMap::<i32, &str, 16>::new();
assert_eq!(map.capacity(), 16);

pub fn clear(&mut self)

Removes all entries from the map, resetting it to an empty state.

This operation completely clears all entries rather than just marking them as deleted.

Time Complexity: O(N)

Examples

let mut map = StackMap::<i32, &str, 8>::new();
map.insert_or_update(1, "one").unwrap();
map.insert_or_update(2, "two").unwrap();
assert_eq!(map.len(), 2);

map.clear();
assert_eq!(map.len(), 0);
assert!(map.is_empty());

pub fn iter(&self) -> impl Iterator<Item = (&K, &V)>

Returns an iterator over the key-value pairs in the map.

The iterator provides immutable references to both keys and values, skipping over deleted entries. The iteration order is based on the internal storage and not dependent on insertion order.

Time Complexity: O(N) to iterate through all elements

Returns

• An iterator yielding (&K, &V) pairs

Examples

let mut map = StackMap::<&str, i32, 8>::new();
map.insert_or_update("one", 1).unwrap();
map.insert_or_update("two", 2).unwrap();

let mut pairs = Vec::new();
for (key, value) in map.iter() {
    pairs.push((*key, *value));
}

// Note: iteration order is not guaranteed
assert_eq!(pairs.len(), 2);
assert!(pairs.contains(&("one", 1)));
assert!(pairs.contains(&("two", 2)));

impl<K, V, const N: usize> StackMap<K, V, N>

where K: PartialEq, V: Clone,

pub fn take(&mut self, key: &K) -> Option<V>

Removes a key from the map, returning the associated value if found.

This method uses a logical deletion approach (setting a deleted flag) rather than physically removing the entry. This preserves the probing sequence for future lookups.

Time Complexity: O(N) in the worst case (linear scan through entries)

Parameters

• key: The key to remove

Returns

• Some(V) with the value if the key was found and removed
• None if the key was not in the map

Examples

let mut map = StackMap::<&str, i32, 8>::new();
map.insert_or_update("apple", 42).unwrap();

assert_eq!(map.take(&"apple"), Some(42));
assert_eq!(map.len(), 0);
assert_eq!(map.take(&"apple"), None); // Already removed

Trait Implementations

impl<K: Debug, V: Debug, const N: usize> Debug for StackMap<K, V, N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.