How does `indexmap::map::IndexMap::swap_indices` reorder entries without invalidating keys?

IndexMap::swap_indices exchanges the positions of two entries in the map by swapping their internal indices, preserving key validity because keys are stored separately from their positions—unlike removing and reinserting, this operation only modifies the internal index mapping without touching the key-value storage. Understanding this mechanism reveals how IndexMap maintains insertion order while allowing efficient reordering.

Basic IndexMap Structure

use indexmap::IndexMap;
 
fn basic_structure() {
    let mut map: IndexMap<String, i32> = IndexMap::new();
    
    // IndexMap maintains insertion order
    map.insert("a".to_string(), 1);
    map.insert("b".to_string(), 2);
    map.insert("c".to_string(), 3);
    
    // Iteration preserves order
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
    // Output: a: 1, b: 2, c: 3
    
    // Internally, IndexMap stores:
    // - A hash table for O(1) key lookup
    // - A Vec of (key, value) pairs for ordered iteration
    // - An index mapping hash entries to Vec positions
}

IndexMap combines hash table lookup with ordered iteration through separate storage.

Basic swap_indices Usage

use indexmap::IndexMap;
 
fn basic_swap_indices() {
    let mut map: IndexMap<String, i32> = IndexMap::new();
    map.insert("a".to_string(), 1);
    map.insert("b".to_string(), 2);
    map.insert("c".to_string(), 3);
    
    // Before: a: 1, b: 2, c: 3
    // Positions: a=0, b=1, c=2
    
    // Swap positions 0 and 2
    map.swap_indices(0, 2);
    
    // After: c: 3, b: 2, a: 1
    // Positions: c=0, b=1, a=2
    
    // Keys still valid, only positions changed
    assert_eq!(map.get("a"), Some(&1));
    assert_eq!(map.get("b"), Some(&2));
    assert_eq!(map.get("c"), Some(&3));
}

swap_indices exchanges entries at two index positions without affecting key lookup.

Key Validity After Swap

use indexmap::IndexMap;
 
fn key_validity() {
    let mut map: IndexMap<String, i32> = IndexMap::new();
    map.insert("a".to_string(), 1);
    map.insert("b".to_string(), 2);
    map.insert("c".to_string(), 3);
    
    // Store references before swap
    let keys_before: Vec<_> = map.keys().collect();
    
    map.swap_indices(0, 2);
    
    // Keys still exist and are accessible
    assert!(map.contains_key("a"));
    assert!(map.contains_key("b"));
    assert!(map.contains_key("c"));
    
    // Values unchanged
    assert_eq!(map["a"], 1);
    assert_eq!(map["b"], 2);
    assert_eq!(map["c"], 3);
    
    // Only iteration order changed
    let keys_after: Vec<_> = map.keys().collect();
    assert_eq!(keys_after, vec!["c", "b", "a"]);
}

Keys remain valid after swapping; only iteration order changes.

Internal Mechanism

use indexmap::IndexMap;
 
fn internal_mechanism() {
    // IndexMap internal structure (simplified):
    //
    // 1. entries: Vec<(K, V)> - stores key-value pairs in order
    // 2. indices: HashTable<usize> - maps keys to positions in entries
    // 
    // When you call swap_indices(0, 2):
    // 
    // Before:
    // entries: [("a", 1), ("b", 2), ("c", 3)]
    // indices: {"a" -> 0, "b" -> 1, "c" -> 2}
    //
    // After swap_indices(0, 2):
    // entries: [("c", 3), ("b", 2), ("a", 1)]  // Swapped in Vec
    // indices: {"a" -> 2, "b" -> 1, "c" -> 0}  // Updated positions
    //
    // Key insight: entries are swapped, indices updated
    // Keys themselves are never invalidated
    
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    map.swap_indices(0, 2);
    
    // The hash table indices are updated to reflect new positions
    // Key lookup still works: hash(key) -> index -> entries[position]
}

The swap exchanges entries in the vector and updates index pointers.

Comparison with Remove and Reinsert

use indexmap::IndexMap;
 
