From 241a3e4689d3004daf9e1d36cec2235cbd301fbf Mon Sep 17 00:00:00 2001 From: Johannes Oertel Date: Thu, 24 Mar 2016 15:39:46 +0100 Subject: Implement `append` for b-trees. 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`. --- src/libstd/collections/mod.rs | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'src/libstd') 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 //! -- cgit 1.4.1-3-g733a5