How does `indexmap::IndexMap::shift_remove` differ from `swap_remove` for maintaining relative element order?

shift_remove removes an element and shifts all subsequent elements to preserve insertion order, operating in O(n) time, while swap_remove replaces the removed element with the last element, preserving O(1) complexity but breaking insertion order for all elements after the removed position. The choice between them is a trade-off between maintaining order guarantees and performance: use shift_remove when iteration order matters, and swap_remove when you need fast removal and don't care about order.

Basic swap_remove Behavior

use indexmap::IndexMap;
 
fn swap_remove_basic() {
    let mut map = IndexMap::new();
    
    // Insert in specific order
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Order: a, b, c, d
    assert_eq!(map.keys().collect::<Vec<_>>(), [&"a", &"b", &"c", &"d"]);
    
    // swap_remove "b"
    map.swap_remove("b");  // Removes "b", moves "d" to "b"'s position
    
    // Order changed: a, d, c
    // "d" was swapped into "b"'s position
    assert_eq!(map.keys().collect::<Vec<_>>(), [&"a", &"d", &"c"]);
    
    // "c" stayed in its position
    // "d" moved from position 3 to position 1
    // Original order [a, b, c, d] is now [a, d, c]
}

swap_remove replaces the removed element with the last element, changing the order.

Basic shift_remove Behavior

use indexmap::IndexMap;
 
fn shift_remove_basic() {
    let mut map = IndexMap::new();
    
    // Insert in specific order
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Order: a, b, c, d
    assert_eq!(map.keys().collect::<Vec<_>>(), [&"a", &"b", &"c", &"d"]);
    
    // shift_remove "b"
    map.shift_remove("b");  // Removes "b", shifts "c" and "d" left
    
    // Order preserved: a, c, d
    // All elements after "b" shifted left by one position
    assert_eq!(map.keys().collect::<Vec<_>>(), [&"a", &"c", &"d"]);
    
    // Original order [a, b, c, d] is now [a, c, d]
    // Relative order of remaining elements unchanged
}

shift_remove shifts subsequent elements to preserve insertion order.

Performance Comparison

use indexmap::IndexMap;
 
fn performance_comparison() {
    // swap_remove: O(1) - constant time
    // Only swaps with last element, no iteration needed
    
    let mut map = IndexMap::new();
    for i in 0..1_000_000 {
        map.insert(i, i);
    }
    
    // Removing from any position is O(1)
    map.swap_remove(&0);      // First element
    map.swap_remove(&500000); // Middle element
    map.swap_remove(&999999); // Last element
    // All equally fast
    
    // shift_remove: O(n) - linear time
    // Must shift all elements after the removed one
    
    let mut map = IndexMap::new();
    for i in 0..1_000_000 {
        map.insert(i, i);
    }
    
    // Removing from different positions has different costs
    map.shift_remove(&999999); // Fast: nothing to shift after
    map.shift_remove(&500000); // Slow: must shift 500,000 elements
    map.shift_remove(&0);      // Slowest: must shift 999,999 elements
}

swap_remove is O(1) regardless of position; shift_remove is O(n) where n is elements after the removed position.

Detailed swap_remove Mechanics

use indexmap::IndexMap;
 
fn swap_remove_mechanics() {
    let mut map = IndexMap::new();
    map.insert("a", 1);  // Index 0
    map.insert("b", 2);  // Index 1
    map.insert("c", 3);  // Index 2
    map.insert("d", 4);  // Index 3
    
    // Internal state (conceptual):
    // indices: {a: 0, b: 1, c: 2, d: 3}
    // entries: [a, b, c, d]
    
    // swap_remove("b") does:
    // 1. Find "b" at index 1
    // 2. Get last element ("d" at index 3)
    // 3. Move "d" to index 1
    // 4. Update "d"'s index from 3 to 1
    // 5. Remove "b" from indices map
    // 6. Remove last entry from entries
    
    map.swap_remove("b");
    
    // After swap_remove:
    // indices: {a: 0, d: 1, c: 2}
    // entries: [a, d, c]
    // "d" moved from position 3 to position 1
    
    // Verification
    assert_eq!(map.get_index(0), Some((&"a", &1)));
    assert_eq!(map.get_index(1), Some((&"d", &4)));  // "d" now at index 1
    assert_eq!(map.get_index(2), Some((&"c", &3)));
}

