What is the difference between `indexmap::IndexMap::shift_remove` and `swap_remove` for element removal?

IndexMap::swap_remove removes an element by swapping it with the last element, then removing from the end—O(1) time complexity but disrupts insertion order. IndexMap::shift_remove removes an element by shifting all subsequent elements backward, preserving insertion order but with O(n) time complexity. The choice depends on whether you need to maintain iteration order after removal. Use swap_remove when order doesn't matter and performance is critical; use shift_remove when insertion order must be preserved for correctness.

Basic IndexMap Structure

use indexmap::IndexMap;
 
fn basic_indexmap() {
    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 preserves insertion order: [a, b, c, d]
    // Each key has an internal index: a=0, b=1, c=2, d=3
    
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
    // Output order: a, b, c, d
}

IndexMap maintains insertion order, mapping each key to an internal index.

Swap Remove Behavior

use indexmap::IndexMap;
 
fn swap_remove_example() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Before: [a, b, c, d] with indices: a=0, b=1, c=2, d=3
    
    map.swap_remove("b"); // Remove "b" by swapping with last element
    
    // After: [a, d, c] with indices: a=0, d=1, c=2
    // "d" moved from index 3 to index 1 to fill "b"'s spot
    
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
    // Output order: a, d, c (order changed!)
}

swap_remove exchanges the removed element with the last element, disrupting order.

Shift Remove Behavior

use indexmap::IndexMap;
 
fn shift_remove_example() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Before: [a, b, c, d] with indices: a=0, b=1, c=2, d=3
    
    map.shift_remove("b"); // Remove "b" and shift subsequent elements
    
    // After: [a, c, d] with indices: a=0, c=1, d=2
    // Elements after "b" shifted left to maintain order
    
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
    // Output order: a, c, d (order preserved!)
}

shift_remove shifts subsequent elements backward, preserving insertion order.

Time Complexity Comparison

use indexmap::IndexMap;
 
fn complexity_comparison() {
    let mut map: IndexMap<u32, u32> = IndexMap::new();
    
    // Insert many elements
    for i in 0..100_000 {
        map.insert(i, i);
    }
    
    // swap_remove: O(1) - just swap and pop
    map.swap_remove(&50_000); // Fast, constant time
    
    // shift_remove: O(n) - shift all subsequent elements
    map.shift_remove(&50_000); // Slower for elements near the start
}

swap_remove is O(1); shift_remove is O(n) for elements near the front.

Internal Index Changes

use indexmap::IndexMap;
 
fn index_changes() {
    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);
    
    // Indices: a=0, b=1, c=2, d=3, e=4
    
    // swap_remove changes indices of the swapped element
    map.swap_remove("b");
    // "e" moved from index 4 to index 1
    // New indices: a=0, e=1, c=2, d=3
    // Indices of c, d unchanged; e changed
    
    // Rebuild for shift_remove example
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("a", 1);
    map2.insert("b", 2);
    map2.insert("c", 3);
    map2.insert("d", 4);
    map2.insert("e", 5);
    
    // Indices: a=0, b=1, c=2, d=3, e=4
    
    map2.shift_remove("b");
    // All elements after b shifted left
    // New indices: a=0, c=1, d=2, e=3
    // All indices from c onward changed
}

swap_remove changes one element's index; shift_remove changes all subsequent indices.

Removal by Index

use indexmap::IndexMap;
 
fn remove_by_index() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Remove by index using swap_remove_index
    let removed = map.swap_remove_index(1);
    // Removes element at index 1 (was "b")
    
    assert_eq!(removed, Some(("b", 2)));
    
    // shift_remove_index also available
    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);
    assert_eq!(removed, Some(("b", 2)));
}

Both methods have index-based variants: swap_remove_index and shift_remove_index.

Return Value

use indexmap::IndexMap;
 
fn return_values() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    
    // Both methods return Option<(K, V)>
    let removed = map.swap_remove("a");
    assert_eq!(removed, Some(("a", 1)));
    
    let removed = map.swap_remove("nonexistent");
    assert_eq!(removed, None);
    
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("a", 1);
    map2.insert("b", 2);
    
    let removed = map2.shift_remove("a");
    assert_eq!(removed, Some(("a", 1)));
}

Both methods return Option<(K, V)>—the removed key-value pair if found.

Iteration Order Impact

use indexmap::IndexMap;
 
fn iteration_order() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    map.insert("fourth", 4);
    
    // swap_remove: iteration order changes
    map.swap_remove("second");
    
    // Iteration order: first, fourth, third
    // "fourth" moved to fill "second"'s position
    
    let keys: Vec<_> = map.keys().collect();
    assert_eq!(keys, vec![&"first", &"fourth", &"third"]);
    
    // shift_remove: iteration order preserved
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("first", 1);
    map2.insert("second", 2);
    map2.insert("third", 3);
    map2.insert("fourth", 4);
    
    map2.shift_remove("second");
    
    // Iteration order: first, third, fourth (order maintained)
    let keys: Vec<_> = map2.keys().collect();
    assert_eq!(keys, vec![&"first", &"third", &"fourth"]);
}

