# Index Map
A map with automatically generated `usize`s as keys. It supports
[_most_](#method-exclusions) of the methods present on the standard library
[`HashMap`](https://doc.rust-lang.org/std/collections/struct.HashMap.html).
If you need a generic key-value pair, with user defined keys, this is
not the crate for you. It is only meant to be used for things that
require automatically generated keys.
## Features
- It automatically generates (and recycles) unique indices as keys,
- Compatible with `#[no_std]` but requires an allocator.
- Doesn't allocate until first value is inserted.
- Values are stored in contiguous memory locations.
- 0 unsafe blocks
## Performance
Due to its simplicity nature, it performs better than `HashMap`.
| insert | 40,057 | 75,381 | -35,324 | -46.86% | 1.88x |
| grow_insert | 12,553 | 100,530 | -87,977 | -87.51% | 8.01x |
| insert_erase | 9,572 | 12,370 | -2,798 | -22.62% | 1.29x |
| lookup | 1,491 | 24,253 | -22,762 | -93.85% | 16.27x |
| lookup_fail | 1.289 | 2.092 | -0.8 | -38.38% | 1.62x |
| bench_iter | 1,812 | 1,888 | -76 | -4.03% | 1.04x |
| clone_small | 120.30 | 163.70 | -43.4 | -26.51% | 1.36x |
| clone_large | 9,635 | 13,041 | -34,06 | -26.12% | 1.35x |
The benchmarks performed here are the same as present in the hashbrown
repo: [bench.rs](https://github.com/rust-lang/hashbrown/blob/master/benches/bench.rs)
## Usage
Anything than needs to have some unique generated id associated with it
is the perfect use case for this library.
An example could be maintaining a process table.
```rust
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);
}
```
## Method Exclusions
- nightly only/unstable
- hasher based functions - the internal structure is based on a `Vec`
and so hashes are not needed.
- [`entry()`](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.entry) -
Although all the methods for `OccupiedEntry` are possible, fundamentally,
keys are automatically generated, and so the methods based on
`VacantEntry` are not possible.
- [`Extend`](https://doc.rust-lang.org/std/iter/trait.Extend.html) &
[`FromIterator`](https://doc.rust-lang.org/std/iter/trait.FromIterator.html) -
It can't take key-value pairs like `HashMap` because of the reason
mentioned above, and it can't return the keys for values inserted.
## Contribution
If you find any bugs or issues, or you want some feature added, feel
free to open an [issue](https://github.com/Lutetium-Vanadium/index-map/issues/new)
or a [pull request](https://github.com/Lutetium-Vanadium/index-map/compare).