What are the trade-offs between indexmap::IndexMap::get_index_of and get for index vs key lookups?
IndexMap::get performs a hash-based lookup with O(1) average complexity by key, while get_index_of finds the index position of a key in the insertion order with O(1) average complexityâboth are fast lookups, but they return different results: get returns a reference to the value, while get_index_of returns the index position of the key-value pair. The trade-off is between direct value access (get) and positional information (get_index_of), with the latter enabling index-based operations like iteration order and position-aware mutations.
Basic get Usage
use indexmap::IndexMap;
fn basic_get() {
let mut map = IndexMap::new();
map.insert("apple", 1);
map.insert("banana", 2);
map.insert("cherry", 3);
// get: Retrieve value by key (O(1) average)
let value = map.get("banana");
println!("Value: {:?}", value); // Some(&2)
// Returns None if key doesn't exist
let missing = map.get("durian");
println!("Missing: {:?}", missing); // None
// get_mut: Get mutable reference to value
if let Some(value) = map.get_mut("banana") {
*value *= 10;
}
println!("Modified: {:?}", map.get("banana")); // Some(&20)
}get returns Option<&V>âa reference to the value if found.
Basic get_index_of Usage
use indexmap::IndexMap;
fn basic_get_index_of() {
let mut map = IndexMap::new();
map.insert("apple", 1);
map.insert("banana", 2);
map.insert("cherry", 3);
// get_index_of: Find position of key (O(1) average)
let index = map.get_index_of("banana");
println!("Index: {:?}", index); // Some(1)
// Returns None if key doesn't exist
let missing = map.get_index_of("durian");
println!("Missing: {:?}", missing); // None
// Use the index for other operations
if let Some(idx) = map.get_index_of("banana") {
// Get both key and value by index
let (key, value) = map.get_index(idx).unwrap();
println!("Key: {}, Value: {}", key, value); // Key: banana, Value: 2
}
}get_index_of returns Option<usize>âthe position in insertion order.
The Return Type Difference
use indexmap::IndexMap;
fn return_types() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// get: Returns value reference
// Option<&V>
let value: Option<&i32> = map.get("a");
match value {
Some(v) => println!("Value: {}", v),
None => println!("Not found"),
}
// get_index_of: Returns index position
// Option<usize>
let position: Option<usize> = map.get_index_of("a");
match position {
Some(idx) => {
println!("Position: {}", idx);
// Now need to call get_index to get value
let (k, v) = map.get_index(idx).unwrap();
println!("Key: {}, Value: {}", k, v);
}
None => println!("Not found"),
}
// If you just need the value: use get
// If you need position: use get_index_of
// If you need both: get_index_of + get_index
}get directly gives the value; get_index_of gives position that can be used for further operations.
Using Index for Additional Operations
use indexmap::IndexMap;
fn index_operations() {
let mut map = IndexMap::new();
map.insert("first", 1);
map.insert("second", 2);
map.insert("third", 3);
// get_index_of enables position-based operations
if let Some(idx) = map.get_index_of("second") {
// Remove by index (preserves order of remaining)
let (key, value) = map.remove_index(idx).unwrap();
println!("Removed: {} -> {}", key, value);
// Insert at specific position
map.insert_before(idx, "inserted", 100);
// Or after specific position
// map.insert_after(idx, "after", 200);
}
// Swap positions
// map.swap_indices(0, 2);
// All these operations require knowing the index
// get_index_of provides that index from a key
}get_index_of enables positional mutations that get doesn't support.
Complexity Analysis
use indexmap::IndexMap;
fn complexity() {
let mut map = IndexMap::new();
for i in 0..1_000_000 {
map.insert(format!("key{}", i), i);
}
// Both operations are O(1) average
// But they have different constant factors
// get:
// 1. Hash the key
// 2. Look up in hash table
// 3. Return value reference
// get_index_of:
// 1. Hash the key
// 2. Look up in hash table
// 3. Return stored index
// Both use the same hash table lookup
// The difference is what's stored and returned
// get_index is O(1) - direct array access
// get_index_of is O(1) - hash table lookup
// To get value from index:
// map.get_index(idx) is O(1)
// So: get_index_of + get_index = get + index lookup
// If you need index AND value, use get_index_of
// If you only need value, use get
}Both are O(1), but get is simpler when you only need the value.
When to Use Each
use indexmap::IndexMap;
fn when_to_use() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Use get when:
// 1. You only need the value
let value = map.get("a");
// 2. Checking existence
if map.get("key").is_some() {
println!("Key exists");
}
// 3. Getting mutable reference
if let Some(v) = map.get_mut("a") {
*v += 1;
}
// Use get_index_of when:
// 1. You need the position
if let Some(idx) = map.get_index_of("b") {
println!("Position: {}", idx);
}
// 2. You need to modify position (remove, insert before/after)
if let Some(idx) = map.get_index_of("b") {
map.remove_index(idx);
}
// 3. You need both key and value from position
if let Some(idx) = map.get_index_of("a") {
let (k, v) = map.get_index(idx).unwrap();
println!("Key: {}, Value: {}", k, v);
}
// 4. Iterating from a specific position
if let Some(idx) = map.get_index_of("b") {
for (_, (key, value)) in map.iter().enumerate() {
// Use position information
}
}
}Use get for value access; use get_index_of for positional operations.
Combination Pattern
use indexmap::IndexMap;
fn combination_pattern() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Common pattern: get_index_of + get_index
// When you need key, value, and position
fn find_entry(map: &IndexMap<&str, i32>, key: &str) -> Option<(usize, &str, i32)> {
map.get_index_of(key).map(|idx| {
let (k, v) = map.get_index(idx).unwrap();
(idx, *k, *v)
})
}
if let Some((idx, key, value)) = find_entry(&map, "b") {
println!("Index: {}, Key: {}, Value: {}", idx, key, value);
}
// Alternative: just use iter and position
// But that's O(n) instead of O(1)
fn find_entry_slow(map: &IndexMap<&str, i32>, key: &str) -> Option<(usize, &str, i32)> {
map.iter()
.enumerate()
.find(|(_, (k, _))| *k == key)
.map(|(idx, (k, v))| (idx, *k, *v))
}
// This is O(n)!
}get_index_of provides O(1) position lookup; iterating to find position is O(n).
Iteration and Position
use indexmap::IndexMap;
fn iteration_position() {
let mut map = IndexMap::new();
map.insert("first", 1);
map.insert("second", 2);
map.insert("third", 3);
// IndexMap preserves insertion order
// get_index_of tells you position in that order
for (key, value) in &map {
let idx = map.get_index_of(key).unwrap();
println!("Index {}: {} -> {}", idx, key, value);
}
// This is efficient because get_index_of is O(1)
// The position is stored in the hash table
// Contrast with HashMap:
// - No order preservation
// - No position queries
// - Can't remove "first" inserted element specifically
}Index positions enable order-aware operations that regular HashMap doesn't support.
Removal Differences
use indexmap::IndexMap;
fn removal_operations() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
// Remove by key (like HashMap)
let removed = map.remove("b"); // Returns Option<V>
println!("Removed: {:?}", removed); // Some(2)
// After remove, order shifts:
// "a" at index 0
// "c" at index 1 (was 2)
// "d" at index 2 (was 3)
let mut map2 = IndexMap::new();
map2.insert("a", 1);
map2.insert("b", 2);
map2.insert("c", 3);
map2.insert("d", 4);
// Remove by index (preserves remaining order)
if let Some(idx) = map2.get_index_of("b") {
let (key, value) = map2.remove_index(idx); // Returns Option<(K, V)>
println!("Removed by index: {} -> {}", key.unwrap(), value.unwrap());
}
// remove_index preserves order of remaining elements
// It's implemented as a swap with last element + pop
// This is O(1) but changes indices of swapped elements
// shift_remove_index is O(n) but keeps all other indices stable
// Use when you need stable indices after removal
}get_index_of enables index-based removal which has different behavior than key-based removal.
Insert at Position
use indexmap::IndexMap;
fn insert_at_position() {
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("c", 3);
// Regular insert puts at end
map.insert("d", 4);
// Order: a, c, d
// Insert at specific position
if let Some(idx) = map.get_index_of("c") {
map.insert_before(idx, "b", 2);
}
// Order: a, b, c, d
// insert_before and insert_after require knowing the position
// get_index_of provides that position
// Regular insert always appends to end
// insert_before/insert_after insert at specific positions
// This is unique to IndexMap - HashMap has no concept of position
}Position-based insertion requires get_index_of to find the insertion point.
Performance Characteristics
use indexmap::IndexMap;
fn performance_characteristics() {
// Both get and get_index_of are O(1) average
// But they have different constant factors
// get:
// - Hash key
// - Probe hash table
// - Return value pointer
// Total: 1 hash + 1-2 memory accesses
// get_index_of:
// - Hash key
// - Probe hash table
// - Return stored index
// Total: 1 hash + 1-2 memory accesses
// get_index (from index):
// - Direct array access
// Total: 1 memory access
// So get_index_of + get_index = 2 operations
// While get = 1 operation
// Use get if you only need value
// Use get_index_of if you need position
// Use combination if you need both
let mut map = IndexMap::new();
for i in 0..1000 {
map.insert(i, i * 10);
}
// Scenario 1: Just need value
// Use get (faster - 1 lookup)
let _ = map.get(&500);
// Scenario 2: Need position
// Use get_index_of (only option)
let _ = map.get_index_of(&500);
// Scenario 3: Need both key and value from position
// Use get_index_of + get_index (2 lookups)
if let Some(idx) = map.get_index_of(&500) {
let (k, v) = map.get_index(idx).unwrap();
}
// Scenario 4: Need key and value, don't need position
// Just iterate with .iter()
for (k, v) in &map {
// Direct iteration, no lookups
}
}Choose based on what information you need: value, position, or both.
Comparison Table
use indexmap::IndexMap;
fn comparison_table() {
// | Method | Input | Returns | Complexity | Use Case |
// |--------|-------|---------|------------|----------|
// | get | Key | Option<&V> | O(1) avg | Get value |
// | get_mut | Key | Option<&mut V> | O(1) avg | Modify value |
// | get_index_of | Key | Option<usize> | O(1) avg | Get position |
// | get_index | usize | Option<(&K, &V)> | O(1) | Get key-value by position |
// | get_index_mut | usize | Option<(&K, &mut V)> | O(1) | Modify by position |
let mut map = IndexMap::new();
map.insert("a", 1);
map.insert("b", 2);
// All these work together:
// Key -> Value (direct)
let v = map.get("a");
// Key -> Index -> Key-Value (two step)
if let Some(idx) = map.get_index_of("a") {
let (k, v) = map.get_index(idx).unwrap();
}
// Index -> Key-Value (direct)
let kv = map.get_index(0);
// None of these have equivalents in HashMap
// HashMap only has get (by key)
}IndexMap provides both key-based and position-based access; HashMap only provides key-based.
Memory Layout
use indexmap::IndexMap;
fn memory_layout() {
// IndexMap stores:
// 1. Hash table (key -> index mapping)
// 2. Dense array of (key, value) pairs
// This is why:
// - get_index_of is O(1): hash table stores indices
// - get_index is O(1): direct array access
// - get is O(1): hash table lookup + offset to value
// The index is stored alongside the hash table entry
// So get_index_of doesn't need to search the array
// Memory overhead vs HashMap:
// - HashMap: hash table + (key, value) entries
// - IndexMap: hash table with indices + (key, value) array
// Extra: indices in hash table entries
// But benefits:
// - Order preservation
// - Position queries
// - Index-based operations
// - Efficient iteration (dense array)
}The additional memory for indices enables position queries.
Practical Example: Ordered Processing
use indexmap::IndexMap;
fn ordered_processing() {
let mut map = IndexMap::new();
// Insert in priority order
map.insert("critical", 1);
map.insert("high", 2);
map.insert("medium", 3);
map.insert("low", 4);
// Process in order (IndexMap preserves insertion order)
for (key, value) in &map {
println!("{}: {}", key, value);
}
// Find position of specific priority
if let Some(idx) = map.get_index_of("medium") {
// All priorities before this are higher
// All priorities after are lower
// Can check relative position
if idx == 0 {
println!("First priority");
} else if idx == map.len() - 1 {
println!("Last priority");
} else {
println!("Middle priority at index {}", idx);
}
}
// This pattern is useful for:
// - Ordered configuration
// - Priority queues
// - Dependency ordering
// - Any ordered semantic structure
}Order preservation combined with position queries enables ordered semantic processing.
Practical Example: Undo/Redo
use indexmap::IndexMap;
fn undo_redo_example() {
// Undo system where you need to:
// 1. Track operations in order
// 2. Find position of specific operations
// 3. Remove operations by position
let mut operations: IndexMap<String, fn() -> ()> = IndexMap::new();
// Register operations in order
// operations.insert("op1", func1);
// operations.insert("op2", func2);
// operations.insert("op3", func3);
// Find position of operation to undo
// if let Some(idx) = operations.get_index_of("op2") {
// // Remove and undo
// operations.remove_index(idx);
// }
// Insert new operation at specific position
// if let Some(idx) = operations.get_index_of("op1") {
// operations.insert_after(idx, "new_op", new_func);
// }
// Without get_index_of, you'd have to:
// 1. Iterate to find position (O(n))
// 2. Use two separate structures (HashMap + Vec)
}get_index_of enables efficient position-based operations on an ordered map.
Synthesis
Quick reference:
| Operation | Method | Complexity | When to Use |
|---|---|---|---|
| Get value by key | get |
O(1) | Just need value |
| Get position of key | get_index_of |
O(1) | Need position |
| Get key-value by index | get_index |
O(1) | Have position, need entry |
| Remove by key | remove |
O(1) | Have key |
| Remove by position | remove_index |
O(1) | Have position |
Decision guide:
// Need value only?
map.get("key"); // Use get
// Need position only?
map.get_index_of("key"); // Use get_index_of
// Need both key and value (but not position)?
map.iter().find(|(k, _)| *k == "key"); // Or use get + iter if just value
// Need position to modify order (remove at, insert before)?
if let Some(idx) = map.get_index_of("key") {
map.remove_index(idx);
// or
map.insert_before(idx, "new_key", value);
}Key insight: The trade-off isn't about performanceâboth get and get_index_of are O(1)âit's about what information you need. get returns the value directly, which is what you need most often. get_index_of returns the position, which enables all the position-aware operations that make IndexMap unique: removing by index, inserting at specific positions, swapping entries, and reasoning about order. The position is stored in the hash table, so get_index_of is essentially free once you've done the hash lookup. The common pattern is using get_index_of to find a position, then get_index, remove_index, or insert_before/after to operate on that position. This combination gives you ordered-map semanticsâHashMap speed with Vec-like positional operationsâthat neither HashMap nor Vec alone provides.