How do I work with index maps and sets in Rust?

Walkthrough

The indexmap crate provides hash maps and sets that preserve insertion order. Unlike HashMap and HashSet which have unpredictable iteration order, IndexMap and IndexSet iterate in the order items were inserted. They also support efficient index-based access, making them useful when you need both key-based lookup and ordered traversal or position-based operations.

Key concepts:

Insertion order — items iterate in the order they were inserted
Index access — access entries by numeric position
Hash map operations — all standard map operations (insert, get, remove)
Hash set operations — set operations with preserved order
Compatibility — API largely compatible with HashMap/HashSet

Code Example

# Cargo.toml
[dependencies]
indexmap = "2.0"

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    // Insert in specific order
    map.insert("apple", 1);
    map.insert("banana", 2);
    map.insert("cherry", 3);
    
    // Iteration preserves insertion order
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
    
    // Access by index
    println!("First item: {:?}", map.get_index(0));
}

Basic IndexMap Operations

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<String, i32> = IndexMap::new();
    
    // Insert values
    map.insert("first".to_string(), 1);
    map.insert("second".to_string(), 2);
    map.insert("third"._string(), 3);
    
    // Get value by key
    if let Some(value) = map.get("second") {
        println!("Value for 'second': {}", value);
    }
    
    // Check if key exists
    println!("Contains 'first': {}", map.contains_key("first"));
    println!("Contains 'fourth': {}", map.contains_key("fourth"));
    
    // Update value
    map.insert("second".to_string(), 20);
    println!("Updated 'second': {:?}", map.get("second"));
    
    // Remove by key
    if let Some((k, v)) = map.shift_remove("third") {
        println!("Removed: {} = {}", k, v);
    }
    
    // Current size
    println!("Size: {}", map.len());
    println!("Is empty: {}", map.is_empty());
    
    // Clear all
    map.clear();
    println!("After clear, is empty: {}", map.is_empty());
}

Index-Based Access

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Get by index
    println!("Index 0: {:?}", map.get_index(0));
    println!("Index 2: {:?}", map.get_index(2));
    println!("Index 10: {:?}", map.get_index(10)); // None
    
    // Get key at index
    println!("Key at index 1: {:?}", map.get_index(1).map(|(k, _)| k));
    
    // Get mutable reference by index
    if let Some((key, value)) = map.get_index_mut(1) {
        println!("Before: {} = {}", key, value);
        *value = 20;
    }
    
    // Get full entry by index
    let entry = map.get_index_entry(2);
    println!("Entry at index 2: {:?}", entry);
    
    // Find index of a key
    println!("Index of 'b': {:?}", map.get_index_of("b"));
    println!("Index of 'z': {:?}", map.get_index_of("z")); // None
    
    // Iterate with indices
    for (idx, (key, value)) in map.iter().enumerate() {
        println!("Index {}: {} = {}", idx, key, value);
    }
}

Insertion Order Preservation

use indexmap::IndexMap;
use std::collections::HashMap;
 
