Arc<Mutex>

Guides

Rust walkthroughs

← Back to all guides

How does indexmap::IndexMap::shift_remove differ from swap_remove for order-preserving deletion?

shift_remove preserves insertion order by shifting all elements after the removed position down one index, while swap_remove swaps the removed element with the last element for O(1) removal but breaks insertion order. IndexMap maintains both a hash table for O(1) lookups and a vector that preserves insertion order—swap_remove exploits this structure for faster removal but changes the order of remaining elements, whereas shift_remove maintains order at the cost of O(n) shifting. Choose shift_remove when you need to iterate in the original insertion order after removals; choose swap_remove when order doesn't matter and you want faster removals.

IndexMap's Dual Structure

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);
    
    // IndexMap maintains:
    // 1. A hash table for O(1) lookups by key
    // 2. An ordered vector for insertion-order iteration
    
    // The vector stores: [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
    // Iteration always yields elements in this order
}

IndexMap combines hash map efficiency with insertion order preservation through its dual structure.

swap_remove: Fast But Order-Breaking

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_remove: {:?}", map.keys().collect::<Vec<_>>());
    // ["a", "b", "c", "d"]
    
    // Remove "b" using swap_remove
    map.swap_remove("b");
    
    // Internally, "b" is swapped with "d", then removed
    // Vector becomes: [("a", 1), ("d", 4), ("c", 3)]
    // "d" moved to position 1, "c" stayed at position 2
    
    println!("After swap_remove: {:?}", map.keys().collect::<Vec<_>>());
    // ["a", "d", "c"] -- Order changed!
    
    // "d" is now before "c" even though it was inserted after
}

swap_remove swaps the target with the last element, then removes it—order is broken.

shift_remove: Order-Preserving

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 shift_remove: {:?}", map.keys().collect::<Vec<_>>());
    // ["a", "b", "c", "d"]
    
    // Remove "b" using shift_remove
    map.shift_remove("b");
    
    // Internally, elements after "b" are shifted down
    // Vector becomes: [("a", 1), ("c", 3), ("d", 4)]
    
    println!("After shift_remove: {:?}", map.keys().collect::<Vec<_>>());
    // ["a", "c", "d"] -- Order preserved!
    
    // "c" and "d" maintain their relative positions
}

shift_remove shifts subsequent elements down—order is preserved but at O(n) cost.

Performance Comparison

use indexmap::IndexMap;
 
// swap_remove: O(1)
// - Find element: O(1) via hash table
// - Swap with last: O(1)
// - Remove last: O(1)
// Total: O(1)
 
// shift_remove: O(n)
// - Find element: O(1) via hash table
// - Shift all elements after it: O(n)
// Total: O(n) where n is elements after removal point
 
fn main() {
    // For a map with 1,000,000 elements:
    
    // Removing the first element with swap_remove:
    // - O(1) operation
    // - Order broken
    
    // Removing the first element with shift_remove:
    // - O(999,999) - shift nearly all elements
    // - Order preserved
    
    // Removing the last element with shift_remove:
    // - O(1) - nothing to shift
    // - Order preserved (trivially)
    
    // Performance impact depends on position:
    // - swap_remove: Same speed regardless of position
    // - shift_remove: Faster for end elements, slower for beginning
}

swap_remove is always O(1); shift_remove varies by position but worst case is O(n).

When Order Matters

use indexmap::IndexMap;
 
fn main() {
    // Use case: Ordered processing pipeline
    let mut pipeline: IndexMap<&str, fn(i32) -> i32> = IndexMap::new();
    
    pipeline.insert("step1", |x| x + 1);
    pipeline.insert("step2", |x| x * 2);
    pipeline.insert("step3", |x| x - 3);
    
    // Removing a step should preserve other steps' order
    pipeline.shift_remove("step2");
    
    // Process in order - steps 1 and 3 remain in original order
    let mut value = 10;
    for (_, transform) in &pipeline {
        value = transform(value);
    }
    println!("Result: {}", value);
}
 
// Use case: Ordered configuration display
fn display_config() {
    let mut config: IndexMap<&str, &str> = IndexMap::new();
    config.insert("name", "Alice");
    config.insert("email", "alice@example.com");
    config.insert("role", "admin");
    
    // Remove deprecated field
    config.shift_remove("role");
    
    // Remaining fields still in insertion order
    for (key, value) in &config {
        println!("{}: {}", key, value);
    }
    // Order: name, then email
}

