Merge multiple sorted ranges
rs with less-than predicate function
into one single sorted output range containing the sorted union of the
elements of inputs. Duplicates are not eliminated, meaning that the total
number of elements in the output is the sum of all elements in the ranges
passed to it; the
length member is offered if all inputs also have
length. The element types of all the inputs must have a common type
Merge!(less,Rs) merge(alias less, Rs...) (
.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));
|less||Predicate the given ranges are sorted by.|
|rs||The ranges to compute the union for.|
A range containing the union of the given ranges.
All of its inputs are assumed to be sorted. This can mean that inputs are
std. Use the result of
std to merge ranges
known to be sorted (show in the example below). Note that there is currently
no way of ensuring that two or more instances of
std are sorted using a specific comparison function
no checking is done here to assure that all inputs
rs are instances of
This algorithm is lazy, doing work progressively as elements are pulled off the result.
Time complexity is proportional to the sum of element counts over all inputs.
If all inputs have the same element type and offer it by
becomes a range with mutable
back where appropriate) that
reflects in the original inputs.
If any of the inputs
rs is infinite so is the result (
empty being always
multiwayMerge for an analogous function
that merges a dynamic number of ranges.
test bi-directional access and common type
.algorithm .comparison : equal; import std .range : retro; import std .traits : CommonType; alias S = short; alias I = int; alias D = double; S a = [1, 2, 3]; I b = [50, 60]; D c = [10, 20, 30, 40]; auto m = merge(a, b, c); static assert(is(typeof(m .front) == CommonType!(S, I, D))); assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60])); assert(equal(m .retro, [60, 50, 40, 30, 20, 10, 3, 2, 1])); m .popFront(); assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60])); m .popBack(); assert(equal(m, [2, 3, 10, 20, 30, 40, 50])); m .popFront(); assert(equal(m, [3, 10, 20, 30, 40, 50])); m .popBack(); assert(equal(m, [3, 10, 20, 30, 40])); m .popFront(); assert(equal(m, [10, 20, 30, 40])); m .popBack(); assert(equal(m, [10, 20, 30])); m .popFront(); assert(equal(m, [20, 30])); m .popBack(); assert(equal(m, )); m .popFront(); assert(m .empty);