ranges::set_intersection and ranges::set_difference algorithm requirements are too strictSection: 26.8.7.4 [set.intersection], 26.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.
Modify 24.2 [iterator.synopsis], header <iterator> synopsis, as indicated:
[…] // 24.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; […]
Modify 24.3.7.7 [alg.req.mergeable] as indicated:
23.3.7.7 Concept
-1- Themergeable[alg.req.mergeable]mergeableconcept 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>>;
Modify 26.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)containsmelements that are equivalent to each other and[first2, last2)containsnelements that are equivalent to them, the firstmin(m, n)elements are copied from the first range to the output range, in order.
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 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)containsmelements that are equivalent to each other and[first2, last2)containsnelements that are equivalent to them, the lastmax(m - n, 0)elements from[first1, last1)is copied to the output range, in order.