Struct VecMap 

pub struct VecMap<K, V> { /* private fields */ }

A Vec-backed map that provides HashMap-like lookup by key.

Duplicates

Duplicates are tolerated: VecMap::insert always appends, and VecMap::get/VecMap::get_mut return the last matching entry so that later writes shadow earlier ones. This optimizes for fast insertion and construction (that might happen on the client’s application hot path), avoiding a linear scan on each insert, or a potential full re-hashing with a hashmap. Additionally, while overriding a metric or a meta definitively happens, it’s assumed to be rare enough so such that the size penalty of duplication is expected to be reasonable.

Important: note that only VecMap::get and VecMap::get_mut are duplicate-aware, so to speak. VecMap::len, VecMap::iter, and others just delegates to the underlying Vec, and won’t deduplicate.

Explicit deduplication is currently being done on-demand by VecMap::dedup. An internal flag is used to avoid undue deduplication (see VecMap::dedup). VecMap is automatically deduped before serialization.

In the future, we could trigger deduplication on other events, for example at insertion if the size is bigger than a threshold (and we haven’t deduped for x operations).

Ordering

As this is a map, iteration order is not defined nor guaranteed. In practice, iteration follows insertion order, but Self::dedup will reverse the underlying vector.

Implementations

impl<K, V> VecMap<K, V>

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

pub fn insert(&mut self, key: K, value: V)

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: ?Sized + PartialEq,

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: ?Sized + PartialEq,

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: ?Sized + PartialEq,

pub fn slow_compare(&self, other: &Self) -> bool

where K: Eq + Hash, V: PartialEq,

Compares two maps for equality, ignoring insertion order and duplicate entries (the last value for a given key wins on both sides). This allocates two intermediate HashMaps, so it’s exposed as a named method rather than PartialEq/Eq, to keep that cost visible at the call site instead of hiding it behind ==.

pub fn remove_slow<Q>(&mut self, key: &Q)

where K: Borrow<Q>, Q: ?Sized + PartialEq,

Remove all entries matching this key from the map. This method uses Vec::retain, and is thus potentially costly (like any removal in a vector-like datastructure).

pub fn iter(&self) -> Iter<'_, (K, V)>

Iterate over the element, including duplicate entries.

pub fn iter_mut(&mut self) -> IterMut<'_, (K, V)>

Iterate mutably over the elements, including duplicate entries.

pub fn len(&self) -> usize

Return the length of the underlying vector, thus including duplicate entries.

pub fn is_empty(&self) -> bool

pub fn is_deduped(&self) -> bool

Return true if the map hasn’t been extended since the last call to Self::dedup, guaranteeing that the underlying vector doesn’t have any duplicate key.

If is_deduped returns false, the map may have duplicate keys.

pub fn mark_deduped(&mut self)

Assert, without scanning, that this map holds no duplicate keys, setting the deduped flag.

For builders whose source guarantees key uniqueness (e.g. msgpack decoding, where the wire format is a map), to skip the Self::dedup pass. A later mutation re-dirties the flag.

Caution: if the source can actually contain duplicate keys, prefer Self::dedup.

pub fn clear(&mut self)

pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<'_, (K, V)>

impl<K: Eq + Hash, V> VecMap<K, V>

pub fn as_deduped_map(&self) -> DedupedVecMap<'_, K, V>

Returns a deduped map, that either borrows from self without performing any work if the map is already deduped, or dedup the entries in a new separate vec otherwise. As opposed to Self::dedup, as_deduped_map takes an immutable reference to self but might allocate. Prefer Self::dedup when applicable.

pub fn defensive_dedup(&self) -> DedupedVecMap<'_, K, V>

This is a convenience wrapper around Self::as_deduped_map used in the msgpack encoder, where we expect the map to be deduped, but call as_deduped_map as a defensive measure. If the latter had to deduplicate and allocate a new vec, we log a warning (at most once).

pub fn dedup(&mut self)

Remove entries with a duplicate key, only keeping the last one. After this, a flag is set internally, such that as long as the map isn’t extended or mutably iterated, the next Self::dedup doesn’t perform the work again.

Trait Implementations

impl<K: Clone, V: Clone> Clone for VecMap<K, V>

fn clone(&self) -> VecMap<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for VecMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for VecMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Extend<(K, V)> for VecMap<K, V>

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V> From<Vec<(K, V)>> for VecMap<K, V>

fn from(data: Vec<(K, V)>) -> Self

Converts to this type from the input type.

impl<K, V> From<VecMap<K, V>> for Vec<(K, V)>

fn from(value: VecMap<K, V>) -> Self

Converts to this type from the input type.

impl<K, V> FromIterator<(K, V)> for VecMap<K, V>

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K, V> IntoIterator for VecMap<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<(K, V)>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a VecMap<K, V>

type Item = &'a (K, V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, (K, V)>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut VecMap<K, V>

type Item = &'a mut (K, V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, (K, V)>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Serialize + Eq + Hash, V: Serialize> Serialize for VecMap<K, V>

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.