Module std.algorithm.setops

This is a submodule of std.algorithm. It contains generic algorithms that implement set operations.

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.
nWayUnion	Computes the union of a set of sets implemented as 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.
setUnion	Lazily computes the set union of two or more sorted ranges.

Functions

Name	Description
cartesianProduct	Lazily computes the Cartesian product of two or more ranges. The product is a range of tuples of elements from each respective range.
largestPartialIntersection	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	Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.
nWayUnion	Computes the union of 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 NWayUnion 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 NWayUnion 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.
setUnion	Lazily computes the union of two or more ranges rs. The ranges are assumed to be sorted by less. Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The length member is offered if all ranges also have length.) The element types of all ranges must have a common type.

Structs

Name	Description
NWayUnion	Computes the union of 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 NWayUnion 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 NWayUnion 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.
SetUnion	Lazily computes the union of two or more ranges rs. The ranges are assumed to be sorted by less. Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The length member is offered if all ranges also have length.) The element types of all ranges must have a common type.

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments