https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82891
Bug ID: 82891
Summary: stable_sort() won't compile with function object that
takes parameters by non-const reference
Product: gcc
Version: 8.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: TonyELewis at hotmail dot com
Target Milestone: ---
This fails to compile:
~~~
#include <algorithm>
#include <vector>
int main() {
std::vector<int> a = { 5, 7, 1, 4, 1, 4, 2 };
std::stable_sort(
std::begin( a ),
std::end ( a ),
[] (int &x, int &y) { return x < y; }
);
}
~~~
...but works with std::sort(). The problem is that libstdc++ is trying to call
the function object with a const int (&), which the compiler can't bind a
non-const reference to.
Yet I suspect this code is valid. In point 9 (P896-897) of $25.1 of the C++14
draft at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf, it
says:
> 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, it should
> work correctly in the construct binary_pred(*first1, *first2) contextually
> converted to bool (Clause 4).
> 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 (Clause 4). binary_pred shall not apply
> any non-constant function
> through the dereferenced iterators.
I'm not versed in standardese but I understand the middle part of this as
saying that an implementation of the standard library should work with any
predicate that can take dereferenced iterators as arguments and can be called
in a bool context (so long as it meets other specific requirements).
The errors on GodBolt are:
> In file included from
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:71:0,
> from
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/algorithm:61,
> from <source>:1:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:
> In instantiation of 'bool
> __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&)
> [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >;
> _Value = const int; _Compare = main()::<lambda(int&, int&)>]':
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:959:14:
> required from '_ForwardIterator std::__lower_bound(_ForwardIterator,
> _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator =
> __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Tp = int; _Compare =
> __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2501:26:
> required from 'void std::__merge_without_buffer(_BidirectionalIterator,
> _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance,
> _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<int*,
> std::vector<int> >; _Distance = long int; _Compare =
> __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2772:34:
> required from 'void std::__inplace_stable_sort(_RandomAccessIterator,
> _RandomAccessIterator, _Compare) [with _RandomAccessIterator =
> __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare =
> __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5004:28:
> required from 'void std::__stable_sort(_RandomAccessIterator,
> _RandomAccessIterator, _Compare) [with _RandomAccessIterator =
> __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare =
> __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5075:36:
> required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with
> _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare =
> main()::<lambda(int&, int&)>]'
> 10 : <source>:10:2: required from here
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11:
> error: no match for call to '(main()::<lambda(int&, int&)>) (int&, const
> int&)'
> { return bool(_M_comp(*__it, __val)); }
> ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11:
> note: candidate: 'bool (*)(int&, int&)' <conversion>
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11:
> note: conversion of argument 3 would be ill-formed:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11:
> error: binding reference of type 'int&' to 'const int' discards qualifiers
> 9 : <source>:9:21: note: candidate: 'main()::<lambda(int&, int&)>' <near
> match>
> [] (int &x, int &y) { return x < y; }
> ^
> 9 : <source>:9:21: note: conversion of argument 2 would be ill-formed:
> In file included from
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:71:0,
> from
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/algorithm:61,
> from <source>:1:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:177:11:
> error: binding reference of type 'int&' to 'const int' discards qualifiers
> { return bool(_M_comp(*__it, __val)); }
> ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:
> In instantiation of 'bool
> __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator)
> [with _Value = const int; _Iterator = __gnu_cxx::__normal_iterator<int*,
> std::vector<int> >; _Compare = main()::<lambda(int&, int&)>]':
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2052:14:
> required from '_ForwardIterator std::__upper_bound(_ForwardIterator,
> _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator =
> __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Tp = int; _Compare =
> __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2510:26:
> required from 'void std::__merge_without_buffer(_BidirectionalIterator,
> _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance,
> _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<int*,
> std::vector<int> >; _Distance = long int; _Compare =
> __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:2772:34:
> required from 'void std::__inplace_stable_sort(_RandomAccessIterator,
> _RandomAccessIterator, _Compare) [with _RandomAccessIterator =
> __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare =
> __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5004:28:
> required from 'void std::__stable_sort(_RandomAccessIterator,
> _RandomAccessIterator, _Compare) [with _RandomAccessIterator =
> __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare =
> __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algo.h:5075:36:
> required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with
> _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare =
> main()::<lambda(int&, int&)>]'
> 10 : <source>:10:2: required from here
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11:
> error: no match for call to '(main()::<lambda(int&, int&)>) (const int&,
> int&)'
> { return bool(_M_comp(__val, *__it)); }
> ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11:
> note: candidate: 'bool (*)(int&, int&)' <conversion>
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11:
> note: conversion of argument 2 would be ill-formed:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11:
> error: binding reference of type 'int&' to 'const int' discards qualifiers
> 9 : <source>:9:21: note: candidate: 'main()::<lambda(int&, int&)>' <near
> match>
> [] (int &x, int &y) { return x < y; }
> ^
> 9 : <source>:9:21: note: conversion of argument 1 would be ill-formed:
> In file included from
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/stl_algobase.h:71:0,
> from
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/algorithm:61,
> from <source>:1:
> /opt/compiler-explorer/gcc-trunk-20171106/include/c++/8.0.0/bits/predefined_ops.h:215:11:
> error: binding reference of type 'int&' to 'const int' discards qualifiers
> { return bool(_M_comp(__val, *__it)); }
> ^~~~~~~~~~~~~~~~~~~~~~~~~~~
> Compiler exited with result code 1
On a 6.2.0 version of the library, I have been able to get it to compile
cleanly by switching a few bits of code to perfect forward...
stl_algobase.h
~~~.diff
947c947
< const _Tp& __val, _Compare __comp)
---
> _Tp&& __val, _Compare __comp)
959c959
< if (__comp(__middle, __val))
---
> if (__comp(__middle, forward<_Tp>(__val)))
~~~
stl_algo.h
~~~.diff
2037c2037
< const _Tp& __val, _Compare __comp)
---
> _Tp&& __val, _Compare __comp)
2049c2049
< if (__comp(__val, __middle))
---
> if (__comp(forward<_Tp>(__val), __middle))
~~~
