This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of LEWG status.

### 3534. `ranges::set_intersection` and `ranges::set_difference` algorithm requirements are too strict

Section: 27.8.7.4 [set.intersection], 27.8.7.5 [set.difference] Status: LEWG Submitter: Alexander Bessonov Opened: 2021-03-16 Last modified: 2021-04-20

Priority: 3

View all issues with LEWG status.

Discussion:

The `std::mergeable` concept requires elements of both source ranges to be copyable to the output iterator, while the standard specifically tells that both algorithms `ranges::set_intersection` and `ranges::set_difference` only use the first range as the source of elements to be copied into output. The following code snippet illustrates the problem:

>     #include <vector>
>     #include <ranges>
>     #include <algorithm>
>     #include <cassert>

>     int main()
>     {
>       std::vector<std::pair<int, int>> v1;
>       std::vector<int> v2;

>       assert(std::ranges::is_sorted(v1));
>       assert(std::ranges::is_sorted(v2));

>       std::vector<std::pair<int, int>> v3;

>       // Compilation error on the following line:
>       std::ranges::set_intersection(v1, v2, std::back_inserter(v3),
>         std::less{}, [](const auto& p) { return p.first; });
>     }

The proposed solution is to introduce a new concept. It could be declared "exposition-only" and is worded `half-mergeable` below:

>     template<class I1, class I2, class Out, class R = ranges::less,
>     	     class P1 = identity, class P2 = identity>
>       concept half-mergeable =
>         input_iterator<I1> &&
>         input_iterator<I2> &&
>         weakly_incrementable<Out> &&
>         indirectly_copyable<I1, Out> &&
>         // indirectly_copyable<I2, Out> && <— this line removed
>         indirect_strict_weak_order<R, projected<I1, P1>, projected<I2, P2>>;

After such template is introduced, `std::mergeable` may be defined based on it:

>     template<class I1, class I2, class Out, class R = ranges::less,
>     	     class P1 = identity, class P2 = identity>
>       concept mergeable = half-mergeable<I1, I2, Out, R, P1, P2> &&
>         indirectly_copyable<I2, Out>;

See also the related discussion on reddit.

[2021-04-20; Reflector poll]

Priority set to 3. Send to LEWG.

Proposed resolution:

This wording is relative to N4878.

1. Modify 25.2 [iterator.synopsis], header `<iterator>` synopsis, as indicated:

   >       […]

   >       // 25.3.7.7 [alg.req.mergeable], concept mergeable
   >       template<class I1, class I2, class Out,
   >           class R = ranges::less, class P1 = identity, class P2 = identity>
   >         concept half-mergeable = see below; // exposition only

   >       template<class I1, class I2, class Out,
   >           class R = ranges::less, class P1 = identity, class P2 = identity>
   >         concept mergeable = see below;

   >      […]

2. Modify 25.3.7.7 [alg.req.mergeable] as indicated:

   > 23.3.7.7 Concept `mergeable` [alg.req.mergeable]

   > -1- The `mergeable` concept specifies the requirements of algorithms that merge sorted sequences into an output sequence by copying elements.

   > >     template<class I1, class I2, class Out, class R = ranges::less,
   > >              class P1 = identity, class P2 = identity>
   > >       concept half-mergeable = // exposition only
   > >         input_iterator<I1> &&
   > >         input_iterator<I2> &&
   > >         weakly_incrementable<Out> &&
   > >         indirectly_copyable<I1, Out> &&
   > >         indirect_strict_weak_order<R, projected<I1, P1>, projected<I2, P2>>;

   > >     template<class I1, class I2, class Out, class R = ranges::less,
   > >              class P1 = identity, class P2 = identity>
   > >       concept mergeable =
   > >         half-mergeable<I1, I2, Out, R, P1, P2> &&
   > >         input_iterator<I1> &&
   > >         input_iterator<I2> &&
   > >         weakly_incrementable<Out> &&
   > >         indirectly_copyable<I1, Out> &&
   > >         indirectly_copyable<I2, Out> &&
   > >         indirect_strict_weak_order<R, projected<I1, P1>, projected<I2, P2>>;

3. Modify 27.8.7.4 [set.intersection] 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 half-mergeablemergeable<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 half-mergeablemergeable<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 = {});

   > > […]

   > > -6- Remarks: Stable (16.4.6.8 [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 `min(m, n)` elements are copied from the first range to the output range, in order.

4. Modify 27.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 half-mergeablemergeable<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 half-mergeablemergeable<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 = {});

   > > […]

   > > -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 `max(m - n, 0)` elements from `[first1, last1)` is copied to the output range, in order.