Struct rustc_data_structures::sorted_map::SortedIndexMultiMap

pub struct SortedIndexMultiMap<I: Idx, K, V> {
    items: IndexVec<I, (K, V)>,
    idx_sorted_by_item_key: Vec<I>,
}

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

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

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

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

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.

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

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

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.

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

Returns the item in the map with the given index.

pub fn get_by_key<Q: 'a + ?Sized, 'a>(
    &'a self,
    key: &Q
) -> impl 'a + Iterator<Item = &'a V> where
    Q: Ord,
    K: Borrow<Q>, 

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.

pub fn get_by_key_enumerated<Q: ?Sized>(
    &self,
    key: &Q
) -> impl '_ + Iterator<Item = (I, &V)> where
    Q: Ord,
    K: Borrow<Q>, 

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(in sorted_map::index_map) fn binary_search_idx<Q: ?Sized>(
    &self,
    key: &Q
) -> Result<usize, usize> where
    Q: Ord,
    K: Borrow<Q>, 

pub(in sorted_map::index_map) fn find_lower_bound<Q: ?Sized>(
    &self,
    key: &Q,
    initial: usize
) -> usize where
    Q: Ord,
    K: Borrow<Q>, 

Returns the index into the idx_sorted_by_item_key array of the first item equal to key.

initial must be an index into that same array for an item that is equal to key.

pub(in sorted_map::index_map) fn find_upper_bound<Q: ?Sized>(
    &self,
    key: &Q,
    initial: usize
) -> usize where
    Q: Ord,
    K: Borrow<Q>, 

Returns the index into the idx_sorted_by_item_key array of the first item greater than key, or self.len() if no such item exists.

initial must be an index into that same array for an item that is equal to key.

pub(in sorted_map::index_map) fn idxs_to_items_enumerated<'a>(
    &'a self,
    idxs: &'a [I]
) -> impl 'a + Iterator<Item = (I, &'a V)>

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

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

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

Creates a value from an iterator.

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

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

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

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

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

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.