Use shift_remove when iteration order must remain consistent after removal.

Performance Benchmarks

use indexmap::IndexMap;
 
fn performance_comparison() {
    // Create map with 100,000 elements
    let mut map: IndexMap<u32, u32> = (0..100_000).map(|i| (i, i)).collect();
    
    // Remove from front: shift_remove is slowest
    // shift_remove near front: O(n)
    // swap_remove near front: O(1)
    
    // Remove from middle: shift_remove moderate
    // shift_remove near middle: O(n/2)
    // swap_remove near middle: O(1)
    
    // Remove from end: both fast
    // shift_remove at end: O(1)
    // swap_remove at end: O(1)
}

swap_remove is always O(1); shift_remove is O(n) except at the end.

Preserving Indices with Entries

use indexmap::IndexMap;
 
fn entry_api() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Using entry API doesn't give direct removal control
    // Use swap_remove_entry or shift_remove_entry
    
    // swap_remove_entry returns (index, key, value)
    let removed = map.swap_remove_entry(&"b");
    // Returns: Some((1, "b", 2)) - index was 1
    
    // shift_remove_entry available too
    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_entry(&"b");
    // Returns: Some((1, "b", 2)) - index was 1
}

swap_remove_entry and shift_remove_entry return the index along with key and value.

Use Case: Priority Queue

use indexmap::IndexMap;
use std::cmp::Ordering;
 
// For priority queue use cases, order doesn't matter
struct TaskQueue {
    tasks: IndexMap<String, u32>, // task name -> priority
}
 
impl TaskQueue {
    fn new() -> Self {
        Self { tasks: IndexMap::new() }
    }
    
    fn add(&mut self, name: &str, priority: u32) {
        self.tasks.insert(name.to_string(), priority);
    }
    
    fn remove(&mut self, name: &str) -> Option<u32> {
        // swap_remove is fine here - order doesn't matter
        self.tasks.swap_remove(name).map(|(_, priority)| priority)
    }
    
    fn get_highest_priority(&self) -> Option<(&String, &u32)> {
        self.tasks.iter().max_by_key(|(_, p)| *p)
    }
}

When order is irrelevant, swap_remove provides better performance.

Use Case: Ordered History

use indexmap::IndexMap;
 
// For ordered history, insertion order must be preserved
struct ActionHistory {
    actions: IndexMap<String, String>, // action_id -> description
}
 
impl ActionHistory {
    fn new() -> Self {
        Self { actions: IndexMap::new() }
    }
    
    fn record(&mut self, id: &str, description: &str) {
        self.actions.insert(id.to_string(), description.to_string());
    }
    
    fn undo(&mut self, id: &str) -> Option<String> {
        // shift_remove preserves action order
        self.actions.shift_remove(id).map(|(_, desc)| desc)
    }
    
    fn get_history(&self) -> Vec<&String> {
        self.actions.keys().collect()
    }
}

When insertion order matters for correctness, use shift_remove.

Mixed Removal Pattern

use indexmap::IndexMap;
 
fn mixed_pattern() {
    let mut cache: IndexMap<String, CachedItem> = IndexMap::new();
    
    // Insert items
    for i in 0..100 {
        cache.insert(format!("item_{}", i), CachedItem { data: i });
    }
    
    // For bulk operations, choose based on needs
    // If maintaining order is important for iteration:
    cache.shift_remove(&"item_50".to_string());
    
    // If order doesn't matter and performance is critical:
    cache.swap_remove(&"item_0".to_string());
    
    // For end elements, both are equivalent:
    let last_key = cache.keys().last().unwrap().clone();
    cache.swap_remove(&last_key); // Same performance as shift_remove
}
 
struct CachedItem {
    data: u32,
}

Choose removal method based on whether order preservation matters.

Comparison Table

| Method | Time Complexity | Order Preservation | Use Case | |--------|-----------------|---------------------|----------| | swap_remove | O(1) | No | Performance-critical, order irrelevant | | shift_remove | O(n) | Yes | Order must be preserved |

Real-World Example: 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> {
        // For LRU, we need to move accessed item to end
        // Use swap_remove + insert to move to end
        if let Some((k, v)) = self.cache.swap_remove(key) {
            self.cache.insert(k, v);
            self.cache.get(key)
        } else {
            None
        }
    }
    
    fn put(&mut self, key: K, value: V) {
        // If at capacity, remove least recently used (first element)
        if self.cache.len() >= self.capacity {
            // Use swap_remove for O(1) removal
            // Order doesn't matter here since we track LRU via get()
            self.cache.swap_remove_index(0);
        }
        
        // Remove if exists (to update position)
        self.cache.swap_remove(&key);
        // Insert at end (most recently used)
        self.cache.insert(key, value);
    }
}

