11 Algorithms library [algorithms]

11.5 Sorting and related operations [alg.sorting]

11.5.5 Set operations on sorted structures [alg.set.operations]

This section defines all the basic set operations on sorted structures. They also work with multisets ( ISO/IEC 14882:2014 §[multiset]) containing multiple copies of equivalent elements. The semantics of the set operations are generalized to multisets in a standard way by defining set_union() to contain the maximum number of occurrences of every element, set_intersection() to contain the minimum, and so on.

11.5.5.1 includes [includes]

template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, class Proj1 = identity, class Proj2 = identity, IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>> bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, class Proj1 = identity, class Proj2 = identity, IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>> Comp = less<>> bool includes(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

Returns: true if [first2,last2) is empty or if every element in the range [first2,last2) is contained in the range [first1,last1). Returns false otherwise.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.

11.5.5.2 set_union [set.union]

template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<I1, I2, O, Comp, Proj1, Proj2> tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)> set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2> tagged_tuple<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>), tag::out(O)> set_union(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

Effects: Constructs a sorted union of the elements from the two ranges; that is, the set of elements that are present in one or both of the ranges.

Requires: The resulting range shall not overlap with either of the original ranges.

Returns: make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result + n),
where n is the number of elements in the constructed range.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.

Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, then all m elements from the first range shall be copied to the output range, in order, and then max(n - m, 0) elements from the second range shall be copied to the output range, in order.

11.5.5.3 set_intersection [set.intersection]

template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<I1, I2, O, Comp, Proj1, Proj2> O set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2> O set_intersection(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements that are present in both of the ranges.

Requires: The resulting range shall not overlap with either of the original ranges.

Returns: The end of the constructed range.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.

Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, the first min(m, n) elements shall be copied from the first range to the output range, in order.

11.5.5.4 set_difference [set.difference]

template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<I1, I2, O, Comp, Proj1, Proj2> tagged_pair<tag::in1(I1), tag::out(O)> set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2> tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::out(O)> set_difference(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

Effects: Copies the elements of the range [first1,last1) which are not present in the range [first2,last2) to the range beginning at result. The elements in the constructed range are sorted.

Requires: The resulting range shall not overlap with either of the original ranges.

Returns: {last1, result + n}, where n is the number of elements in the constructed range.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.

Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, the last max(m - n, 0) elements from [first1,last1) shall be copied to the output range.

11.5.5.5 set_symmetric_difference [set.symmetric.difference]

template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<I1, I2, O, Comp, Proj1, Proj2> tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)> set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity> requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2> tagged_tuple<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>), tag::out(O)> set_symmetric_difference(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

Effects: Copies the elements of the range [first1,last1) that are not present in the range [first2,last2), and the elements of the range [first2,last2) that are not present in the range [first1,last1) to the range beginning at result. The elements in the constructed range are sorted.

Requires: The resulting range shall not overlap with either of the original ranges.

Returns: make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result + n),
where n is the number of elements in the constructed range.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 applications of the comparison function and projections.

Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2,last2) contains n elements that are equivalent to them, then |m - n| of those elements shall be copied to the output range: the last m - n of these elements from [first1,last1) if m > n, and the last n - m of these elements from [first2,last2) if m < n.