Date: Wed, 10 Mar 2021 10:58:52 +0000

Well yes, this sounds like fun to argue about. I wonder what Tristan would

think.

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

std-proposals_at_[hidden]> wrote:

> I found myself using this code in the solving the task I can briefly

> summarize below:

>

> Imagine we have a map of the following kind:

>

> class ExpensiveFileObject { ... };

>

> std::map<std::string, ExpensiveFileObject> tracked_files;

>

> This container stores files “tracked” by the application. It maps a file

> path to the expensive-to-create object.

>

> Now we are given a list of file paths to stop tracking:

>

> void stop_tracking(std::vector<std::string> file_list)

> {

> std::ranges::sort(file_list);

>

> std::set_intersect(

> tracked_files.begin(),

> tracked_files.end(),

> file_list.begin(),

> file_list.end(),

> function_output_iterator{[](const std::pair<std::string,

> ExpensiveFileObject> &v) { v.second.stop_tracking(); },

> pair_with_string_comparison_functor{});

> }

>

> This code cannot currently be directly migrated to

> ranges::set_intersection algorithm. If we would, we would either had to do

> one of the following:

>

> 1. Convert file_list to a vector of pairs with dummy ExpensiveFileObject

> objects.

> 2. Call std::ranges::set_intersection(tracked_files | std::views::keys,

> file_list, ...) and do an extra map lookup on each hit.

> 3. Create a special output function iterator capable of taking both pair

> and string, just to “satisfy” an overly strict algorithm requirement.

>

> All these variants do not seem reasonable or effective.

>

> Sincerely,

> Alexander Bessonov

> HHD Software Ltd.

>

> *From:* Gašper Ažman

> *Sent:* Wednesday, March 10, 2021 11:47 AM

> *To:* Std-Proposals

> *Cc:* Alexander Bessonov

> *Subject:* Re: [std-proposals] ranges::set_intersection and

> ranges::set_difference requirements are too strict

>

> 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

>>

> --

> Std-Proposals mailing list

> Std-Proposals_at_[hidden]

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

>

think.

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

std-proposals_at_[hidden]> wrote:

> I found myself using this code in the solving the task I can briefly

> summarize below:

>

> Imagine we have a map of the following kind:

>

> class ExpensiveFileObject { ... };

>

> std::map<std::string, ExpensiveFileObject> tracked_files;

>

> This container stores files “tracked” by the application. It maps a file

> path to the expensive-to-create object.

>

> Now we are given a list of file paths to stop tracking:

>

> void stop_tracking(std::vector<std::string> file_list)

> {

> std::ranges::sort(file_list);

>

> std::set_intersect(

> tracked_files.begin(),

> tracked_files.end(),

> file_list.begin(),

> file_list.end(),

> function_output_iterator{[](const std::pair<std::string,

> ExpensiveFileObject> &v) { v.second.stop_tracking(); },

> pair_with_string_comparison_functor{});

> }

>

> This code cannot currently be directly migrated to

> ranges::set_intersection algorithm. If we would, we would either had to do

> one of the following:

>

> 1. Convert file_list to a vector of pairs with dummy ExpensiveFileObject

> objects.

> 2. Call std::ranges::set_intersection(tracked_files | std::views::keys,

> file_list, ...) and do an extra map lookup on each hit.

> 3. Create a special output function iterator capable of taking both pair

> and string, just to “satisfy” an overly strict algorithm requirement.

>

> All these variants do not seem reasonable or effective.

>

> Sincerely,

> Alexander Bessonov

> HHD Software Ltd.

>

> *From:* Gašper Ažman

> *Sent:* Wednesday, March 10, 2021 11:47 AM

> *To:* Std-Proposals

> *Cc:* Alexander Bessonov

> *Subject:* Re: [std-proposals] ranges::set_intersection and

> ranges::set_difference requirements are too strict

>

> 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

>>

> --

> Std-Proposals mailing list

> Std-Proposals_at_[hidden]

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

>

Received on 2021-03-10 04:59:06