SharedVec    

[SharedVec] is a fast but limited ordered collection for storing values of a single type.

What is a [SharedVec]?

[SharedVec] is a fast and ordered collection, similar to [Vec], onto which values can be pushed. In contrast to a [Vec], a [SharedVec] allows pushing values through a shared reference. Pushing values is an O(1) operation and will never relocate previously pushed values, i.e., previous values remain at a stable address in memory. This enables safe pushing through a shared reference.

When pushing a value, a [SharedVec] returns a shared reference to the value in addition to a key. This key does not borrow from the [SharedVec] and can be used to retrieve the value in O(1). In addition, given an exclusive reference to the [SharedVec], the key can be used to obtain an exclusive reference to the value in O(1). Every key corresponds to an index indicating the position of the value in the [SharedVec]. Values can also be accessed by their index in O(log n). Iterating over a [SharedVec] or converting it to a [Vec] will also preserve the order in which values have been pushed onto the [SharedVec].

Here is a list of similar data structures and their differences:

• A TypedArena does not provide a key and returns an exclusive reference to a value inserted through a shared reference. A key is useful because it exists independently of the [SharedVec] (it does not borrow). It can thus be passed around more freely than a reference and can also be meaningfully serialized (for details see below).
• A Slab and a SlotMap cannot be mutated trough a shared reference. If mutation through a shared reference is not required, you may want to consider those as they are generally much more flexible.

Serialization

Using the serde feature flag, a [SharedVec] and its keys can be serialized with Serde.

A [SharedVec] storing values of type T is serialized as a sequence of type T, just as a [Vec] is, and keys are serialized as an index into this sequence. This enables external tools to simply treat keys as indices into the serialized sequence. Using a previously serialized and then deserialized key for accessing a value without also serializing and then deserializing the corresponding [SharedVec] is an O(log n) operation (just as accessing by index).

This exact serialization behavior is considered part of the stability guarantees.

Example

# use sharedvec::*;
let vegetables = SharedVec::<&'static str>::new();

let (cucumber_key, cucumber) = vegetables.push("Cucumber");
let (paprika_key, paprika) = vegetables.push("Paprika");

assert_eq!(vegetables[cucumber_key], "Cucumber");

assert_eq!(Vec::from(vegetables), vec!["Cucumber", "Paprika"]);