[][src]Struct rustc_data_structures::sorted_map::SortedMap

pub struct SortedMap<K: Ord, V> {
    data: Vec<(K, V)>,
}
⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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)>
⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

Methods

impl<K: Ord, V> SortedMap<K, V>[src]

pub fn new() -> SortedMap<K, V>[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V>[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn remove(&mut self, key: &K) -> Option<V>[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Ord
[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn clear(&mut self)[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

Iterate over elements, sorted by key

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

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

Iterate over the keys, sorted

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

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

Iterate over values, sorted by key

pub fn len(&self) -> usize[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn is_empty(&self) -> bool[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn range<R>(&self, range: R) -> &[(K, V)] where
    R: RangeBounds<K>, 
[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn remove_range<R>(&mut self, range: R) where
    R: RangeBounds<K>, 
[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

pub fn offset_keys<F>(&mut self, f: F) where
    F: Fn(&mut K), 
[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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
[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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>, 
[src]

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

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

⚙️ This is an internal compiler API. (rustc_private)

This crate is being loaded from the sysroot, a permanently unstable location for private compiler dependencies. It is not intended for general use. Prefer using a public version of this crate from crates.io via Cargo.toml.

Trait Implementations

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

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

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

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

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

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

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

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

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

type Output = V

The returned type after indexing.

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

impl<K: Ord, V> IntoIterator for SortedMap<K, V>[src]

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?

impl<K: Ord, V: Ord> Ord for SortedMap<K, V>[src]

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

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

impl<K: Ord, V> StructuralEq for SortedMap<K, V>[src]

impl<K: Ord, V> StructuralPartialEq for SortedMap<K, V>[src]

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

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<'a, T> Captures<'a> for T where
    T: ?Sized
[src]

impl<T> Decodable for T where
    T: UseSpecializedDecodable
[src]

impl<T> Encodable for T where
    T: UseSpecializedEncodable + ?Sized
[src]

impl<Q, K> Equivalent<K> for Q where
    K: Borrow<Q> + ?Sized,
    Q: Eq + ?Sized
[src]

impl<T> Erased for T[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<I> IntoIterator for I where
    I: Iterator
[src]

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?

impl<E> SpecializationError for E[src]

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.