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