indexmap-rs / indexmap

A hash table with consistent order and fast iteration; access items by key or sequence index
https://docs.rs/indexmap/
Other
1.71k stars 150 forks source link

Add `insert_sorted` #315

Closed cuviper closed 8 months ago

cuviper commented 8 months ago
impl<K: Hash + Ord, V, S: BuildHasher> IndexMap<K, V, S> {
    pub fn insert_sorted(&mut self, key: K, value: V) -> (usize, Option<V>);
}
impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
    pub fn insert_sorted(self, value: V) -> (usize, &'a mut V);
}
impl<T: Hash + Ord, S: BuildHasher> IndexSet<T, S> {
    pub fn insert_sorted(&mut self, value: T) -> (usize, bool);
}

These use a binary_search to find the sorted index, then shift_insert, so they are O(n) overall. The insertion index is unspecified if the existing entries are not already sorted, but it will still act like a consistent shift_insert at that point.

Closes #89.