[patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

[Dropping gcc-patches@ from the CC list.]

On 24/01/15 22:46 +0000, Jonathan Wakely wrote:
>On 24/01/15 23:03 +0100, François Dumont wrote:
>>@@ -1155,9 +1150,8 @@
>>	  return _S_iter(__y);
>>	}
>>
>>-      template<typename _Kt,
>>-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
>>-	iterator
>>+      template<typename _Kt>
>>+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
>>	_M_find_tr(const _Kt& __k)
>
>This doesn't work.
>
>Consider:
>
> #include <set>
>
> struct I
> {
>   int i;
>   operator int() const { return i; }
> };
>
> int main()
> {
>   std::set<int> s;
>   I i = { };
>   s.find(i);
> }
>
>(I will add something like this to the testsuite.)
>
>This program is valid according to any C++ standard, but fails to
>compile with your patch applied because overload resolution
>instantiates std::_Rb_tree<>::_M_find_tr<I> which instantiates
>enable_if<false, iterator>::type, which is an error. SFINAE does not
>apply, because the invalid type enable_if<false, iterator>::type is
>not found during *substitution*. It's just invalid, so when _Compare
>is not transparent, instantiating the function template is simply an
>error.

Here's a simpler example explaining the problem:

  #include <type_traits>

  template<typename T>
  struct trait : std::false_type
  { };

  template<typename T>
  struct X {
    template<typename U>
      typename std::enable_if<trait<T>::value, int>::type
      f() { return 1; }

    int f() const { return 0; }
  };

  int main()
  {
    const X<int> x{};
    return x.f();
  }

Obviously this should call the non-template X<int>::f(), but overload
resolution tries to instantiate the template X<int>::f<U>() but that
uses the invalid type enable_if<false, int>::type. At the point where
the invalid type is discovered we haven't even deduced U yet, let
alone attempted substituting the deduced type into the template, so
this is not a substition failure.

>Observe that my __is_transparent alias template takes two template
>arguments, so that it depends on the template parameter of the
>function, not only on _Compare. That means whether if the type is
>invalid that will be found during template argument substitution, so
>SFINAE applies.

The equivalent fix to the example above would be:

  template<typename T, typename U> // !!! second parameter
  struct trait : std::false_type
  { };

  template<typename T>
  struct X {
    template<typename U>
      typename std::enable_if<trait<T, U>::value, int>::type
      f() { return 1; }

    int f() const { return 0; }
  };

Now the compiler doesn't know whether enable_if<>::type is valid or
not until after deducing and substituting U (which never happens
at all in the example because U can't be deduced in the x.f() call).