Struct rustc_data_structures::sorted_map::SortedMap

pub struct SortedMap<K: Ord, V> { /* fields omitted */ }

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>

pub fn new() -> 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: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Ord, 

pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
    K: Borrow<Q>,
    Q: Ord, 

pub fn clear(&mut self)

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

pub fn iter(&self) -> Iter<(K, V)>

Iterate over elements, sorted by key

pub fn keys(&self) -> impl Iterator<Item = &K> + ExactSizeIterator

Iterate over the keys, sorted

pub fn values(&self) -> impl Iterator<Item = &V> + ExactSizeIterator

Iterate over values, sorted by key

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

Important traits for &'_ [u8]

impl<'_> Read for &'_ [u8]impl<'_> Write for &'_ mut [u8]

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>, 

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.

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.

pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Ord, 

Trait Implementations

impl<K: Eq + Ord, V: Eq> Eq for SortedMap<K, V>

impl<K: Ord + Ord, V: Ord> Ord for SortedMap<K, V>

fn cmp(&self, other: &SortedMap<K, V>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl<K: PartialEq + Ord, V: PartialEq> PartialEq<SortedMap<K, V>> for SortedMap<K, V>

fn eq(&self, other: &SortedMap<K, V>) -> bool

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

fn ne(&self, other: &SortedMap<K, V>) -> bool

This method tests for !=.

impl<K: Clone + Ord, V: Clone> Clone for SortedMap<K, V>

fn clone(&self) -> SortedMap<K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: PartialOrd + Ord, V: PartialOrd> PartialOrd<SortedMap<K, V>> for SortedMap<K, V>

fn partial_cmp(&self, other: &SortedMap<K, V>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &SortedMap<K, V>) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &SortedMap<K, V>) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &SortedMap<K, V>) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &SortedMap<K, V>) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K: Default + Ord, V: Default> Default for SortedMap<K, V>

fn default() -> SortedMap<K, V>

Returns the "default value" for a type.

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

Creates an iterator from a value.

impl<K: Debug + Ord, V: Debug> Debug for SortedMap<K, V>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'a, K, Q: ?Sized, V> Index<&'a Q> for SortedMap<K, V> where
    K: Ord + Borrow<Q>,
    Q: Ord, 

type Output = V

The returned type after indexing.

fn index(&self, key: &Q) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, K, Q: ?Sized, V> IndexMut<&'a Q> for SortedMap<K, V> where
    K: Ord + Borrow<Q>,
    Q: Ord, 

fn index_mut(&mut self, key: &Q) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<K: Hash + Ord, V: Hash> Hash for SortedMap<K, V>

fn hash<__HKV: Hasher>(&self, state: &mut __HKV)

Feeds this value into the given [Hasher].

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

Feeds a slice of this type into the given [Hasher].

impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V>

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

Creates a value from an iterator.

impl<K: Encodable + Ord, V: Encodable> Encodable for SortedMap<K, V>

fn encode<__SKV: Encoder>(&self, s: &mut __SKV) -> Result<(), __SKV::Error>

impl<K: Decodable + Ord, V: Decodable> Decodable for SortedMap<K, V>

fn decode<__DKV: Decoder>(
    d: &mut __DKV
) -> Result<SortedMap<K, V>, __DKV::Error>