indexmapThe `indexmap` crate in Rust provides a data structure called `IndexMap` (and its set equivalent, `IndexSet`) which combines the best features of a hash map and a vector. Unlike the standard library's `HashMap`, `IndexMap` maintains the insertion order of its key-value pairs. This means when you iterate over an `IndexMap`, the elements will be yielded in the order they were first inserted, not in an arbitrary or hash-dependent order.
Key Characteristics and Features:
1. Insertion Order Preservation: This is the primary distinguishing feature. When you insert a new key-value pair, it is added to the "end" of the map's internal order. Iteration always follows this order.
2. Hybrid Data Structure: Internally, `IndexMap` uses a combination of a hash table (for `O(1)` average-case key lookups) and a `Vec` (to store the key-value pairs in insertion order and provide `O(1)` access by index).
3. Performance: It offers `O(1)` average time complexity for most common operations like insertion, lookup (`get`), and deletion (`remove`), similar to `HashMap`. However, operations that require shifting elements (like `shift_remove`) can be `O(N)`.
4. Indexed Access: Due to its `Vec` component, `IndexMap` provides methods to access elements by their integer index (`get_index`, `get_full`), which is not possible with a standard `HashMap`. This also enables efficient removal by index (`swap_remove_index`, `shift_remove_index`).
5. Use Cases: `IndexMap` is ideal when you need:
* The fast key-based lookups of a `HashMap`.
* The predictable, insertion-order iteration of a `Vec` or a `BTreeMap` (but with `O(1)` average key lookup instead of `O(log N)` for `BTreeMap`).
* To maintain a specific order of items based on their insertion sequence.
* To be able to remove items and potentially shift subsequent items to fill the gap, while preserving relative order (`shift_remove`).
Comparison:
* vs. `HashMap`: `HashMap` offers better raw performance in some scenarios where order is completely irrelevant, as `IndexMap` has a slightly higher memory footprint and overhead due to maintaining the order `Vec`. However, `IndexMap`'s `O(1)` average case is still excellent.
* vs. `BTreeMap`: `BTreeMap` also offers predictable iteration order, but it's based on sorted keys, not insertion order. Its operations are `O(log N)`, while `IndexMap` offers `O(1)` average for many operations.
* vs. `Vec<(_, _)>`: A `Vec` of tuples would maintain insertion order, but key lookups would be `O(N)`. `IndexMap` solves this by adding the `O(1)` lookup capability.
To use `indexmap`, you need to add it to your `Cargo.toml` file as a dependency.
Example Code
```rust
use indexmap::IndexMap;
fn main() {
// 1. Create a new IndexMap
let mut users: IndexMap<u32, String> = IndexMap::new();
// 2. Insert key-value pairs
// Elements are inserted in this order.
println!("\n--- Inserting elements ---");
users.insert(101, "Alice".to_string());
users.insert(103, "Charlie".to_string());
users.insert(102, "Bob".to_string());
users.insert(105, "Eve".to_string());
// If a key already exists, its value is updated, but its position in order doesn't change.
// The original order (101, 103, 102, 105) is maintained for 102.
users.insert(102, "Bobby".to_string());
// 3. Iterate over the IndexMap (order is preserved!)
println!("\n--- Iterating over users (insertion order) ---");
for (id, name) in &users {
println!("ID: {}, Name: {}", id, name);
}
// Expected output order: (101, Alice), (103, Charlie), (102, Bobby), (105, Eve)
// 4. Access elements by key (like a HashMap)
println!("\n--- Accessing by key ---");
if let Some(name) = users.get(&103) {
println!("User with ID 103 is: {}", name);
}
if let Some(name) = users.get(&999) {
println!("User with ID 999 is: {}", name); // This won't print
} else {
println!("User with ID 999 not found.");
}
// 5. Access elements by index (unique to IndexMap among map types)
println!("\n--- Accessing by index ---");
if let Some((id, name)) = users.get_index(0) {
println!("Element at index 0: ID {}, Name {}", id, name);
}
if let Some((id, name)) = users.get_index(2) {
println!("Element at index 2: ID {}, Name {}", id, name);
}
// Be careful with out-of-bounds indices, get_index returns Option
if users.get_index(100).is_none() {
println!("No element at index 100.");
}
// 6. Remove elements
// `remove` by key - maintains relative order of remaining elements, O(N)
println!("\n--- Removing user 102 (Bobby) ---");
users.remove(&102);
for (id, name) in &users {
println!("ID: {}, Name: {}", id, name);
}
// Expected order now: (101, Alice), (103, Charlie), (105, Eve)
// `shift_remove` by key - same as `remove`, just another name.
println!("\n--- Shift removing user 101 (Alice) ---");
users.shift_remove(&101);
for (id, name) in &users {
println!("ID: {}, Name: {}", id, name);
}
// Expected order now: (103, Charlie), (105, Eve)
// `swap_remove` by key - O(1) but does NOT preserve relative order of remaining elements.
// The last element (105) would swap places with the removed element (103).
println!("\n--- Swap removing user 103 (Charlie) ---");
users.swap_remove(&103);
for (id, name) in &users {
println!("ID: {}, Name: {}", id, name);
}
// Expected order now: (105, Eve) (if 105 was the only other element, no swap happens, otherwise it would have taken 103's place)
// 7. Check current size
println!("\n--- Map size ---");
println!("Current number of users: {}", users.len());
// Demonstrate `IndexSet` as well (similar principles but for unique elements only)
println!("\n--- Demonstrating IndexSet ---");
let mut numbers = indexmap::IndexSet::new();
numbers.insert(30);
numbers.insert(10);
numbers.insert(20);
numbers.insert(10); // Duplicate, will not be inserted again
println!("Numbers in insertion order:");
for num in &numbers {
println!("{}", num);
}
// Expected order: 30, 10, 20
}
```
To run this code, add the following to your `Cargo.toml`:
```toml
[dependencies]
indexmap = "2.0"
```