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 aSlotMap
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"]);