HashMap's Friends

Recipe	Crates	Categories
Store Data in an Insertion-ordered Map
Store Data in a multimap
Store Collections of Objects that Need Stable, Safe References

Store Data in an Insertion-ordered Map

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

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: {cat:?}, names: {names:?}");
    }
    Ok(())
}

Store Collections of Objects that Need Stable, Safe References

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]);
    }
}