densemap

Documentation

This library provides a collection DenseMap that are permanently accessible by unique keys and fast iterable. A key is generated upon insertion and can be used to access any element. Inserts, removes, and gets run in constant time, and iteration has the same performance as Vec. Also DenseMap reduces memory usage by reusing removed areas.

Examples

use densemap::{DenseMap, Key};

// Creates a new dense map and inserts some elements.
let mut densemap = DenseMap::new();
let key_of_alice = densemap.insert("alice");
let key_of_bob = densemap.insert("bob");

// Gets an element.
assert_eq!(densemap.get(key_of_alice), Some(&"alice"));

// Removes an element.
assert_eq!(densemap.remove(key_of_alice), Some("alice"));
let key_of_charlie = densemap.insert("charlie");

// Keys are unique and permanently accessible.
assert_eq!(densemap.get(key_of_alice), None);

// Iterates all elements.
for value in densemap.values() {
    println!("{value}");
}

Differences from other libraries

This library is similar to slotmap::DenseSlotMap, but it has some differences. DenseMap has a performance advantage due to reduced overhead. Also this library simply provides only a collection DenseMap.

Benchmarks

The performance measurement results for inserts, removes, reinserts, and iterates on the collections of std-1.72.1. slab-0.4.9, slotmap-1.0.6, and densemap-0.1.0 are shown below table. The results are measured by using criterion on WSL.

License

This library is licensed under the MIT license.