25 Algorithms library [algorithms]

25.8 Sorting and related operations [alg.sorting]

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

1
#
This subclause defines all the basic set operations on sorted structures.
They also work with multisets ([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.

25.8.6.1 includes [includes]

🔗
template<class InputIterator1, class InputIterator2> constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class InputIterator1, class InputIterator2, class Compare> constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare> bool includes(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, class Proj1 = identity, class Proj2 = identity, indirect_­strict_­weak_­order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less> constexpr bool ranges::includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, class Proj1 = identity, class Proj2 = identity, indirect_­strict_­weak_­order<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Comp = ranges::less> constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let comp be less{}, proj1 be identity{}, and proj2 be identity{}, for the overloads with no parameters by those names.
2
#
Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.
3
#
Returns: true if and only if [first2, last2) is a subsequence of [first1, last1).
[ Note
:
A sequence S is a subsequence of another sequence T if S can be obtained from T by removing some, all, or none of T's elements and keeping the remaining elements in the same order.
— end note
 ]
4
#
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

25.8.6.2 set_­union [set.union]

🔗
template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_union(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_union_result<I1, I2, O> ranges::set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.
2
#
Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.
The resulting range does not overlap with either of the original ranges.
3
#
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.
4
#
Returns: Let result_­last be the end of the constructed range.
Returns
  • (4.1)
    result_­last for the overloads in namespace std.
  • (4.2)
    {last1, last2, result_­last} for the overloads in namespace ranges.
5
#
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
6
#
Remarks: Stable ([algorithm.stable]).
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 are copied to the output range, in order, and then the final elements from the second range are copied to the output range, in order.

25.8.6.3 set_­intersection [set.intersection]

🔗
template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_intersection(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_intersection_result<I1, I2, O> ranges::set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::set_intersection(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.
2
#
Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.
The resulting range does not overlap with either of the original ranges.
3
#
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.
4
#
Returns: Let result_­last be the end of the constructed range.
Returns
  • (4.1)
    result_­last for the overloads in namespace std.
  • (4.2)
    {last1, last2, result_­last} for the overloads in namespace ranges.
5
#
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
6
#
Remarks: Stable ([algorithm.stable]).
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 elements are copied from the first range to the output range, in order.

25.8.6.4 set_­difference [set.difference]

🔗
template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<I1, O> ranges::set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O> ranges::set_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.
2
#
Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.
The resulting range does not overlap with either of the original ranges.
3
#
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.
4
#
Returns: Let result_­last be the end of the constructed range.
Returns
  • (4.1)
    result_­last for the overloads in namespace std.
  • (4.2)
    {last1, result_­last} for the overloads in namespace ranges.
5
#
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
6
#
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 elements from [first1, last1) is copied to the output range, in order.

25.8.6.5 set_­symmetric_­difference [set.symmetric.difference]

🔗
template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_symmetric_difference(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_symmetric_difference_result<I1, I2, O> ranges::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.
2
#
Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.
The resulting range does not overlap with either of the original ranges.
3
#
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.
4
#
Returns: Let result_­last be the end of the constructed range.
Returns
  • (4.1)
    result_­last for the overloads in namespace std.
  • (4.2)
    {last1, last2, result_­last} for the overloads in namespace ranges.
5
#
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
6
#
Remarks: Stable ([algorithm.stable]).
If [first1, last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, then of those elements shall be copied to the output range: the last of these elements from [first1, last1) if , and the last of these elements from [first2, last2) if .
In either case, the elements are copied in order.