This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++20 status.

### 3031. Algorithms and predicates with non-const reference arguments

Section: 25.8 [alg.sorting] Status: C++20 Submitter: Jonathan Wakely Opened: 2017-11-08 Last modified: 2021-02-25

Priority: 2

View all other issues in [alg.sorting].

View all issues with C++20 status.

Discussion:

This doesn't compile with any major implementation:

>     int i[1] = { };
>     std::stable_sort(i, i, [](int& x, int& y) { return x < y; });

The problem is that the `Compare` expects non-const references. We say "It is assumed that `comp` will not apply any non-constant function through the dereferenced iterator" But that isn't sufficient to forbid the example.

My first thought was to modify [alg.sorting] to make the `Compare` requirements use `comp(as_const(x), as_const(x))` but that would get very verbose to add to every expression using `comp`.

[2017-11 Albuquerque Wednesday night issues processing]

Priority set to 2; Jonathan to improve the statement of the problem.

[2018-02 David Jones provided this truly awful example:]

>     #include <algorithm>
>     #include <iostream>
>     #include <vector>

>     struct Base {
>         Base(int value) : v(value) {}
>         friend bool operator<(const Base& l, const Base& r) { return l.v < r.v; }
>         int v;
>     };

>     struct Derived : public Base {
>         using Base::Base;
>         bool operator<(const Derived& o) /* no const here */ { return v > o.v; }
>     };

>     int main(void) {
>         std::vector<Base> b = {{1}, {5}, {0}, {3}};
>         std::vector<Derived> d = {{0}, {1}, {3}, {5}};

>         std::cout << std::lower_bound(d.begin(), d.end(), 4)->v << std::endl;

>         std::sort(b.begin(), b.end());
>         for (const auto &x : b) std::cout << x.v << " ";
>         std::cout << std::endl;

>         std::sort(d.begin(), d.end());
>         for (const auto &x : d) std::cout << x.v << " ";
>         std::cout << std::endl;
>     }

>     libc++:
>     =====
>     $ bin/clang++ -std=c++11 -stdlib=libc++ tmp/ex.cc && ./a.out
>     5
>     0 1 3 5
>     0 1 3 5
>     =====

>     libstdc++:
>     =====
>     $ bin/clang++ -std=c++11 -stdlib=libstdc++ tmp/ex.cc && ./a.out
>     0
>     0 1 3 5
>     5 3 1 0
>     =====

[2018-08 Batavia Monday issue discussion]

Tim to provide wording; status to 'Open'

[ 2018-08-20, Tim adds P/R based on Batavia discussion.]

Similar to the Ranges TS design, the P/R below requires `Predicate`, `BinaryPredicate`, and `Compare` to accept all mixes of `const` and non-`const` arguments.

[2018-08-23 Batavia Issues processing]

Status to Tentatively Ready after minor wording nit (corrected in place)

[2018-11, Adopted in San Diego]

Proposed resolution:

This wording is relative to N4762.

1. Edit 25.2 [algorithms.requirements] p6-7 as indicated:

   > -6- The `Predicate` parameter is used whenever an algorithm expects a function object (20.14 [function.objects]) that, when applied to the result of dereferencing the corresponding iterator, returns a value testable as `true`. In other words, if an algorithm takes `Predicate pred` as its argument and `first` as its iterator argument with value type `T`, it should work correctly in the construct `pred(*first)` contextually converted to `bool` (7.3 [conv]). The function object `pred` shall not apply any non-constant function through the dereferenced iterator. Given a glvalue `u` of type (possibly `const`) `T` that designates the same object as `*first`, `pred(u)` shall be a valid expression that is equal to `pred(*first)`.

   > -7- The `BinaryPredicate` parameter is used whenever an algorithm expects a function object that when applied to the result of dereferencing two corresponding iterators or to dereferencing an iterator and type `T` when `T` is part of the signature returns a value testable as `true`. In other words, if an algorithm takes `BinaryPredicate binary_pred` as its argument and `first1` and `first2` as its iterator arguments with respective value types `T1` and `T2`, it should work correctly in the construct `binary_pred(*first1, *first2)` contextually converted to `bool` (7.3 [conv]). Unless otherwise specified, `BinaryPredicate` always takes the first iterator's `value_type` as its first argument, that is, in those cases when `T value` is part of the signature, it should work correctly in the construct `binary_pred(*first1, value)` contextually converted to `bool` (7.3 [conv]). `binary_pred` shall not apply any non-constant function through the dereferenced iterators. Given a glvalue `u` of type (possibly `const`) `T1` that designates the same object as `*first1`, and a glvalue `v` of type (possibly `const`) `T2` that designates the same object as `*first2`, `binary_pred(u, *first2)`, `binary_pred(*first1, v)`, and `binary_pred(u, v)` shall each be a valid expression that is equal to `binary_pred(*first1, *first2)`, and `binary_pred(u, value)` shall be a valid expression that is equal to `binary_pred(*first1, value)`.

2. Edit 25.8 [alg.sorting] p2 as indicated:

   > `Compare` is a function object type (20.14 [function.objects]) that meets the requirements for a template parameter named `BinaryPredicate` (25.2 [algorithms.requirements]). The return value of the function call operation applied to an object of type `Compare`, when contextually converted to `bool` (7.3 [conv]), yields `true` if the first argument of the call is less than the second, and `false` otherwise. `Compare comp` is used throughout for algorithms assuming an ordering relation. It is assumed that `comp` will not apply any non-constant function through the dereferenced iterator.