Proposed resolution:

This wording is relative to N4762.

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

   -6- The Predicate parameter is used whenever an algorithm expects a function object ([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 ([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 ([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 ([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 [alg.sorting] p2 as indicated:

   Compare is a function object type ([function.objects]) that meets the requirements for a template parameter named BinaryPredicate ([algorithms.requirements]). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool ([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.

[ 2018-11, Adopted in San Diego ]

[ 2018-08-23 Batavia Issues processing ]

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

[ 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 Batavia Monday issue discussion ]

Tim to provide wording; status to 'Open'

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

[ 2017-11 Albuquerque Wednesday night issues processing ]

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

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.