This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Immediate status.
ranges::set_difference should return in_in_out_resultSection: 26.8.7.5 [set.difference] Status: Immediate Submitter: Ruslan Arutyunyan Opened: 2026-03-18 Last modified: 2026-03-25
Priority: Not Prioritized
View all issues with Immediate status.
Discussion:
Serial ranges::set_difference returns in_out_result, even though it takes two input ranges.
This is probably fine because it assumes that the output size is always sufficient for the
algorithms to write all necessary elements. We only need to go to the end of the first input
and we usually do not care where the second input stops even if we did not fully traverse it.
However, for parallel range algorithms the output size can be insufficient to have every single
element from input that fits. When the output has smaller size than the number of elements it
is supposed to take (based on the input), it should be useful for users to understand where
stop points are for both first and second inputs. Thus, we need to return in_in_out_result.
The algorithm should return the stop point of the first input, which is the first element that
has to be written to the output but doesn't fit and it should also return the stop point of the
second input, which is the element that was compared with the input1 element that does not
fit. Otherwise, the algorithm returns an iterator that compares equal with last2, for the
second input, meaning that it is already exhausted.
set_difference will also be beneficial if and when we are going
to add serial range algorithms with the range-as-the-output-design aspect. For the behavior
illustration purposes please look at the serial implementation of such algorithm:
template <class In1, class In2, class Out>
using set_difference_truncated_result = std::ranges::in_in_out_result<In1, In2, Out>;
struct set_difference_fn
{
template<std::input_iterator I1, std::sentinel_for<I1> S1,
std::input_iterator I2, std::sentinel_for<I2> S2,
std::input_iterator O, std::sentinel_for<O> OutS,
class Comp = std::ranges::less,
class Proj1 = std::identity, class Proj2 = std::identity>
requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_difference_truncated_result<I1, I2, O>
operator()(I1 first1, S1 last1, I2 first2, S2 last2,
O result, OutS result_last, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
while (!(first1 == last1 || first2 == last2))
{
if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
{
if (result == result_last)
break;
*result = *first1;
++first1;
++result;
}
else if (std::invoke(comp, std::invoke(proj2, *first2),
std::invoke(proj1, *first1)))
++first2;
else
{
++first1;
++first2;
}
}
while (first1 != last1 && result != result_last)
{
*result = *first1;
++first1;
++result;
}
return {first1, first2, result};
}
template<std::ranges::input_range R1, std::ranges::input_range R2,
std::ranges::input_range OR, class Comp = std::ranges::less,
class Proj1 = std::identity, class Proj2 = std::identity>
requires std::mergeable<std::ranges::iterator_t<R1>, std::ranges::iterator_t<R2>,
std::ranges::iterator_t<OR>, Comp, Proj1, Proj2>
constexpr set_difference_truncated_result<std::ranges::borrowed_iterator_t<R1>,
std::ranges::borrowed_iterator_t<R2>,formatPainter
std::ranges::borrowed_iterator_t<OR>>
operator()(R1&& r1, R2&& r2, OR&& result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
return (*this)(std::ranges::begin(r1), std::ranges::end(r1),
std::ranges::begin(r2), std::ranges::end(r2),
std::ranges::begin(result), std::ranges::end(result),
std::move(comp), std::move(proj1), std::move(proj2));
}
};
inline constexpr set_difference_fn set_difference{};
For instance, if the first input is std::vector v1{1, 2, 3, 4, 5, 6, 7}, the second input is
std::vector v2{3, 4, 7}, and the output is std::vector<int> output(3) then
for the call
auto [in1, in2, out] = std::ranges::set_difference(v1, v2, output);
output is {1, 2, 5}
in1 points to 6 in v1
in2 points to 7 in v2
out points to output.end()
Previous resolution [SUPERSEDED]:
This wording is relative to N5032.
Modify 26.4 [algorithm.syn], header
<algorithm>synopsis, as indicated:[…] namespace ranges { template<class I, class O> using set_difference_result = in_out_result<I, O>; template<class I1, class, I2, class O> using set_difference_truncated_result = in_in_out_result<I1, I2, O>; 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 set_difference_result<I1, O> 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 set_difference_result<borrowed_iterator_t<R1>, O> set_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> set_difference_truncated_result<I1, I2, O> set_difference(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // freestanding-deleted template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> set_difference_truncated_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // freestanding-deleted } […]Modify 26.8.7.5 [set.difference] as indicated:
[…] 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 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_difference_truncated_result<I1, I2, O> ranges::set_difference(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_difference_truncated_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});-1- Let: […]
-2- Preconditions: The ranges[first1, last1)and[first2, last2)are sorted with respect tocompandproj1orproj2, respectively. The resulting range does not overlap with either of the original ranges. -3- Effects: Constructs a sorted difference between the elements from the two ranges; that is, the set of elements that are present in the range[first1, last1)but not[first2, last2). If[first1, last1)containsmelements that are equivalent to each other and[first2, last2)containsnelements that are equivalent to them, the last max(m − n, 0)elements from[first1, last1)are included in the sorted difference, in order. Of those equivalent elements, the first min(m, n)elements in both ranges are considered skipped. An element from the second range is also considered skipped if it compares less than the min(N + 1, M)th element of the sorted difference. Copies the firstNelements of the sorted difference to the range[result, result + N). -4- Returns:
(4.1) —
result_lastfor the overloads in namespacestd.(4.2) —
For non-parallel algorithm overloads in namespace{last1, result + N}for the overloads in namespaceranges, ifNis equal toM.ranges:
(4.2.1) —
{last1, result + N}, ifNis equal toM.(4.2.2) — Otherwise,
{j1, result_last}, where the iteratorj1points to the position of the element in[first1, last1)corresponding to the(N + 1)th element of the sorted difference.(4.3) —
Otherwise,For parallel algorithm overloads in namespace{j1, result_last}for the overloads in namespaceranges, where the iteratorj1points to the position of the element in[first1, last1)corresponding to the(N + 1)th element of the sorted difference.ranges:
(4.3.1) —
{last1, first2 + B, result + N}, ifNis equal toM, whereBis the number of skipped elements in[first2, last2).(4.3.2) — Otherwise,
{ first1 + A, first2 + B, result_last}, whereAandBare the numbers of copied or skipped elements in[first1, last1)and[first2, last2), respectively.
[Croydon 2026-03-24; update wording after LWG review]
[Croydon 2026-03-24; move to Immediate]
Proposed resolution:
This wording is relative to N5032.
Modify 26.4 [algorithm.syn], header <algorithm> synopsis, as indicated:
[…]
namespace ranges {
template<class I, class O>
using set_difference_result = in_out_result<I, O>;
template<class I1, class, I2, class O>
using set_difference_truncated_result = in_in_out_result<I1, I2, O>;
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 set_difference_result<I1, O>
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 set_difference_result<borrowed_iterator_t<R1>, O>
set_difference(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
set_difference_truncated_result<I1, I2, O>
set_difference(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {},
Proj2 proj2 = {}); // freestanding-deleted
template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
sized-random-access-range OutR, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
set_difference_truncated_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}); // freestanding-deleted
}
[…]
Modify 26.8.7.5 [set.difference] as indicated:
[…] 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 = {}); template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2, sized_sentinel_for<I2> S2, random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_difference_truncated_result<I1, I2, O> ranges::set_difference(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2, sized-random-access-range OutR, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_difference_truncated_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>> ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});-1- Let: […]
-2- Preconditions: The ranges[first1, last1)and[first2, last2)are sorted with respect tocompandproj1orproj2, respectively. The resulting range does not overlap with either of the original ranges. -3- Effects: Constructs a sorted difference between the elements from the two ranges; that is, the set of elements that are present in the range[first1, last1)but not[first2, last2). If[first1, last1)containsmelements that are equivalent to each other and[first2, last2)containsnelements that are equivalent to them, the last max(m − n, 0)elements from[first1, last1)are included in the sorted difference, in order. Of those equivalent elements, the first min(m, n)elements in both ranges are considered skipped. An element from the second range is also considered skipped if it compares less than the min(N + 1, M)th element of the sorted difference. Copies the firstNelements of the sorted difference to the range[result, result + N). -4- Returns:
(4.1) —
result_lastfor the overloads in namespacestd.(4.2) —
{last1, result + N}for the non-parallel overloads in namespaceranges, ifNis equal toM.(4.3) —
Otherwise,For the parallel algorithm overloads in namespace{j1, result_last}for the overloads in namespaceranges, where the iteratorj1points to the position of the element in[first1, last1)corresponding to the(N + 1)th element of the sorted difference.ranges:
(4.3.1) —
{last1, first2 + B, result + N}, ifNis equal toM, whereBis the number of skipped elements in[first2, last2).(4.3.2) — Otherwise,
{ first1 + A, first2 + B, result_last}, whereAandBare the numbers of copied or skipped elements in[first1, last1)and[first2, last2), respectively.