How do I preserve insertion order with indexmap in Rust?

Walkthrough

The indexmap crate provides hash-based data structures that maintain insertion order. Unlike the standard HashMap and HashSet, which have arbitrary iteration order, IndexMap and IndexSet iterate in the order elements were inserted. This makes them ideal for JSON serialization, configuration parsing, ordered caches, and any scenario where deterministic iteration order matters while maintaining O(1) lookup performance.

Key concepts:

IndexMap — like HashMap but preserves insertion order
IndexSet — like HashSet but preserves insertion order
Index Access — access elements by position with get_index()
Mutable Operations — modify values in place while preserving order
Performance — nearly identical to HashMap for lookups, slightly slower for inserts

Code Example

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

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    
    map.insert("c", 3);
    map.insert("a", 1);
    map.insert("b", 2);
    
    // Iteration order matches insertion order
    for (key, value) in &map {
        println!("{}: {}", key, value); // c, a, b
    }
}

Basic IndexMap Usage

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    
    // Insert in specific order
    map.insert("apple", 5);
    map.insert("banana", 3);
    map.insert("cherry", 8);
    
    // Lookup by key (O(1))
    println!("apple count: {:?}", map.get("apple"));
    
    // Iteration preserves insertion order
    println!("\nIn insertion order:");
    for (key, value) in &map {
        println!("  {} => {}", key, value);
    }
    
    // Keys(), values() also preserve order
    println!("\nKeys: {:?}", map.keys().collect::<Vec<_>>());
    println!("Values: {:?}", map.values().collect::<Vec<_>>());
}

Index-Based Access

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // Access by index (O(1))
    println!("Index 0: {:?}", map.get_index(0));
    println!("Index 1: {:?}", map.get_index(1));
    println!("Index 2: {:?}", map.get_index(2));
    
    // Get mutable reference by index
    if let Some((key, value)) = map.get_index_mut(1) {
        println!("\nModifying {}", key);
        *value *= 10;
    }
    
    // Get key-value pair by index
    for i in 0..map.len() {
        if let Some((k, v)) = map.get_index(i) {
            println!("Position {}: {} = {}", i, k, v);
        }
    }
}

Compare with HashMap Order

use std::collections::HashMap;
use indexmap::IndexMap;
 
fn main() {
    // Standard HashMap - unpredictable order
    let mut std_map = HashMap::new();
    std_map.insert("c", 3);
    std_map.insert("a", 1);
    std_map.insert("b", 2);
    
    println!("HashMap iteration order:");
    for (k, v) in &std_map {
        println!("  {} => {}", k, v);
    }
    
    // IndexMap - insertion order guaranteed
    let mut index_map = IndexMap::new();
    index_map.insert("c", 3);
    index_map.insert("a", 1);
    index_map.insert("b", 2);
    
    println!("\nIndexMap iteration order:");
    for (k, v) in &index_map {
        println!("  {} => {}", k, v);
    }
}

IndexSet

use indexmap::IndexSet;
 
fn main() {
    let mut set = IndexSet::new();
    
    // Insert in specific order
    set.insert("red");
    set.insert("green");
    set.insert("blue");
    set.insert("red"); // Duplicate - ignored
    
    // Check membership
    println!("Contains red: {}", set.contains("red"));
    println!("Contains yellow: {}", set.contains("yellow"));
    
    // Iteration preserves insertion order
    println!("\nIn insertion order:");
    for value in &set {
        println!("  {}", value);
    }
    
    // Access by index
    println!("\nBy index:");
    for i in 0..set.len() {
        println!("  Index {}: {:?}", i, set.get_index(i));
    }
}

Updating Values

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    
    // insert() returns old value if key exists
    map.insert("a", 1);
    let old = map.insert("a", 2);
    println!("Old value for 'a': {:?}", old);
    
    // entry() API (similar to HashMap)
    map.entry("b").or_insert(10);
    map.entry("b").and_modify(|v| *v += 1).or_insert(1);
    
    // Update without changing position
    if let Some(value) = map.get_mut("a") {
        *value = 100;
    }
    
    for (k, v) in &map {
        println!("{} => {}", k, v);
    }
}

