SortedMap in rustc_data_structures::sorted_map - Rust (original) (raw)
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.
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.
Gets a mutable reference to the value in the entry, or insert a new one.
Iterate over elements, sorted by key
Iterate over the keys, sorted
Iterate over values, sorted by key
sm.range_is_empty(r) == sm.range(r).is_empty(), but is faster.
Mutate all keys with the given function f. This mutation must not change the sort-order of keys.
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.
Looks up the key in self.data via slice::binary_search().
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