How does indexmap::IndexMap::swap_remove_index differ from shift_remove_index for index stability?
swap_remove_index removes an element by swapping it with the last element, preserving O(1) complexity but invalidating indices of swapped elements, while shift_remove_index removes an element by shifting all subsequent elements down, maintaining all other indices but with O(n) complexity. The choice between these methods depends on whether you need index stability or performance.
IndexMap's Ordered Structure
use indexmap::IndexMap;
fn indexmap_basics() {
// IndexMap is a HashMap that maintains insertion 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);
// Access by index (position in insertion order)
assert_eq!(map[0], 1); // "a" is at index 0
assert_eq!(map[1], 2); // "b" is at index 1
assert_eq!(map[2], 3); // "c" is at index 2
assert_eq!(map[3], 4); // "d" is at index 3
// Iteration follows insertion order
for (i, (key, value)) in map.iter().enumerate() {
println!("Index {}: {} = {}", i, key, value);
}
// Output:
// Index 0: a = 1
// Index 1: b = 2
// Index 2: c = 3
// Index 3: d = 4
}IndexMap combines hash map lookup with positional indexing, making index stability important.
swap_remove_index Behavior
use indexmap::IndexMap;
fn swap_remove_demo() {
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:1, b:2, c:3, d:4] at indices [0, 1, 2, 3]
// Remove index 1 (the "b" entry)
let removed = map.swap_remove_index(1);
assert_eq!(removed, Some(("b", 2)));
// After: [a:1, d:4, c:3] at indices [0, 1, 2]
// "d" moved from index 3 to index 1!
// Let's verify:
assert_eq!(map[0], 1); // "a" still at index 0
assert_eq!(map[1], 4); // "d" now at index 1 (was at index 3)
assert_eq!(map[2], 3); // "c" still at index 2
// "d" got swapped into position 1
// The last element fills the gap
}swap_remove_index swaps the last element into the removed position, causing index changes.
shift_remove_index Behavior
use indexmap::IndexMap;
fn shift_remove_demo() {
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:1, b:2, c:3, d:4] at indices [0, 1, 2, 3]
// Remove index 1 (the "b" entry)
let removed = map.shift_remove_index(1);
assert_eq!(removed, Some(("b", 2)));
// After: [a:1, c:3, d:4] at indices [0, 1, 2]
// All subsequent elements shifted down by 1
// Let's verify:
assert_eq!(map[0], 1); // "a" still at index 0
assert_eq!(map[1], 3); // "c" shifted from index 2 to 1
assert_eq!(map[2], 4); // "d" shifted from index 3 to 2
// All indices after removal point are now shifted by -1
}shift_remove_index maintains insertion order but shifts all subsequent elements.
Visual Comparison
use indexmap::IndexMap;
fn visual_comparison() {
// Initial state:
// Index: 0 1 2 3
// Key: "a" "b" "c" "d"
// Value: 1 2 3 4
// After swap_remove_index(1):
// Index: 0 1 2
// Key: "a" "d" "c" <- "d" swapped in from position 3
// Value: 1 4 3
// After shift_remove_index(1):
// Index: 0 1 2
// Key: "a" "c" "d" <- "c" and "d" shifted left
// Value: 1 3 4
}The key difference: swap changes which element is at an index; shift changes indices of elements.
Index Stability Impact
use indexmap::IndexMap;
fn index_stability_impact() {
// Scenario: tracking indices for external references
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("first", 1);
map.insert("second", 2);
map.insert("third", 3);
map.insert("fourth", 4);
// External code has cached indices
let cached_indices = vec![0, 1, 2, 3];
// Problem with swap_remove_index:
// If we remove index 1, element at index 3 moves to index 1
// Any code holding "index 3 = fourth" is now wrong
map.swap_remove_index(1);
// map.get_index(3) is now out of bounds!
// map.get_index(1) returns what was at index 3
// Cached indices are now WRONG
// Solution: shift_remove_index preserves indices
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_index(1);
// Indices 0, 1, 2 still valid (for "first", "third", "fourth")
// Any index > 1 has shifted by -1, but order is preserved
}If external code holds indices, shift_remove_index is safer.
Performance Comparison
use indexmap::IndexMap;
fn performance_comparison() {
// swap_remove_index: O(1)
// - Just swap with last element
// - Update hash table entries
// - Pop the last slot
// shift_remove_index: O(n)
// - Remove the element
// - Shift all subsequent elements one position left
// - Update hash table entries for ALL shifted elements
// For small maps: negligible difference
// For large maps: significant difference
let mut map: IndexMap<i32, i32> = IndexMap::new();
// Insert 100,000 elements
for i in 0..100_000 {
map.insert(i, i * 2);
}
// Remove from middle
// swap_remove_index: ~constant time
map.swap_remove_index(50_000);
// Reset
map.clear();
for i in 0..100_000 {
map.insert(i, i * 2);
}
// shift_remove_index: ~linear time
map.shift_remove_index(50_000);
// This touches all 50,000 elements after index 50000
}swap_remove_index is O(1); shift_remove_index is O(n) where n is elements after removal point.
When to Use swap_remove_index
use indexmap::IndexMap;
fn use_swap_remove() {
// Use swap_remove_index when:
// 1. Order doesn't matter
// 2. You need O(1) removal
// 3. You don't hold external index references
// 4. Processing the entire map after removal
// Example: batch processing where order doesn't matter
let mut tasks: IndexMap<u32, Task> = IndexMap::new();
// Insert tasks
for i in 0..1000 {
tasks.insert(i, Task::new(i));
}
// Process and remove completed tasks
// Order doesn't matter, just want them gone fast
while !tasks.is_empty() {
let idx = 0;
if process_task(&tasks[idx]) {
tasks.swap_remove_index(idx);
}
}
// Example: implementing a work queue where order doesn't matter
let mut work_queue: IndexMap<TaskId, WorkItem> = IndexMap::new();
// Remove any completed item - don't care about position
work_queue.swap_remove_index(42);
}
struct Task {
id: u32,
}
impl Task {
fn new(id: u32) -> Self {
Self { id }
}
}
fn process_task(_task: &Task) -> bool {
true
}
type TaskId = u32;
struct WorkItem;Use swap_remove_index when order isn't important and you need fast removal.
When to Use shift_remove_index
use indexmap::IndexMap;
fn use_shift_remove() {
// Use shift_remove_index when:
// 1. Order must be preserved
// 2. External code holds index references
// 3. Iteration order matters
// 4. You're building a stable index
// Example: ordered sequence that external code references
let mut timeline: IndexMap<Time, Event> = IndexMap::new();
timeline.insert(Time(0), Event::Start);
timeline.insert(Time(1), Event::Process);
timeline.insert(Time(2), Event::Check);
timeline.insert(Time(3), Event::End);
// Remove middle event - order must stay chronological
timeline.shift_remove_index(2); // Remove Check
// Timeline is now: Start, Process, End
// Order preserved, indices predictable
// Example: UI list where removal should not reorder
let mut items: IndexMap<ItemId, Item> = IndexMap::new();
items.insert(0, Item::new("First"));
items.insert(1, Item::new("Second"));
items.insert(2, Item::new("Third"));
// Remove "Second" - "Third" should still be visible after "First"
items.shift_remove_index(1);
// Now: First, Third
// User expects "Third" to still be after "First"
// Example: stable indices for entity system
let mut entities: IndexMap<EntityId, Entity> = IndexMap::new();
// External systems may cache indices
// shift_remove_index keeps remaining entities in same relative order
}
#[derive(Clone, Copy)]
struct Time(u32);
#[derive(Clone)]
enum Event {
Start,
Process,
Check,
End,
}
type ItemId = u32;
struct Item {
name: String,
}
impl Item {
fn new(name: &str) -> Self {
Self { name: name.to_string() }
}
}
type EntityId = u32;
struct Entity;Use shift_remove_index when order matters or indices are externally referenced.
The Equivalent Key-Based Methods
use indexmap::IndexMap;
fn key_based_removal() {
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Key-based removal has same options:
// swap_remove: O(1), doesn't preserve order
map.swap_remove("b");
// Same effect as swap_remove_index(1)
// shift_remove: O(n), preserves order
map.shift_remove("b");
// Same effect as shift_remove_index(1)
// The _index variants are useful when you already have the index
// and don't want to do a hash lookup
}The key-based swap_remove and shift_remove methods have equivalent behavior.
Benchmarks
use indexmap::IndexMap;
fn benchmark() {
// Benchmark removal at different positions
// Size: 100,000 elements
let mut map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..100_000 {
map.insert(i, i);
}
// Remove at beginning (index 0)
// swap_remove: ~constant
// shift_remove: O(n) - must shift all 99,999 elements
// Remove at end (index 99,999)
// swap_remove: ~constant (no swap needed, just pop)
// shift_remove: ~constant (no elements after)
// Remove at middle (index 50,000)
// swap_remove: ~constant
// shift_remove: O(n/2) - must shift ~50,000 elements
// Rule of thumb:
// - Removal near end: shift_remove is fast (few/no shifts)
// - Removal at beginning/middle: swap_remove is much faster
// - If order matters: pay the O(n) cost of shift_remove
}The performance gap is largest for removals at the beginning of large maps.
Index Invalidation Patterns
use indexmap::IndexMap;
fn index_invalidation() {
// Pattern 1: External index references
let mut map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..10 {
map.insert(i, i);
}
// Store references by index
let important_indices: Vec<usize> = vec![0, 3, 7];
// swap_remove_index invalidates references
map.swap_remove_index(5);
// What was at index 9 is now at index 5
// important_indices[2] (7) might now point to wrong element
// Pattern 2: Iterating while removing
let mut map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..10 {
map.insert(i, i);
}
// Removing with swap while iterating (backwards is safe)
let mut i = map.len();
while i > 0 {
i -= 1;
if should_remove(map[i]) {
map.swap_remove_index(i);
// Safe: we process from end to start
// Removed elements are at the end, already processed
}
}
// Forwards iteration with removal requires tracking
let mut map: IndexMap<i32, i32> = IndexMap::new();
for i in 0..10 {
map.insert(i, i);
}
// Better: collect indices to remove, then remove in reverse
let to_remove: Vec<usize> = map.iter()
.filter(|(_, &v)| should_remove(v))
.map(|(i, _)| i)
.collect();
for idx in to_remove.into_iter().rev() {
map.swap_remove_index(idx);
}
}
fn should_remove(_value: i32) -> bool {
true // Simplified
}Be careful with indices held across removalsâswap can invalidate them unexpectedly.
Real-World Example: Ordered Event Processing
use indexmap::IndexMap;
struct EventLog {
events: IndexMap<EventId, Event>,
}
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct EventId(u64);
struct Event {
id: EventId,
timestamp: u64,
event_type: EventType,
}
enum EventType {
Start,
Stop,
Log(String),
Error(String),
}
impl EventLog {
fn new() -> Self {
Self {
events: IndexMap::new(),
}
}
fn add_event(&mut self, event: Event) {
self.events.insert(event.id, event);
}
// Remove expired events, preserving order for replay
fn remove_expired(&mut self, cutoff: u64) {
// Must use shift_remove to preserve event order
// Events are processed in insertion order for replay
let indices_to_remove: Vec<usize> = self.events
.iter()
.enumerate()
.filter(|(_, (_, event))| event.timestamp < cutoff)
.map(|(i, _)| i)
.collect();
// Remove in reverse order to maintain valid indices
for idx in indices_to_remove.into_iter().rev() {
self.events.shift_remove_index(idx);
}
}
// Remove specific event, order doesn't matter after this
fn cancel_event(&mut self, event_id: EventId) -> Option<Event> {
// Use swap_remove since we're canceling - order isn't important
// for events that won't happen
self.events.swap_remove(&event_id)
}
fn replay(&self) -> impl Iterator<Item = &Event> {
self.events.values()
}
}
fn event_log_usage() {
let mut log = EventLog::new();
log.add_event(Event { id: EventId(1), timestamp: 100, event_type: EventType::Start });
log.add_event(Event { id: EventId(2), timestamp: 200, event_type: EventType::Log("msg".into()) });
log.add_event(Event { id: EventId(3), timestamp: 300, event_type: EventType::Stop });
// Remove expired events (before timestamp 250)
log.remove_expired(250);
// Remaining events are in order: Log, Stop
// If we had used swap_remove, order might have been: Stop, Log
}Event logs need ordered replayâuse shift_remove_index to preserve sequence.
Real-World Example: Entity System
use indexmap::IndexMap;
struct EntityManager {
entities: IndexMap<EntityId, Entity>,
// Indices are used for fast lookup in other systems
}
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct EntityId(u32);
struct Entity {
id: EntityId,
components: Vec<Component>,
}
enum Component {
Position(f32, f32),
Velocity(f32, f32),
Health(i32),
}
impl EntityManager {
fn spawn(&mut self) -> EntityId {
let id = EntityId(self.next_id());
self.entities.insert(id, Entity {
id,
components: Vec::new(),
});
id
}
fn despawn(&mut self, id: EntityId) {
// Use shift_remove to keep indices stable
// Other systems may have cached entity indices
self.entities.shift_remove(&id);
}
fn get_index(&self, id: EntityId) -> Option<usize> {
self.entities.get_index_of(&id)
}
fn get_by_index(&self, index: usize) -> Option<&Entity> {
self.entities.get_index(index).map(|(_, e)| e)
}
fn next_id(&self) -> u32 {
// Simplified
self.entities.len() as u32
}
}
// Other systems cache indices for fast access
struct PhysicsSystem {
// Cached indices into entity manager
tracked_entities: Vec<usize>,
}
impl PhysicsSystem {
fn process(&mut self, entities: &EntityManager) {
// Relies on stable indices
for &idx in &self.tracked_entities {
if let Some(entity) = entities.get_by_index(idx) {
// Process entity physics
}
}
}
// If entities used swap_remove, cached indices would be wrong!
}Entity systems often cache indicesâshift_remove_index maintains stability.
Summary Table
use indexmap::IndexMap;
fn summary() {
// | Method | Time Complexity | Order Preserved | Index Stability |
// |----------------------|-----------------|-----------------|------------------------|
// | swap_remove_index | O(1) | No | Invalidates later ones |
// | shift_remove_index | O(n) | Yes | Preserves (shifts -1) |
// swap_remove_index:
// - Fast: constant time
// - Swaps last element into removed position
// - Order changed: last element moves to removal position
// - Good for: unordered collections, bulk processing
// shift_remove_index:
// - Slower: linear time
// - Shifts all subsequent elements left
// - Order preserved: elements keep relative order
// - Good for: ordered sequences, stable indices, UI lists
}Synthesis
Quick reference:
use indexmap::IndexMap;
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// swap_remove_index(i): O(1), swaps with last
// Before: [a:1, b:2, c:3]
map.swap_remove_index(1); // Remove "b"
// After: [a:1, c:3] <- "c" swapped to index 1
// shift_remove_index(i): O(n), shifts left
let mut map: IndexMap<&str, i32> = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Before: [a:1, b:2, c:3]
map.shift_remove_index(1); // Remove "b"
// After: [a:1, c:3] <- order preservedKey insight: The choice between swap_remove_index and shift_remove_index is fundamentally a trade-off between performance and stability. swap_remove_index achieves O(1) removal by exploiting the fact that IndexMap maintains elements in a contiguous arrayâwhen you remove an element, it simply moves the last element into that position. This is fast but breaks any assumptions about ordering or external index references. shift_remove_index preserves order by doing what a Vec would do: moving every element after the removal point one position to the left. This maintains all relative ordering and keeps indices predictable (each remaining element's index decreases by exactly 1 if it was after the removed element), but costs O(n) time. The decision should be based on your use case: if you're treating IndexMap as an unordered collection with O(1) removal needs, use swap_remove_index; if you're using it as an ordered sequence where indices matter (like a timeline, entity list, or anything where external code holds position references), pay the O(n) cost of shift_remove_index. The most common pitfall is using swap_remove_index when order mattersâsuddenly elements appear to "jump around" in iteration order, and cached indices point to wrong elements. The key question to ask: "Will any code be surprised if elements move?" If yes, use shift_remove_index.