Skip to content

Add insert_sorted#315

Merged
cuviper merged 1 commit intoindexmap-rs:masterfrom
cuviper:insert_sorted
Feb 26, 2024
Merged

Add insert_sorted#315
cuviper merged 1 commit intoindexmap-rs:masterfrom
cuviper:insert_sorted

Conversation

@cuviper
Copy link
Member

@cuviper cuviper commented Feb 25, 2024

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.

@cuviper cuviper enabled auto-merge February 26, 2024 22:54
@cuviper cuviper added this pull request to the merge queue Feb 26, 2024
Merged via the queue into indexmap-rs:master with commit 9deec7c Feb 26, 2024
@cuviper cuviper deleted the insert_sorted branch February 27, 2024 02:25
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

An insert_sorted() method

1 participant