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

Code before:
                    }
                } 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(other_key, other_val);
                    }
                    break;
                }
            }
        }
    }

    /// Constructs a double-ended iterator over a sub-range of elements in the map.
    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
    /// yield elements from min (inclusive) to max (exclusive).
    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
    /// range from 4 to 10.
    ///
    /// # Panics
    ///
    /// Panics if range `start > end`.
    /// Panics if range `start == end` and both bounds are `Excluded`.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::ops::Bound::Included;
    ///
    /// let mut map = BTreeMap::new();
    /// map.insert(3, "a");
    /// map.insert(5, "b");
    /// map.insert(8, "c");
    /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
    ///     println!("{key}: {value}");
    /// }
    /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
    /// ```
    #[stable(feature = "btree_range", since = "1.17.0")]
    pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
    where
        T: Ord,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        if let Some(root) = &self.root {
            Range { inner: root.reborrow().range_search(range) }
        } else {
            Range { inner: LeafRange::none() }

Review comment (performance):
It seems like this is also probably inefficient: we'd want to do a bulk build here, especially if we're merging in a much larger `other` map into `self`. I think this is similar to the linear search above on Ordering::Greater.

I think it's worth at least adding an unresolved question and/or expanding the merge function's doc comment to say something about merges with expected few-matches being better done with e.g. `self.into_iter().sorted_zip(other.into_iter()).collect::<BTreeMap<_, _>>()`, given a sorted_zip that does the advancing of left/right (merge sort's merge effectively). I'm not sure what the constant factors are -- probably depends on how expensive allocation and moving the keys/values around is -- but it seems remiss not to mention it.

Code after:
                        }
                        Ordering::Greater => {
                            // SAFETY: we know our self_key's ordering is greater than other_key,
                            // so inserting before will guarantee sorted order
                            unsafe {
                                self_cursor.insert_before_unchecked(other_key, other_val);
                            }
                            break;
                        }
                        Ordering::Less => {
                            // FIXME: instead of doing a linear search here,
                            // this can be optimized to search the tree by starting
                            // from self_cursor and going towards the root and then
                            // back down to the proper node -- that should probably
                            // be a new method on Cursor*.
                            self_cursor.next();
                        }
                    }
                } else {
                    // FIXME: If we get here, that means all of other's keys are greater than
                    // self's keys. For performance, this should really do a bulk insertion of items
                    // from other_iter into the end of self `BTreeMap`. Maybe this should be
                    // a method for Cursor*?

                    // 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(other_key, other_val);
                    }
                    break;
                }
            }
        }
    }

    /// Constructs a double-ended iterator over a sub-range of elements in the map.
    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
    /// yield elements from min (inclusive) to max (exclusive).
    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
    /// range from 4 to 10.
    ///
    /// # Panics
    ///
    /// Panics if range `start > end`.
    /// Panics if range `start == end` and both bounds are `Excluded`.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;