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>

source

pub fn new() -> Self

source

pub fn len(&self) -> usize

source

pub fn is_empty(&self) -> bool

source

pub fn into_iter(self) -> impl DoubleEndedIterator<Item = (K, V)>

Returns an iterator over the items in the map in insertion order.

source

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.

source

pub fn iter(&self) -> impl '_ + DoubleEndedIterator<Item = (&K, &V)>

Returns an iterator over the items in the map in insertion order.

source

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.

source

pub fn get(&self, idx: I) -> Option<&(K, V)>

Returns the item in the map with the given index.

source

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.

source

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.

source

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>

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<I: Debug + Idx, K: Debug, V: Debug> Debug for SortedIndexMultiMap<I, K, V>

source§

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

Formats the value using the given formatter. Read more
source§

impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V>

source§

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

Creates a value from an iterator. Read more
source§

impl<I: Idx, K, V> Hash for SortedIndexMultiMap<I, K, V>
where K: Hash, V: Hash,

source§

fn hash<H: Hasher>(&self, hasher: &mut H)

Feeds this value into the given Hasher. Read more
1.3.0 · source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
source§

impl<I: Idx, K, V, C> HashStable<C> for SortedIndexMultiMap<I, K, V>
where K: HashStable<C>, V: HashStable<C>,

source§

fn hash_stable(&self, ctx: &mut C, hasher: &mut StableHasher)

source§

impl<I: Idx, K, V> Index<I> for SortedIndexMultiMap<I, K, V>

source§

type Output = V

The returned type after indexing.
source§

fn index(&self, idx: I) -> &Self::Output

Performs the indexing (container[index]) operation. Read more
source§

impl<I: Idx, K: PartialEq, V: PartialEq> PartialEq for SortedIndexMultiMap<I, K, V>

source§

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

Tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

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>
where K: Send, V: Send, I: Send,

§

impl<I, K, V> Sync for SortedIndexMultiMap<I, K, V>
where I: Sync, K: Sync, V: Sync,

§

impl<I, K, V> Unpin for SortedIndexMultiMap<I, K, V>
where I: Unpin, K: Unpin, V: Unpin,

§

impl<I, K, V> UnwindSafe for SortedIndexMultiMap<I, K, V>
where I: UnwindSafe, K: UnwindSafe, V: UnwindSafe,

Blanket Implementations§

source§

impl<T> Aligned for T

source§

const ALIGN: Alignment = const ALIGN: Alignment = Alignment::of::<Self>();

Alignment of Self.
source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> IntoEither for T

source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts 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 more
source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts 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 more
source§

impl<T> ToOwned for T
where T: Clone,

source§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

impl<'a, T> Captures<'a> for T
where 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