Rollup merge of #66648 - crgl:btree-clone-from, r=Amanieu

Implement clone_from for BTreeMap and BTreeSet

See #28481. This results in up to 90% speedups on simple data types when `self` and `other` are the same size, and is generally comparable or faster. Some concerns:

1. This implementation requires an `Ord` bound on the `Clone` implementation for `BTreeMap` and `BTreeSet`. Since these structs can only be created externally for keys with `Ord` implemented, this should be fine? If not, there's certainly a less safe way to do this.
2. Changing `next_unchecked` on `RangeMut` to return mutable key references allows for replacing the entire overlapping portion of both maps without changing the external interface in any way. However, if `clone_from` fails it can leave the `BTreeMap` in an invalid state, which might be unacceptable.

~This probably needs an FCP since it changes a trait bound, but (as far as I know?) that change cannot break any external code.~

1 files changed, 20 insertions, 0 deletions

diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
index f5be72c39b2..0d009507fc7 100644
--- a/src/liballoc/tests/btree/map.rs
+++ b/src/liballoc/tests/btree/map.rs
@@ -786,6 +786,26 @@ fn test_clone() {
 }
 
 #[test]
+fn test_clone_from() {
+    let mut map1 = BTreeMap::new();
+    let size = 30;
+
+    for i in 0..size {
+        let mut map2 = BTreeMap::new();
+        for j in 0..i {
+            let mut map1_copy = map2.clone();
+            map1_copy.clone_from(&map1);
+            assert_eq!(map1_copy, map1);
+            let mut map2_copy = map1.clone();
+            map2_copy.clone_from(&map2);
+            assert_eq!(map2_copy, map2);
+            map2.insert(100 * j + 1, 2 * j + 1);
+        }
+        map1.insert(i, 10 * i);
+    }
+}
+
+#[test]
 #[allow(dead_code)]
 fn test_variance() {
     use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values};