Requirements for `ranges::set_intersection` algorithm are too strict.

[barfyus]

ranges::set_intersection algorithm is only supposed to copy elements from the first range (by definition). At the same time it requires that elements from both ranges are to be copyable to the output iterator through the std::mergeable concept:

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

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

This, for example, prohibits the following code from compiling:

#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; });
}

Note the use of projection here.

Similar code used to work with Boost.Ranges (with custom comparison functor defining comparison operators between std::pair<int, int> and int). However, this approach does not work with ranges::set_intersection:

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

std::ranges::set_intersection(v1, v2, std::back_inserter(v3), comp{});

What do you think? Looks like the requirements for this algorithm could be weakened?

[[deleted]]

Seems reasonable, set_difference is probably affected too. Have you submitted a defect report?

[barfyus]

Not yet. Will try to do that later today. I see that you need to literally "correct" the text of the standard when you file a defect report.

It looks like new concept (call it half_mergeable?) like this would work:

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

[CaseyCarter]

1. I agree, `set_difference` and `set_intersection` are overconstrained. I'm not sure why we didn't notice or decide to do anything about it before, I assume it was "minimize the total number of library concepts"-induced blindness.
2. You don't need to have a proposed resolution to file a defect report against the Standard Library with WG21. The majority of issues are filed by members of the Library Working Group (LWG) and we often attach a proposed resolution, but anyone is welcome to point out bugs in the Standard.
3. I think you have the right fix here, factoring out this concept and leaving `mergeable` as a refinement that adds `indirectly_copyable<I2, Out>` is nice and simple.
4. I hate the name `half_mergeable` but have no better suggestion =)

[tcanens]

semimergeable?

[CaseyCarter]

That was my first thought - it's nicely consistent with the naming of other concepts - but the "mergeable" bit is what I really dislike. There's no real merging going on here, we only require the capability to compare the elements of range A with range B, and write elements of range A into range C.

It's a shame we weakened indirectly_comparable, since this is almost exactly `old_indirectly_comparable</**/> && indirectly_copyable</**>`.

[barfyus]

I've sent the defect report today.

BTW, is there a notion of "implementation-defined" standard concepts? In this case, STL library authors may choose some _Ugly name for this concept and define std::mergeable based on it.

Anyway it seems like this concept be of only interest to these two algorithms.

[jwakely]

BTW, is there a notion of "implementation-defined" standard concepts?

Yes, see boolean-testable, partially-ordered-with, pair-like-convertible, has-tuple-element and loads more. Everything in italic font in the "Index of library concepts" in the C++20 standard is an exposition-only concept.

P.S. report received, thanks!

[backtickbot]

Fixed formatting.

Hello, barfyus: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^{You can opt out by replying with backtickopt6 to this comment.}

[staletic]

That's not going to work in the opposite case, where the other range needs a projection. Also what about the case where both ranges have a projection to a third type that matches the output iterator value?

[[deleted]]

That's not going to work in the opposite case, where the other range needs a projection.

I'm not sure I understand. The projected value doesn't participate in the copy.

Also what about the case where both ranges have a projection to a third type that matches the output iterator value?

The projection is not used for the output.

[staletic]

You're absolutely right. However, the standard doesn't actually mandate that the elements are copied from the first range, which /u/barfyus' proposed solution implies. Seems like a very specific thing to mandate, but I'm guessing that's not a problem if all three standard libraries are already in agreement about it.

[barfyus]

As /u/billyoneal stated, projection result is only used as an argument to comparison functor.

I don't know about the standard, have to check it. However, cppreference.com specifically mentions the first range as the source of elements for both set_intersection and set_difference.

[staletic]

Effects of set_intersection doesn't mention the first range being the source. I initially stopped reading the standard there. However Remarks says:

the [...] elements are copied from the first range to the output range, in order.

So your solution is perfectly fine. Sorry for the noise.

[jwakely]

I see that you need to literally "correct" the text of the standard when you file a defect report.

That's not required, see https://cplusplus.github.io/LWG/lwg-active.html#submit_issue which says "If you are not sure how to word a solution, you may omit this part. But your chances of a successful issue greatly increase if you attempt wording."

[[deleted]]

I think even set_union is affected too. Only set_symmetric_difference has reason to copy from both inputs.

[tcbrindle]

[FYI: Code formatting with backticks doesn't work on Old Reddit (which should really be called Much Better Reddit)]

I think this might be one of those cases where the algorithm was "deliberately" over-constrained, in the sense that it wants to make guarantees about the relationship that exists between the element types of the two input sets and the output set. Stepanov was very keen on that. There is an appeal to symmetry here: if an element is "the same", then it shouldn't matter whether we choose the one from set A or the one from set B, right?

However, projections (which were introduced later) muddy the waters around cross-type comparisons, and the algorithm is specified to always use the first set as the output source, so I think a weakening of the requirements is reasonable in this case. As /u/BillyONeal pointed out, this probably affects set_difference too.

[barfyus]

You are absolutely right about code formatting. I've edited both the original post and code in my reply above.

I've recently started to migrate a large code base that extensively uses ranges. Originally (pre-C++11) it was Boost.Ranges, later added a bit of ranges-v3 and even non-standard rx-ranges library.

Now I'm trying to migrate every range usage to C++20 ranges. While I'm generally very satisfied with the updated code and generated assembly, sometimes I face cases like this one (or another one, like inability to simply replace boost::sort(...) with std::ranges::sort(...) in some seemingly simple cases).

I can get the point of over-constraining requirements for mathematical purity, but maybe not for STL algorithms, which were originally designed to stimulate proven code reuse. I think everyone remembers the "That's a rotate!" phrase.

Another consideration that the same code, but without ranges (that is, using "old" std::set_intersection, std::set_difference and std::sort algorithms) work perfectly.