Struct rustc_ap_rustc_data_structures::sorted_map::SortedIndexMultiMap [−][src]
pub struct SortedIndexMultiMap<I: Idx, K, V> { /* fields omitted */ }
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.
Implementations
impl<I: Idx, K: Ord, V> SortedIndexMultiMap<I, K, V>
[src]
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]
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]
pub fn into_iter_enumerated(
self
) -> impl DoubleEndedIterator<Item = (I, (K, V))>
[src]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]
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]
pub fn iter_enumerated(
&self
) -> impl '_ + DoubleEndedIterator<Item = (I, (&K, &V))>
[src]Returns an iterator over the items in the map in insertion order along with their indices.
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>,
[src]
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>,
[src]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]
pub fn get_by_key_enumerated<Q: ?Sized>(
&self,
key: &Q
) -> impl '_ + Iterator<Item = (I, &V)> where
Q: Ord,
K: Borrow<Q>,
[src]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]
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(&self) -> SortedIndexMultiMap<I, K, V>
[src]Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]Performs copy-assignment from source
. Read more
impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V>
[src]
impl<I: Idx, K: Ord, V> FromIterator<(K, V)> for SortedIndexMultiMap<I, K, V>
[src]impl<I: Idx, K, V, C> HashStable<C> for SortedIndexMultiMap<I, K, V> where
K: HashStable<C>,
V: HashStable<C>,
[src]
impl<I: Idx, K, V, C> HashStable<C> for SortedIndexMultiMap<I, K, V> where
K: HashStable<C>,
V: HashStable<C>,
[src]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, 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]
impl<I: Idx, K: PartialEq, V: PartialEq> PartialEq<SortedIndexMultiMap<I, K, V>> for SortedIndexMultiMap<I, K, V>
[src]impl<I: Idx, K: Eq, V: Eq> Eq 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> BorrowMut<T> for T where
T: ?Sized,
[src]
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]pub fn borrow_mut(&mut self) -> &mut T
[src]
pub fn borrow_mut(&mut self) -> &mut T
[src]Mutably borrows from an owned value. Read more
impl<Q, K> Equivalent<K> for Q where
K: Borrow<Q> + ?Sized,
Q: Eq + ?Sized,
[src]
impl<Q, K> Equivalent<K> for Q where
K: Borrow<Q> + ?Sized,
Q: Eq + ?Sized,
[src]pub fn equivalent(&self, key: &K) -> bool
[src]
pub fn equivalent(&self, key: &K) -> bool
[src]Compare self to key
and return true
if they are equal.
impl<T> Instrument for T
[src]
impl<T> Instrument for T
[src]fn instrument(self, span: Span) -> Instrumented<Self>
[src]
fn instrument(self, span: Span) -> Instrumented<Self>
[src]Instruments this type with the provided Span
, returning an
Instrumented
wrapper. Read more
fn in_current_span(self) -> Instrumented<Self>
[src]
fn in_current_span(self) -> Instrumented<Self>
[src]impl<T> ToOwned for T where
T: Clone,
[src]
impl<T> ToOwned for T where
T: Clone,
[src]type Owned = T
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn to_owned(&self) -> T
[src]Creates owned data from borrowed data, usually by cloning. Read more
pub fn clone_into(&self, target: &mut T)
[src]
pub fn clone_into(&self, target: &mut T)
[src]🔬 This is a nightly-only experimental API. (toowned_clone_into
)
recently added
Uses borrowed data to replace owned data, usually by cloning. Read more
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
pub fn vzip(self) -> V
impl<'a, T> Captures<'a> for T where
T: ?Sized,
[src]
T: ?Sized,