Function std.algorithm.sorting.merge
Merge multiple sorted ranges rs
with less-than predicate function pred
into one single sorted output range containing the sorted union of the
elements of inputs.
Merge!(less,Rs) merge(alias less, Rs...)
(
Rs rs
)
if (Rs .length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));
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
CommonType
.
Parameters
Name | Description |
---|---|
less | Predicate the given ranges are sorted by. |
rs | The ranges to compute the union for. |
Returns
A range containing the union of the given ranges.
Details
All of its inputs are assumed to be sorted. This can mean that inputs are
instances of std
. Use the result of sort
, or 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 pred
. Therefore
no checking is done here to assure that all inputs rs
are instances of
std
.
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 ref
, output
becomes a range with mutable front
(and back
where appropriate) that
reflects in the original inputs.
If any of the inputs rs
is infinite so is the result (empty
being always
false
).
See Also
multiwayMerge
for an analogous function
that merges a dynamic number of ranges.
Example
import std .algorithm .comparison : equal;
import std .range : retro;
int[] a = [1, 3, 5];
int[] b = [2, 3, 4];
assert(a .merge(b) .equal([1, 2, 3, 3, 4, 5]));
assert(a .merge(b) .retro .equal([5, 4, 3, 3, 2, 1]));
Example
test bi-directional access and common type
import std .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, [20]));
m .popFront();
assert(m .empty);