Crate index_map

A map with automatically generated usizes 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.

IndexMap

A map of usize to value, which allows efficient O(1) inserts, O(1) indexing and O(1) removal.

IntoIter

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.

ValuesMut

A mutable iterator over the values of a IndexMap.