swap_remove updates the index of the swapped element to maintain correct lookups.

Detailed shift_remove Mechanics

use indexmap::IndexMap;
 
fn shift_remove_mechanics() {
    let mut map = IndexMap::new();
    map.insert("a", 1);  // Index 0
    map.insert("b", 2);  // Index 1
    map.insert("c", 3);  // Index 2
    map.insert("d", 4);  // Index 3
    
    // Internal state (conceptual):
    // indices: {a: 0, b: 1, c: 2, d: 3}
    // entries: [a, b, c, d]
    
    // shift_remove("b") does:
    // 1. Find "b" at index 1
    // 2. Remove "b" from indices map
    // 3. Shift entries[2..] left by one position
    // 4. Update indices for all shifted elements
    
    map.shift_remove("b");
    
    // After shift_remove:
    // indices: {a: 0, c: 1, d: 2}
    // entries: [a, c, d]
    // "c" moved from 2 to 1, "d" moved from 3 to 2
    
    // Verification
    assert_eq!(map.get_index(0), Some((&"a", &1)));
    assert_eq!(map.get_index(1), Some((&"c", &3)));  // "c" now at index 1
    assert_eq!(map.get_index(2), Some((&"d", &4)));  // "d" now at index 2
}

shift_remove updates indices for all elements that were shifted.

When Order Matters

use indexmap::IndexMap;
 
fn when_order_matters() {
    // Use case: Ordered processing queue
    
    let mut queue: IndexMap<u32, &str> = IndexMap::new();
    queue.insert(1, "task-a");
    queue.insert(2, "task-b");
    queue.insert(3, "task-c");
    queue.insert(4, "task-d");
    
    // Process tasks in order
    for (id, task) in &queue {
        println!("Processing {}: {}", id, task);
    }
    
    // Cancel task 2 (in the middle)
    // We want remaining tasks to keep their relative order
    queue.shift_remove(&2);
    
    // Order is preserved: 1, 3, 4
    let remaining: Vec<_> = queue.keys().collect();
    assert_eq!(remaining, [&1, &3, &4]);
    
    // This matches user's mental model:
    // "Cancel this task, keep other tasks in order"
    
    // With swap_remove, order would be: 1, 4, 3
    // Confusing: "Why did task 4 jump ahead of task 3?"
}

Use shift_remove when users expect order to be preserved after removal.

When Performance Matters More

use indexmap::IndexMap;
 
fn when_performance_matters() {
    // Use case: High-frequency cache with LRU eviction
    
    let mut cache: IndexMap<String, Vec<u8>> = IndexMap::new();
    
    // Populate cache
    for i in 0..10_000 {
        cache.insert(format!("key-{}", i), vec![0u8; 1024]);
    }
    
    // Evict random entries frequently
    // Order doesn't matter, performance does
    
    let keys_to_remove: Vec<_> = cache.keys()
        .take(1000)
        .cloned()
        .collect();
    
    // Use swap_remove for O(1) removal
    for key in keys_to_remove {
        cache.swap_remove(&key);  // Fast, order doesn't matter
    }
    
    // If we used shift_remove:
    // - Each removal would be O(n)
    // - Total: O(n^2) for removing k elements
    // - With 1000 removals from a 10000-entry map: expensive
}

Use swap_remove when order is irrelevant and performance is critical.

Index Stability

use indexmap::IndexMap;
 
fn index_stability() {
    // swap_remove invalidates indices
    
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Get indices before removal
    let index_b = map.get_index_of("b");  // Returns 1
    
    map.swap_remove("b");
    
    // Index 1 now refers to "c" (swapped from position 2)
    assert_eq!(map.get_index(1), Some((&"c", &3)));
    
    // If you saved indices expecting stability, they're now wrong
    // This is a common source of bugs
    
    // shift_remove maintains relative positions
    
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    let index_c = map.get_index_of("c");  // Returns 2
    
    map.shift_remove("b");  // Remove element at index 1
    
    // "c" is now at index 1 (shifted left)
    assert_eq!(map.get_index_of("c"), Some(1));
    
    // "c"'s relative position to other elements is preserved
    // It's now one position earlier, but still after "a" and before "d"
}

