Library Reference

version 2.112.0

Internal API

If you spot a problem with this page, click here to create a Bugzilla issue.

Quickly fork, edit online, and submit a pull request for this page.Requires a signed-in GitHub account. This works well for small changes.If you'd like to make larger changes you may want to consider usinga local clone.

std.container.rbtree

This module implements a red-black tree container.

This module is a submodule ofstd.container.

Sourcestd/container/rbtree.d

License:

Distributed under the Boost Software License, Version 1.0.(See accompanying file LICENSE_1_0.txt or copy atboost.org/LICENSE_1_0.txt).

Authors:

Steven Schveighoffer,Andrei Alexandrescu

Examples:

import std.algorithm.comparison : equal;import std.container.rbtree;auto rbt = redBlackTree(3, 1, 4, 2, 5);writeln(rbt.front);// 1assert(equal(rbt[], [1, 2, 3, 4, 5]));rbt.removeKey(1, 4);assert(equal(rbt[], [2, 3, 5]));rbt.removeFront();assert(equal(rbt[], [3, 5]));rbt.insert([1, 2, 4]);assert(equal(rbt[], [1, 2, 3, 4, 5]));// Query bounds in O(log(n))assert(rbt.lowerBound(3).equal([1, 2]));assert(rbt.equalRange(3).equal([3]));assert(rbt.upperBound(3).equal([4, 5]));// A Red Black tree with the highest element at front:import std.range : iota;auto maxTree = redBlackTree!"a > b"(iota(5));assert(equal(maxTree[], [4, 3, 2, 1, 0]));// adding duplicates will not add them, but return 0auto rbt2 = redBlackTree(1, 3);writeln(rbt2.insert(1));// 0assert(equal(rbt2[], [1, 3]));writeln(rbt2.insert(2));// 1// however you can allow duplicatesauto ubt = redBlackTree!true([0, 1, 0, 1]);assert(equal(ubt[], [0, 0, 1, 1]));

classRedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if (is(typeof((ref const T a) => binaryFun!less(a, a))));

Implementation of a red-black tree container.

All inserts, removes, searches, and any function in general has complexity ofΟ(lg(n)).

To use a different comparison than"a < b", pass a different operator string that can be used bystd.functional.binaryFun, or pass in a function, delegate, functor, or any type whereless(a, b) results in abool value.

Note that less should produce a strict ordering. That is, for two unequal elementsa andb,less(a, b) == !less(b, a).less(a, a) should always equalfalse.

Care should also be taken to not modify elements in the tree (e.g. viafront /back, which return byref) in a way which would affect the order defined by theless predicate.

IfallowDuplicates is set totrue, then inserting the same element more than once continues to add more elements. If it isfalse, duplicate elements are ignored on insertion. If duplicates are allowed, then new elements are inserted after all existing duplicate elements.

aliasElem = T;

Element type for the tree

aliasRange = RBRange!(RBNode*); aliasConstRange = RBRange!(const(RBNode)*); aliasImmutableRange = RBRange!(immutable(RBNode)*);

The range types forRedBlackTree

@property boolempty() const;

Check if any elements exist in the container. Returnsfalse if at least one element exists.

@property size_tlength() const;

Returns the number of elements in the container.

ComplexityΟ(1).

@property RedBlackTreedup();

Duplicate this container. The resulting container contains a shallow copy of the elements.

ComplexityΟ(n)

RangeopSlice(); ConstRangeopSlice() const; ImmutableRangeopSlice() immutable;

Fetch a range that spans all the elements in the container.

ComplexityΟ(1)

ref inout(Elem)front() inout;

The front element in the container

ComplexityΟ(1)

ref inout(Elem)back() inout;

The last element in the container

ComplexityΟ(log(n))

boolopBinaryRight(string op)(Eleme) const if (op == "in");

in operator. Check to see if the given element exists in the container.

ComplexityΟ(log(n))

boolopEquals(Objectrhs);

Compares two trees for equality.

ComplexityΟ(n)

nothrow @safe size_ttoHash();

Generates a hash for the tree. Note that with a custom comparison function it may not hold that if two rbtrees are equal, the hashes of the trees will be equal.

voidclear();

Removes all elements from the container.

ComplexityΟ(1)

size_tstableInsert(Stuff)(Stuffstuff) if (isImplicitlyConvertible!(Stuff, Elem));

Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.

Returns:

The number of elements inserted.

ComplexityΟ(log(n))

size_tstableInsert(Stuff)(scope Stuffstuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem)); aliasinsert = stableInsert;

Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.

Returns:

The number of elements inserted.

ComplexityΟ(m * log(n))

ElemremoveAny();

Remove an element from the container and return its value.

