What are the trade-offs between indexmap::IndexMap::shift_remove and swap_remove for maintaining element order?
swap_remove is O(1) but disrupts element order by swapping the removed element with the last element, while shift_remove preserves insertion order at the cost of O(n) performance due to shifting all subsequent elements. This fundamental trade-off between speed and order preservation affects every ordered collection removal—IndexMap gives you the choice. The right selection depends on whether your code relies on iteration order or just needs fast removals.
Understanding IndexMap's Ordered Nature
use indexmap::IndexMap;
fn main() {
// IndexMap preserves insertion order
let mut map = IndexMap::new();
map.insert("apple", 1);
map.insert("banana", 2);
map.insert("cherry", 3);
map.insert("date", 4);
// Iteration follows insertion order
for (key, value) in &map {
println!("{}: {}", key, value);
}
// Output:
// apple: 1
// banana: 2
// cherry: 3
// date: 4
// IndexMap stores entries in a contiguous array
// plus a hash table for O(1) lookups
// Indices: [0] [1] [2] [3]
// Entries: [apple] [banana] [cherry] [date]
// Removing elements has two options...
}IndexMap maintains insertion order in an internal array alongside its hash table.
swap_remove: Fast but Disorderly
use indexmap::IndexMap;
fn main() {
let mut map = IndexMap::new();
map.insert("apple", 1);
map.insert("banana", 2);
map.insert("cherry", 3);
map.insert("date", 4);
// Current order: apple, banana, cherry, date
// swap_remove: O(1) complexity
// Swaps removed element with last, then removes last
let removed = map.swap_remove("banana");
println!("Removed: {:?}", removed); // Some(2)
// Order after swap_remove:
for (key, _) in &map {
println!("{}", key);
}
// apple
// date <-- moved from position 3 to position 1!
// cherry
// What happened:
// Before: [apple, banana, cherry, date]
// [0] [1] [2] [3]
//
// Remove "banana" (position 1):
// 1. Swap position 1 with position 3 (last)
// [apple, date, cherry, banana]
// 2. Remove last position
// [apple, date, cherry]
//
// "date" moved to fill "banana"'s position
}swap_remove swaps the target with the last element, changing order but keeping removal O(1).
shift_remove: Ordered but Slower
use indexmap::IndexMap;
fn main() {
let mut map = IndexMap::new();
map.insert("apple", 1);
map.insert("banana", 2);
map.insert("cherry", 3);
map.insert("date", 4);
// Current order: apple, banana, cherry, date
// shift_remove: O(n) complexity in worst case
// Shifts all elements after the removed one
let removed = map.shift_remove("banana");
println!("Removed: {:?}", removed); // Some(2)
// Order after shift_remove:
for (key, _) in &map {
println!("{}", key);
}
// apple
// cherry <-- shifted from position 2 to position 1
// date <-- shifted from position 3 to position 2
// What happened:
// Before: [apple, banana, cherry, date]
// [0] [1] [2] [3]
//
// Remove "banana" (position 1):
// 1. Remove element at position 1
// 2. Shift all subsequent elements left by 1
// [apple, cherry, date]
//
// Order is preserved!
}shift_remove shifts subsequent elements, preserving order at O(n) cost.
Performance Comparison
use indexmap::IndexMap;
fn benchmark() {
// Complexity comparison:
//
// swap_remove: O(1) - constant time
// - Swap two entries in the array
// - Pop last entry
// - Update hash table indices
//
// shift_remove: O(n) - linear in position
// - Remove entry at position
// - Shift all subsequent entries
// - Update hash table indices for shifted entries
// swap_remove is always O(1):
// - 1 million elements: same cost to remove any element
// - Remove from beginning: O(1)
// - Remove from middle: O(1)
// - Remove from end: O(1)
// shift_remove varies by position:
// - Remove from end: O(1) (nothing to shift)
// - Remove from middle: O(n/2) average
// - Remove from beginning: O(n) (shift everything)
let mut map = IndexMap::new();
for i in 0..1_000_000 {
map.insert(i, i);
}
// swap_remove: same cost everywhere
map.swap_remove(&0); // O(1) - first element
map.swap_remove(&500000); // O(1) - middle element
map.swap_remove(&999999); // O(1) - last element
// shift_remove: varies dramatically
// (hypothetically, if we hadn't already removed elements)
map.shift_remove(&999999); // O(1) - last, nothing to shift
map.shift_remove(&500000); // O(n/2) - middle
map.shift_remove(&0); // O(n) - first, shift everything
}swap_remove is always O(1); shift_remove varies from O(1) to O(n) based on position.
When Order Matters
use indexmap::IndexMap;
fn order_sensitive_code() {
// Example 1: Ordered iteration for display
let mut settings = IndexMap::new();
settings.insert("theme", "dark");
settings.insert("language", "en");
settings.insert("timezone", "UTC");
// Users expect settings in a certain order
// Removing with swap_remove would scramble display
settings.shift_remove("language");
// Order preserved: theme, timezone
for (key, _) in &settings {
println!("{}", key); // theme, timezone (not theme, timezone)
}
// Example 2: Priority queue with stable ordering
let mut priorities = IndexMap::new();
priorities.insert("high", 3);
priorities.insert("medium", 2);
priorities.insert("low", 1);
// Process in order: high, medium, low
// If we use swap_remove and remove "medium":
// Order becomes: high, low, high
// "low" jumps to middle position!
priorities.shift_remove("medium");
// Order preserved: high, low
}Use shift_remove when code relies on iteration order.
When Order Doesn't Matter
use indexmap::IndexMap;
fn order_insensitive_code() {
// Example 1: Set-like behavior (order irrelevant)
let mut unique_ids = IndexMap::new();
for id in [100, 200, 300, 400] {
unique_ids.insert(id, ());
}
// We only care about membership, not order
unique_ids.swap_remove(&200);
// Order changed? Who cares - we just check contains()
// Example 2: Cache with arbitrary eviction
let mut cache = IndexMap::new();
cache.insert("a", "data_a");
cache.insert("b", "data_b");
cache.insert("c", "data_c");
// Evicting arbitrary entry - order doesn't matter
if let Some((key, _)) = cache.pop() {
println!("Evicted: {}", key);
}
// Or evict specific key - swap_remove is fine
cache.swap_remove("b");
// Example 3: Lookup-heavy workload
// Primary operation is get(), not iteration
let mut lookup_map = IndexMap::new();
// ... populate ...
let value = lookup_map.get(&key); // O(1) lookup
// Remove when done - order irrelevant
lookup_map.swap_remove(&key);
}Use swap_remove when iteration order is unimportant.
Index Invalidation
use indexmap::IndexMap;
fn index_invalidation() {
// IndexMap allows index-based access
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
// Get indices
let index_b = map.get_index_of("b"); // Some(1)
let index_c = map.get_index_of("c"); // Some(2)
let index_d = map.get_index_of("d"); // Some(3)
// swap_remove invalidates indices of swapped elements
map.swap_remove("b");
// "d" moved from index 3 to index 1
let new_index_d = map.get_index_of("d"); // Some(1) - changed!
let new_index_c = map.get_index_of("c"); // Some(2) - unchanged
// shift_remove invalidates indices of all subsequent elements
let mut map2 = IndexMap::new();
map2.insert("a", 1);
map2.insert("b", 2);
map2.insert("c", 3);
map2.insert("d", 4);
map2.shift_remove("b");
// "c" moved from index 2 to index 1
// "d" moved from index 3 to index 2
let new_index_c2 = map2.get_index_of("c"); // Some(1) - changed
let new_index_d2 = map2.get_index_of("d"); // Some(2) - changed
// Both operations invalidate indices
// The difference is WHICH indices:
// - swap_remove: the last element's index changes
// - shift_remove: all elements after removal shift
// Recommendation: Don't hold indices across removals
// Re-look up indices after any modification
}Both operations invalidate indices—shift_remove affects more indices than swap_remove.
Hybrid Approaches
use indexmap::IndexMap;
fn hybrid_approach() {
// Sometimes you need both behaviors in the same codebase
struct OrderedCache {
entries: IndexMap<String, String>,
preserve_order: bool,
}
impl OrderedCache {
fn remove(&mut self, key: &str) -> Option<String> {
if self.preserve_order {
self.entries.shift_remove(key)
} else {
self.entries.swap_remove(key)
}
}
}
// Or: use shift_remove for most operations, swap_remove for hot paths
fn process_with_selective_removal(map: &mut IndexMap<String, Data>) {
// Hot path: need fast removal, don't care about order
if should_evict_quickly() {
map.swap_remove(&key_to_evict);
}
// Normal path: preserve order for user-visible display
if should_remove_cleanly() {
map.shift_remove(&key_to_remove);
}
}
// Another pattern: batch removals then compact
fn batch_remove(map: &mut IndexMap<i32, String>, keys: &[i32]) {
// Remove all at once (order doesn't matter during removal)
for key in keys {
map.swap_remove(key);
}
// The remaining order is... something
// If you need ordered output, sort the remaining entries
}
}Choose based on context—different parts of code may need different approaches.
Comparison with Standard Library
use indexmap::IndexMap;
use std::collections::HashMap;
fn compare_with_std() {
// HashMap: no order, removal doesn't expose order issues
let mut std_map = HashMap::new();
std_map.insert("a", 1);
std_map.insert("b", 2);
std_map.remove("a"); // O(1), no order to preserve
// HashMap doesn't expose iteration order guarantees
// (there's an order, but it's unspecified)
// IndexMap: explicit order, must choose removal strategy
let mut index_map = IndexMap::new();
index_map.insert("a", 1);
index_map.insert("b", 2);
// Two choices:
index_map.swap_remove("a"); // O(1), scrambles order
// or
index_map.shift_remove("a"); // O(n), preserves order
// Vec has the same trade-off:
let mut vec = vec!["a", "b", "c", "d"];
vec.swap_remove(1); // O(1), "b" removed, "d" takes its place
// vec is now ["a", "d", "c"]
let mut vec2 = vec!["a", "b", "c", "d"];
vec2.remove(1); // O(n), "b" removed, elements shift
// vec2 is now ["a", "c", "d"]
}The same O(1) vs O(n) trade-off exists in Vec::swap_remove vs Vec::remove.
Entry API and Removal
use indexmap::IndexMap;
use indexmap::map::Entry;
fn entry_api() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Entry API provides swap_remove_entry and shift_remove_entry
match map.entry("b") {
Entry::Occupied(entry) => {
// Both options available:
// entry.swap_remove(); // O(1), disorderly
entry.shift_remove(); // O(n), orderly
}
Entry::Vacant(_) => {}
}
// The entry methods return the removed value
let mut map2 = IndexMap::new();
map2.insert("x", 10);
if let Entry::Occupied(entry) = map2.entry("x") {
let value = entry.swap_remove();
println!("Removed: {}", value); // Removed: 10
}
}The Entry API mirrors both removal methods for occupied entries.
Real-World Scenarios
use indexmap::IndexMap;
fn real_world_scenarios() {
// Scenario 1: LRU Cache with ordered eviction
// Use swap_remove if you don't need strict LRU order
// Use shift_remove for proper LRU semantics
struct SimpleLruCache<K, V> {
entries: IndexMap<K, V>,
max_size: usize,
}
impl<K: std::hash::Hash + Eq + Clone, V> SimpleLruCache<K, V> {
fn insert(&mut self, key: K, value: V) {
// Remove oldest (first) when full
if self.entries.len() >= self.max_size {
// For proper LRU: need shift_remove to maintain order
// First element is oldest, shift keeps relative order
self.entries.shift_remove_index(0);
}
self.entries.insert(key, value);
}
}
// Scenario 2: Configuration map where display order matters
struct Config {
settings: IndexMap<String, String>,
}
impl Config {
fn remove(&mut self, key: &str) {
// User sees settings in order, preserve it
self.settings.shift_remove(key);
}
fn display(&self) {
// Order is predictable and stable
for (key, value) in &self.settings {
println!("{} = {}", key, value);
}
}
}
// Scenario 3: Request tracking where order doesn't matter
struct RequestTracker {
requests: IndexMap<u64, Request>,
}
impl RequestTracker {
fn complete(&mut self, id: u64) {
// Order irrelevant, just need fast removal
self.requests.swap_remove(&id);
}
}
}Choose based on whether order is visible to users or affects semantics.
Synthesis
Quick reference:
use indexmap::IndexMap;
// swap_remove:
// - Complexity: O(1)
// - Order: NOT preserved (last element moves to fill gap)
// - Best for: Performance-critical code, order-insensitive data
// - Analogy: Like Vec::swap_remove
// shift_remove:
// - Complexity: O(n) where n = elements after removed one
// - Order: Preserved (subsequent elements shift left)
// - Best for: Order-sensitive code, user-visible collections
// - Analogy: Like Vec::remove
fn quick_reference() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
// [a, b, c, d] before removal
// swap_remove("b"):
// - O(1)
// - Result: [a, d, c]
// - "d" swapped into "b"'s position
// shift_remove("b"):
// - O(n) where n = elements after "b" (2 elements: c, d)
// - Result: [a, c, d]
// - Order preserved
// Decision matrix:
// ┌─────────────────────────────┬───────────────┬───────────────┐
// │ Condition │ swap_remove │ shift_remove │
// ├─────────────────────────────┼───────────────┼───────────────┤
// │ Iteration order matters │ ✗ │ ✓ │
// │ User sees the collection │ ✗ │ ✓ │
// │ Performance critical │ ✓ │ ✗ │
// │ Many removals from front │ ✓ │ ✗ │
// │ Few removals, mostly lookups │ Either works │ Either works │
// │ Implementing LRU/FIFO │ ✗ │ ✓ │
// │ Just a lookup table │ ✓ │ Overkill │
// └─────────────────────────────┴───────────────┴───────────────┘
}Key insight: The choice between swap_remove and shift_remove is fundamentally about whether your collection's iteration order carries semantic meaning. If order is just an implementation detail—if you're using IndexMap for its O(1) lookups with O(1) removal and stable iteration within a single operation—then swap_remove is the right choice. But if order matters—if you're implementing an ordered queue, displaying items in a specific sequence, or depending on iteration order for correctness—then shift_remove preserves that contract at the cost of O(n) performance. The performance penalty is often acceptable because removals are typically less frequent than lookups and insertions, and O(n) at the end of a collection is still O(1).