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

3031. Algorithms and predicates with non-const reference arguments

Section: 23.7 [alg.sorting] Status: New Submitter: Jonathan Wakely Opened: 2017-11-08 Last modified: 2018-03-03

Priority: 2

View all other issues in [alg.sorting].

View all issues with New 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 
=====

Proposed resolution: