View source code
Display the source code in std/algorithm/setops.d from which this
page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a
Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signedin GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
local clone.
Module std.algorithm.setops
This is a submodule of std
.
It contains generic algorithms that implement set operations.
The functions multiwayMerge
, multiwayUnion
, setDifference
,
setIntersection
, setSymmetricDifference
expect a range of sorted
ranges as input.
All algorithms are generalized to accept as input not only sets but also multisets. Each algorithm documents behaviour in the presence of duplicated inputs.
Function Name  Description 

cartesianProduct  Computes Cartesian product of two ranges. 
largestPartialIntersection  Copies out the values that occur most frequently in a range of ranges. 
largestPartialIntersectionWeighted  Copies out the values that occur most frequently (multiplied by pervalue weights) in a range of ranges. 
multiwayMerge  Merges a range of sorted ranges. 
multiwayUnion  Computes the union of a range of sorted ranges. 
setDifference  Lazily computes the set difference of two or more sorted ranges. 
setIntersection  Lazily computes the intersection of two or more sorted ranges. 
setSymmetricDifference  Lazily computes the symmetric set difference of two or more sorted ranges. 
Functions
Name  Description 

cartesianProduct(range1, range2)

Lazily computes the Cartesian product of two or more ranges. The product is a range of tuples of elements from each respective range. 
largestPartialIntersection(ror, tgt, sorted)

Given a range of sorted forward ranges
ror , copies to tgt the elements that are common to most ranges, along with their number
of occurrences. All ranges in ror are assumed to be sorted by less . Only the most frequent tgt elements are returned.

largestPartialIntersectionWeighted(ror, tgt, weights, sorted)

Similar to largestPartialIntersection , but associates a weight
with each distinct element in the intersection.

multiwayMerge(ror)

Merges multiple sets. The input sets are passed as a
range of ranges and each is assumed to be sorted by less . Computation is done lazily, one union element at a time. The
complexity of one popFront operation is Ο(log(ror ). However, the length of ror decreases as ranges
in it are exhausted, so the complexity of a full pass through MultiwayMerge is dependent on the distribution of the lengths of ranges
contained within ror . If all ranges have the same length n
(worst case scenario), the complexity of a full pass through MultiwayMerge is Ο(n * ror ), i.e., log(ror times worse than just spanning all ranges in
turn. The output comes sorted (unstably) by less .

multiwayUnion(ror)

Computes the union of multiple ranges. The input ranges are passed
as a range of ranges and each is assumed to be sorted by less . Computation is done lazily, one union element at a time.
multiwayUnion(ror) is functionally equivalent to multiwayMerge(ror) .

setDifference(r1, r2)

Lazily computes the difference of r1 and r2 . The two ranges
are assumed to be sorted by less . The element types of the two
ranges must have a common type.

setIntersection(ranges)

Lazily computes the intersection of two or more input ranges ranges . The ranges are assumed to be sorted by less . The element
types of the ranges must have a common type.

setSymmetricDifference(r1, r2)

Lazily computes the symmetric difference of r1 and r2 ,
i.e. the elements that are present in exactly one of r1 and r2 . The two ranges are assumed to be sorted by less , and the
output is also sorted by less . The element types of the two
ranges must have a common type.

Structs
Name  Description 

MultiwayMerge

Merges multiple sets. The input sets are passed as a
range of ranges and each is assumed to be sorted by less . Computation is done lazily, one union element at a time. The
complexity of one popFront operation is Ο(log(ror ). However, the length of ror decreases as ranges
in it are exhausted, so the complexity of a full pass through MultiwayMerge is dependent on the distribution of the lengths of ranges
contained within ror . If all ranges have the same length n
(worst case scenario), the complexity of a full pass through MultiwayMerge is Ο(n * ror ), i.e., log(ror times worse than just spanning all ranges in
turn. The output comes sorted (unstably) by less .

SetDifference

Lazily computes the difference of r1 and r2 . The two ranges
are assumed to be sorted by less . The element types of the two
ranges must have a common type.

SetIntersection

Lazily computes the intersection of two or more input ranges ranges . The ranges are assumed to be sorted by less . The element
types of the ranges must have a common type.

SetSymmetricDifference

Lazily computes the symmetric difference of r1 and r2 ,
i.e. the elements that are present in exactly one of r1 and r2 . The two ranges are assumed to be sorted by less , and the
output is also sorted by less . The element types of the two
ranges must have a common type.

Authors
License
Copyright © 19992018 by the D Language Foundation  Page generated by ddox.