fn vs_remove_reinsert() {
    let mut map: IndexMap<String, i32> = IndexMap::new();
    map.insert("a".to_string(), 1);
    map.insert("b".to_string(), 2);
    map.insert("c".to_string(), 3);
    
    // Approach 1: swap_indices (efficient)
    map.swap_indices(0, 2);
    // Only swaps positions, O(1) internal update
    // No reallocation, no rehashing
    
    // Approach 2: remove and reinsert (inefficient)
    let v0 = map.swap_remove_index(0);  // Actually removes
    // This would shift all elements and invalidate positions
    
    // swap_indices is specifically designed for reordering
    // without the overhead of removal/reinsertion
    
    // Use swap_indices when:
    // - You need to reorder entries
    // - You want to preserve all keys
    // - You want efficient operation
}

swap_indices is more efficient than remove-reinsert patterns.

Indices vs Keys

use indexmap::IndexMap;
 
fn indices_vs_keys() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // Index: position in iteration order (0, 1, 2, ...)
    // Key: the actual key value ("first", "second", "third")
    
    // Access by index
    let (key, value) = map.get_index(1).unwrap();
    assert_eq!(key, &"second");
    assert_eq!(value, &2);
    
    // Access by key
    let value = map.get("second");
    assert_eq!(value, Some(&2));
    
    // swap_indices operates on indices (positions)
    map.swap_indices(0, 2);
    
    // Now position 0 has what was at position 2
    let (key, value) = map.get_index(0).unwrap();
    assert_eq!(key, &"third");  // Was at index 2
    assert_eq!(value, &3);
    
    // Key-based access still works
    assert_eq!(map.get("first"), Some(&1));  // Now at index 2
    assert_eq!(map.get("third"), Some(&3));  // Now at index 0
}

swap_indices operates on positions; keys remain valid regardless of position.

Move Operations Family

use indexmap::IndexMap;
 
fn move_operations() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // swap_indices: exchange two positions
    map.swap_indices(0, 3);
    // Order: d, b, c, a
    
    // swap_remove_index: remove by index, last element fills gap
    // let old = map.swap_remove_index(1);  // Would remove "b"
    // Order would change more significantly
    
    // shift_remove_index: remove by index, shift remaining
    // let old = map.shift_remove_index(1);
    // Preserves order but O(n)
    
    // For reordering without removal:
    // - swap_indices: O(1), changes two positions
    // - Other approaches involve removal
}

swap_indices is the primary method for reordering without removal.

Swapping with Validity Bounds

use indexmap::IndexMap;
 
fn bounds_checking() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Valid indices: 0, 1, 2
    map.swap_indices(0, 2);  // OK
    
    // Invalid indices panic
    // map.swap_indices(0, 3);  // Panics: index out of bounds
    // map.swap_indices(0, 100);  // Panics: index out of bounds
    
    // Safe swapping with bounds check
    fn safe_swap<K, V>(map: &mut IndexMap<K, V>, i: usize, j: usize) {
        let len = map.len();
        if i < len && j < len {
            map.swap_indices(i, j);
        }
    }
}

swap_indices panics on out-of-bounds indices; check bounds before calling.

Sorting with swap_indices

use indexmap::IndexMap;
 
fn sorting_example() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("banana", 3);
    map.insert("apple", 1);
    map.insert("cherry", 2);
    map.insert("date", 4);
    
    // Collect indices for sorting
    let mut indices: Vec<usize> = (0..map.len()).collect();
    
    // Sort indices by key
    let entries: Vec<_> = map.iter().collect();
    indices.sort_by_key(|&i| entries[i].0);
    
    // Apply sorted order using swaps
    // Note: This is a simple but not optimal approach
    // In practice, use the indices directly or rebuild
    
    // Better: just sort the IndexMap directly
    // (IndexMap doesn't have a built-in sort, but you can extract and rebuild)
    
    let mut entries: Vec<_> = map.drain(..).collect();
    entries.sort_by_key(|(k, _)| *k);
    for (k, v) in entries {
        map.insert(k, v);
    }
    
    // Now in sorted order
    assert_eq!(map.keys().collect::<Vec<_>>(), vec![&"apple", &"banana", &"cherry", &"date"]);
}

