C++ – How to Declare Operator < Before Using std::lexicographical_compare

c++c++20language-lawyer

The following code compiles before C++20:

#include <algorithm>
#include <vector>

struct Foo
{
};

struct FooArray
{
    std::vector<Foo> a;
};

bool operator<(const FooArray& a, const FooArray& b)
{
    return std::lexicographical_compare(std::begin(a.a), std::end(a.a), std::begin(b.a), std::end(b.a));
}

bool operator<(const Foo& a, const Foo& b)
{
    return false;
}

With c++20 enabled GCC 10 and 11 reject the code, but only when optimisations are enabled:

In file included from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:71,
                 from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/algorithm:61,
                 from <source>:1:
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = const Foo*; _Iterator2 = const Foo*]':
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:1240:14:   required from 'constexpr bool std::__lexicographical_compare_impl(_II1, _II1, _II2, _II2, _Compare) [with _II1 = const Foo*; _II2 = const Foo*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:1257:46:   required from 'static constexpr bool std::__lexicographical_compare<_BoolType>::__lc(_II1, _II1, _II2, _II2) [with _II1 = const Foo*; _II2 = const Foo*; bool _BoolType = false]'
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:1302:60:   required from 'constexpr bool std::__lexicographical_compare_aux(_II1, _II1, _II2, _II2) [with _II1 = const Foo*; _II2 = const Foo*]'
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:1605:48:   required from 'constexpr bool std::lexicographical_compare(_II1, _II1, _II2, _II2) [with _II1 = __gnu_cxx::__normal_iterator<const Foo*, std::vector<Foo> >; _II2 = __gnu_cxx::__normal_iterator<const Foo*, std::vector<Foo> >]'
<source>:15:40:   required from here
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'const Foo' and 'const Foo')
   43 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:67,
                 from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/algorithm:61,
                 from <source>:1:
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_iterator.h:1097:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL> __gnu_cxx::operator<=>(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)' (reversed)
 1097 |     operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_iterator.h:1097:5: note:   template argument deduction/substitution failed:
In file included from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:71,
                 from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/algorithm:61,
                 from <source>:1:
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/predefined_ops.h:43:23: note:   'const Foo' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   43 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:67,
                 from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/algorithm:61,
                 from <source>:1:
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_iterator.h:1114:5: note: candidate: 'template<class _Iterator, class _Container> constexpr std::__detail::__synth3way_t<_T1> __gnu_cxx::operator<=>(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)' (rewritten)
 1114 |     operator<=>(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_iterator.h:1114:5: note:   template argument deduction/substitution failed:
In file included from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/stl_algobase.h:71,
                 from /opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/algorithm:61,
                 from <source>:1:
/opt/compiler-explorer/gcc-10.5.0/include/c++/10.5.0/bits/predefined_ops.h:43:23: note:   'const Foo' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   43 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
<source>:13:6: note: candidate: 'bool operator<(const FooArray&, const FooArray&)'
   13 | bool operator<(const FooArray& a, const FooArray& b)
      |      ^~~~~~~~
<source>:13:32: note:   no known conversion for argument 1 from 'const Foo' to 'const FooArray&'
   13 | bool operator<(const FooArray& a, const FooArray& b)
      |                ~~~~~~~~~~~~~~~~^
Compiler returned: 1

GCC 12 and later compile the code. MSVC always compiles the code, clang rejects it when c++20 is enabled.

https://godbolt.org/z/9ra6hn7c9

Which compiler is correct? Does bool operator<(const Foo& a, const Foo& b) need to be declared before calling std::lexicographical_compare? Is this a change in c++20 or did the code just happen to work in c++17 (I was surprised the code wasn't causing problems in c++17 too)?

Best Answer

This is ill-formed no diagnostic required as per temp.param#7.

First note that there are two point of instantiations(POI). The first POI is at namespace scope just after operator<(const FooArray& a, const FooArray& b) as per temp.point:

For a function template specialization, a member function template specialization, or a specialization for a member function or static data member of a class template, if the specialization is implicitly instantiated because it is referenced from within another template specialization and the context from which it is referenced depends on a template parameter, the point of instantiation of the specialization is the point of instantiation of the enclosing specialization. Otherwise, the point of instantiation for such a specialization immediately follows the namespace scope declaration or definition that refers to the specialization.

The second POI is at the end of the translation unit.

Now as per temp.point#7:

A specialization for a class template has at most one point of instantiation within a translation unit. A specialization for any template may have points of instantiation in multiple translation units. If two different points of instantiation give a template specialization different meanings according to the one-definition rule, the program is ill-formed, no diagnostic required.

This means that the given program is IFNDR because it violates basic.def.odr:

In each such definition, the overloaded operators referred to, the implicit calls to conversion functions, constructors, operator new functions and operator delete functions, shall refer to the same function.

The above is violated because at the first POI, there is no operator< that we can refer to but at the second POI there is. So they don't refer to the same function.

The solution is to provide a declaration before first POI so that the referred to functions are the samea at both the POIs.

Related Question