Date: Wed, 10 Mar 2021 08:47:27 +0000

I guess the main question here is whether we want the set algorithms to

share requirements or do we want all of them to be minimal.

According to some discussions on the topic by Alex Stepanov and Bjarne,

conceptual requirements shouldn't necessarily be minimal, they should be

sensible for the algebraic structure (or, you know, category) they operate

on.

On the other hand the engineering concerns you raise are also valid. Could

you give us a good example that removing this restriction would enable?

On Wed, Mar 10, 2021 at 7:55 AM Alexander Bessonov via Std-Proposals <

std-proposals_at_[hidden]> wrote:

> 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

> <http://en.cppreference.com/w/cpp/iterator/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.

> --

> Std-Proposals mailing list

> Std-Proposals_at_[hidden]

> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

>

share requirements or do we want all of them to be minimal.

According to some discussions on the topic by Alex Stepanov and Bjarne,

conceptual requirements shouldn't necessarily be minimal, they should be

sensible for the algebraic structure (or, you know, category) they operate

on.

On the other hand the engineering concerns you raise are also valid. Could

you give us a good example that removing this restriction would enable?

On Wed, Mar 10, 2021 at 7:55 AM Alexander Bessonov via Std-Proposals <

std-proposals_at_[hidden]> wrote:

> 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

> <http://en.cppreference.com/w/cpp/iterator/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.

> --

> Std-Proposals mailing list

> Std-Proposals_at_[hidden]

> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

>

Received on 2021-03-10 02:47:42