Removing Elements

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    println!("Before removal:");
    for (k, v) in &map {
        println!("  {} => {}", k, v);
    }
    
    // Remove by key (shifts subsequent elements)
    map.remove("b");
    
    println!("\nAfter remove('b'):");
    for (k, v) in &map {
        println!("  {} => {}", k, v);
    }
    
    // Remove by index
    map.remove_index(0); // Removes 'a'
    
    println!("\nAfter remove_index(0):");
    for (k, v) in &map {
        println!("  {} => {}", k, v);
    }
    
    // Swap remove (O(1), but changes order)
    let mut map2 = IndexMap::new();
    map2.insert("a", 1);
    map2.insert("b", 2);
    map2.insert("c", 3);
    
    map2.swap_remove("b"); // Swaps last element to 'b's position
    
    println!("\nAfter swap_remove('b'):");
    for (k, v) in &map2 {
        println!("  {} => {}", k, v);
    }
}

Insert at Specific Position

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("c", 3);
    
    // Insert at specific position
    map.insert_before("b", "c", 2); // Insert "b" before "c"
    
    // Alternatively, use insert_sorted for sorted insertion
    let mut sorted_map = IndexMap::new();
    sorted_map.insert("c", 3);
    sorted_map.insert("a", 1);
    sorted_map.insert("b", 2);
    
    // Re-sort by key
    sorted_map.sort_keys();
    
    println!("Sorted by key:");
    for (k, v) in &sorted_map {
        println!("  {} => {}", k, v);
    }
}

Serde Serialization

// Cargo.toml:
// indexmap = { version = "2.0", features = ["serde"] }
 
use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("z", 1);
    map.insert("a", 2);
    map.insert("m", 3);
    
    // Serialize to JSON (order preserved)
    let json = serde_json::to_string(&map).unwrap();
    println!("JSON: {}", json);
    // Output: {"z":1,"a":2,"m":3}
    
    // Deserialize back (order preserved)
    let parsed: IndexMap<String, i32> = serde_json::from_str(&json).unwrap();
    println!("\nDeserialized order:");
    for (k, v) in &parsed {
        println!("  {} => {}", k, v);
    }
}

JSON Configuration Example

// Cargo.toml:
// indexmap = { version = "2.0", features = ["serde"] }
 
use indexmap::IndexMap;
use serde::{Deserialize, Serialize};
 
#[derive(Debug, Serialize, Deserialize)]
struct Config {
    // Preserve field order for readable config files
    #[serde(flatten)]
    settings: IndexMap<String, String>,
}
 
fn main() {
    let json = r#"{
        "database_host": "localhost",
        "database_port": "5432",
        "api_key": "secret",
        "timeout": "30"
    }"#;
    
    let config: Config = serde_json::from_str(json).unwrap();
    
    println!("Settings in file order:");
    for (key, value) in &config.settings {
        println!("  {} = {}", key, value);
    }
    
    // Re-serialize preserves order
    let output = serde_json::to_string_pretty(&config).unwrap();
    println!("\nRe-serialized:\n{}", output);
}

Ordered Dictionary Pattern

use indexmap::IndexMap;
 
struct OrderedDictionary {
    words: IndexMap<String, Vec<String>>,
}
 
impl OrderedDictionary {
    fn new() -> Self {
        Self { words: IndexMap::new() }
    }
    
    fn add_word(&mut self, word: &str, definitions: Vec<String>) {
        self.words.insert(word.to_string(), definitions);
    }
    
    fn lookup(&self, word: &str) -> Option<&Vec<String>> {
        self.words.get(word)
    }
    
    fn word_at(&self, index: usize) -> Option<(&String, &Vec<String>)> {
        self.words.get_index(index)
    }
    
    fn words(&self) -> impl Iterator<Item = &String> {
        self.words.keys()
    }
}
 