Both methods change indices, but shift_remove preserves relative order.

Iteration Behavior After Removal

use indexmap::IndexMap;
 
fn iteration_behavior() {
    // swap_remove: iteration order changes unpredictably
    
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Remove "b" (second element)
    map.swap_remove("b");
    
    // Iteration order: a, d, c (last element swapped to position 1)
    let order: Vec<_> = map.keys().collect();
    assert_eq!(order, [&"a", &"d", &"c"]);
    
    // shift_remove: iteration order preserved
    
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Remove "b" (second element)
    map.shift_remove("b");
    
    // Iteration order: a, c, d (order preserved, "b" removed)
    let order: Vec<_> = map.keys().collect();
    assert_eq!(order, [&"a", &"c", &"d"]);
    
    // Use shift_remove when iteration order must be deterministic
    // relative to insertion order
}

shift_remove maintains insertion order during iteration; swap_remove does not.

Retain Operations

use indexmap::IndexMap;
 
fn retain_operations() {
    // IndexMap has retain methods that use shift semantics
    
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // retain uses shift_remove semantics internally
    // Keeps elements where predicate returns true
    map.retain(|_key, &mut value| value % 2 == 1);
    
    // Order preserved: a, c
    assert_eq!(map.keys().collect::<Vec<_>>(), [&"a", &"c"]);
    
    // retain preserves order by design
    // It's the batch equivalent of shift_remove
    
    // For swap semantics in batch:
    // You'd need to implement it manually
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    let keys_to_remove: Vec<_> = map.iter()
        .filter(|(_, &v)| v % 2 == 0)
        .map(|(k, _)| k.clone())
        .collect();
    
    for key in &keys_to_remove {
        map.swap_remove(key);  // Use swap semantics
    }
    
    // Order: a, c (but with swap semantics, so potentially different)
}

retain uses shift semantics by default to preserve order during batch removal.

Practical Use Cases

use indexmap::IndexMap;
 
fn use_cases() {
    // Use shift_remove when:
    // 1. Insertion order is semantically meaningful
    // 2. Users expect order stability
    // 3. Iteration order affects correctness
    // 4. Implementing ordered data structures
    
    // Example: Ordered command history
    let mut command_history: IndexMap<u64, String> = IndexMap::new();
    command_history.insert(1, "command-a".to_string());
    command_history.insert(2, "command-b".to_string());
    command_history.insert(3, "command-c".to_string());
    
    // Undo specific command
    command_history.shift_remove(&2);  // Order preserved: 1, 3
    
    // Example: Playlist queue
    let mut playlist: IndexMap<String, Song> = IndexMap::new();
    // ... add songs in order
    
    // Remove song, preserve order of remaining songs
    playlist.shift_remove(&song_id);
    
    // Use swap_remove when:
    // 1. Order doesn't matter
    // 2. Performance is critical
    // 3. Frequent removals from large maps
    // 4. Implementing caches or sets
    
    // Example: LRU cache (actually use LRU-specific structure)
    let mut cache: IndexMap<CacheKey, CacheValue> = IndexMap::new();
    
    // Evict entry, don't care about order
    cache.swap_remove(&old_key);  // O(1)
    
    // Example: Deduplication
    let mut seen: IndexMap<String, ()> = IndexMap::new();
    for item in items {
        seen.entry(item.clone()).or_insert(());
    }
    // If removing, order doesn't matter
    seen.swap_remove(&duplicate);
}

Choose based on whether order matters for your use case.

Memory Layout Implications

use indexmap::IndexMap;
 
fn memory_layout() {
    // swap_remove: One move operation
    // Moves single element (last) to fill gap
    
    let mut map = IndexMap::new();
    map.insert("a", vec![1, 2, 3]);   // Large value
    map.insert("b", vec![4, 5, 6]);
    map.insert("c", vec![7, 8, 9]);
    map.insert("d", vec![10, 11, 12]);
    
    // swap_remove("b")
    // 1. Move "d" to position 1 (one move)
    // 2. Pop last entry
    // Cost: O(1) moves
    
    // shift_remove: Multiple move operations
    // Moves all elements after gap
    
    let mut map = IndexMap::new();
    for i in 0..1000 {
        map.insert(i, vec![1, 2, 3]);
    }
    
    // shift_remove(&0)
    // Must move entries 1 through 999
    // Cost: O(n) moves
    
    // For small values, cost is low
    // For large values (heap allocations), cost is higher
}

