Auto merge of #32466 - jooert:btree_append, r=apasel422

Implement `append` for b-trees.

I have finally found time to revive #26227, this time only with an `append` implementation.

The algorithm implemented here is linear in the size of the two b-trees. It firsts creates
a `MergeIter` from the two b-trees and then builds a new b-tree by pushing
key-value pairs from the `MergeIter` into nodes at the right heights.

Three functions for stealing have been added to the implementation of `Handle` as
well as a getter for the height of a `NodeRef`.

The docs have been updated with performance information about `BTreeMap::append` and
the remark about B has been removed now that it is the same for all instances of `BTreeMap`.

cc @gereeter @Gankro @apasel422

1 files changed, 4 insertions, 6 deletions

diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 4de442fd3a1..44613d77671 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -120,12 +120,10 @@
 //!
 //! For Sets, all operations have the cost of the equivalent Map operation.
 //!
-//! |          | get       | insert   | remove   | predecessor |
-//! |----------|-----------|----------|----------|-------------|
-//! | HashMap  | O(1)~     | O(1)~*   | O(1)~    | N/A         |
-//! | BTreeMap | O(log n)  | O(log n) | O(log n) | O(log n)    |
-//!
-//! Note that BTreeMap's precise performance depends on the value of B.
+//! |          | get       | insert   | remove   | predecessor | append |
+//! |----------|-----------|----------|----------|-------------|--------|
+//! | HashMap  | O(1)~     | O(1)~*   | O(1)~    | N/A         | N/A    |
+//! | BTreeMap | O(log n)  | O(log n) | O(log n) | O(log n)    | O(n+m) |
 //!
 //! # Correct and Efficient Usage of Collections
 //!