Complex reorderings may be better handled by rebuilding the map.

Reordering by Value

use indexmap::IndexMap;
 
fn reorder_by_value() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("x", 30);
    map.insert("y", 10);
    map.insert("z", 20);
    
    // Get indices in value-sorted order
    let mut indexed: Vec<_> = map.iter().enumerate().collect();
    indexed.sort_by_key(|(_, (_, v))| *v);
    
    // Build new order
    let sorted_indices: Vec<usize> = indexed.into_iter().map(|(i, _)| i).collect();
    
    // For complex reorderings, rebuild the map:
    let entries: Vec<_> = map.drain(..).collect();
    let mut sorted_entries = entries.clone();
    sorted_entries.sort_by_key(|(_, v)| *v);
    
    for (k, v) in sorted_entries {
        map.insert(k, v);
    }
    
    // Now in value-sorted order
    let values: Vec<_> = map.values().collect();
    assert_eq!(values, vec![&10, &20, &30]);
}

swap_indices is best for simple swaps; complex reorderings may warrant rebuilding.

Concurrent Considerations

use indexmap::IndexMap;
// Note: IndexMap is not thread-safe by default
 
fn concurrent_note() {
    // IndexMap is not Sync
    // If you need thread-safe access, wrap in Mutex or RwLock
    
    // use std::sync::Mutex;
    // let map: Mutex<IndexMap<K, V>> = Mutex::new(IndexMap::new());
    
    // swap_indices requires &mut self
    // So it needs exclusive access
    
    // Under Mutex, only one thread can swap at a time
    // This is fine - swap_indices is O(1) and fast
    
    // Key insight: swapping doesn't invalidate keys
    // Other threads holding references to keys
    // (not values!) don't need to worry about invalidation
}

swap_indices requires mutable access; use synchronization for concurrent access.

Performance Characteristics

use indexmap::IndexMap;
 
fn performance() {
    // swap_indices is O(1)
    // - Swaps two entries in the internal Vec
    // - Updates two indices in the hash table
    // - No memory allocation
    // - No rehashing
    
    // Compare to other operations:
    // - get(): O(1)
    // - insert(): O(1) amortized
    // - swap_indices(): O(1)
    // - remove(): O(1) with swap_remove, O(n) with shift_remove
    
    // IndexMap maintains:
    // - Hash table: O(1) key lookup
    // - Vec: O(1) index access
    // - Index mapping: O(1) position lookup
    
    // swap_indices touches minimal internal state:
    // - Two entries in Vec
    // - Two indices in hash table
}

swap_indices is O(1), touching only two entries and their indices.

Practical Use Case: Priority Queue Ordering

use indexmap::IndexMap;
 
fn priority_queue_example() {
    // Use IndexMap as ordered storage with swap_indices for reordering
    
    let mut tasks: IndexMap<String, u32> = IndexMap::new();
    tasks.insert("task_a".to_string(), 100);  // priority
    tasks.insert("task_b".to_string(), 50);
    tasks.insert("task_c".to_string(), 75);
    
    // Move highest priority to front
    // (Simplified: in practice, find max first)
    
    // Find index of highest priority
    let max_idx = tasks
        .iter()
        .enumerate()
        .max_by_key(|(_, (_, &p))| p)
        .map(|(i, _)| i)
        .unwrap();
    
    // Swap to front
    if max_idx != 0 {
        tasks.swap_indices(0, max_idx);
    }
    
    // First task is now highest priority
    let (first_task, first_priority) = tasks.get_index(0).unwrap();
    println!("First: {} with priority {}", first_task, first_priority);
}

swap_indices enables manual reordering for priority-based structures.

Practical Use Case: LRU Cache Reordering

use indexmap::IndexMap;
 
