[−][src]Struct rustc_data_structures::sorted_map::SortedMap
SortedMap
is a data structure with similar characteristics as BTreeMap but
slightly different trade-offs: lookup, insertion, and removal are O(log(N))
and 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.
Methods
impl<K: Ord, V> SortedMap<K, V>
[src]
impl<K: Ord, V> SortedMap<K, V>
pub fn new() -> SortedMap<K, V> | [src] |
pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V> | [src] |
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> | [src] |
pub fn remove(&mut self, key: &K) -> Option<V> | [src] |
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where | [src] |
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where | [src] |
pub fn clear(&mut self) | [src] |
ⓘImportant traits for Iter<'a, T>
pub fn iter(&self) -> Iter<(K, V)> | [src] |
Iterate over elements, sorted by key
pub fn keys( | [src] |
Iterate over the keys, sorted
pub fn values( | [src] |
Iterate over values, sorted by key
pub fn len(&self) -> usize | [src] |
pub fn is_empty(&self) -> bool | [src] |
pub fn range<R>(&self, range: R) -> &[(K, V)] where | [src] |
pub fn remove_range<R>(&mut self, range: R) where | [src] |
pub fn offset_keys<F>(&mut self, f: F) where | [src] |
Mutate all keys with the given function f
. This mutation must not
change the sort-order of keys.
pub fn insert_presorted(&mut self, elements: Vec<(K, V)>) | [src] |
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.
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where | [src] |
Trait Implementations
impl<K: Ord, V> IntoIterator for SortedMap<K, V>
[src]
impl<K: Ord, V> IntoIterator for SortedMap<K, V>
type Item = (K, V)
The type of the elements being iterated over.
type IntoIter = IntoIter<(K, V)>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Self::IntoIter | [src] |
impl<K: Eq + Ord, V: Eq> Eq for SortedMap<K, V>
[src]
impl<K: Eq + Ord, V: Eq> Eq for SortedMap<K, V>
impl<K: PartialOrd + Ord, V: PartialOrd> PartialOrd<SortedMap<K, V>> for SortedMap<K, V>
[src]
impl<K: PartialOrd + Ord, V: PartialOrd> PartialOrd<SortedMap<K, V>> for SortedMap<K, V>
fn partial_cmp(&self, other: &SortedMap<K, V>) -> Option<Ordering> | [src] |
fn lt(&self, other: &SortedMap<K, V>) -> bool | [src] |
fn le(&self, other: &SortedMap<K, V>) -> bool | [src] |
fn gt(&self, other: &SortedMap<K, V>) -> bool | [src] |
fn ge(&self, other: &SortedMap<K, V>) -> bool | [src] |
impl<K: Default + Ord, V: Default> Default for SortedMap<K, V>
[src]
impl<K: Default + Ord, V: Default> Default for SortedMap<K, V>
impl<K: PartialEq + Ord, V: PartialEq> PartialEq<SortedMap<K, V>> for SortedMap<K, V>
[src]
impl<K: PartialEq + Ord, V: PartialEq> PartialEq<SortedMap<K, V>> for SortedMap<K, V>
fn eq(&self, other: &SortedMap<K, V>) -> bool | [src] |
fn ne(&self, other: &SortedMap<K, V>) -> bool | [src] |
impl<K: Clone + Ord, V: Clone> Clone for SortedMap<K, V>
[src]
impl<K: Clone + Ord, V: Clone> Clone for SortedMap<K, V>
fn clone(&self) -> SortedMap<K, V> | [src] |
fn clone_from(&mut self, source: &Self) | 1.0.0 [src] |
Performs copy-assignment from source
. Read more
impl<K: Ord + Ord, V: Ord> Ord for SortedMap<K, V>
[src]
impl<K: Ord + Ord, V: Ord> Ord for SortedMap<K, V>
fn cmp(&self, other: &SortedMap<K, V>) -> Ordering | [src] |
fn max(self, other: Self) -> Self | 1.21.0 [src] |
Compares and returns the maximum of two values. Read more
fn min(self, other: Self) -> Self | 1.21.0 [src] |
Compares and returns the minimum of two values. Read more
impl<K: Debug + Ord, V: Debug> Debug for SortedMap<K, V>
[src]
impl<K: Debug + Ord, V: Debug> Debug for SortedMap<K, V>
impl<K: Hash + Ord, V: Hash> Hash for SortedMap<K, V>
[src]
impl<K: Hash + Ord, V: Hash> Hash for SortedMap<K, V>
fn hash<__HKV: Hasher>(&self, state: &mut __HKV) | [src] |
fn hash_slice<H>(data: &[Self], state: &mut H) where | 1.3.0 [src] |
Feeds a slice of this type into the given [Hasher
]. Read more
impl<'a, K, Q: ?Sized, V> Index<&'a Q> for SortedMap<K, V> where
K: Ord + Borrow<Q>,
Q: Ord,
[src]
impl<'a, K, Q: ?Sized, V> Index<&'a Q> for SortedMap<K, V> where
K: Ord + Borrow<Q>,
Q: Ord,
impl<'a, K, Q: ?Sized, V> IndexMut<&'a Q> for SortedMap<K, V> where
K: Ord + Borrow<Q>,
Q: Ord,
[src]
impl<'a, K, Q: ?Sized, V> IndexMut<&'a Q> for SortedMap<K, V> where
K: Ord + Borrow<Q>,
Q: Ord,
impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V>
[src]
impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V>
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self | [src] |
impl<K: Encodable + Ord, V: Encodable> Encodable for SortedMap<K, V>
[src]
impl<K: Encodable + Ord, V: Encodable> Encodable for SortedMap<K, V>
impl<K: Decodable + Ord, V: Decodable> Decodable for SortedMap<K, V>
[src]
impl<K: Decodable + Ord, V: Decodable> Decodable for SortedMap<K, V>
Auto Trait Implementations
impl<K, V> Send for SortedMap<K, V> where
K: Send,
V: Send,
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> Sync for SortedMap<K, V> where
K: Sync,
V: Sync,
Blanket Implementations
impl<T> Erased for T
[src]
impl<T> Erased for T
impl<T> Send for T where
T: ?Sized,
[src]
impl<T> Send for T where
T: ?Sized,
impl<T> Sync for T where
T: ?Sized,
[src]
impl<T> Sync for T where
T: ?Sized,
impl<T> From for T
[src]
impl<T> From for T
impl<I> IntoIterator for I where
I: Iterator,
[src]
impl<I> IntoIterator for I where
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I | [src] |
impl<T, U> Into for T where
U: From<T>,
[src]
impl<T, U> Into for T where
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
impl<T> ToOwned for T where
T: Clone,
impl<T, U> TryFrom for T where
T: From<U>,
[src]
impl<T, U> TryFrom for T where
T: From<U>,
type Error = !
try_from
)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> Borrow for T where
T: ?Sized,
[src]
impl<T> Borrow for T where
T: ?Sized,
impl<T> BorrowMut for T where
T: ?Sized,
[src]
impl<T> BorrowMut for T where
T: ?Sized,
ⓘImportant traits for &'_ mut I
fn borrow_mut(&mut self) -> &mut T | [src] |
impl<T, U> TryInto for T where
U: TryFrom<T>,
[src]
impl<T, U> TryInto for T where
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
try_from
)The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error> | [src] |
impl<T> Any for T where
T: 'static + ?Sized,
[src]
impl<T> Any for T where
T: 'static + ?Sized,
fn get_type_id(&self) -> TypeId | [src] |
impl<T> Encodable for T where
T: UseSpecializedEncodable + ?Sized,
[src]
impl<T> Encodable for T where
T: UseSpecializedEncodable + ?Sized,
impl<T> Decodable for T where
T: UseSpecializedDecodable,
[src]
impl<T> Decodable for T where
T: UseSpecializedDecodable,
impl<E> SpecializationError for E
[src]
impl<E> SpecializationError for E
impl<T> Erased for T
impl<T> Erased for T