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.
Section: 27.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.
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.
Edit 27.2 [algorithms.requirements] p6-7 as indicated:
-6- The
-7- ThePredicate
parameter is used whenever an algorithm expects a function object (22.10 [function.objects]) that, when applied to the result of dereferencing the corresponding iterator, returns a value testable astrue
. In other words, if an algorithm takesPredicate pred
as its argument andfirst
as its iterator argument with value typeT
, it should work correctly in the constructpred(*first)
contextually converted tobool
(7.3 [conv]). The function objectpred
shall not apply any non-constant function through the dereferenced iterator. Given a glvalueu
of type (possiblyconst
)T
that designates the same object as*first
,pred(u)
shall be a valid expression that is equal topred(*first)
.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 typeT
whenT
is part of the signature returns a value testable astrue
. In other words, if an algorithm takesBinaryPredicate binary_pred
as its argument andfirst1
andfirst2
as its iterator arguments with respective value typesT1
andT2
, it should work correctly in the constructbinary_pred(*first1, *first2)
contextually converted tobool
(7.3 [conv]). Unless otherwise specified,BinaryPredicate
always takes the first iterator'svalue_type
as its first argument, that is, in those cases whenT value
is part of the signature, it should work correctly in the constructbinary_pred(*first1, value)
contextually converted tobool
(7.3 [conv]).binary_pred
shall not apply any non-constant function through the dereferenced iterators. Given a glvalueu
of type (possiblyconst
)T1
that designates the same object as*first1
, and a glvaluev
of type (possiblyconst
)T2
that designates the same object as*first2
,binary_pred(u, *first2)
,binary_pred(*first1, v)
, andbinary_pred(u, v)
shall each be a valid expression that is equal tobinary_pred(*first1, *first2)
, andbinary_pred(u, value)
shall be a valid expression that is equal tobinary_pred(*first1, value)
.
Edit 27.8 [alg.sorting] p2 as indicated:
Compare
is a function object type (22.10 [function.objects]) that meets the requirements for a template parameter namedBinaryPredicate
(27.2 [algorithms.requirements]). The return value of the function call operation applied to an object of typeCompare
, when contextually converted tobool
(7.3 [conv]), yieldstrue
if the first argument of the call is less than the second, andfalse
otherwise.Compare comp
is used throughout for algorithms assuming an ordering relation.It is assumed thatcomp
will not apply any non-constant function through the dereferenced iterator.