fn main() {
    let mut dict = OrderedDictionary::new();
    
    // Add words in specific order
    dict.add_word("apple", vec!["A fruit".into(), "A tech company".into()]);
    dict.add_word("banana", vec!["A yellow fruit".into()]);
    dict.add_word("cherry", vec!["A small red fruit".into()]);
    
    println!("Words in order:");
    for word in dict.words() {
        println!("  - {}", word);
    }
    
    println!("\nFirst word: {:?}", dict.word_at(0));
    println!("Definition of 'banana': {:?}", dict.lookup("banana"));
}

LRU Cache Implementation

use indexmap::IndexMap;
 
struct LruCache<K, V> {
    cache: IndexMap<K, V>,
    capacity: usize,
}
 
impl<K: std::hash::Hash + Eq + Clone, V> LruCache<K, V> {
    fn new(capacity: usize) -> Self {
        Self {
            cache: IndexMap::with_capacity(capacity),
            capacity,
        }
    }
    
    fn get(&mut self, key: &K) -> Option<&V> {
        // Move to end (most recently used)
        if self.cache.contains_key(key) {
            let (_, value) = self.cache.remove_entry(key).unwrap();
            self.cache.insert(key.clone(), value);
        }
        self.cache.get(key)
    }
    
    fn put(&mut self, key: K, value: V) {
        // Remove if exists
        self.cache.remove(&key);
        
        // Evict oldest if at capacity
        if self.cache.len() >= self.capacity {
            self.cache.remove_index(0);
        }
        
        self.cache.insert(key, value);
    }
    
    fn len(&self) -> usize {
        self.cache.len()
    }
}
 
fn main() {
    let mut cache = LruCache::new(3);
    
    cache.put("a", 1);
    cache.put("b", 2);
    cache.put("c", 3);
    
    println!("Cache size: {}", cache.len());
    
    // Access 'a' - moves it to most recently used
    cache.get(&"a".to_string());
    
    // Add new item - evicts 'b' (oldest after 'a' access)
    cache.put("d", 4);
    
    println!("\nCache contents (oldest to newest):");
    // Note: This accesses internal cache directly for demo
    for (k, v) in &cache.cache {
        println!("  {} => {}", k, v);
    }
}

First/Last Access

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("first", 1);
    map.insert("middle", 2);
    map.insert("last", 3);
    
    // Get first and last elements
    println!("First: {:?}", map.first());
    println!("Last: {:?}", map.last());
    
    // Mutable access to last
    if let Some((key, value)) = map.last_mut() {
        println!("\nModifying last key: {}", key);
        *value = 100;
    }
    
    // Pop last element
    let popped = map.pop();
    println!("\nPopped: {:?}", popped);
    println!("Remaining: {:?}", map.iter().collect::<Vec<_>>());
}

Find Key Index

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("apple", 5);
    map.insert("banana", 3);
    map.insert("cherry", 8);
    
    // Get the index of a key
    if let Some(index) = map.get_index_of("banana") {
        println!("'banana' is at index {}", index);
    }
    
    // Check if contains and get index
    let key_to_find = "cherry";
    match map.get_full(key_to_find) {
        Some((index, key, value)) => {
            println!("Found '{}' at index {} with value {}", key, index, value);
        }
        None => println!("Key not found"),
    }
}

Iteration Patterns

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Iterate with indices
    for (index, (key, value)) in map.iter().enumerate() {
        println!("Index {}: {} = {}", index, key, value);
    }
    
    // Mutable iteration
    for (_, value) in map.iter_mut() {
        *value *= 2;
    }
    
    println!("\nAfter doubling:");
    for (k, v) in &map {
        println!("  {} => {}", k, v);
    }
    
    // Drain all elements
    let drained: Vec<_> = map.drain(..).collect();
    println!("\nDrained: {:?}", drained);
    println!("Map is now empty: {}", map.is_empty());
}

Set Operations with IndexSet

use indexmap::IndexSet;
 
