How does `indexmap::IndexMap::shift_insert` enable positional insertion unlike standard maps?

indexmap::IndexMap::shift_insert enables insertion at a specific index position while shifting all subsequent entries to make room—a capability impossible with standard HashMap or BTreeMap which provide no ordering guarantees, and distinct from IndexMap's regular insert which either replaces existing entries or appends to the end. This positional control allows you to maintain a specific order of entries based on application requirements, not just insertion order, enabling patterns like priority-based insertion, alphabetically sorted insertion at specific positions, or building ordered maps where entry position carries semantic meaning beyond the key-value relationship.

Standard HashMap vs IndexMap Ordering

use std::collections::HashMap;
use indexmap::IndexMap;
 
fn main() {
    // HashMap: no ordering guarantees
    let mut hashmap = HashMap::new();
    hashmap.insert("c", 3);
    hashmap.insert("a", 1);
    hashmap.insert("b", 2);
    
    println!("HashMap iteration order is undefined:");
    for (k, v) in &hashmap {
        println!("  {}: {}", k, v);  // Order varies
    }
    
    // IndexMap: preserves insertion order
    let mut indexmap = IndexMap::new();
    indexmap.insert("c", 3);
    indexmap.insert("a", 1);
    indexmap.insert("b", 2);
    
    println!("\nIndexMap preserves insertion order:");
    for (k, v) in &indexmap {
        println!("  {}: {}", k, v);  // c, a, b
    }
}

HashMap provides no ordering; IndexMap preserves insertion order by default.

Basic IndexMap Insertion

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    
    // Regular insert appends to end
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    println!("After inserts:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    
    // Insert with existing key replaces value, keeps position
    map.insert("second", 20);
    
    println!("\nAfter replacing 'second':");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // "second" stays at index 1, value changes to 20
}

Regular insert appends new entries and replaces existing entries in-place.

shift_insert at Specific Position

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("c", 3);
    map.insert("e", 5);
    
    println!("Initial state:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // Index 0: a = 1
    // Index 1: c = 3
    // Index 2: e = 5
    
    // Insert "b" at index 1, shifting c and e
    map.shift_insert(1, "b", 2);
    
    println!("\nAfter shift_insert(1, 'b', 2):");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // Index 0: a = 1
    // Index 1: b = 2
    // Index 2: c = 3
    // Index 3: e = 5
    
    // Insert "d" at index 3
    map.shift_insert(3, "d", 4);
    
    println!("\nAfter shift_insert(3, 'd', 4):");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // Index 0: a = 1
    // Index 1: b = 2
    // Index 2: c = 3
    // Index 3: d = 4
    // Index 4: e = 5
}

shift_insert inserts at the specified index, shifting all entries at that index and after to make room.

