sparse_set_container 1.0.0

A container based on sparse set. Stable keys, O(1) lookup, cache-friendly iterations, and no hashing.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

# Sparse Set Container
A container based on a sparse set

[![crates.io][crates.io shield]][crates.io link]
[![Documentation][docs.rs badge]][docs.rs link]

[![Download Status][shields.io download count]][crates.io link]

[crates.io shield]: https://img.shields.io/crates/v/sparse_set_container?label=latest
[crates.io link]: https://crates.io/crates/sparse_set_container
[docs.rs badge]: https://docs.rs/sparse_set_container/badge.svg?version=0.4.0
[docs.rs link]: https://docs.rs/sparse_set_container/1.0.0/sparse_set_container/
[shields.io download count]: https://img.shields.io/crates/d/sparse_set_container.svg

## Usage

Add this to your Cargo.toml:

```toml
[dependencies]
sparse_set_container = "1.0"
```

### Description

An array-like container based on sparse set implementation that allows O(1) access to elements without hashing and allows cache-friendly iterations.

| Operation | SparseSet | Vec |
| --------- | --------- | ------- |
| push      | O(1)      | O(1)    |
| lookup    | O(1)      | O(1)    |
| size/len  | O(1)      | O(1)    |
| remove    | O(n)      | O(n)    |
| swap_remove | O(1)    | O(1)    |

For iterating over the elements SparseSetContainer exposes an iterator over an internal Vec with values, which is as efficient as iterating over a Vec directly.

Differences to Vec:
- Instead of using indexes, when adding an element, it returns a lightweight key structure that can be used to access the element later
  - The key is not invalidated when elements are removed from the container
  - If the pointed-at element was removed, the key will not be pointing to any other elements, even if new elements are inserted
- There is a slight overhead in insertion/lookup/removal operations compared to Vec, though the overhead is constant
- Consumes more memory:
  - for each value `4*sizeof(usize)` bytes on top of the size of the element itself
    - (e.g. 32 bytes per element on 64-bit systems)
  - per each `2^(sizeof(usize)*8)` removals the memory consumption will also grow by `2*sizeof(usize)`
    - (e.g. 16 bytes per 18446744073709551616 elements removed on 64-bit systems)
- Many Vec operations are not supported (create an [issue on github](https://github.com/gameraccoon/sparse_set_container/issues) if you want to request one)

### When it is useful

If you want to have a Vec of your elements but also want to store indexes to it in a safe way.  
E.g. you have a list of elements in UI that the user can add and remove, but you want to refer to the elements from that list from somewhere else.

### Examples

```rust
use sparse_set_container::SparseSet;

let mut elements = SparseSet::new();
elements.push("1");
let key2 = elements.push("2");
elements.push("3");

elements.remove(key2);
elements.push("4")

if !elements.contains(key2) {
    println!("Value 2 is not in the container");
}

// Prints 1 3 4 
for v in elements.values() {
    print!("{} ", v);
}

// Prints 1 3 4 
for k in elements.keys() {
    print!("{} ", elements.get(k).unwrap());
}
```

### License

Licensed under the MIT license: http://opensource.org/licenses/MIT