C++ Logo

std-proposals

Advanced search

Re: ranges::set_intersection and ranges::set_difference requirements are too strict

From: Alexander Bessonov <alexbav_at_[hidden]>
Date: Wed, 10 Mar 2021 18:35:19 +0300
I thought STL was about the reuse of algorithms: "that's a rotate!",
remember? :)

What makes me sad is that set algorithms being promoted to "ranges"-version
became more strict than their original "std" variants.

BTW, the same is with sort/is_sorted:

// legacy code
struct A
{
};

bool operator <(const A &a1, const A &a2) { ... }
std::vector<A> c;
// end of legacy code

std::sorted(c.begin(), c.end());

The last line being changed to

std::ranges::sort(c);

does not compile anymore. ranges::less is also unnecessary strict (in this
case), but at least you can pass a std::less{} instead.

This is off-topic, of course.


Sincerely,
Alexander Bessonov
HHD Software Ltd.
-----Original Message-----
From: Jason McKesson via Std-Proposals
Sent: Wednesday, March 10, 2021 6:04 PM
To: std-proposals_at_[hidden]
Cc: Jason McKesson
Subject: Re: [std-proposals] ranges::set_intersection and
ranges::set_difference requirements are too strict

On Wed, Mar 10, 2021 at 5:41 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.

It seems to me that this ought to be a different *function*. You don't
seem to be doing a "set intersection" operation. What you're doing is
just "for each key matching the ordered sequence", only more
efficiently since you sorted the sequence of keys before starting. And
you use the comparison functor to make the asymmetric comparison
between the values of the map work with the values of the key
sequence.

I think a more specific "map_over_keys" kind of function would seem to
be more appropriate.
-- 
Std-Proposals mailing list
Std-Proposals_at_[hidden]
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals 

Received on 2021-03-10 09:35:36