oneapi::tbb::parallel_sort range overload - get the "range" argument by a forwarding reference

[ivankochin]

1. At the current moment (10 Oct. 2021), the parallel_sort algorithm has an overload for ranges with only the non-const lvalue argument.
2. We got the issue at GitHub (parallel_sort requires lvalue range, thus cannot be used rlavue ranges (which is a common use case in our codebase) #500) which asks for supporting passing arguments as an rvalue. One of the use cases is sorting views (like C++20 std::span).
3. The other use case is sorting rvalue ranges using a comparator with side effects.
4. Еhe closest standard interface to the parallel_sort overload for ranges is the std::ranges::sort() function template. The std::ranged::sort() gets the range argument by the forwarding reference. So it was decided to get the argument by the forwarding reference and then use perfect forwarding to get begin/end pair for this range.
5. The closest standard interface to the parallel_sort overload for ranges is the std::ranged::sort() function template. It uses std::ranges::begin()/end() to get iterators. But oneapi::tbb::parallel_sort ranges overload uses std::begin()/end().
6. There is the inconsistency between std::begin()/end() and C++20 std::ranges::begin()/end() interfaces: std::begin()/end() has only overloads for const and non-const lvalue references. std::ranges::begin() uses forwarding reference to call the corresponding obj.begin() method.
7. This inconsistency does not matter since the std::ranges::sort() calls the std::ranges::begin()/end() methods without passing the range without calling std::forward for the arguments, so the arguments passed to the std::ranges::begin()/end() are always lvalue.
8. Based on points 4-7 we can make a conclusion that there is no difference between using std::begin()/end() and std::ranges::begin()/end() in this case.

[akukanov]

As far as I understand, the change in PR #605 formally allows applying parallel_sort to const containers. I guess it will still result in compile-time error somewhere around the use of swap, but does not that worsen the diagnostics? Maybe it makes sense to add an explicitly deleted overload for const ranges, so that the rvalue overload is only applicable for temporaries?

[ivankochin]

The constant ranges are also the use case for this overload because some view-like containers (like std::span) may provide write access to the pointers even if the container is constant. Consider the following example:

int main() {
    std::array<int, 1> arr = {1};
    const std::span<int> sp = arr;

    *sp.begin() = 2;

    std::cout << arr[0] << std::endl; // prints 2
}

This example successfully compiles and prints 2. The span is constant there but it points to the non-const array, so begin() returns non-constant iterator.

[akukanov]

I find the "view-like containers" terminology confusing; a view does not hold/own any data, while a container does.
But I see the point - you say that a const view allows changing the data in its underlying container. OK, then restricting overloads is not a good option. Are there other ways to improve the diagnostics - e.g. require (through static assert or constraints) that std::begin() applied to the argument shall return a non-const iterator?

[ivankochin]

Yes, there are, we improved the diagnostic by the additional C++20 constraints requirements in this patch: #656