Use shift_remove when iteration order reflects meaningful sequence or priority.

When Order Doesn't Matter

use indexmap::IndexMap;
 
fn main() {
    // Use case: Cache with LRU eviction
    let mut cache: IndexMap<String, Vec<u8>> = IndexMap::new();
    
    cache.insert("key1".to_string(), vec![1, 2, 3]);
    cache.insert("key2".to_string(), vec![4, 5, 6]);
    cache.insert("key3".to_string(), vec![7, 8, 9]);
    
    // Evict an entry - don't care about order
    // Use swap_remove for O(1) removal
    cache.swap_remove("key2");
    
    // Use case: Set-like collection with fast removal
    let mut set_like: IndexMap<i32, ()> = IndexMap::new();
    set_like.insert(1, ());
    set_like.insert(2, ());
    set_like.insert(3, ());
    
    // Just need to remove, don't care about positions
    set_like.swap_remove(&2);
}

Use swap_remove when order is irrelevant and you want the fastest removal.

Index-Based Removal

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);
    
    // Remove by index instead of key
    // swap_remove_index: O(1), breaks order
    let removed = map.swap_remove_index(1);  // Removes "b"
    println!("Removed: {:?}", removed);  // Some(("b", 2))
    println!("Remaining: {:?}", map.keys().collect::<Vec<_>>());  // ["a", "c"]
    
    // shift_remove_index: O(n), preserves order
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("a", 1);
    map2.insert("b", 2);
    map2.insert("c", 3);
    
    let removed = map2.shift_remove_index(1);  // Removes "b"
    println!("Removed: {:?}", removed);  // Some(("b", 2))
    println!("Remaining: {:?}", map2.keys().collect::<Vec<_>>());  // ["a", "c"]
}

Both methods have index-based variants for removal by position.

Iteration Behavior After Removal

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<i32, &str> = IndexMap::new();
    for i in 0..10 {
        map.insert(i, &format!("value{}", i));
    }
    
    // Using swap_remove
    map.swap_remove(&5);  // Swap position 5 with position 9
    
    // Iteration shows reordered elements
    println!("After swap_remove:");
    for (k, v) in &map {
        println!("  {}: {}", k, v);
    }
    // 5 is gone, but 9 moved to position 5
    
    // Rebuild map
    let mut map2: IndexMap<i32, &str> = IndexMap::new();
    for i in 0..10 {
        map2.insert(i, &format!("value{}", i));
    }
    
    // Using shift_remove
    map2.shift_remove(&5);
    
    // Iteration shows original order preserved
    println!("After shift_remove:");
    for (k, v) in &map2 {
        println!("  {}: {}", k, v);
    }
    // Elements 6-9 shifted down, order preserved
}

shift_remove maintains iteration order; swap_remove doesn't.

Comparison with HashMap

use std::collections::HashMap;
use indexmap::IndexMap;
 
fn main() {
    // HashMap: No order, only swap_remove available (conceptually)
    let mut hashmap: HashMap<i32, &str> = HashMap::new();
    hashmap.insert(1, "a");
    hashmap.insert(2, "b");
    hashmap.insert(3, "c");
    
    // HashMap doesn't expose indices
    // Order is undefined
    // No shift_remove equivalent - order doesn't exist
    
    // IndexMap: Order exists, choice of removal method
    let mut indexmap: IndexMap<i32, &str> = IndexMap::new();
    indexmap.insert(1, "a");
    indexmap.insert(2, "b");
    indexmap.insert(3, "c");
    
    // Two removal options:
    // - swap_remove: HashMap-like, no order guarantee
    // - shift_remove: Preserves order, O(n)
    
    // IndexMap gives you the choice
}

IndexMap provides order-preserving operations that HashMap cannot.

Real-World Use Case: Priority Queue Alternative

use indexmap::IndexMap;
 
struct TaskQueue {
    tasks: IndexMap<String, Task>,
}
 
struct Task {
    priority: u32,
    description: String,
}
 
impl TaskQueue {
    fn new() -> Self {
        TaskQueue {
            tasks: IndexMap::new(),
        }
    }
    
    fn add_task(&mut self, id: String, task: Task) {
        self.tasks.insert(id, task);
    }
    
    fn remove_task(&mut self, id: &str) -> Option<Task> {
        // Use shift_remove to preserve task order
        // Tasks might be prioritized by insertion order
        self.tasks.shift_remove(id)
    }
    