fn main() {
    // HashMap - unpredictable order
    let mut hash_map: HashMap<&str, i32> = HashMap::new();
    hash_map.insert("cherry", 3);
    hash_map.insert("apple", 1);
    hash_map.insert("banana", 2);
    hash_map.insert("date", 4);
    
    println!("HashMap iteration (unpredictable):";
    for (k, v) in &hash_map {
        print!("{}={}, ", k, v);
    }
    println!();
    
    // IndexMap - preserves insertion order
    let mut index_map: IndexMap<&str, i32> = IndexMap::new();
    index_map.insert("cherry", 3);
    index_map.insert("apple", 1);
    index_map.insert("banana", 2);
    index_map.insert("date", 4);
    
    println!("\nIndexMap iteration (insertion order):";
    for (k, v) in &index_map {
        print!("{}={}, ", k, v);
    }
    println!();
    
    // This order is guaranteed and consistent
    let keys: Vec<_> = index_map.keys().collect();
    println!("\nKeys in order: {:?}", keys);
}

Removal Methods

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    map.insert("e", 5);
    
    println!("Initial: {:?}", map.iter().collect::<Vec<_>>());
    
    // shift_remove: preserves order of remaining elements (O(n))
    map.shift_remove("c");
    println!("After shift_remove('c'): {:?}", map.iter().collect::<Vec<_>>());
    
    // swap_remove: swaps with last element, O(1) but changes order
    map.insert("c", 3); // Add back
    map.swap_remove("b");
    println!("After swap_remove('b'): {:?}", map.iter().collect::<Vec<_>>());
    
    // Remove by index
    map.shift_remove_index(1);
    println!("After shift_remove_index(1): {:?}", map.iter().collect::<Vec<_>>());
    
    // pop: remove the last element
    if let Some((k, v)) = map.pop() {
        println!("Popped: {} = {}", k, v);
    }
    println!("After pop: {:?}", map.iter().collect::<Vec<_>>());
}

IndexSet Operations

use indexmap::IndexSet;
 
fn main() {
    let mut set: IndexSet<&str> = IndexSet::new();
    
    // Insert values
    set.insert("apple");
    set.insert("banana");
    set.insert("cherry");
    set.insert("banana"); // Duplicate, won't be added
    
    println!("Set contents (order preserved):");
    for item in &set {
        println!("  {}", item);
    }
    
    // Check membership
    println!("\nContains 'banana': {}", set.contains("banana"));
    println!("Contains 'date': {}", set.contains("date"));
    
    // Get by index
    println!("\nIndex 0: {:?}", set.get_index(0));
    println!("Index 2: {:?}", set.get_index(2));
    
    // Get index of value
    println!("Index of 'cherry': {:?}", set.get_index_of("cherry"));
    
    // Remove by value
    set.shift_remove("banana");
    println!("\nAfter removing 'banana':");
    for (i, item) in set.iter().enumerate() {
        println!("  {}: {}", i, item);
    }
    
    // Remove by index
    set.shift_remove_index(0);
    println!("\nAfter removing index 0:");
    for item in &set {
        println!("  {}", item);
    }
}

Set Operations

use indexmap::IndexSet;
 
fn main() {
    let mut a: IndexSet<i32> = IndexSet::new();
    a.insert(1);
    a.insert(2);
    a.insert(3);
    
    let mut b: IndexSet<i32> = IndexSet::new();
    b.insert(2);
    b.insert(3);
    b.insert(4);
    
    // Union (preserves order from a, then b)
    let union: IndexSet<i32> = a.union(&b).cloned().collect();
    println!("Union: {:?}", union.iter().collect::<Vec<_>>());
    
    // Intersection (preserves order from a)
    let intersection: IndexSet<i32> = a.intersection(&b).cloned().collect();
    println!("Intersection: {:?}", intersection.iter().collect::<Vec<_>>());
    
    // Difference (preserves order from a)
    let difference: IndexSet<i32> = a.difference(&b).cloned().collect();
    println!("Difference (a - b): {:?}", difference.iter().collect::<Vec<_>>());
    
    // Symmetric difference (preserves order)
    let sym_diff: IndexSet<i32> = a.symmetric_difference(&b).cloned().collect();
    println!("Symmetric difference: {:?}", sym_diff.iter().collect::<Vec<_>>());
    
    // Subset/superset checks
    let mut c: IndexSet<i32> = IndexSet::new();
    c.insert(1);
    c.insert(2);
    
    println!("\nIs {1,2} subset of {1,2,3}: {}", c.is_subset(&a));
    println!("Is {1,2,3} superset of {1,2}: {}", a.is_superset(&c));
    println!("Is {1,2} disjoint from {3,4}: {}", c.is_disjoint(&b));
}

Entry API

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    // entry API similar to HashMap
    map.entry("apple").or_insert(1);
    map.entry("banana").or_insert(2);
    
    // Won't overwrite existing
    map.entry("apple").or_insert(100);
    println!("apple: {:?}", map.get("apple")); // Still 1
    
    // or_insert_with for lazy evaluation
    map.entry("cherry").or_insert_with(|| {
        println!("Computing value for cherry");
        3
    });
    
    // and_modify to update existing
    map.entry("apple").and_modify(|v| *v *= 10);
    println!("apple after modify: {:?}", map.get("apple"));
    
    // Combine or_insert_with and and_modify
    map.entry("banana")
        .and_modify(|v| *v += 1)
        .or_insert(1);
    
    println!("\nFinal map:");
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
}

