#key-value #slab #compact #linked-list #id #structure #key-index

compactmap

Compact Vec-based map that choses assigns IDs for your values on it's own. Very similar to Slab.

11 releases

Uses old Rust 2015

0.3.7 Jan 10, 2018
0.3.6 Jan 1, 2018
0.3.5 Dec 30, 2017
0.3.2 Nov 12, 2017
0.1.0 Dec 20, 2015

#2057 in Data structures

Download history 3/week @ 2024-02-19 23/week @ 2024-02-26 6/week @ 2024-03-04 7/week @ 2024-03-11 103/week @ 2024-04-01

111 downloads per month
Used in dnscache

MIT/Apache

53KB
1.5K SLoC

Compactmap - Vec-based map that uses usize as key type and maintains internal linked list for removed nodes.

You don't choose the key when inserting a new value. You can remove any entry.

Based on this post by eddyb.

The function and structure of CompactMap is almost the same as Slab apart from missing cached length and more features. If I knew about Slab earlier, CompactMap wouldn't have appeared.

TODO:

  • More thorough tests
  • Entry (is it really needed?)

License is MIT or Apache, like for Rust itself.


lib.rs:

A map-esque data structure that small integer keys for you on insertion. Key of removed entries are reused for new insertions. Underlying data is stored in a vector, keys are just indexes of that vector. The main trick is keeping in-place linked list of freed indexes for reuse.

Serde is supported. If you need pre-computed length at serialization time (for example, for bincode), use serde_ser_len feature.

If you are worried about losing strict typing advantages because of those usizes, you can use special wrapper

See also: Slab

Dependencies

~175KB