Removes all elements and deallocates all memory for this tree.
Iterates over elements in order. NOTE: should not be used while inserting or deleting elements from the tree.
Iterates over elements in order. NOTE: should not be used while inserting or deleting elements from the tree.
Check if the tree contains an element.
Element-wise comparison.
Gets the address of the first matching element, or null if it isn't in the tree.
Adds an element to the tree.
Removes (at most) one element from the tree.
Combined element hash.
Updates an element already in the set or creates a new one therein.
Returns the number of elements currently stored in the tree.
1 // tip: debug w/ visualizer at https://www.cs.usfca.edu/~galles/visualization/BTree.html 2 enum BTreeParameters params = { 3 nodeSlots: 3, 4 customCompare: true, 5 useBinarySearch: Ternary.yes, 6 }; 7 auto btree = BTree!(int, params)((ref a, ref b) => a - b); 8 static const payload = [ 9 34, 33, 38, 10 28, 27, 22, 11 30, 21, 24, 12 18, 19, 20, 26, 32, 42, 13 23, 14 ]; 15 16 assert(btree.length == 0); 17 foreach (x; payload) { 18 // at first, the set does not contain x 19 assert(x !in btree); 20 assert(!btree.remove(x)); 21 // insert x and test returned address 22 int* p = btree.put(x); 23 assert(*p == x); 24 // now it does contain x, so test lookup 25 assert(x in btree); 26 assert(p == btree[x]); 27 // redundant insert is redundant 28 int* q = btree.put(x); 29 assert(q == p); 30 } 31 32 // sanity check: the b-tree didn't come up with new elements we didn't insert 33 assert(btree.length == payload.length); 34 foreach (ref const x; btree) { 35 import std.algorithm.searching : canFind; 36 assert(payload.canFind(x)); 37 } 38 39 // remove all but the last 3 elements in reverse order 40 for (int n = 1; n + 2 < payload.length; ++n) { 41 auto x = payload[$ - n]; 42 assert(x in btree); 43 btree.remove(x); 44 assert(x !in btree); 45 assert(btree.length == payload.length - n); 46 } 47 assert(btree.length == 3); 48 49 // make sure we test aggregate equality 50 auto other = BTree!int(); 51 assert(btree != other); 52 import std.range.primitives : put; 53 static const remaining = [33, 34, 38]; 54 put(other, remaining); 55 assert(btree == other); 56 57 // clear gets rid of the rest 58 btree.clear(); 59 assert(btree.length == 0); 60 foreach (x; payload) assert(x !in btree);
static struct S { int x; uint discriminator; nothrow @nogc: alias x this; int opCmp(in S other) const => this.x - other.x; } enum BTreeParameters params = { allowDuplicates: true }; BTree!(S, params) multiset; scope(exit) multiset.clear(); static const payload = [ S(6), S(2), S(4), S(5), S(6, 9), S(4, 20) ]; assert(multiset.length == 0); foreach (x; payload) { S* p = multiset.put(x); assert(*p == x); assert(x in multiset); } assert(multiset.length == payload.length); assert(multiset.remove(S(4))); assert(S(4) in multiset); assert(multiset.remove(S(4))); assert(S(4) !in multiset); assert(multiset.length == payload.length - 2u); assert(multiset.remove(S(6))); assert(multiset.remove(S(6))); assert(!multiset.remove(S(6)));
B-tree data structure template.
B-trees are optimized for "cache friendliness" and low overhead per stored element. The main tradeoff w.r.t other self-balancing trees is that insertions and deletions from a B-tree will move multiple elements around per operation, invalidating references and iterators. When elements are big, consider storing them through indirect references.
In order to ensure all memory is deallocated, remember to call clear. Alternatively, if stored elements don't need elaborate destruction, and the provided allocator supports arenas, a full deallocation called externally will not leave anything leaking (but beware of use-after-free bugs in this case).
While keeping duplicates is not the default, it can be used to implement multisets. Just note that, if duplicate elements are allowed in the B-tree, they will have an unspecified order among themselves (i.e. not related to order of insertion).