Hello Everyone,

ranges::set_intersection and ranges::set_difference algorithms (among other set_* algorithms and ranges::merge) explicitly require its parameters to satisfy std::mergeable concept:

https://en.cppreference.com/w/cpp/algorithm/ranges/set_intersection
https://en.cppreference.com/w/cpp/algorithm/ranges/set_difference

https://en.cppreference.com/w/cpp/iterator/mergeable

Part of this concept requires that elements of the _second_ range must be copyable to the destination:

std::indirectly_copyable<I2, Out>

However, by definition of both these algorithms, they only ever copy elements of the first range. This prohibits useful scenarios like the one shown below:

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

struct comp
{
    bool operator()(int p1, const std::pair<int, int> &p2) const
    {
        return p1 < p2.first;
    }

    bool operator()(const std::pair<int, int> &p1, int p2) const
    {
        return p1.first < p2;
    }
};

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

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

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

    // The following line also gives compilation error (for the same reason):
    std::ranges::set_intersection(v1, v2, std::back_inserter(v3), comp{});
    
    // This one compiles:
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3), comp{});
}

It looks like the requirements for these two algorithms are too strict. Maybe the new concept, let’s call it “half_mergeable” has to be added for these two algorithms?

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

What do you think?

Sincerely,
Alexander Bessonov
HHD Software Ltd.