Repository: rust-lang/rust
File: library/alloc/src/collections/btree/map.rs (Rust)

Code before:
        // find the first gap that has the smallest key greater than or equal to
        // the first key from other
        let mut self_cursor = self.lower_bound_mut(Bound::Included(&first_other_key));

        if let Some((self_key, _)) = self_cursor.peek_next() {
            match K::cmp(&first_other_key, self_key) {
                Ordering::Equal => {
                    self_cursor.with_next(|self_key, self_val| {
                        conflict(self_key, self_val, first_other_val)
                    });
                }
                Ordering::Less =>
                // SAFETY: we know our other_key's ordering is less than self_key,
                // so inserting before will guarantee sorted order
                unsafe {
                    self_cursor.insert_before_unchecked(first_other_key, first_other_val);
                },
                Ordering::Greater => {
                    unreachable!("Cursor's peek_next should return None.");
                }
            }
        } else {
            // SAFETY: reaching here means our cursor is at the end
            // self BTreeMap so we just insert other_key here
            unsafe {
                self_cursor.insert_after_unchecked(first_other_key, first_other_val);
            }
        }

        for (other_key, other_val) in other_iter {
            loop {
                if let Some((self_key, _)) = self_cursor.peek_next() {
                    match K::cmp(&other_key, self_key) {
                        Ordering::Equal => {
                            self_cursor.with_next(|self_key, self_val| {
                                conflict(self_key, self_val, other_val)
                            });
                            break;
                        }
                        Ordering::Less => {
                            // SAFETY: we know our other_key's ordering is less than self_key,
                            // so inserting before will guarantee sorted order
                            unsafe {
                                self_cursor.insert_before_unchecked(other_key, other_val);
                            }
                            break;
                        }
                        Ordering::Greater => {
                            // advance the cursor forward
                            self_cursor.next();
                        }

Review comment (suggestion):
```suggestion
                self_cursor.insert_before_unchecked(first_other_key, first_other_val);
```
we have the smallest `other` key, we know any later keys must be larger, so having the cursor moved to right after the inserted entry means we don't need a redundant comparison to decide to move after this key.


Code after:
        // the first key from other
        let mut self_cursor = self.lower_bound_mut(Bound::Included(&first_other_key));

        if let Some((self_key, _)) = self_cursor.peek_next() {
            match K::cmp(self_key, &first_other_key) {
                Ordering::Equal => {
                    // if `f` unwinds, the next entry is already removed leaving
                    // the tree in valid state.
                    // FIXME: Once `MaybeDangling` is implemented, we can optimize
                    // this through using a drop handler and transmutating CursorMutKey<K, V>
                    // to CursorMutKey<ManuallyDrop<K>, ManuallyDrop<V>> (see PR #152418)
                    if let Some((k, v)) = self_cursor.remove_next() {
                        // SAFETY: we remove the K, V out of the next entry,
                        // apply 'f' to get a new (K, V), and insert it back
                        // into the next entry that the cursor is pointing at
                        let v = conflict(&k, v, first_other_val);
                        unsafe { self_cursor.insert_after_unchecked(k, v) };
                    }
                }
                Ordering::Greater =>
                // SAFETY: we know our other_key's ordering is less than self_key,
                // so inserting before will guarantee sorted order
                unsafe {
                    self_cursor.insert_before_unchecked(first_other_key, first_other_val);
                },
                Ordering::Less => {
                    unreachable!("Cursor's peek_next should return None.");
                }
            }
        } else {
            // SAFETY: reaching here means our cursor is at the end
            // self BTreeMap so we just insert other_key here
            unsafe {
                self_cursor.insert_before_unchecked(first_other_key, first_other_val);
            }
        }

        for (other_key, other_val) in other_iter {
            loop {
                if let Some((self_key, _)) = self_cursor.peek_next() {
                    match K::cmp(self_key, &other_key) {
                        Ordering::Equal => {
                            // if `f` unwinds, the next entry is already removed leaving
                            // the tree in valid state.
                            // FIXME: Once `MaybeDangling` is implemented, we can optimize
                            // this through using a drop handler and transmutating CursorMutKey<K, V>
                            // to CursorMutKey<ManuallyDrop<K>, ManuallyDrop<V>> (see PR #152418)
                            if let Some((k, v)) = self_cursor.remove_next() {
                                // SAFETY: we remove the K, V out of the next entry,
                                // apply 'f' to get a new (K, V), and insert it back
                                // into the next entry that the cursor is pointing at