Display the source code in std/container/rbtree.d from which this page was generated on github.

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 using local clone.

`std.container.rbtree.RedBlackTree/redBlackTree` - multiple declarations

Function redBlackTree

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


						
				auto redBlackTree(E)();
				

				

				auto redBlackTree(bool allowDuplicates, E)();
				

				

				auto redBlackTree(alias less, E)()
				

				if (is(typeof(binaryFun!less(E.init, E.init))));
				

				

				auto redBlackTree(alias less, bool allowDuplicates, E)()
				

				if (is(typeof(binaryFun!less(E.init, E.init))));
				

				

				auto redBlackTree(Stuff)
				(
				

				  Stuff range
				

				)
				

				if (isInputRange!Stuff && !isArray!Stuff);
				

				

				auto redBlackTree(bool allowDuplicates, Stuff)
				(
				

				  Stuff range
				

				)
				

				if (isInputRange!Stuff && !isArray!Stuff);
				

				

				auto redBlackTree(alias less, Stuff)
				(
				

				  Stuff range
				

				)
				

				if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff);
				

				

				auto redBlackTree(alias less, bool allowDuplicates, Stuff)
				(
				

				  Stuff range
				

				)
				

				if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff);

Parameters

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

Example

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 ranges
auto 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));

Class RedBlackTree

Implementation of a red-black tree container.


						
				class RedBlackTree(T, alias less, bool allowDuplicates = false)
				

				  
				

				if (is(typeof(binaryFun!less(T.init, T.init))));

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 by binaryFun, or pass in a function, delegate, functor, or any type where less(a, b) results in a bool value.

Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false.

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

Constructors

Name	Description
`this` ()	Constructor. Pass in an array of elements, or individual elements to initialize the tree with.
`this` (stuff)	Constructor. Pass in a range of elements to initialize the tree with.
`this` ()

Properties

Name	Type	Description
`dup`[get]	`RedBlackTree`	Duplicate this container. The resulting container contains a shallow copy of the elements.
`empty`[get]	`bool`	Check if any elements exist in the container. Returns `false` if at least one element exists.
`length`[get]	`size_t`	Returns the number of elements in the container.

Methods

Name	Description
`back` ()	The last element in the container
`clear` ()	Removes all elements from the container.
`equalRange` (e)	Get a range from the container with all elements that are == e according to the less comparator
`front` ()	The front element in the container
`lowerBound` (e)	Get a range from the container with all elements that are < e according to the less comparator
`opBinaryRight` (e)	`in` operator. Check to see if the given element exists in the container.
`opEquals` (rhs)	Compares two trees for equality.
`opSlice` ()	Fetch a range that spans all the elements in the container.
`remove` (r)	Removes the given range from the container.
`remove` (r)	Removes the given `Take!Range` from the container
`removeAny` ()	Remove an element from the container and return its value.
`removeBack` ()	Remove the back element from the container.
`removeFront` ()	Remove the front element from the container.
`removeKey` (elems)	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. If `allowDuplicates` is true, duplicates are removed only if duplicate values are given.
`stableInsert` (stuff)	Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.
`stableInsert` (stuff)	Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.
`toHash` ()	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.
`toString` (sink, fmt)	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.
`upperBound` (e)	Get a range from the container with all elements that are > e according to the less comparator
`factory` (classname)	Create instance of class specified by the fully qualified name classname. The class must either have no constructors or have a default constructor.
`opCmp` (o)	Compare with another Object obj.
`opEquals` (o)	Test whether `this` is equal to `o`. The default implementation only compares by identity (using the `is` operator). Generally, overrides and overloads for `opEquals` should attempt to compare objects by their contents. A class will most likely want to add an overload that takes your specific type as the argument and does the content comparison. Then you can override this and forward it to your specific typed overload with a cast. Remember to check for `null` on the typed overload.
`toHash` ()	Compute hash function for Object.
`toString` ()	Convert Object to a human readable string.

Aliases

Name	Description
`ConstRange`	The range types for `RedBlackTree`
`Elem`	Element type for the tree
`ImmutableRange`	The range types for `RedBlackTree`
`insert`	Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.
`Range`	The range types for `RedBlackTree`

Authors

Steven Schveighoffer, Andrei Alexandrescu

License

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