    fn list_tasks(&self) -> impl Iterator<Item = (&String, &Task)> {
        self.tasks.iter()
    }
}
 
fn main() {
    let mut queue = TaskQueue::new();
    
    queue.add_task("task1".to_string(), Task { priority: 1, description: "First".to_string() });
    queue.add_task("task2".to_string(), Task { priority: 2, description: "Second".to_string() });
    queue.add_task("task3".to_string(), Task { priority: 3, description: "Third".to_string() });
    
    queue.remove_task("task2");
    
    // Remaining tasks still in order: task1, task3
    for (id, task) in queue.list_tasks() {
        println!("{}: {}", id, task.description);
    }
}

shift_remove maintains task queue order even after deletions.

Real-World Use Case: Configuration Management

use indexmap::IndexMap;
 
struct Config {
    values: IndexMap<String, String>,
}
 
impl Config {
    fn new() -> Self {
        Config {
            values: IndexMap::new(),
        }
    }
    
    fn set(&mut self, key: String, value: String) {
        // Insertion order matters for display purposes
        self.values.insert(key, value);
    }
    
    fn remove(&mut self, key: &str) -> Option<String> {
        // Use shift_remove to maintain display order
        self.values.shift_remove(key)
    }
    
    fn to_string_ordered(&self) -> String {
        // Output in consistent, predictable order
        self.values
            .iter()
            .map(|(k, v)| format!("{}={}", k, v))
            .collect::<Vec<_>>()
            .join("\n")
    }
}
 
fn main() {
    let mut config = Config::new();
    
    config.set("database".to_string(), "postgres".to_string());
    config.set("port".to_string(), "5432".to_string());
    config.set("host".to_string(), "localhost".to_string());
    
    // Config file order: database, port, host
    println!("Before:\n{}", config.to_string_ordered());
    
    config.remove("port");
    
    // After removal: database, host (order preserved)
    println!("\nAfter:\n{}", config.to_string_ordered());
}

Configuration files often require consistent ordering—shift_remove maintains it.

Retain Operation

use indexmap::IndexMap;
 
fn main() {
    let mut map: IndexMap<i32, i32> = IndexMap::new();
    for i in 0..10 {
        map.insert(i, i * 10);
    }
    
    // retain: Keeps elements matching predicate
    // This is equivalent to repeated shift_remove
    // Order is preserved
    map.retain(|_k, &mut v| v > 30);
    
    println!("After retain: {:?}", map.keys().collect::<Vec<_>>());
    // [4, 5, 6, 7, 8, 9] - Order preserved
    
    // retain mutates in place with shift semantics
}

retain uses shift semantics internally, preserving order of remaining elements.

Memory Layout Implications

use indexmap::IndexMap;
 
fn main() {
    // swap_remove:
    // - No memory reallocation
    // - Simply swaps two entries, removes last
    // - Indices of other elements may change
    // - Good for cache locality
    
    // shift_remove:
    // - May shift many elements in memory
    // - Maintains indices of remaining elements
    // - Indices are stable (except removed)
    // - May have cache effects from shifting
    
    let mut map: IndexMap<usize, usize> = IndexMap::new();
    for i in 0..1000 {
        map.insert(i, i);
    }
    
    // swap_remove(0): Swap entry 0 with entry 999, remove 999
    // Memory: One swap, one remove
    
    // shift_remove(0): Shift entries 1-999 down, remove 999
    // Memory: Up to 999 shifts
    
    // Trade-off: CPU time vs. order preservation
}

swap_remove minimizes memory operations; shift_remove prioritizes order.

Synthesis

Method comparison:

Aspect swap_remove shift_remove
Time complexity O(1) O(n) worst case
Order preservation No Yes
Index stability No Yes
Memory operations Minimal (swap) Shifts elements
Use case Order irrelevant Order matters

When to use each:

  • swap_remove: Caches, sets, collections where order doesn't matter
  • shift_remove: Ordered configs, task queues, sequences, display lists

Key insight: IndexMap uniquely offers both removal strategies, letting you choose between O(1) speed and order preservation. The right choice depends on whether your use case depends on iteration order. If order matters—configuration files, ordered lists, task sequences—use shift_remove. If order is irrelevant—caches, sets, temporary storage—use swap_remove for the performance benefit. The performance gap grows with map size and removal position: removing the first element with shift_remove is O(n), while swap_remove remains O(1) regardless of position.