thinset 0.2.0

A data structure for sparse sets of unsigned integers that sacrifices space for speed.
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
86
87
88
89
90
91

<div align="center">
  <h1>thinset</h1>
  <p>
    <strong>A data structure optimized for sparse sets of unsigned integers.</strong>
  </p>
  <p>

[![crates.io][crates.io shield]][crates.io link]
[![Documentation][docs.rs badge]][docs.rs link]
![Rust CI][github ci badge]
[![rustc 1.0+]][Rust 1.0]
<br />
<br />
[![Dependency Status][deps.rs status]][deps.rs link]
[![Download Status][shields.io download count]][crates.io link]

  </p>
</div>

[crates.io shield]: https://img.shields.io/crates/v/thinset?label=latest
[crates.io link]: https://crates.io/crates/thinset
[docs.rs badge]: https://docs.rs/thinset/badge.svg?version=0.1.0
[docs.rs link]: https://docs.rs/thinset/0.1.0/thinset/
[github ci badge]: https://github.com/Chriscbr/thinset/actions/workflows/rust.yml/badge.svg
[rustc 1.0+]: https://img.shields.io/badge/rustc-1.0%2B-blue.svg
[Rust 1.0]: https://blog.rust-lang.org/2015/05/15/Rust-1.0.html
[deps.rs status]: https://deps.rs/repo/github/Chriscbr/thinset/status.svg
[deps.rs link]: https://deps.rs/crate/thinset/0.1.0
[shields.io download count]: https://img.shields.io/crates/d/thinset.svg

## Usage

Add this to your Cargo.toml:

```toml
[dependencies]
thinset = "0.1"
```

### Description

<!-- cargo-rdme start -->

An implementation of a set using a pair of sparse and dense arrays as backing stores.

This type of set is useful when you need to efficiently track set membership for integers
from a large universe, but the values are relatively spread apart.

The sparse set supports constant-time insertion, removal, lookups as expected.
In addition:

- Compared to the standard library's `HashSet`, clearing the set is constant-time instead of linear time.
- Compared to bitmap-based sets like the `bit-set` crate, iteration over the set is
proportional to the cardinality of the set (how many elements you have) instead of proportional to the maximum size of the set.

The main downside is that the set requires more memory than other set implementations.

The implementation is based on the paper "An efficient representation for sparse sets" (1993)
by Briggs and Torczon.

#### Examples

```rust
use thinset::SparseSet;

// Specify a maximum value for the set
let mut s: SparseSet<usize> = SparseSet::new(100);
s.insert(0);
s.insert(3);
s.insert(7);

s.remove(7);

if !s.contains(7) {
    println!("There is no 7");
}

// Print 0, 1, 3 in some order
for x in s.iter() {
    println!("{}", x);
}
```

<!-- cargo-rdme end -->

## License

Dual-licensed for compatibility with the Rust project.

Licensed under the Apache License Version 2.0: http://www.apache.org/licenses/LICENSE-2.0,
or the MIT license: http://opensource.org/licenses/MIT, at your option.