Hashmap's Friends

Store Data in an Insertion-ordered Map

indexmap indexmap-crates.io indexmap-github indexmap-lib.rs cat-data-structures cat-no-std

IndexMap is a data structure in Rust that combines the features of a hashmap and a vector.

indexmap offers a hash map that separately keeps track of insertion order and allows you to efficiently iterate over its elements in that order.

use indexmap::IndexMap;

/// This example demonstrates the usage of `IndexMap` from the `indexmap` crate.
///
/// `IndexMap` is a hash table that preserves the order of key insertion.
/// It provides methods for accessing elements by index and using the `entry`.
/// API.
fn main() {
    // Create an IndexMap:
    let mut map = IndexMap::new();

    // Insert elements:
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);

    // Iterate in insertion order:
    println!("Iterating over IndexMap in insertion order:");
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }

    // Access elements by index:
    if let Some((key, value)) = map.get_index(1) {
        println!("Element at index 1: {}: {}", key, value);
    }

    // Use the `entry` API:
    map.entry("d").or_insert(4);
    map.entry("a").or_insert(10); // This won't change "a" because it already exists.
    println!("IndexMap after using entry API:");
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
}

Store Data in a multimap

multimap multimap-crates.io multimap-github multimap-lib.rs

A MultiMap allows you to store multiple values for a single key, which can be useful when you need to associate several items with the same identifier.

multimap is implemented as a thin wrapper around std::collections::HashMap.

//! This example demonstrates how to use a `MultiMap` to store multiple values
//! for the same key.
use anyhow::Result;
use crates_io_api::Category;
use crates_io_api::SyncClient;
use multimap::MultiMap;

// Calls the crates.io API client and retrieve the categories a given crate
// belongs to.
fn get_categories_for_crate(crate_name: &str) -> Result<Vec<Category>> {
    let client = SyncClient::new(
        "my-user-agent (my-contact@domain.com)",
        std::time::Duration::from_millis(1000), // Rate limit interval
    )?;
    // Retrieve the crate's information:
    let crt = client.get_crate(crate_name)?;
    Ok(crt.categories)
}

fn main() -> Result<()> {
    let crate_names = vec!["toml", "config", "nom", "pest"];

    let mut m: MultiMap<String, &str> = MultiMap::new();
    for name in crate_names {
        for cat in get_categories_for_crate(name)? {
            // There can be multiple crates in the same category.
            // A multimap allows multiple values for the same key.
            m.insert(cat.slug, name);
        }
    }

    // Get all values for a given key:
    println!(
        "List of crates in the `config` category: {:?}",
        m.get_vec("config")
    );

    // Or iterate over all keys and the key's vector:
    for (cat, names) in m.iter_all() {
        println!("Category: {:?}, names: {:?}", cat, names);
    }
    Ok(())
}

Store Collections of Objects that Need Stable, Safe References

slotmap slotmap-crates.io slotmap-github slotmap-lib.rs

Slotmap offers a way to handle collections where items can be added or removed dynamically, and each item is identified by a unique key. Slotmap ensures stable indices, meaning once an item is inserted, its key remains valid until the item is explicitly removed.

Use slotmap to store collections of objects that need stable, safe references but have no clear ownership otherwise, such as game entities or graph nodes.

slotmap provides three containers with persistent unique keys to access stored values, SlotMap, HopSlotMap and DenseSlotMap. Two secondary maps, SecondaryMap and SparseSecondaryMap are also provided that map further objects to the keys created by one of the slot maps.

//! Demonstrates the usage of `SlotMap` and `SecondaryMap` from the `slotmap`
//! crate.
//!
//! This example showcases how to create, insert, access, and remove elements
//! from a `SlotMap`, and how to use a `SecondaryMap` to associate additional
//! data with the elements in the `SlotMap`.
use slotmap::SecondaryMap;
use slotmap::SlotMap;

fn main() {
    // Create a new SlotMap.
    let mut sm = SlotMap::new();

    // Upon insertion, a unique key is generated.
    // It can be used to later access or remove the values.
    // Insertion, removal and access all take O(1) time.
    let key1 = sm.insert("value");

    // The difference between a `BTreeMap` or `HashMap` and a slot map is that
    // the key is generated, always unique,
    // and will only refer to the value that was inserted.
    let key2 = sm.insert("value");
    assert_ne!(key1, key2);

    // Access values by key.
    assert_eq!(sm[key1], "value");
    println!("Value for `key1`: {:?}", sm.get(key1));

    // Remove a value
    // The keys returned by slotmap are versioned.
    // This means that once a key is removed, it stays removed,
    // even if the physical storage inside the slotmap is reused for new
    // elements.
    sm.remove(key1);
    assert!(!sm.contains_key(key1));

    // Try to access the removed value.
    println!("Key1 after removal: {:?}", sm.get(key1));

    assert_eq!(sm.get(key2), Some(&"value"));

    // You can also create (multiple) secondary maps that can map the keys
    // returned by SlotMap to other values, to associate arbitrary data with
    // objects stored in slot maps.
    let mut sec = SecondaryMap::new();
    // Insert a value into the secondary map, associated with `key2`.
    sec.insert(key2, "secondary");

    for (key, val) in sm {
        println!("In slotmap: {}; in secondary map: {}", val, sec[key]);
    }
}