Vec-collections: Sets and maps based on smallvec

Hi all,

vec-collections is a crate providing sets and maps that are backed by smallvec.

This is useful if you want to have small sets or maps that do not allocate, or larger sets with a very compact in memory representation.

Here is a small usage example:

// create a set with elements 1,2,3. Does not allocate
let x: VecSet<[u32; 4]> = vecset!{ 1, 2, 3 };
// create a set with elements 2,3,4. Does not allocate
let y: VecSet<[u32; 4]> = vecset!{ 2, 3, 4 };
// in place union of x and y. Does not allocate.
x |= y;
// create a set with elements 5,6,7. Does not allocate
let z: VecSet<[u32; 4]> = vecset!{ 5, 6, 7 };
// spills on the heap, since the result no longer fits in the
// underlying SmallVec<[u32; 4]>
x |= z;

There is some documentation about the performance and memory usage tradeoffs in the docs.

For very small sets, this is faster than any of the std collections because it does not allocate.

For large collections, it is faster than BTreeSet / BTreeMap but slightly slower than FnvHashSet / FnvHashMap.

One caveat is that since the in memory representation is just a sorted array, insertion or removal of individual elements from large collections is very slow (O(N)). If your use case requires that, you would be better off using std collections.

The interface is very similar to the std collections. Fast set operations (intersection, union etc.) are supported, including in place versions. See example above.

Cheers,

Rüdiger

7 Likes

This looks great!

By the way, if you (or anyone else) want to create another collection based on SmallVec, we've also had a request for a deque type:

2 Likes

Thanks!

Yeah, a Deque is definitely something I might do. There are lots of VecDeques in typical rust libp2p programs that very rarely exceed a few elements.

Will open an issue.