[−][src]Struct rustc_ap_rustc_data_structures::sorted_map::SortedIndexMultiMap
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.
Methods
impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V>
[src]
pub fn new() -> Self
[src]
pub fn len(&self) -> usize
[src]
pub fn is_empty(&self) -> bool
[src]
pub fn into_iter(self) -> impl DoubleEndedIterator<Item = (K, V)>
[src]
Returns an iterator over the items in the map in insertion order.
pub fn into_iter_enumerated(
self
) -> impl DoubleEndedIterator<Item = (I, (K, V))>
[src]
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)>
[src]
Returns an iterator over the items in the map in insertion order.
pub fn iter_enumerated(
&self
) -> impl '_ + DoubleEndedIterator<Item = (I, (&K, &V))>
[src]
&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)>
[src]
Returns the item in the map with the given index.
pub fn get_by_key<'a, Q: 'a + ?Sized>(
&'a self,
key: &Q
) -> impl 'a + Iterator<Item = &'a V> where
Q: Ord,
K: Borrow<Q>,
[src]
&'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>,
[src]
&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.
Trait Implementations
impl<I: Clone + Idx, K: Clone, V: Clone> Clone for SortedIndexMultiMap<I, K, V>
[src]
fn clone(&self) -> SortedIndexMultiMap<I, K, V>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<I: Debug + Idx, K: Debug, V: Debug> Debug for SortedIndexMultiMap<I, K, V>
[src]
impl<I: Idx, K: Eq, V: Eq> Eq for SortedIndexMultiMap<I, K, V>
[src]
impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V>
[src]
fn from_iter<J>(iter: J) -> Self where
J: IntoIterator<Item = (K, V)>,
[src]
J: IntoIterator<Item = (K, V)>,
impl<I: Idx, K, V> Hash for SortedIndexMultiMap<I, K, V> where
K: Hash,
V: Hash,
[src]
K: Hash,
V: Hash,
fn hash<H: Hasher>(&self, hasher: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<I: Idx, K, V, C> HashStable<C> for SortedIndexMultiMap<I, K, V> where
K: HashStable<C>,
V: HashStable<C>,
[src]
K: HashStable<C>,
V: HashStable<C>,
fn hash_stable(&self, ctx: &mut C, hasher: &mut StableHasher)
[src]
impl<I: Idx, K, V> Index<I> for SortedIndexMultiMap<I, K, V>
[src]
impl<I: Idx, K: PartialEq, V: PartialEq> PartialEq<SortedIndexMultiMap<I, K, V>> for SortedIndexMultiMap<I, K, V>
[src]
Auto Trait Implementations
impl<I, K, V> RefUnwindSafe for SortedIndexMultiMap<I, K, V> where
I: RefUnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
I: RefUnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
impl<I, K, V> Send for SortedIndexMultiMap<I, K, V> where
I: Send,
K: Send,
V: Send,
I: Send,
K: Send,
V: Send,
impl<I, K, V> Sync for SortedIndexMultiMap<I, K, V> where
I: Sync,
K: Sync,
V: Sync,
I: Sync,
K: Sync,
V: Sync,
impl<I, K, V> Unpin for SortedIndexMultiMap<I, K, V> where
I: Unpin,
K: Unpin,
V: Unpin,
I: Unpin,
K: Unpin,
V: Unpin,
impl<I, K, V> UnwindSafe for SortedIndexMultiMap<I, K, V> where
I: UnwindSafe,
K: UnwindSafe,
V: UnwindSafe,
I: UnwindSafe,
K: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<'a, T> Captures<'a> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<Q, K> Equivalent<K> for Q where
K: Borrow<Q> + ?Sized,
Q: Eq + ?Sized,
[src]
K: Borrow<Q> + ?Sized,
Q: Eq + ?Sized,
fn equivalent(&self, key: &K) -> bool
[src]
impl<T> Erased for T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<E> SpecializationError for E
[src]
default fn not_found<S, T>(
trait_name: &'static str,
method_name: &'static str
) -> E where
T: ?Sized,
[src]
trait_name: &'static str,
method_name: &'static str
) -> E where
T: ?Sized,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,