Jooseong Lee wrote:
I don't see how erase(a,b) can be O(log N), is that a typo?
No, it's not. In order to explain this, I have to explain split() first: split(Tree&& tree, key a, key b) splits a tree to two trees, say tree_l and tree_r, so that tree_l contains all keys less than a, tree_r contains all keys greater than b. By B-Tree's nature, this is O(log N).
erase(a, b) works like this: 1. compute lb = lower_bound(a), ub = upper_bound(b) pair. These are iterators. O(log N) 2. compute order(lb), order(ub). Therefore, order(ub) - order(lb) is the number of elements that will be erased. O(log N) 3-1. When order(ub) - order(lb) < 30, the tree erases element one by one 3-2. When it exceeds 30, the algorithm first splits the tree to two trees by calling spit(std::move(*this), lb, ub) and joins the two split trees. split() and join() is O(log N), and there is one split() call and join() call, so the whole complexity is O(log N)
You have to call the destructors on the elements that you have erased, so it must be O(N) in general. Your description skips the part where you drop the portion of the tree between the two splits. If the element type has a trivial destructor and they are stored contiguously, then you can try to argue that it is better than O(N). This will depend on the complexity guarantees of your memory allocator. But your elements are not stored contiguously; destroying N elements will require O(N) "pages" to be released, if your pages are fixed-size. So it is still O(N). Regards, Phil.