LRU cache uses swap_remove because order is managed via access patterns, not insertion.

Real-World Example: Ordered Task List

use indexmap::IndexMap;
 
struct TaskList {
    tasks: IndexMap<String, Task>,
}
 
#[derive(Clone)]
struct Task {
    description: String,
    completed: bool,
}
 
impl TaskList {
    fn new() -> Self {
        Self { tasks: IndexMap::new() }
    }
    
    fn add(&mut self, id: &str, description: &str) {
        self.tasks.insert(
            id.to_string(),
            Task {
                description: description.to_string(),
                completed: false,
            },
        );
    }
    
    fn remove(&mut self, id: &str) -> bool {
        // Use shift_remove to preserve task order
        // Users expect tasks to remain in added order
        self.tasks.shift_remove(id).is_some()
    }
    
    fn complete(&mut self, id: &str) {
        if let Some(task) = self.tasks.get_mut(id) {
            task.completed = true;
        }
    }
    
    fn list(&self) -> Vec<(&String, &Task)> {
        self.tasks.iter().collect()
    }
}

Ordered task list uses shift_remove to maintain user-expected ordering.

Real-World Example: Position-Based Removal

use indexmap::IndexMap;
 
struct OrderedRegistry {
    items: IndexMap<String, Item>,
}
 
struct Item {
    name: String,
    position: usize,
}
 
impl OrderedRegistry {
    fn remove_at_position(&mut self, position: usize) -> Option<String> {
        // shift_remove_index for position-based removal
        // Maintains order of remaining items
        self.items.shift_remove_index(position)
            .map(|(key, _)| key)
    }
    
    fn get_position(&self, key: &str) -> Option<usize> {
        self.items.get_index_of(key)
    }
    
    fn get_at(&self, position: usize) -> Option<(&String, &Item)> {
        self.items.get_index(position)
    }
}

When position in the map matters, shift_remove_index preserves positions.

Synthesis

Removal method comparison:

| Aspect | swap_remove | shift_remove | |--------|---------------|----------------| | Time complexity | O(1) always | O(n) near front, O(1) at end | | Order preservation | No | Yes | | Index stability | Unstable (one index changes) | Stable (subsequent indices shift) | | Best for | Caches, sets, performance-critical | Ordered collections, sequences |

Index effects:

| Method | Indices Changed | Order After Removal | |--------|-----------------|---------------------| | swap_remove | Last element's index | Last element fills removed slot | | shift_remove | All subsequent indices | Elements shift left, order preserved |

Decision guide:

| Scenario | Recommended Method | |----------|-------------------| | Cache implementation | swap_remove | | Set membership | swap_remove | | Queue/deque (order matters) | shift_remove | | History/audit log | shift_remove | | Removing last element | Either (same performance) | | High-frequency removals | swap_remove |

Key insight: IndexMap::swap_remove provides O(1) removal by swapping the removed element with the last element, making it ideal for caches and sets where iteration order doesn't matter. IndexMap::shift_remove preserves insertion order by shifting subsequent elements backward, making it necessary for ordered collections, queues, and any use case where stable iteration order is part of the API contract. The performance difference is most significant for elements near the front of the map: swap_remove remains constant-time while shift_remove requires shifting all subsequent elements. When position matters—whether for user-facing ordering or for maintaining valid indices after removal—shift_remove is essential despite the performance cost.

Loading page…

What is the difference between indexmap::IndexMap::shift_remove and swap_remove for element removal?

Basic IndexMap Structure

Swap Remove Behavior

Shift Remove Behavior

Time Complexity Comparison

Internal Index Changes

Removal by Index

Return Value

Iteration Order Impact

Performance Benchmarks

Preserving Indices with Entries

Use Case: Priority Queue

Use Case: Ordered History

Mixed Removal Pattern

Comparison Table

Real-World Example: LRU Cache Implementation

Real-World Example: Ordered Task List

Real-World Example: Position-Based Removal

Synthesis

What is the difference between indexmap::IndexMap::shift_remove and swap_remove for element removal?

Basic IndexMap Structure

Swap Remove Behavior

Shift Remove Behavior

Time Complexity Comparison

Internal Index Changes

Removal by Index

Return Value

Iteration Order Impact

Performance Benchmarks

Preserving Indices with Entries

Use Case: Priority Queue

Use Case: Ordered History

Mixed Removal Pattern

Comparison Table

Real-World Example: LRU Cache Implementation

Real-World Example: Ordered Task List

Real-World Example: Position-Based Removal

Synthesis

What is the difference between `indexmap::IndexMap::shift_remove` and `swap_remove` for element removal?

What is the difference between `indexmap::IndexMap::shift_remove` and `swap_remove` for element removal?