How does indexmap::IndexMap::shift_remove maintain index ordering compared to swap_remove?
shift_remove preserves insertion order by shifting all subsequent entries down, maintaining indices but incurring O(n) time, while swap_remove swaps the removed entry with the last entry, preserving O(1) time but changing indices. This trade-off between index stability and performance is the key difference between the two removal methods in IndexMap.
Basic Removal Operations
use indexmap::IndexMap;
fn basic_removal() {
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
// Current order: [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
// Indices: a=0, b=1, c=2, d=3
// Remove "b" with swap_remove
let removed = map.swap_remove("b");
assert_eq!(removed, Some(2));
// After swap_remove: [("a", 1), ("d", 4), ("c", 3)]
// "d" swapped with "b" position
// Indices changed: a=0, d=1, c=2
}swap_remove moves the last entry into the removed position, changing indices.
use indexmap::IndexMap;
fn shift_removal() {
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
// Current order: [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
// Remove "b" with shift_remove
let removed = map.shift_remove("b");
assert_eq!(removed, Some(2));
// After shift_remove: [("a", 1), ("c", 3), ("d", 4)]
// Entries after "b" shifted down
// Indices preserved: a=0, c=1, d=2
}shift_remove shifts subsequent entries, preserving relative order.
Index Stability After Removal
use indexmap::IndexMap;
fn index_stability() {
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 indices before removal
let idx_a = map.get_index_of("a"); // 0
let idx_b = map.get_index_of("b"); // 1
let idx_c = map.get_index_of("c"); // 2
let idx_d = map.get_index_of("d"); // 3
// swap_remove changes indices
map.swap_remove("b");
// After swap_remove:
assert_eq!(map.get_index_of("a"), Some(0)); // Same
assert_eq!(map.get_index_of("c"), Some(1)); // Changed from 2 to 1
assert_eq!(map.get_index_of("d"), Some(2)); // Changed from 3 to 2
// "d" swapped into "b"'s position
// shift_remove preserves relative order
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.shift_remove("b");
// After shift_remove:
assert_eq!(map2.get_index_of("a"), Some(0)); // Same
assert_eq!(map2.get_index_of("c"), Some(1)); // Changed from 2 to 1 (preserved order)
assert_eq!(map2.get_index_of("d"), Some(2)); // Changed from 3 to 2 (preserved order)
// "c" and "d" shifted down, preserving their relative order
}swap_remove changes indices unpredictably; shift_remove maintains relative order.
Time Complexity
use indexmap::IndexMap;
fn complexity() {
// swap_remove: O(1) time
// - Swap last element into removed position
// - Update hash table
// - Remove from end
// shift_remove: O(n) time
// - Shift all subsequent entries down
// - Update indices in hash table for shifted entries
// - Remove from position
let mut map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..1000000 {
map.insert(i, i * 2);
}
// Removing from middle:
// swap_remove: Very fast (constant time)
// map.swap_remove(&500000); // O(1)
// shift_remove: Slower (linear time)
// map.shift_remove(&0); // O(n) - worst case, shifts everything
// map.shift_remove(&999999); // O(1) - best case, nothing to shift
}swap_remove is O(1); shift_remove is O(n) in the worst case.
Memory Layout Implications
use indexmap::IndexMap;
fn memory_layout() {
// IndexMap maintains:
// 1. A hash table for O(1) lookups
// 2. An ordered array for insertion-order iteration
// swap_remove:
// - Swaps entry in the array (memswap)
// - Updates hash table entry for swapped key
// - Array order changes (last entry moves)
// shift_remove:
// - Removes entry from array
// - Shifts all subsequent entries down
// - Updates hash table entries for all shifted keys
// - Array order preserved
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);
// swap_remove("b"):
// Before: [a, b, c, d, e]
// After: [a, e, c, d] (e moved to b's position)
// shift_remove("b"):
// Before: [a, b, c, d, e]
// After: [a, c, d, e] (c, d, e shifted down)
}swap_remove changes memory order; shift_remove maintains it.
Iteration Order
use indexmap::IndexMap;
fn iteration_order() {
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
// Original iteration order: a, b, c, d
map.swap_remove("b");
// After swap_remove: a, d, c
// "d" moved before "c"
let keys: Vec<_> = map.keys().collect();
assert_eq!(keys, vec
![&"a", &"d", &"c"]);
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.shift_remove("b");
// After shift_remove: a, c, d
// Relative order preserved
let keys: Vec<_> = map2.keys().collect();
assert_eq!(keys, vec
![&"a", &"c", &"d"]);
}shift_remove preserves iteration order; swap_remove may reorder.
Use Cases for Each Method
use indexmap::IndexMap;
fn use_cases() {
// Use swap_remove when:
// 1. Performance is critical
// 2. Index stability doesn't matter
// 3. You're not tracking indices externally
// Use shift_remove when:
// 1. Index stability is required
// 2. You need predictable iteration order
// 3. You're tracking positions externally
// 4. You need insertion-order semantics after removal
// Example: Priority queue where order matters
// Use shift_remove to maintain priority order
// Example: High-performance cache
// Use swap_remove for speed
}Choose based on whether you need index stability or performance.
External Index Tracking
use indexmap::IndexMap;
fn external_tracking() {
// If you track indices externally, shift_remove is safer
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("first", 1);
map.insert("second", 2);
map.insert("third", 3);
// Suppose you store indices somewhere
let stored_indices: std::collections::HashMap<&str, usize> = [
("first", 0),
("second", 1),
("third", 2),
].into_iter().collect();
// swap_remove would invalidate stored indices
map.swap_remove("first");
// Now "third" is at index 0, "second" at index 1
// stored_indices["second"] = 1 is correct (lucky!)
// stored_indices["third"] = 2 is now wrong (should be 1)
// shift_remove maintains relative positions
let mut map2: IndexMap<&str, i32> = IndexMap::new();
map2.insert("first", 1);
map2.insert("second", 2);
map2.insert("third", 3);
map2.shift_remove("first");
// "second" is at index 0, "third" is at index 1
// Relative order preserved, easier to update external tracking
}shift_remove is safer when external code tracks indices.
Entry Index Access
use indexmap::IndexMap;
fn entry_access() {
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Access by index
let (key, value) = map.get_index(1).unwrap();
assert_eq!((*key, *value), (&"b", 2));
// After swap_remove, the index refers to different entry
map.swap_remove("b");
let (key, value) = map.get_index(1).unwrap();
assert_eq!((*key, *value), (&"c", 2)); // "c" now at index 1
// With shift_remove, indices shift predictably
let mut map2: IndexMap<&str, i32> = IndexMap::new();
map2.insert("a", 1);
map2.insert("b", 2);
map2.insert("c", 3);
map2.shift_remove("b");
// Now index 1 contains "c"
// Indices after 1 shifted down
}Index-based access behaves differently after each removal method.
Performance Benchmarks
use indexmap::IndexMap;
fn benchmarks() {
// Rough performance comparison:
// swap_remove:
// - O(1) for any position
// - Constant time regardless of map size
// - Minimal memory movement (just swap)
// shift_remove:
// - O(n) worst case (removing from beginning)
// - O(1) best case (removing from end)
// - Memory movement proportional to remaining entries
// For large maps with frequent removals from beginning:
// swap_remove is much faster
// For small maps or removals from end:
// shift_remove has acceptable performance
// Example sizes:
let mut large_map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..100000 {
large_map.insert(i, i);
}
// Removing from beginning with shift_remove: ~100000 shifts
// Removing from beginning with swap_remove: ~2 operations
// Removing from end: both are similar (nothing to shift)
}Performance difference is significant for large maps and front removals.
Comparison with HashMap
use indexmap::IndexMap;
use std::collections::HashMap;
fn hashmap_comparison() {
// std::collections::HashMap doesn't maintain order
// No equivalent to swap_remove vs shift_remove
// IndexMap provides both:
// - Insertion-order iteration
// - Index-based access
// - Order-preserving or fast removal options
let mut map: IndexMap<i32, i32> = IndexMap::new();
map.insert(1, 1);
map.insert(2, 2);
map.insert(3, 3);
// Remove by key with choice of behavior:
map.swap_remove(&2); // Fast, may reorder
map.shift_remove(&2); // Order-preserving, slower
// HashMap only has one removal:
let mut hashmap: HashMap<i32, i32> = HashMap::new();
hashmap.insert(1, 1);
hashmap.insert(2, 2);
hashmap.remove(&2); // No order to preserve
}IndexMap offers choice; HashMap has no ordering to preserve.
Retain Method
use indexmap::IndexMap;
fn retain_example() {
// IndexMap also has retain methods:
let mut map: IndexMap<i32, i32> = IndexMap::new();
map.insert(1, 10);
map.insert(2, 20);
map.insert(3, 30);
map.insert(4, 40);
// retain removes elements that don't match predicate
// Uses shift_remove internally (preserves order)
map.retain(|k, v| *k > 2);
// Order preserved: [(3, 30), (4, 40)]
assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec
![3, 4]);
// For swap_remove semantics with retain:
// Use retain with manual swap_remove logic
}retain uses order-preserving removal semantics.
Splitting IndexMap
use indexmap::IndexMap;
fn split_off() {
let mut map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..10 {
map.insert(i, i * 10);
}
// split_off splits at index, preserving order
let map2 = map.split_off(5);
// map: [(0, 0), (1, 10), (2, 20), (3, 30), (4, 40)]
// map2: [(5, 50), (6, 60), (7, 70), (8, 80), (9, 90)]
// Both preserve insertion order
// split_off doesn't involve removal, so no swap vs shift question
}split_off preserves order; it's not a removal operation.
Practical Recommendations
use indexmap::IndexMap;
fn recommendations() {
// Use swap_remove when:
// - Building a cache or LRU structure
// - Performance is critical
// - You don't track indices
// - Order after removal doesn't matter
// Use shift_remove when:
// - Index stability is required
// - External code references indices
// - You need predictable iteration order
// - Building a queue or ordered collection
// - Implementing a ordered map with consistent positions
// Default to shift_remove if:
// - Correctness depends on order
// - Map size is small
// - Removals are infrequent
// - Removing from end (similar performance)
// Default to swap_remove if:
// - Map is large
// - Many removals
// - Order doesn't matter
}Choose based on your specific requirements for order and performance.
Comparison Table
fn comparison() {
// ┌─────────────────────────────────────────────────────────────────────────┐
// │ Aspect │ swap_remove │ shift_remove │
// ├─────────────────────────────────────────────────────────────────────────┤
// │ Time complexity │ O(1) │ O(n) worst case │
// │ Index stability │ Changes indices │ Preserves order │
// │ Iteration order │ May change │ Preserved │
// │ Memory movement │ Single swap │ Shift remaining │
// │ Best case │ O(1) always │ O(1) at end │
// │ Worst case │ O(1) always │ O(n) at start │
// │ Use case │ Performance │ Order correctness │
// │ External indices │ Invalidates │ Easier to update │
// └─────────────────────────────────────────────────────────────────────────┘
}Complete Example
use indexmap::IndexMap;
fn complete_example() {
// Scenario: Task queue with priority ordering
// Need to remove completed tasks while maintaining order
let mut task_queue: IndexMap<String, TaskStatus> = IndexMap::new();
task_queue.insert("task1".to_string(), TaskStatus::Running);
task_queue.insert("task2".to_string(), TaskStatus::Pending);
task_queue.insert("task3".to_string(), TaskStatus::Pending);
task_queue.insert("task4".to_string(), TaskStatus::Running);
// Using shift_remove maintains task order
if task_queue.shift_remove(&"task2".to_string()).is_some() {
// Task2 completed and removed
// Remaining order: task1, task3, task4
}
// Indices remain consistent for monitoring
// task1 is still first, task3 moved to second, task4 is third
// Scenario: High-performance cache
// Don't care about order, want fast removal
let mut cache: IndexMap<String, CachedData> = IndexMap::new();
cache.insert("key1".to_string(), CachedData { data: vec
![1] });
cache.insert("key2".to_string(), CachedData { data: vec
![2] });
cache.insert("key3".to_string(), CachedData { data: vec
![3] });
// Using swap_remove for speed
cache.swap_remove(&"key2".to_string());
// Order may change, but removal is O(1)
}
#[derive(Debug)]
enum TaskStatus {
Pending,
Running,
}
struct CachedData {
data: Vec<i32>,
}
fn main() {
complete_example();
}Summary
fn summary() {
// ┌─────────────────────────────────────────────────────────────────────────┐
// │ Method │ Best for │
// ├─────────────────────────────────────────────────────────────────────────┤
// │ swap_remove │ - High-performance removals │
// │ │ - Cache implementations │
// │ │ - When order doesn't matter │
// │ │ - Large maps with frequent removals │
// ├─────────────────────────────────────────────────────────────────────────┤
// │ shift_remove │ - Order-preserving removals │
// │ │ - Task/process queues │
// │ │ - External index tracking │
// │ │ - Consistent iteration order │
// │ │ - Small maps or rare removals │
// └─────────────────────────────────────────────────────────────────────────┘
// Key points:
// 1. swap_remove is O(1), shift_remove is O(n) worst case
// 2. swap_remove may change indices, shift_remove preserves order
// 3. shift_remove maintains iteration order after removal
// 4. swap_remove moves last entry into removed position
// 5. shift_remove shifts all subsequent entries down
// 6. Choose based on performance vs. order requirements
// 7. For external index tracking, prefer shift_remove
}Key insight: The choice between swap_remove and shift_remove in IndexMap represents a fundamental trade-off between performance and predictability. swap_remove achieves O(1) time complexity by swapping the last element into the removed position, which invalidates indices and may change iteration order. shift_remove preserves the insertion order by shifting subsequent elements down, maintaining index stability at the cost of O(n) time in the worst case. Use swap_remove when you need fast removal and don't track indices externally—typical for caches or high-performance structures. Use shift_remove when insertion order matters, when external code tracks positions, or when you need predictable behavior—typical for task queues, ordered collections, or when indices are referenced elsewhere. The default remove method uses swap_remove for backward compatibility and performance, so you must explicitly choose shift_remove when order preservation is required.