fn lru_example() {
    // IndexMap can implement LRU cache behavior with swap_indices
    
    let mut cache: IndexMap<String, String> = IndexMap::new();
    cache.insert("a".to_string(), "value_a".to_string());
    cache.insert("b".to_string(), "value_b".to_string());
    cache.insert("c".to_string(), "value_c".to_string());
    
    // Access "b" - move to end (most recently used)
    fn touch<K, V>(map: &mut IndexMap<K, V>, key: &K) 
    where 
        K: std::hash::Hash + Eq + Clone,
    {
        if let Some((idx, _)) = map.get_full(key) {
            // Move to end by swapping with last
            let last = map.len() - 1;
            if idx != last {
                map.swap_indices(idx, last);
            }
        }
    }
    
    touch(&mut cache, &"b".to_string());
    
    // Order now: a, c, b (b moved to end)
    // Note: For true LRU, consider IndexMap's move_index* methods
    // or use an LRU-specific crate
}

LRU caches can use swap_indices to mark entries as recently used.

Related Methods

use indexmap::IndexMap;
 
fn related_methods() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // get_index: access by position
    let entry = map.get_index(1);
    assert_eq!(entry, Some((&"b", &2)));
    
    // get_index_mut: mutable access by position
    if let Some((k, v)) = map.get_index_mut(1) {
        *v = 20;
    }
    
    // swap_indices: exchange two positions (covered)
    
    // move_index: move entry to new position (shifting others)
    // (If available in your version)
    
    // swap_remove_index: remove and swap with last
    let removed = map.swap_remove_index(0);
    // Last entry fills the gap, order changes
    
    // shift_remove_index: remove and shift remaining
    // Preserves order of remaining elements
    
    // get_full: get (index, key, value) from key
    let full = map.get_full(&"b");
    // Returns Some((index, &key, &value))
}

IndexMap provides many index-based methods for position operations.

Summary Table

fn summary_table() {
    // ┌─────────────────────────────────────────────────────────────────────────┐
    // │ Operation          │ Effect                           │ Complexity    │
    // ├─────────────────────────────────────────────────────────────────────────┤
    // │ swap_indices(i, j) │ Exchanges entries at positions   │ O(1)          │
    // │ swap_remove_index  │ Removes entry, last fills gap     │ O(1)          │
    // │ shift_remove_index │ Removes entry, shifts remaining  │ O(n)          │
    // │ get_index(i)       │ Gets entry at position           │ O(1)          │
    // │ get_full(k)        │ Gets (index, k, v) for key       │ O(1)          │
    // │ insert             │ Adds at end                       │ O(1) amortized│
    // └─────────────────────────────────────────────────────────────────────────┘
}

Key Points Summary

fn key_points() {
    // 1. swap_indices exchanges two entries by their positions
    // 2. Keys remain valid after swap; only positions change
    // 3. Operation is O(1) - swaps entries and updates indices
    // 4. Internal structure: Vec for entries, hash table for indices
    // 5. Index positions are different from key values
    // 6. Panics on out-of-bounds indices
    // 7. More efficient than remove-and-reinsert patterns
    // 8. Useful for manual reordering (priority, LRU, etc.)
    // 9. For complex reorderings, consider rebuilding the map
    // 10. IndexMap maintains insertion order; swap_indices modifies it
    // 11. get_full() returns index position alongside key and value
    // 12. IndexMap provides both key-based and position-based access
}

Key insight: swap_indices enables efficient reordering of IndexMap entries by directly manipulating the internal index structure. The key insight is that IndexMap stores key-value pairs in a Vec (for iteration order) and maintains a hash table mapping keys to positions. When swap_indices(i, j) is called, it swaps the entries at those positions in the Vec and updates the hash table indices—keys themselves are never invalidated or moved in memory. This makes swap_indices an O(1) operation suitable for implementing priority-based ordering, LRU cache access patterns, or any scenario where you need to reorder entries without losing key validity. For complex reorderings (like full sorting), consider extracting, sorting, and rebuilding rather than multiple individual swaps.

How does indexmap::map::IndexMap::swap_indices reorder entries without invalidating keys?