Display the source code in std/algorithm/setops.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.

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

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

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