#container #allocations #nested #elements #stores #object #indirection-collapsing

flatvec

An indirection-collapsing container that stores all its elements in at most 2 allocations

3 releases (breaking)

0.3.0 Oct 30, 2021
0.2.0 Mar 6, 2021
0.1.0 Oct 13, 2020

#16 in #allocations

MIT/Apache

17KB
326 lines

flatvec

An indirection-collapsing container that generalizes from nested.

This crate provides a container FlatVec and two traits, IntoFlat and FromFlat. A FlatVec is parameterized on one type, and IntoFlat and FromFlat are both parameterized on two types. None of these type parameters need to be the same.

This permits collapsing indirections while also permitting minimal/zero-copy usage, as demonstrated in examples/domain_name.rs.

This interface also permits some interesting other applications, as in examples/gzip.rs.


lib.rs:

An indirection-collapsing container that generalizes nested.

A FlatVec can be used like a Vec<String> or Vec<Vec<u8>>, but with a maximum of 2 heap allocations instead of n + 1 (currently it's always 2 but that should change with 1.51).

Insertion into and retrieval from a FlatVec is mediated by two traits, IntoFlat and FromFlat, which are both parameterized on two types. The simplest way to use this crate is to impl IntoFlat<T, u8> for T and impl FromFlat<'_, T, u8> for T for some type T in your crate.

But since the interface supports a generic backing type parameter, the flattened input objects can be stored as any representation that is convenient. u8 is a reasonable default choice, but may not be quite right for your application.

Additionally, since FromFlat has a lifetime parameter, accessing the stored objects in a FlatVec can be a zero-copy operation. For example, one may flatten objects with indirections into a dense in-memory storage, then access them later via a reference-wrapping handle type. A simple example of this is in examples/domain_name.rs.

This interface is extremely powerful and essentially amounts to in-memory serialization and conversion all in one. For example, a user can construct a FlatVec that compresses all of its elements with gzip. This is not necessarily a good idea, but you can do it.

Dependencies

~255KB