ComplexityΟ(log(n))

voidremoveFront();

Remove the front element from the container.

ComplexityΟ(log(n))

voidremoveBack();

Remove the back element from the container.

ComplexityΟ(log(n))

Rangeremove(Ranger);

Removes the given range from the container.

Returns:

A range containing all of the elements that were after the given range.

ComplexityΟ(m * log(n)) (where m is the number of elements in the range)

Rangeremove(Take!Ranger);

Removes the givenTake!Range from the container

Returns:

A range containing all of the elements that were after the given range.

ComplexityΟ(m * log(n)) (where m is the number of elements in the range)

size_tremoveKey(U...)(Uelems) if (allSatisfy!(isImplicitlyConvertibleToElem, U)); size_tremoveKey(U)(scope U[]elems) if (isImplicitlyConvertible!(U, Elem)); size_tremoveKey(Stuff)(Stuffstuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem) && !isDynamicArray!Stuff);

Removes elements from the container that are equal to the given values according to the less comparator. One element is removed for each value given which is in the container. IfallowDuplicates is true, duplicates are removed only if duplicate values are given.

Returns:

The number of elements removed.

ComplexityΟ(m log(n)) (where m is the number of elements to remove)

Example

import std.algorithm, std.container;auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);rbt.removeKey(1, 4, 7);assert(equal(rbt[], [0, 1, 1, 5]));rbt.removeKey(1, 1, 0);assert(equal(rbt[], [5]));

RangeupperBound(Eleme); ConstRangeupperBound(Eleme) const; ImmutableRangeupperBound(Eleme) immutable;

Get a range from the container with all elements that are > e according to the less comparator

ComplexityΟ(log(n))

RangelowerBound(Eleme); ConstRangelowerBound(Eleme) const; ImmutableRangelowerBound(Eleme) immutable;

Get a range from the container with all elements that are < e according to the less comparator

ComplexityΟ(log(n))

autoequalRange(this This)(Eleme);

Get a range from the container with all elements that are == e according to the less comparator

ComplexityΟ(log(n))

autotrisect(this This)(Eleme);

Returns a static array of 3 rangesr such thatr[0] is the same as the result oflowerBound(value),r[1] is the same as the result ofequalRange(value), andr[2] is the same as the result ofupperBound(value).

ComplexityΟ(log(n))

voidtoString(scope void delegate(const(char)[])sink, ref scope const FormatSpec!charfmt) const;

Formats the RedBlackTree into a sink function. For more info see std.format.formatValue. Note that this only is available when the element type can be formatted. Otherwise, the default toString from Object is used.

this(Elem[]elems...);

Constructor. Pass in an array of elements, or individual elements to initialize the tree with.

this(Stuff)(Stuffstuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem));

Constructor. Pass in a range of elements to initialize the tree with.

this();

autoredBlackTree(E)(E[]elems...); autoredBlackTree(bool allowDuplicates, E)(E[]elems...); autoredBlackTree(alias less, E)(E[]elems...) if (is(typeof(binaryFun!less(E.init, E.init)))); autoredBlackTree(alias less, bool allowDuplicates, E)(E[]elems...) if (is(typeof(binaryFun!less(E.init, E.init)))); autoredBlackTree(Stuff)(Stuffrange) if (isInputRange!Stuff && !isArray!Stuff); autoredBlackTree(bool allowDuplicates, Stuff)(Stuffrange) if (isInputRange!Stuff && !isArray!Stuff); autoredBlackTree(alias less, Stuff)(Stuffrange) if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff); autoredBlackTree(alias less, bool allowDuplicates, Stuff)(Stuffrange) if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff);

Convenience function for creating aRedBlackTree!E from a list of values.

Parameters:

allowDuplicates	Whether duplicates should be allowed (optional, default: false)
less	predicate to sort by (optional)
E[]`elems`	elements to insert into the rbtree (variadic arguments)
Stuff`range`	range elements to insert into the rbtree (alternative to elems)

Examples:

import std.range : iota;auto rbt1 =redBlackTree(0, 1, 5, 7);auto rbt2 =redBlackTree!string("hello","world");auto rbt3 =redBlackTree!true(0, 1, 5, 7, 5);auto rbt4 =redBlackTree!"a > b"(0, 1, 5, 7);auto rbt5 =redBlackTree!("a > b",true)(0.1, 1.3, 5.9, 7.2, 5.9);// also works with rangesauto rbt6 =redBlackTree(iota(3));auto rbt7 =redBlackTree!true(iota(3));auto rbt8 =redBlackTree!"a > b"(iota(3));auto rbt9 =redBlackTree!("a > b",true)(iota(3));

Movatterモバイル変換

Library Reference

std.container.rbtree