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.