Expand description
A map with automatically generated usize
s as keys.
§Usage
use index_map::IndexMap;
let mut process_table = IndexMap::new();
// Create some processes
// Unlike HashMap, insert only takes a value, and returns the key.
let vim = process_table.insert("vim".to_string());
// ^^^----------------------------------------------------------.
let cargo = process_table.insert("cargo".to_string()); // |
// ^^^^^--------------------------------------------------------|
let rls = process_table.insert("rust-analyser".to_string()); // |
// ^^^----------------------------------------------------------|
// |
// Unique numbers representing each process <------------------'
// Check for a specific one.
if !process_table.contains_key(6) {
println!("Invalid PID 6");
}
// cargo finished running, remove it
process_table.remove(cargo);
// Look up the values associated with some keys.
let to_find = [2, 4];
for &pid in &to_find {
match process_table.get(pid) {
Some(process) => println!("{}: {}", pid, process),
None => println!("{} not found", pid)
}
}
// Look up the value for a key (will panic if the key is not found).
println!("PID 0 process name: {}", process_table[0]);
// Iterate over everything.
for (pid, process) in &process_table {
println!("{}: \"{}\"", pid, process);
}
§How it works
It internally is based on a Vec
, where each element either stores a value, or stores the index
of the next free element. Since it accommodates for empty elements in between, it can perform
O(1)* inserts and O(1) removals from any index. The “free” indices essentially make a singly
linked list.
* amortized similar to Vec::push()
(triggers a resize when len()
==
capacity()
)
Take the following example:
*
represents an element
-
represents no index (end of the linked list)
<int>
represents the index of the next free element
Assuming there are already 3 elements,
Initial State:
.---.---.---.
| * | * | * | head - None
'---'---'---'
0 1 2
Op - remove(1)
State:
.---.---.---.
| * | - | * |
'---'---'---'
^-- head [ 1 ]
Op - remove(2)
State:
```text
.---.---.---.
| * | - | 1 |
'---'---'---'
^-- head [ 2 ]
Op - insert
State:
.---.---.---.
| * | - | * |
'---'---'---'
^-- head [ 1 ]
Structs§
- Drain
- A draining iterator over the entries of a
IndexMap
. - Index
Map - A map of
usize
to value, which allows efficient O(1) inserts, O(1) indexing and O(1) removal. - Into
Iter - An owning iterator over the entries of a
IndexMap
. - Iter
- An iterator over the entries of a
IndexMap
. - IterMut
- A mutable iterator over the entries of a
IndexMap
. - Keys
- An iterator over the keys of a
IndexMap
. - Values
- An iterator over the values of a
IndexMap
. - Values
Mut - A mutable iterator over the values of a
IndexMap
.