Make BTreeMap's from_sorted_iter public

[PlasmaPower]

Use case: I'm trying to merge BTreeMaps, but in the case of a duplicate key, I'd prefer to add the values instead of ignoring the first. To do this, I was planning on implementing a custom MergeIter, which seems simple enough. However, I encountered one problem: BTreeMap's from_sorted_iter is private, meaning that I cannot efficiently use this iterator to merge maps.

I think the reasoning behind this being private is that being passed an unsorted iterator would result in a logic error in the BTreeMap. However, it's already possible to cause this in safe code with an unreliable Cmp implementation.

If the function is made public, I'd recommend a couple of changes to make it ready for use without other internal functions. First, don't take self, but instead start with an empty map. Note that we might also consider just asserting that the map is empty to start with, as I think this change would require either an unnecessary BTreeMap creation or mem::uninitialized in BTreeMap::append. Second, add fix_right_edge() to the end of the function. This change shouldn't cause any problems for BTreeMap::append as it's already calling it afterwords.

[Stebalien]

Actually, from_sorted_iter could simply assert that the iterators are sorted (slightly slower but not asymptotically slower).

[PlasmaPower]

I suppose so. It's too bad we can't have debug_asserts in std as it's always built for release.

[dtolnay]

I would prefer not to assert. The caller can wrap their iterator in an iterator adapter containing the assert if they want that.

https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search also does not verify that its input is sorted.

[ang-zeyu]

linking this to https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815