Struct rustc_data_structures::sorted_map::SortedMap
source · pub struct SortedMap<K, V> {
data: Vec<(K, V)>,
}
Expand description
SortedMap
is a data structure with similar characteristics as BTreeMap but
slightly different trade-offs: lookup is O(log(n)), insertion and removal
are O(n) but elements can be iterated in order cheaply.
SortedMap
can be faster than a BTreeMap
for small sizes (<50) since it
stores data in a more compact way. It also supports accessing contiguous
ranges of elements as a slice, and slices of already sorted elements can be
inserted efficiently.
Fields§
§data: Vec<(K, V)>
Implementations§
source§impl<K: Ord, V> SortedMap<K, V>
impl<K: Ord, V> SortedMap<K, V>
sourcepub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V>
pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V>
Construct a SortedMap
from a presorted set of elements. This is faster
than creating an empty map and then inserting the elements individually.
It is up to the caller to make sure that the elements are sorted by key and that there are no duplicates.
pub fn insert(&mut self, key: K, value: V) -> Option<V>
pub fn remove(&mut self, key: &K) -> Option<V>
pub fn get<Q>(&self, key: &Q) -> Option<&V>where K: Borrow<Q>, Q: Ord + ?Sized,
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>where K: Borrow<Q>, Q: Ord + ?Sized,
sourcepub fn get_mut_or_insert_default(&mut self, key: K) -> &mut Vwhere
K: Eq,
V: Default,
pub fn get_mut_or_insert_default(&mut self, key: K) -> &mut Vwhere K: Eq, V: Default,
Gets a mutable reference to the value in the entry, or insert a new one.
pub fn clear(&mut self)
sourcepub fn keys(
&self
) -> impl Iterator<Item = &K> + ExactSizeIterator + DoubleEndedIterator
pub fn keys( &self ) -> impl Iterator<Item = &K> + ExactSizeIterator + DoubleEndedIterator
Iterate over the keys, sorted
sourcepub fn values(
&self
) -> impl Iterator<Item = &V> + ExactSizeIterator + DoubleEndedIterator
pub fn values( &self ) -> impl Iterator<Item = &V> + ExactSizeIterator + DoubleEndedIterator
Iterate over values, sorted by key
pub fn len(&self) -> usize
pub fn is_empty(&self) -> bool
pub fn range<R>(&self, range: R) -> &[(K, V)]where R: RangeBounds<K>,
pub fn remove_range<R>(&mut self, range: R)where R: RangeBounds<K>,
sourcepub fn offset_keys<F>(&mut self, f: F)where
F: Fn(&mut K),
pub fn offset_keys<F>(&mut self, f: F)where F: Fn(&mut K),
Mutate all keys with the given function f
. This mutation must not
change the sort-order of keys.
sourcepub fn insert_presorted(&mut self, elements: Vec<(K, V)>)
pub fn insert_presorted(&mut self, elements: Vec<(K, V)>)
Inserts a presorted range of elements into the map. If the range can be inserted as a whole in between to existing elements of the map, this will be faster than inserting the elements individually.
It is up to the caller to make sure that the elements are sorted by key and that there are no duplicates.
sourcefn lookup_index_for<Q>(&self, key: &Q) -> Result<usize, usize>where
K: Borrow<Q>,
Q: Ord + ?Sized,
fn lookup_index_for<Q>(&self, key: &Q) -> Result<usize, usize>where K: Borrow<Q>, Q: Ord + ?Sized,
Looks up the key in self.data
via slice::binary_search()
.
fn range_slice_indices<R>(&self, range: R) -> (usize, usize)where R: RangeBounds<K>,
pub fn contains_key<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Ord + ?Sized,
Trait Implementations§
source§impl<K, V, __D: Decoder> Decodable<__D> for SortedMap<K, V>where
K: Decodable<__D>,
V: Decodable<__D>,
impl<K, V, __D: Decoder> Decodable<__D> for SortedMap<K, V>where K: Decodable<__D>, V: Decodable<__D>,
source§impl<K, V, __E: Encoder> Encodable<__E> for SortedMap<K, V>where
K: Encodable<__E>,
V: Encodable<__E>,
impl<K, V, __E: Encoder> Encodable<__E> for SortedMap<K, V>where K: Encodable<__E>, V: Encodable<__E>,
source§impl<K: HashStable<CTX> + StableOrd, V: HashStable<CTX>, CTX> HashStable<CTX> for SortedMap<K, V>
impl<K: HashStable<CTX> + StableOrd, V: HashStable<CTX>, CTX> HashStable<CTX> for SortedMap<K, V>
fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher)
source§impl<'a, K, Q, V> IndexMut<&'a Q> for SortedMap<K, V>where
K: Ord + Borrow<Q>,
Q: Ord + ?Sized,
impl<'a, K, Q, V> IndexMut<&'a Q> for SortedMap<K, V>where K: Ord + Borrow<Q>, Q: Ord + ?Sized,
source§impl<K: Ord, V> IntoIterator for SortedMap<K, V>
impl<K: Ord, V> IntoIterator for SortedMap<K, V>
source§impl<K: Ord, V: Ord> Ord for SortedMap<K, V>
impl<K: Ord, V: Ord> Ord for SortedMap<K, V>
1.21.0 · source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere Self: Sized,
source§impl<K: PartialEq, V: PartialEq> PartialEq<SortedMap<K, V>> for SortedMap<K, V>
impl<K: PartialEq, V: PartialEq> PartialEq<SortedMap<K, V>> for SortedMap<K, V>
source§impl<K: PartialOrd, V: PartialOrd> PartialOrd<SortedMap<K, V>> for SortedMap<K, V>
impl<K: PartialOrd, V: PartialOrd> PartialOrd<SortedMap<K, V>> for SortedMap<K, V>
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read moreimpl<K: Eq, V: Eq> Eq for SortedMap<K, V>
impl<K, V> StructuralEq for SortedMap<K, V>
impl<K, V> StructuralPartialEq for SortedMap<K, V>
Auto Trait Implementations§
impl<K, V> RefUnwindSafe for SortedMap<K, V>where K: RefUnwindSafe, V: RefUnwindSafe,
impl<K, V> Send for SortedMap<K, V>where K: Send, V: Send,
impl<K, V> Sync for SortedMap<K, V>where K: Sync, V: Sync,
impl<K, V> Unpin for SortedMap<K, V>where K: Unpin, V: Unpin,
impl<K, V> UnwindSafe for SortedMap<K, V>where K: UnwindSafe, V: UnwindSafe,
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
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: 24 bytes