Struct rustc_data_structures::sorted_map::index_map::SortedIndexMultiMap[][src]

pub struct SortedIndexMultiMap<I: Idx, K, V> {
    items: IndexVec<I, (K, V)>,
    idx_sorted_by_item_key: Vec<I>,
}
Expand description

An indexed multi-map that preserves insertion order while permitting both O(log n) lookup of an item by key and O(1) lookup by index.

This data structure is a hybrid of an IndexVec and a SortedMap. Like IndexVec, SortedIndexMultiMap assigns a typed index to each item while preserving insertion order. Like SortedMap, SortedIndexMultiMap has efficient lookup of items by key. However, this is accomplished by sorting an array of item indices instead of the items themselves.

Unlike SortedMap, this data structure can hold multiple equivalent items at once, so the get_by_key method and its variants return an iterator instead of an Option. Equivalent items will be yielded in insertion order.

Unlike a general-purpose map like BTreeSet or HashSet, SortedMap and SortedIndexMultiMap require O(n) time to insert a single item. This is because we may need to insert into the middle of the sorted array. Users should avoid mutating this data structure in-place.

Fields

items: IndexVec<I, (K, V)>

The elements of the map in insertion order.

idx_sorted_by_item_key: Vec<I>

Indices of the items in the set, sorted by the item’s key.

Implementations

Returns an iterator over the items in the map in insertion order.

Returns an iterator over the items in the map in insertion order along with their indices.

Returns an iterator over the items in the map in insertion order.

Returns an iterator over the items in the map in insertion order along with their indices.

Returns the item in the map with the given index.

Returns an iterator over the items in the map that are equal to key.

If there are multiple items that are equivalent to key, they will be yielded in insertion order.

Returns an iterator over the items in the map that are equal to key along with their indices.

If there are multiple items that are equivalent to key, they will be yielded in insertion order.

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Creates a value from an iterator. Read more

Feeds this value into the given Hasher. Read more

Feeds a slice of this type into the given Hasher. Read more

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

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

This method tests for !=.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Performs the conversion.

Performs the conversion.

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

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

recently added

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.

Layout

Note: Most layout information is completely unstable and may be different between compiler versions and platforms. 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: 48 bytes