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: 25.8.7.4 [set.intersection], 25.8.7.5 [set.difference] Status: LEWG Submitter: Alexander Bessonov Opened: 2021-03-16 Last modified: 2021-04-24

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>;
```

[2021-04-20; Reflector poll]

Priority set to 3. Send to LEWG.

Proposed resolution:

This wording is relative to N4878.

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

```  […]

// 23.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 23.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 25.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 25.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.