pub struct SortedIndexMultiMap<I: Idx, K, V> {
items: IndexVec<I, (K, V)>,
idx_sorted_by_item_key: Vec<I>,
}
Expand description
An indexed multi-map that preserves insertion order while permitting both O(log n) lookup of an item by key and O(1) lookup by index.
This data structure is a hybrid of an IndexVec
and a SortedMap
. Like IndexVec
,
SortedIndexMultiMap
assigns a typed index to each item while preserving insertion order.
Like SortedMap
, SortedIndexMultiMap
has efficient lookup of items by key. However, this
is accomplished by sorting an array of item indices instead of the items themselves.
Unlike SortedMap
, this data structure can hold multiple equivalent items at once, so the
get_by_key
method and its variants return an iterator instead of an Option
. Equivalent
items will be yielded in insertion order.
Unlike a general-purpose map like BTreeSet
or HashSet
, SortedMap
and
SortedIndexMultiMap
require O(n) time to insert a single item. This is because we may need
to insert into the middle of the sorted array. Users should avoid mutating this data structure
in-place.
Fields§
§items: IndexVec<I, (K, V)>
The elements of the map in insertion order.
idx_sorted_by_item_key: Vec<I>
Indices of the items in the set, sorted by the item’s key.
Implementations§
source§impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V>
impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V>
pub fn new() -> Self
pub fn len(&self) -> usize
pub fn is_empty(&self) -> bool
sourcepub fn into_iter(self) -> impl DoubleEndedIterator<Item = (K, V)>
pub fn into_iter(self) -> impl DoubleEndedIterator<Item = (K, V)>
Returns an iterator over the items in the map in insertion order.
sourcepub fn into_iter_enumerated(
self,
) -> impl DoubleEndedIterator<Item = (I, (K, V))>
pub fn into_iter_enumerated( self, ) -> impl DoubleEndedIterator<Item = (I, (K, V))>
Returns an iterator over the items in the map in insertion order along with their indices.
sourcepub fn iter(&self) -> impl '_ + DoubleEndedIterator<Item = (&K, &V)>
pub fn iter(&self) -> impl '_ + DoubleEndedIterator<Item = (&K, &V)>
Returns an iterator over the items in the map in insertion order.
sourcepub fn iter_enumerated(
&self,
) -> impl '_ + DoubleEndedIterator<Item = (I, (&K, &V))>
pub fn iter_enumerated( &self, ) -> impl '_ + DoubleEndedIterator<Item = (I, (&K, &V))>
Returns an iterator over the items in the map in insertion order along with their indices.
sourcepub fn get_by_key(&self, key: K) -> impl Iterator<Item = &V> + '_
pub fn get_by_key(&self, key: K) -> impl Iterator<Item = &V> + '_
Returns an iterator over the items in the map that are equal to key
.
If there are multiple items that are equivalent to key
, they will be yielded in
insertion order.
sourcepub fn get_by_key_enumerated(
&self,
key: K,
) -> impl Iterator<Item = (I, &V)> + '_
pub fn get_by_key_enumerated( &self, key: K, ) -> impl Iterator<Item = (I, &V)> + '_
Returns an iterator over the items in the map that are equal to key
along with their
indices.
If there are multiple items that are equivalent to key
, they will be yielded in
insertion order.
pub fn contains_key(&self, key: K) -> bool
Trait Implementations§
source§impl<I: Clone + Idx, K: Clone, V: Clone> Clone for SortedIndexMultiMap<I, K, V>
impl<I: Clone + Idx, K: Clone, V: Clone> Clone for SortedIndexMultiMap<I, K, V>
source§fn clone(&self) -> SortedIndexMultiMap<I, K, V>
fn clone(&self) -> SortedIndexMultiMap<I, K, V>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V>
impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V>
source§impl<I: Idx, K, V> Hash for SortedIndexMultiMap<I, K, V>
impl<I: Idx, K, V> Hash for SortedIndexMultiMap<I, K, V>
source§impl<I: Idx, K, V, C> HashStable<C> for SortedIndexMultiMap<I, K, V>where
K: HashStable<C>,
V: HashStable<C>,
impl<I: Idx, K, V, C> HashStable<C> for SortedIndexMultiMap<I, K, V>where
K: HashStable<C>,
V: HashStable<C>,
fn hash_stable(&self, ctx: &mut C, hasher: &mut StableHasher)
source§impl<I: Idx, K, V> Index<I> for SortedIndexMultiMap<I, K, V>
impl<I: Idx, K, V> Index<I> for SortedIndexMultiMap<I, K, V>
impl<I: Idx, K: Eq, V: Eq> Eq for SortedIndexMultiMap<I, K, V>
Auto Trait Implementations§
impl<I, K, V> Freeze for SortedIndexMultiMap<I, K, V>
impl<I, K, V> RefUnwindSafe for SortedIndexMultiMap<I, K, V>
impl<I, K, V> Send for SortedIndexMultiMap<I, K, V>
impl<I, K, V> Sync for SortedIndexMultiMap<I, K, V>
impl<I, K, V> Unpin for SortedIndexMultiMap<I, K, V>
impl<I, K, V> UnwindSafe for SortedIndexMultiMap<I, K, V>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§unsafe fn clone_to_uninit(&self, dst: *mut T)
unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key
and return true
if they are equal.source§impl<T> Instrument for T
impl<T> Instrument for T
source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T> IntoEither for T
impl<T> IntoEither for T
source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§impl<T> WithSubscriber for T
impl<T> WithSubscriber for T
source§fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
source§fn with_current_subscriber(self) -> WithDispatch<Self>
fn with_current_subscriber(self) -> WithDispatch<Self>
impl<'a, T> Captures<'a> for Twhere
T: ?Sized,
Layout§
Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...)
attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.
Size: 48 bytes