Proposed resolution:

This wording is relative to N4878.

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

     […]
     
     // [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 [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 [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 ([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 [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.

[ 2021-04-20; Reflector poll ]

Priority set to 3. Send to LEWG.

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.