55

What is wrong in this code?

#include <map>

template<typename T>
struct TMap
{
    typedef std::map<T, T> Type;
};

template<typename T>
T test(typename TMap <T>::Type &tmap_) { return 0.0; }

int _tmain(int argc, _TCHAR* argv[])
{
    TMap<double>::Type tmap;
    tmap[1.1] = 5.2;
    double d = test(tmap); //Error: could not deduce template argument for T
    return 0;
}
Rakete1111
  • 47,013
  • 16
  • 123
  • 162
Johnas
  • 1,263
  • 3
  • 12
  • 23

4 Answers4

91

That is non-deducible context. That is why the template argument cannot be deduced by the compiler.

Just imagine if you might have specialized TMap as follows:

template <>
struct TMap<SomeType>
{
    typedef std::map <double, double> Type;
};

How would the compiler deduce the type SomeType, given that TMap<SomeType>::Type is std::map<double, double>? It cannot. It's not guaranteed that the type which you use in std::map is also the type in TMap. The compiler cannot make this dangerous assumption. There may not any relation between the type arguments, whatsoever.

Also, you might have another specialization of TMap defined as:

template <>
struct TMap<OtherType>
{
    typedef std::map <double, double> Type;
};

This makes the situation even worse. Now you've the following:

  • TMap<SomeType>::Type = std::map<double, double>.
  • TMap<OtherType>::Type = std::map<double, double>.

Now ask yourself: given TMap<T>::Type is std::map<double, double>, how would the compiler know whether T is SomeType or OtherType? It cannot even know how many such choices it has, neither can it know the choices themselves...

I'm just asking you for the sake of thought-experiment (assuming it can know the complete set of choices).

