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 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.

Module std.algorithm.setops

This is a submodule of std.algorithm. 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.

Cheat Sheet
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 per-value 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

NameDescription
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.length 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.length)). 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.length * log(ror.length)), i.e., log(ror.length) 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).uniq.
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

NameDescription
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.length)). 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.length * log(ror.length)), i.e., log(ror.length) 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

Andrei Alexandrescu

License

Boost License 1.0.