shift_remove performs more memory moves, especially costly for large values.

Complete Example

use indexmap::IndexMap;
 
fn complete_example() {
    // Scenario: Task queue with priorities
    
    let mut tasks: IndexMap<String, Task> = IndexMap::new();
    
    #[derive(Debug, Clone)]
    struct Task {
        name: String,
        priority: u8,
    }
    
    // Add tasks in priority order
    tasks.insert("task-1".to_string(), Task { name: "Setup".into(), priority: 1 });
    tasks.insert("task-2".to_string(), Task { name: "Process".into(), priority: 2 });
    tasks.insert("task-3".to_string(), Task { name: "Cleanup".into(), priority: 3 });
    tasks.insert("task-4".to_string(), Task { name: "Report".into(), priority: 4 });
    
    println!("Original order:");
    for (id, task) in &tasks {
        println!("  {}: {}", id, task.name);
    }
    
    // Cancel task-2 (in the middle)
    // Use shift_remove to maintain order for remaining tasks
    tasks.shift_remove("task-2");
    
    println!("\nAfter shift_remove(\"task-2\"):");
    for (id, task) in &tasks {
        println!("  {}: {}", id, task.name);
    }
    // Output: task-1, task-3, task-4 (order preserved)
    
    // Alternative: swap_remove
    let mut tasks2: IndexMap<String, Task> = IndexMap::new();
    tasks2.insert("task-1".to_string(), Task { name: "Setup".into(), priority: 1 });
    tasks2.insert("task-2".to_string(), Task { name: "Process".into(), priority: 2 });
    tasks2.insert("task-3".to_string(), Task { name: "Cleanup".into(), priority: 3 });
    tasks2.insert("task-4".to_string(), Task { name: "Report".into(), priority: 4 });
    
    tasks2.swap_remove("task-2");
    
    println!("\nAfter swap_remove(\"task-2\"):");
    for (id, task) in &tasks2 {
        println!("  {}: {}", id, task.name);
    }
    // Output: task-1, task-4, task-3 (order changed)
}

Synthesis

Core difference:

// swap_remove: O(1), breaks order
map.swap_remove(&key);
// Last element moves to fill gap
// [a, b, c, d] -remove(b)-> [a, d, c]
 
// shift_remove: O(n), preserves order
map.shift_remove(&key);
// All elements after gap shift left
// [a, b, c, d] -remove(b)-> [a, c, d]

Performance summary:

Method	Time Complexity	Order Preserved?	Use Case
`swap_remove`	O(1)	No	Caches, sets, order irrelevant
`shift_remove`	O(n)	Yes	Queues, ordered collections

Decision guide:

// Use shift_remove when:
// - Insertion order matters semantically
// - Iteration order must be stable
// - Users expect preserved order
// - Implementing ordered data structures
// - Batch operations use retain() (implicit shift semantics)
 
// Use swap_remove when:
// - Order doesn't matter
// - Performance is critical
// - Frequent removals from large maps
// - Implementing caches
// - Random access/removal patterns
 
// Example: Ordered queue
tasks.shift_remove(&task_id);  // Order matters
 
// Example: Cache eviction
cache.swap_remove(&key);  // Order doesn't matter, speed matters

Key insight: The choice between shift_remove and swap_remove is a direct trade-off between order preservation and performance—shift_remove maintains the insertion order guarantee that makes IndexMap useful as an ordered map, but at the cost of O(n) removal time that can be expensive for large maps or frequent removals. swap_remove provides the O(1) removal performance you'd expect from a hash map, but sacrifices the order guarantee. The standard library's HashMap doesn't have this choice because it doesn't preserve order at all; IndexMap's dual removal methods let you decide per-call whether you need order preservation or speed. For most use cases where order matters, use shift_remove (or retain for batch operations); for high-performance scenarios where order is irrelevant, swap_remove provides the speed of a standard hash map while still benefiting from IndexMap's ordered iteration when you need it.

How does indexmap::IndexMap::shift_remove differ from swap_remove for maintaining relative element order?