Rakete1111
  • 47,013
  • 16
  • 123
  • 162
Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • 13
    Superb answer. This problem has tripped me up repeatedly and I took a very long time to understand why it’s impossible to deduce the context. Your short example shows this perfectly. – Konrad Rudolph May 19 '11 at 15:18
  • 2
    So I have to write: double d = test(tmap) ? – Johnas May 19 '11 at 15:28
  • 1
    if only, I could give this answer +10. So thorough and precise answer, compared to the complexity of the topic. – Ramadheer Singh May 19 '11 at 18:54
  • 6
    This is essentially an inverse-function problem: Given an output value, you're asking for the input point at which your function takes that value. However, functions aren't invertible in general, so the question doesn't even exist unless you require your function to be an invertible one. In the template scenario, the corresponding requirement would be that all templates have globally unique member names; a requirement that C++ does not make. – Kerrek SB Oct 28 '11 at 10:47
  • @KerrekSB - Am I correct that the corresponding requirement that you mention would be (more precisely) that all templates of the same **name** (i.e., including all specializations) have member names that are unique within the set of specializations + default? And, to follow up, is it correct that the only reason the line of code in the question is not possible is due to the possibility of template specializations, or are there other reasons? – Dan Nissenbaum Nov 10 '12 at 17:02
  • @DanNissenbaum: No, this is much more basic. Imagine you have `struct Foo { typedef int type; typedef char bogus; };` and `stuct Bar { typedef int type; typedef double bogus; };`. Now you want to specialize on `T::type = int` and use `T::bogus`. It just makes no sense. – Kerrek SB Nov 10 '12 at 18:09
  • @Nawaz: +1 for great answer! In the declaration of TMap, the T template parameter is supposed to be the same inside the TMap scope declaration, right? So I don't manage to understand why the reason is not the possiblity of template specializations. Could you explain please? Thanks! – aldeb Jun 25 '13 at 10:31
  • @segfolt: I didn't understand your question. Can you rephrase your question? – Nawaz Jun 25 '13 at 11:34
  • @Nawaz: How is it possible that the template parameter `T` in `typedef std::map Type;` and the one in `template struct TMap` can be differents? I mean it seems obvious to me that if you call the `test` function with an argument of type `TMap::Type` (`tmap` in the OP's example) then the prototype of the function `test` to be called is `T test(typename TMap ::Type &tmap_) { return 0.0; }`. Because the `T` in `template struct TMap` and in `typedef std::map Type;` are the same – aldeb Jun 25 '13 at 11:39
  • 1
    @segfolt: No, it is not obvious. Please read my answer few more times, and also read about template specialization. – Nawaz Jun 25 '13 at 12:02
  • @Nawaz: I know it's not obvious, I already read your answer a couple of times, and I know I'm thinking wrong, the point is that I don't know why. What I don't understand is why this statement of DanNissenbaum is wrong: "the only reason the line of code in the question is not possible is due to the possibility of template specializations". Answer by KerrekSB: "No, this is much more basic [...]". When I read your question it's seems like the only reason the OP's code is wrong is because of the possibility of template specialization. What I am missing? – aldeb Jun 25 '13 at 12:38
  • @SamBruns So I stumbled upon this topic and had to basically stare at this answer for a good 2 hours before realizing what it is that's happening. In the first line of `_tmain`, tmap is defined to be of type `std::map`. The second line doesn't matter, and the third line breaks for this reason (which I'm not sure anyone pointed out yet): *the template definition `test` does NOT specify a binding that `test`'s T template argument must always or ever be a `double` simply because it returns `0.0`.* The literal double return value `0.0` is semantically not connected to `T`. – Steven Lu May 15 '15 at 03:01
  • Therefore, even though it's *really* easy to believe that such a deduction can be made, e.g. that `T` must be `double` and therefore `test(tMap::Type)`, a.k.a. `test(std::map)` is to be instantiated, there is technically no evidence for the compiler to go ahead and instantiate it because the spec does not allow the compiler to deduce it from the `0.0`. And, so I suppose this is a case of "eliminate potentially exponential time behavior in the compiler" which is a very sound strategy, but I do lament that this is getting close to the core of the notion that "TMP sucks" – Steven Lu May 15 '15 at 03:07
  • @StevenLu: Yes, it was a bit hard to understand at first glance, but now it's clear. Thanks for the clarification! – aldeb May 15 '15 at 06:52
  • Just curious, can c++17 deduction guides help here? – Denis Yaroshevskiy Jul 31 '17 at 00:32
  • @DenisYaroshevskiy: No. It cannot. It works differently. Deduction guides are invoked in a different context. (But then I've not used it, so cannot claim with 100% surity). – Nawaz Jul 31 '17 at 04:56
3

Exactly what the compiler error message says: in TMap<T>::Type, T is not deduceable according to the standard. The motivation for this is probably that it isn't technically possible to implement: the compiler would have to instantiate all possible TMap<T> in order to see if one (and only one) matched the type you passed. And there is an infinite number of TMap<T>.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • I think you made a mistake here – the compiler “only” has to consider the transitive closure of all existing specialisations and deduce the best match. This is a finite (but potentially still very large) number of instantiations. But apart from that there may simply be several equally good matches (see Nawaz’ example). – Konrad Rudolph May 19 '11 at 15:20
  • No. In many cases, there won't be any existing specializations. And even if there are, type induction can trigger a new specialization. – James Kanze May 19 '11 at 15:34
  • @James If there are no specialisations then the situation is “easy”: just try a pattern matching over the typedef to deduce the template argument. This should be feasible in principle. – Konrad Rudolph May 19 '11 at 15:43
  • @Konrad: Even if there are no specializations, the situation is not easy. Its not safe to assume that type argument to `std::map` is same or somehow depending on the type of the `TMap`. Its therefore not feasible. – Nawaz May 19 '11 at 15:48
  • @Nawaz True, you need to have an “inverted” pattern matching. But this is possible. The compiler would have to create a cross product of all `test` overloads and would have to analyse each parameter in turn, seeing that a `Type` `typedef` inside a `TMap` were required, and inversely-match *that* against the passed argument. In the final step, it could then match the template arguments used in `TMap` against the available types in the `map` parametrisation …. – Konrad Rudolph May 19 '11 at 17:44
  • @Konrad What sort of pattern matching. You have to expand the template for every possible type, in order to know how `Type` is defined in that expansion. (Note that `Type` could easily be something like `typedef typename SomeOtherTemplate::Type Type;`, or even something more complex.) – James Kanze May 19 '11 at 17:51
  • @Konrad: If the type argument of `std::map` doesn't depend on the type argument of `TMap`, how could that be possible? All possible types would be valid candidates for `TMap`, then. – Nawaz May 19 '11 at 17:53
  • 3
    The worst problem is of course that template metaprogramming is Turing Complete. And that in turn means that the necessary pattern matching is equivalent to solving the halting problem (i.e. write the specialization of `A::B` so that `B` is typedef'ed to int iff N represents an algorithm that halts) – MSalters May 20 '11 at 11:06
2

Even you have:

TMap<SomeType>::Type = std::map<double, double>.

But before you call test(tmap)

TMap<double>::Type tmap;
tmap[1.1] = 5.2;
double d = test(tmap);

You already have it declared as

TMap<double>::Type tmap;

why this information can not be utilized. #typedef is not just simple string replacement.

zgcheng
  • 21
  • 2
1

I don't think "we can't do this" argument is correct. If we slightly modify this example, the compiler is happily deducing arguments for us.

template<typename T>
struct TMap //...

template <class T>
struct tmap_t : TMap<T>::Type {};

template<typename T>
T test(tmap_t<T> tmap) // ...

tmap_t<double> tmap;  // ...
double d = test(tmap);  // compiles just fine.

I don't see a huge difference between the original example and mine. The real issue here seems that C++ treats typedefs and type declarations differently

Is this a good thing?

Denis Yaroshevskiy
  • 1,218
  • 11
  • 24