C++ Logo

std-proposals

Advanced search

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

From: Jason McKesson <jmckesson_at_[hidden]>
Date: Wed, 10 Mar 2021 10:04:20 -0500
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.

Received on 2021-03-10 09:04:48