fn main() {
    let mut set1 = IndexSet::new();
    set1.insert("a");
    set1.insert("b");
    set1.insert("c");
    
    let mut set2 = IndexSet::new();
    set2.insert("b");
    set2.insert("c");
    set2.insert("d");
    
    // Intersection
    let intersection: IndexSet<_> = set1.intersection(&set2).cloned().collect();
    println!("Intersection: {:?}", intersection);
    
    // Union
    let union: IndexSet<_> = set1.union(&set2).cloned().collect();
    println!("Union: {:?}", union);
    
    // Difference
    let diff: IndexSet<_> = set1.difference(&set2).cloned().collect();
    println!("Difference (set1 - set2): {:?}", diff);
    
    // Symmetric difference
    let sym_diff: IndexSet<_> = set1.symmetric_difference(&set2).cloned().collect();
    println!("Symmetric difference: {:?}", sym_diff);
}

Preserving Order from JSON

// Cargo.toml:
// indexmap = { version = "2.0", features = ["serde"] }
 
use indexmap::IndexMap;
use serde::Deserialize;
 
#[derive(Debug, Deserialize)]
struct ApiResponse {
    #[serde(flatten)]
    data: IndexMap<String, serde_json::Value>,
}
 
fn main() {
    let json = r#"{
        "user_3": {"name": "Charlie"},
        "user_1": {"name": "Alice"},
        "user_2": {"name": "Bob"}
    }"#;
    
    let response: ApiResponse = serde_json::from_str(json).unwrap();
    
    println!("Users in original order:");
    for (key, value) in &response.data {
        println!("  {}: {:?}", key, value);
    }
}

Memory-Efficient Capacity

use indexmap::IndexMap;
 
fn main() {
    // Pre-allocate capacity
    let mut map = IndexMap::with_capacity(100);
    
    println!("Capacity: {}, Len: {}", map.capacity(), map.len());
    
    // Add items
    for i in 0..50 {
        map.insert(format!("key_{}", i), i);
    }
    
    println!("After inserts - Capacity: {}, Len: {}", map.capacity(), map.len());
    
    // Shrink to fit
    map.shrink_to_fit();
    println!("After shrink - Capacity: {}, Len: {}", map.capacity(), map.len());
}

Use with Hash Builders

use indexmap::IndexMap;
use std::hash::{BuildHasherDefault, Hasher};
 
// Simple custom hasher for demonstration
#[derive(Default)]
struct SimpleHasher(u64);
 
impl Hasher for SimpleHasher {
    fn finish(&self) -> u64 {
        self.0
    }
    
    fn write(&mut self, bytes: &[u8]) {
        for byte in bytes {
            self.0 = self.0.wrapping_add(*byte as u64);
        }
    }
}
 
fn main() {
    let mut map: IndexMap<String, i32, BuildHasherDefault<SimpleHasher>> = 
        IndexMap::default();
    
    map.insert("hello".to_string(), 1);
    map.insert("world".to_string(), 2);
    
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
}

Comparison Operations

use indexmap::IndexMap;
 
fn main() {
    let mut map1 = IndexMap::new();
    map1.insert("a", 1);
    map1.insert("b", 2);
    
    let mut map2 = IndexMap::new();
    map2.insert("a", 1);
    map2.insert("b", 2);
    
    let mut map3 = IndexMap::new();
    map3.insert("b", 2);
    map3.insert("a", 1);
    
    // Equal: same keys, values, and order
    println!("map1 == map2: {}", map1 == map2);
    
    // Not equal: different order
    println!("map1 == map3: {}", map1 == map3);
}

Summary

IndexMap preserves insertion order unlike HashMap
IndexSet preserves insertion order unlike HashSet
Access elements by index with get_index() and get_index_mut()
Find key position with get_index_of() and get_full()
Use remove() for order-preserving removal, swap_remove() for O(1)
Insert at specific positions with insert_before() and insert_sorted()
Sort with sort_keys() and sort_by()
Get first/last with first(), last(), first_mut(), last_mut()
Enable serde feature for JSON serialization that preserves order
Perfect for: JSON configs, ordered caches, dictionaries, API responses, deterministic iteration
Performance is comparable to HashMap for most operations
Use when order matters more than slight performance overhead