Shift Behavior Details

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("x", 10);
    map.insert("y", 20);
    map.insert("z", 30);
    
    // Insert at beginning
    map.shift_insert(0, "w", 0);
    println!("After inserting 'w' at index 0:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // w, x, y, z (all shifted right)
    
    // Insert at end (same as regular insert)
    map.shift_insert(4, "end", 100);
    println!("\nAfter inserting 'end' at index 4:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // w, x, y, z, end
    
    // Insert in middle
    map.shift_insert(2, "middle", 50);
    println!("\nAfter inserting 'middle' at index 2:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // w, x, middle, y, z, end
}

Entries at and after the insertion index are shifted right by one position.

Comparison with insert

use indexmap::IndexMap;
 
fn main() {
    let mut map1 = IndexMap::new();
    let mut map2 = IndexMap::new();
    
    // Both start the same
    map1.insert("a", 1);
    map1.insert("c", 3);
    
    map2.insert("a", 1);
    map2.insert("c", 3);
    
    // insert with new key: appends to end
    map1.insert("b", 2);
    println!("After insert('b', 2):");
    for (i, (k, v)) in map1.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // a, c, b (appended)
    
    // shift_insert: places at specific position
    map2.shift_insert(1, "b", 2);
    println!("\nAfter shift_insert(1, 'b', 2):");
    for (i, (k, v)) in map2.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // a, b, c (alphabetically ordered)
    
    // insert with existing key: replaces in place
    map1.insert("a", 10);
    println!("\nAfter insert('a', 10) on map1:");
    for (i, (k, v)) in map1.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // a stays at index 0, value changes to 10
    
    // shift_insert with existing key: moves to new position
    // Note: shift_insert with existing key behaves differently!
    // It actually panics if the key exists.
}

insert appends or replaces in-place; shift_insert inserts at a position and shifts.

Existing Key Behavior

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // shift_insert panics if key already exists
    // This would panic:
    // map.shift_insert(0, "b", 20);
    // panic: "key already exists"
    
    // To move an existing entry, use swap_indices or shift_remove + shift_insert
    let old_index = map.get_index_of("b").unwrap();  // 1
    let value = map.shift_remove("b").unwrap();
    map.shift_insert(0, "b", value);
    
    println!("After moving 'b' to front:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // b, a, c
}

shift_insert panics if the key already exists; to reposition, remove and re-insert.

Maintaining Sorted Order

use indexmap::IndexMap;
 
fn insert_sorted(map: &mut IndexMap<&str, i32>, key: &str, value: i32) {
    // Find correct position to maintain alphabetical order
    let pos = map.iter()
        .position(|(k, _)| *k > key)
        .unwrap_or(map.len());
    
    map.shift_insert(pos, key, value);
}
 
fn main() {
    let mut map = IndexMap::new();
    
    insert_sorted(&mut map, "delta", 4);
    insert_sorted(&mut map, "alpha", 1);
    insert_sorted(&mut map, "charlie", 3);
    insert_sorted(&mut map, "bravo", 2);
    
    println!("Sorted order:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // alpha, bravo, charlie, delta
}

Use shift_insert to maintain sorted order dynamically.

Priority-Based Insertion

use indexmap::IndexMap;
 
#[derive(Debug)]
struct Task {
    name: String,
    priority: u8,  // Lower number = higher priority
}
 
fn insert_by_priority(map: &mut IndexMap<String, Task>, task: Task) {
    let pos = map.iter()
        .position(|(_, t)| t.priority > task.priority)
        .unwrap_or(map.len());
    
    map.shift_insert(pos, task.name.clone(), task);
}
 
fn main() {
    let mut tasks = IndexMap::new();
    
    insert_by_priority(&mut tasks, Task { name: "email".to_string(), priority: 5 });
    insert_by_priority(&mut tasks, Task { name: "backup".to_string(), priority: 2 });
    insert_by_priority(&mut tasks, Task { name: "log".to_string(), priority: 8 });
    insert_by_priority(&mut tasks, Task { name: "critical".to_string(), priority: 1 });
    
    println!("Tasks by priority:");
    for (i, (name, task)) in tasks.iter().enumerate() {
        println!("  {}: {:?} ", i, task);
    }
    // critical (1), backup (2), email (5), log (8)
}

Position insertion enables priority queues with O(n) insertion.

Index Preservation Across Operations

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    println!("Initial indices:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    
    // Access by index
    println!("\nAccess by index:");
    println!("  map[0] = {:?}", map.get_index(0));  // Some((&"a", &1))
    println!("  map[2] = {:?}", map.get_index(2));  // Some((&"c", &3))
    
    // Indices after shift_insert
    map.shift_insert(1, "x", 10);
    
    println!("\nAfter shift_insert(1, 'x', 10):");
    println!("  map[0] = {:?}", map.get_index(0));  // "a"
    println!("  map[1] = {:?}", map.get_index(1));  // "x"
    println!("  map[2] = {:?}", map.get_index(2));  // "b"
    println!("  map[3] = {:?}", map.get_index(3));  // "c"
    println!("  map[4] = {:?}", map.get_index(4));  // "d"
    
    // Keys to indices changed
    println!("\nKey positions:");
    println!("  'a' at index {:?}", map.get_index_of("a"));  // 0
    println!("  'b' at index {:?}", map.get_index_of("b"));  // 2 (shifted)
    println!("  'c' at index {:?}", map.get_index_of("c"));  // 3 (shifted)
}

shift_insert shifts indices for entries at and after the insertion point.

Combining with shift_remove

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Move "d" from position 3 to position 0
    let value = map.shift_remove("d").unwrap();
    println!("Removed 'd': {}", value);
    
    map.shift_insert(0, "d", value);
    
    println!("\nAfter moving 'd' to front:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // d, a, b, c
    
    // Move "a" from position 1 to end
    let value = map.shift_remove("a").unwrap();
    map.shift_insert(3, "a", value);  // len is 3 after remove
    
    println!("\nAfter moving 'a' to end:");
    for (i, (k, v)) in map.iter().enumerate() {
        println!("  Index {}: {} = {}", i, k, v);
    }
    // d, b, c, a
}

Combine shift_remove and shift_insert to move entries within the map.

Performance Characteristics

use indexmap::IndexMap;
 
fn main() {
    // shift_insert is O(n) because it shifts entries
    let mut map = IndexMap::new();
    
    // Building a map by appending (O(1) per insert)
    for i in 0..1000 {
        map.insert(format!("key{}", i), i);
    }
    
    // Inserting at beginning requires shifting all entries (O(n))
    // This is slower than append
    map.shift_insert(0, "new_first".to_string(), -1);
    
    // Inserting near the end is faster (fewer shifts)
    map.shift_insert(900, "near_end".to_string(), 9000);
    
    // Regular insert at end is O(1)
    map.insert("last".to_string(), 1000);
    
    println!("Map size: {}", map.len());
    
    // For comparison, HashMap insertion is O(1) average
    // but HashMap has no ordering
}

shift_insert is O(n) due to index shifting; regular insert is O(1) amortized.

Use Case: Ordered Configuration

use indexmap::IndexMap;
 
#[derive(Debug)]
struct ConfigEntry {
    key: String,
    value: String,
    source: String,  // "default", "env", "file", "cli"
}
 
fn main() {
    let mut config: IndexMap<String, ConfigEntry> = IndexMap::new();
    
    // Default values at the beginning
    config.shift_insert(0, "port".to_string(), ConfigEntry {
        key: "port".to_string(),
        value: "8080".to_string(),
        source: "default".to_string(),
    });
    
    config.shift_insert(1, "host".to_string(), ConfigEntry {
        key: "host".to_string(),
        value: "localhost".to_string(),
        source: "default".to_string(),
    });
    
    // Environment variables override (insert before defaults)
    config.shift_insert(0, "host".to_string(), ConfigEntry {
        key: "host".to_string(),
        value: "0.0.0.0".to_string(),
        source: "env".to_string(),
    });
    
    // Config file values (insert at specific priority position)
    // This would panic since "host" already exists - need to handle conflicts
    
    // The order shows precedence for debugging
    println!("Configuration (in precedence order):");
    for (i, (key, entry)) in config.iter().enumerate() {
        println!("  {}: {} = {} (from {})", i, key, entry.value, entry.source);
    }
}

Position insertion enables priority-based ordering for configuration layers.

Use Case: Playlist Management

use indexmap::IndexMap;
 
#[derive(Debug, Clone)]
struct Song {
    title: String,
    artist: String,
}
 
fn main() {
    let mut playlist: IndexMap<String, Song> = IndexMap::new();
    
    // Add songs
    playlist.insert("song1".to_string(), Song {
        title: "First".to_string(),
        artist: "Artist A".to_string(),
    });
    playlist.insert("song2".to_string(), Song {
        title: "Second".to_string(),
        artist: "Artist B".to_string(),
    });
    playlist.insert("song3".to_string(), Song {
        title: "Third".to_string(),
        artist: "Artist C".to_string(),
    });
    
    // Insert a song at position 1 (second in playlist)
    playlist.shift_insert(1, "new_song".to_string(), Song {
        title: "New Song".to_string(),
        artist: "Artist D".to_string(),
    });
    
    // Move a song to the beginning (now playing)
    let song = playlist.shift_remove("song3").unwrap();
    playlist.shift_insert(0, "song3".to_string(), song);
    
    println!("Playlist order:");
    for (i, (id, song)) in playlist.iter().enumerate() {
        println!("  {}: {} by {}", i + 1, song.title, song.artist);
    }
}

shift_insert enables playlist reordering where position matters.

Synthesis

Method comparison:

Method	Behavior	Complexity
`insert`	Append new key, replace existing in-place	O(1) amortized
`shift_insert`	Insert at index, shift entries right	O(n)

IndexMap ordering capabilities:

Operation	Standard HashMap	BTreeMap	IndexMap
Preserves insertion order	No	No	Yes
Access by index	No	No	Yes
Insert at position	N/A	N/A	`shift_insert`
Move entry to position	N/A	N/A	`shift_remove` + `shift_insert`

Key insight: IndexMap::shift_insert provides positional control that standard maps fundamentally cannot offer—HashMap has no ordering, and BTreeMap maintains key-based ordering with no application control. This enables patterns where entry position carries semantic meaning: priority queues where position indicates processing order, configuration layers where earlier entries take precedence, playlists where position is the primary concern, and any scenario where you need to maintain a specific order independent of key sorting. The cost is O(n) for shifting, acceptable for moderate sizes or when position changes are infrequent. The method panics if the key already exists, requiring shift_remove first to reposition entries, which ensures no duplicate keys and maintains index consistency. Use shift_insert when position matters; use regular insert when you only need key-value lookup with insertion order preservation.

How does indexmap::IndexMap::shift_insert enable positional insertion unlike standard maps?