Index Map

A map with automatically generated usizes as keys. It supports most of the methods present on the standard library HashMap.

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.

| name | IndexMap [ns/iter] | HashMap [ns/iter] | diff [ns/iter] | diff % | speedup | | ------------ | ------------------ | ----------------- | -------------- | ------- | ------- | | insert | 40,057 | 75,381 | -35,324 | -46.86% | 1.88x | | growinsert | 12,553 | 100,530 | -87,977 | -87.51% | 8.01x | | inserterase | 9,572 | 12,370 | -2,798 | -22.62% | 1.29x | | lookup | 1,491 | 24,253 | -22,762 | -93.85% | 16.27x | | lookupfail | 1.289 | 2.092 | -0.8 | -38.38% | 1.62x | | benchiter | 1,812 | 1,888 | -76 | -4.03% | 1.04x | | clonesmall | 120.30 | 163.70 | -43.4 | -26.51% | 1.36x | | clonelarge | 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

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 = processtable.insert("vim".tostring()); // ^^^----------------------------------------------------------. let cargo = processtable.insert("cargo".tostring()); // | // ^^^^^--------------------------------------------------------. let rls = processtable.insert("rust-analyser".tostring()); // | // ^^^----------------------------------------------------------| // | // Unique numbers representing each process <------------------'

// Check for a specific one. if !processtable.containskey(6) { println!("Invalid PID 6}"); }

// cargo finished running, remove it process_table.remove(cargo);

// Look up the values associated with some keys. let tofind = [2, 4]; for &pid in &tofind { 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() - Although all the methods for OccupiedEntry are possible, fundamentally, keys are automatically generated, and so the methods based on VacantEntry are not possible.

• Extend & FromIterator - 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 or a pull request.