Iteration Methods

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Iterate over key-value pairs
    println!("Key-value pairs:");
    for (key, value) in map.iter() {
        println!("  {} = {}", key, value);
    }
    
    // Iterate over keys
    println!("\nKeys:");
    for key in map.keys() {
        println!("  {}", key);
    }
    
    // Iterate over values
    println!("\nValues:");
    for value in map.values() {
        println!("  {}", value);
    }
    
    // Mutable iteration
    println!("\nValues (mutable, doubled):");
    for value in map.values_mut() {
        *value *= 2;
    }
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
    
    // Into iteration (consumes map)
    let map2: IndexMap<&str, i32> = [("x", 10), ("y", 20)].into_iter().collect();
    println!("\nFrom iterator:");
    for (k, v) in map2 {
        println!("  {} = {}", k, v);
    }
}

Building from Iterators

use indexmap::{IndexMap, IndexSet};
 
fn main() {
    // From array
    let map: IndexMap<&str, i32> = [
        ("apple", 1),
        ("banana", 2),
        ("cherry", 3),
    ].into_iter().collect();
    
    println!("From array:");
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
    
    // From vec of tuples
    let vec = vec![(1, "one"), (2, "two"), (3, "three")];
    let map2: IndexMap<i32, &str> = vec.into_iter().collect();
    
    println!("\nFrom vec:");
    for (k, v) in &map2 {
        println!("  {} = {}", k, v);
    }
    
    // Set from iterator
    let set: IndexSet<_> = ["x", "y", "z", "y"].iter().cloned().collect();
    println!("\nSet from iterator: {:?}", set.iter().collect::<Vec<_>>());
    
    // With capacity
    let mut map_with_cap: IndexMap<i32, String> = IndexMap::with_capacity(100);
    println!("Capacity: {}", map_with_cap.capacity());
}

Sorting

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("cherry", 3);
    map.insert("apple", 1);
    map.insert("banana", 2);
    map.insert("date", 4);
    
    println!("Original order:");
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
    
    // Sort by key
    map.sort_keys();
    println!("\nAfter sort_keys():");
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
    
    // Sort by values (using sort_by)
    map.sort_by(|k1, v1, k2, v2| v1.cmp(v2));
    println!("\nAfter sort_by value:");
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
    
    // Reverse sort
    map.sort_by(|k1, v1, k2, v2| v2.cmp(v1));
    println!("\nAfter reverse sort by value:");
    for (k, v) in &map {
        println!("  {} = {}", k, v);
    }
}

Swapping and Moving Entries

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    println!("Before swap: {:?}", map.keys().collect::<Vec<_>>());
    
    // Swap two entries by index
    map.swap_indices(0, 3);
    println!("After swap(0, 3): {:?}", map.keys().collect::<Vec<_>>());
    
    // Move entry to end
    let index = map.get_index_of("b").unwrap();
    map.move_index(index, map.len() - 1);
    println!("After moving 'b' to end: {:?}", map.keys().collect::<Vec<_>>());
    
    // Reverse the map
    let reversed: IndexMap<&str, i32> = map.into_iter().rev().collect();
    println!("Reversed: {:?}", reversed.keys().collect::<Vec<_>>());
}

Capacity Management

use indexmap::IndexMap;
 
fn main() {
    // Create with capacity
    let mut map: IndexMap<i32, &str> = IndexMap::with_capacity(10);
    println!("Initial capacity: {}", map.capacity());
    
    // Add items
    for i in 0..5 {
        map.insert(i, &format!("value{}", i));
    }
    println!("After 5 inserts - len: {}, capacity: {}", map.len(), map.capacity());
    
    // Reserve additional capacity
    map.reserve(100);
    println!("After reserve(100) - capacity: {}", map.capacity());
    
    // Shrink to fit
    map.shrink_to_fit();
    println!("After shrink_to_fit - capacity: {}", map.capacity());
    
    // Shrink to minimum capacity
    map.shrink_to(10);
    println!("After shrink_to(10) - capacity: {}", map.capacity());
}

Real-World Example: Ordered Configuration

use indexmap::IndexMap;
 
#[derive(Debug, Clone)]
struct Config {
    values: IndexMap<String, String>,
}
 
impl Config {
    fn new() -> Self {
        Self {
            values: IndexMap::new(),
        }
    }
    
    fn set(&mut self, key: &str, value: &str) {
        self.values.insert(key.to_string(), value.to_string());
    }
    
