Struct rustc_data_structures::sorted_map::SortedMap

pub struct SortedMap<K: Ord, V> {
    data: Vec<(K, V)>,
}

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.

Fields

data: Vec<(K, V)>

Implementations

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)

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

Iterate over elements, sorted by key

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

Iterate over the keys, sorted

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

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.

fn lookup_index_for<Q: ?Sized>(&self, key: &Q) -> Result<usize, usize> where
    K: Borrow<Q>,
    Q: Ord, 

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: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Ord, 

Trait Implementations

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: Debug + Ord, V: Debug> Debug for SortedMap<K, V>

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

Formats the value using the given formatter.

impl<K: Ord, V, __D: Decoder> Decodable<__D> for SortedMap<K, V> where
    K: Decodable<__D>,
    V: Decodable<__D>, 

fn decode(__decoder: &mut __D) -> Result<Self, <__D as Decoder>::Error>

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, __E: Encoder> Encodable<__E> for SortedMap<K, V> where
    K: Encodable<__E>,
    V: Encodable<__E>, 

fn encode(&self, __encoder: &mut __E) -> Result<(), <__E as Encoder>::Error>

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: Hash + Ord, V: Hash> Hash for SortedMap<K, V>

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

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<'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: 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: 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.

#[must_use]

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

Compares and returns the maximum of two values.

#[must_use]

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

Compares and returns the minimum of two values.

#[must_use]

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

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: 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.

#[must_use]

fn lt(&self, other: &Rhs) -> bool

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

#[must_use]

fn le(&self, other: &Rhs) -> bool

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

#[must_use]

fn gt(&self, other: &Rhs) -> bool

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

#[must_use]

fn ge(&self, other: &Rhs) -> bool

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

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

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

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