    fn get(&self, key: &str) -> Option<&String> {
        self.values.get(key)
    }
    
    fn remove(&mut self, key: &str) -> Option<String> {
        self.values.shift_remove(key)
    }
    
    // Get value at specific position
    fn get_at(&self, index: usize) -> Option<(&String, &String)> {
        self.values.get_index(index)
    }
    
    // Find the position of a key
    fn position(&self, key: &str) -> Option<usize> {
        self.values.get_index_of(key)
    }
    
    // Render as ordered list
    fn to_ordered_list(&self) -> Vec<String> {
        self.values
            .iter()
            .map(|(k, v)| format!("{} = {}", k, v))
            .collect()
    }
}
 
fn main() {
    let mut config = Config::new();
    
    // Set values in specific order
    config.set("host", "localhost");
    config.set("port", "8080");
    config.set("database", "myapp");
    config.set("user", "admin");
    
    println!("Configuration (in order):");
    for line in config.to_ordered_list() {
        println!("  {}", line);
    }
    
    // Access by position
    println!("\nFirst config: {:?}", config.get_at(0));
    
    // Find position
    println!("Position of 'database': {:?}", config.position("database"));
    
    // Update preserves order
    config.set("port", "443");
    println!("\nAfter updating port:");
    for (k, v) in &config.values {
        println!("  {} = {}", k, v);
    }
}

Real-World Example: Request Headers

use indexmap::IndexMap;
 
#[derive(Debug)]
struct Headers {
    headers: IndexMap<String, String>,
}
 
impl Headers {
    fn new() -> Self {
        Self {
            headers: IndexMap::new(),
        }
    }
    
    fn insert(&mut self, name: &str, value: &str) {
        // Headers are case-insensitive, so store lowercase
        self.headers.insert(name.to_lowercase(), value.to_string());
    }
    
    fn get(&self, name: &str) -> Option<&String> {
        self.headers.get(&name.to_lowercase())
    }
    
    fn remove(&mut self, name: &str) -> Option<String> {
        self.headers.shift_remove(&name.to_lowercase())
    }
    
    // Headers need to be sent in the same order they were added
    fn to_http_string(&self) -> String {
        self.headers
            .iter()
            .map(|(k, v)| format!("{}: {}", k, v))
            .collect::<Vec<_>>()
            .join("\r\n")
    }
}
 
fn main() {
    let mut headers = Headers::new();
    
    // Standard headers in typical order
    headers.insert("Host", "example.com");
    headers.insert("User-Agent", "MyApp/1.0");
    headers.insert("Accept", "application/json");
    headers.insert("Authorization", "Bearer token123");
    
    // Order is preserved
    println!("HTTP Headers:\n{}\n", headers.to_http_string());
    
    // Access headers
    println!("Host: {:?}", headers.get("Host"));
    println!("Authorization: {:?}", headers.get("authorization")); // case-insensitive
    
    // Remove header
    headers.remove("Authorization");
    println!("\nAfter removing Authorization:");
    println!("{}", headers.to_http_string());
}

Real-World Example: Menu Items

use indexmap::IndexMap;
 
#[derive(Debug, Clone)]
struct MenuItem {
    name: String,
    price: f64,
    description: String,
}
 
struct Menu {
    items: IndexMap<String, MenuItem>,
}
 
impl Menu {
    fn new() -> Self {
        Self {
            items: IndexMap::new(),
        }
    }
    
    fn add(&mut self, id: &str, name: &str, price: f64, description: &str) {
        self.items.insert(id.to_string(), MenuItem {
            name: name.to_string(),
            price,
            description: description.to_string(),
        });
    }
    
    fn get(&self, id: &str) -> Option<&MenuItem> {
        self.items.get(id)
    }
    
    fn get_by_position(&self, pos: usize) -> Option<(&str, &MenuItem)> {
        self.items.get_index(pos).map(|(k, v)| (k.as_str(), v))
    }
    
    fn position(&self, id: &str) -> Option<usize> {
        self.items.get_index_of(id)
    }
    
    fn display(&self) {
        println!("Menu:");
        for (idx, (id, item)) in self.items.iter().enumerate() {
            println!("  {}. {} - ${:.2}", idx + 1, item.name, item.price);
            println!("     ID: {}", id);
            println!("     {}", item.description);
        }
    }
    
    fn display_numbered(&self) {
        println!("\nQuick menu (by number):");
        for (idx, (_, item)) in self.items.iter().enumerate() {
            println!("  {}. {} - ${:.2}", idx + 1, item.name, item.price);
        }
    }
}
 
fn main() {
    let mut menu = Menu::new();
    
    // Add items in display order
    menu.add("burger", "Classic Burger", 12.99, "Beef patty with fresh vegetables");
    menu.add("fries", "French Fries", 4.99, "Crispy golden fries");
    menu.add("shake", "Milkshake", 6.99, "Choose vanilla, chocolate, or strawberry");
    menu.add("soda", "Soft Drink", 2.99, "Various flavors available");
    
    menu.display();
    menu.display_numbered();
    
    // Order by number
    println!("\nOrdering item #2:");
    if let Some((id, item)) = menu.get_by_position(1) {
        println!("  You ordered: {} for ${:.2}", item.name, item.price);
    }
    
    // Look up by ID
    println!("\nDetails for 'burger':");
    if let Some(item) = menu.get("burger") {
        println!("  {} - ${:.2}", item.name, item.price);
    }
}

Comparing HashMap vs IndexMap

use std::collections::HashMap;
use indexmap::IndexMap;
 
fn main() {
    let data = vec![
        ("first", 1),
        ("second", 2),
        ("third", 3),
        ("fourth", 4),
    ];
    
    // HashMap
    let mut hashmap: HashMap<&str, i32> = HashMap::new();
    for (k, v) in &data {
        hashmap.insert(*k, *v);
    }
    
    // IndexMap
    let mut indexmap: IndexMap<&str, i32> = IndexMap::new();
    for (k, v) in &data {
        indexmap.insert(*k, *v);
    }
    
    println!("HashMap keys (unordered): {:?}", hashmap.keys().collect::<Vec<_>>());
    println!("IndexMap keys (ordered): {:?}", indexmap.keys().collect::<Vec<_>>());
    
    // IndexMap supports index access
    println!("\nIndexMap[0]: {:?}", indexmap.get_index(0));
    println!("IndexMap index of 'third': {:?}", indexmap.get_index_of("third"));
    
    // HashMap doesn't have these methods
    // hashmap.get_index(0); // Error: no such method
}

Performance Considerations

use indexmap::IndexMap;
use std::time::Instant;
 
fn main() {
    // IndexMap has slightly higher memory overhead than HashMap
    // due to maintaining order indices
    
    let n = 100_000;
    
    // Insert performance
    let mut map = IndexMap::with_capacity(n);
    let start = Instant::now();
    for i in 0..n {
        map.insert(i, i * 2);
    }
    let insert_time = start.elapsed();
    println!("Insert {} items: {:?}", n, insert_time);
    
    // Lookup performance (similar to HashMap)
    let start = Instant::now();
    let mut sum = 0;
    for i in 0..n {
        if let Some(v) = map.get(&i) {
            sum += v;
        }
    }
    let lookup_time = start.elapsed();
    println!("Lookup {} items: {:?}", n, lookup_time);
    
    // shift_remove is O(n), swap_remove is O(1)
    let mut map2 = map.clone();
    
    let start = Instant::now();
    for i in 0..1000 {
        map.shift_remove(&i);
    }
    let shift_time = start.elapsed();
    println!("shift_remove 1000 items: {:?}", shift_time);
    
    let start = Instant::now();
    for i in 1000..2000 {
        map2.swap_remove(&i);
    }
    let swap_time = start.elapsed();
    println!("swap_remove 1000 items: {:?}", swap_time);
    
    println!("\nTip: Use swap_remove when order doesn't matter");
    println!("Tip: Use shift_remove when you need to preserve order");
}

Summary

IndexMap and IndexSet preserve insertion order, unlike HashMap and HashSet
Use get_index(i) and get_index_mut(i) for position-based access
Use get_index_of(key) to find the position of a key
shift_remove preserves order (O(n)), swap_remove is faster but changes order (O(1))
sort_keys() sorts by key, sort_by() allows custom sorting
Entry API works like HashMap: entry(key).or_insert(value)
Set operations: union, intersection, difference, symmetric_difference
Ideal for: configuration with order, headers, ordered menus, any case where iteration order matters
Slightly higher memory overhead than HashMap due to order tracking
Use when you need both key lookup AND ordered/indexed access