Why template parameters of dependent type names cannot be deduced, and what to do about it

Following the presentation a type by any other name at the CppCon, a great talk that shows how to incrementally refactor code using tooling and type aliases, I got interested in one of the observation made by Jon Cohen: template parameters of dependent type names cannot be deduced.

This short post aims at describing this issue and explaining why it is so. We will explain why C++ cannot do much better considering its type system and some basic mathematics. We will conclude by showing different ways to solve this issue, including one from Haskell.


Introducing the problem

Before we dive into the explanations, we first have to describe the issue raised by Jon Cohen and introduce the notion of dependent names in C++.


Dependent names

Inside the definition of a template, the meaning of some of the identifiers might depend on one or several template parameters. We call these identifiers dependent names. For instance in the following code, the meaning of const_iterator depends on the type T:

template<typename T>
void f(Container<T> const& cont)
Container<T>::const_iterator it = ...; //Ambiguous (and will not compile)

Because C++ syntax is overloaded, such a name could in theory refer to a static member as much as a type. To remove some of the ambiguity, dependent names are not considered as referring to types “unless the keyword typename is used or unless it was already established as a type name” (from cppreference.com).

This is why we have to add the typename keyword to make our previous code valid:

template<typename T>
void f(Container<T> const& cont)
typename Container<T>::const_iterator it = ...; // OK, const_iterator refers to a type

We will refer to these dependent names qualified with typename as dependent type names.

Note: This was a rather quick introduction to dependent names and dependent type names. The reader is encouraged to look at the cppreference.com or this blog post from Eli Bendersky for more detailed information on the subject.


Taking dependent type names as arguments

Dependent type names can appear inside the signature of function templates, as shown below in this over-constrained implementation of for_each:

template<typename T, typename Consumer>
void for_each(
typename std::vector<T>::const_iterator first, //dependent type on T
typename std::vector<T>::const_iterator last, //dependent type on T
Consumer consumer)
for (;first != last; ++first)
view raw BadForEach.cpp hosted with ❤ by GitHub

While it may look fine on the surface, there is a problem here. Upon calling for_each, the compiler will be able to deduce the type of the iterator, but not be able to infer the template parameter T.

The net result is that the following code, which looks perfectly valid, will not compile: the compiler will complain that it is unable to “deduce the template parameter T”.

std::vector<int> ints = {1, 2, 3};
for_each(ints.begin(), ints.end(), [](int i) { // Does not compile
std::cout << i << '\n';

The problem is what Jon Cohen referred as “template parameters of dependent type names cannot be deduced” in his talk. And as he points out, this kind of error will likely confuse more than one newcomer to C++. Why can’t the compiler figure out the type of T?


Hidden dependent type names

The previous example featured a case in which the dependent type name was pretty easy to spot. The typename and the ::const_iterator appeared clearly. But it gets hard to spot when we introduce type aliases.

For instance, we can write an alias template container_t to select a different container depending on the type of element we would like to store in it (we do not use std::conditional_t to show we are dealing with dependent type names):

  • If the type is copyable, we want to use a std::vector
  • Otherwise we want to use a std::list
template<class T>
using container_t =
typename std::conditional<

We can now define a function f which takes as parameter a container_t. As we can see, it gets really hard to spot that we are dealing with a dependent type name from the signature alone:

template<class T>
void f(container_t<T> const& v) { /* ... */ }
view raw HiddenAlias.cpp hosted with ❤ by GitHub

Despite being hidden, the problem still remains. The compiler will be unable to deduce the type of elements stored in the container:

container_t<int> v;
f(v); // KO: Does not compile, compiler cannot deduce T
f<int>(v); // OK: Compiles file

This is precisely the tricky case that Jon Cohen raised in his presentation, and this one will most likely annoy C++ beginners for quite a long time.


Why the compiler cannot do much better

Let us now explain why the compiler cannot deduce the type of a parameter T from a type name that depends on the parameter T.


Type level functions

We can conceive a type name depending on a template parameter as the result of a function applied on the template parameter. The syntax is different, but it obey the same principle (*).

For instance, here is the type-level function that computes the common type between two or more types in C++, followed by what would the syntax of a normal function call:

using result_t = std::common_type_t<t1, t2>;
// In principle similar to:
auto result_t = std::common_type_t(t1, t2);

Similarly, the const_iterator dependent type name can be seen as the result of the application of a type-level function on the vector class template:

using iterator_t = std::vector<t1>::const_iterator;
// Could be rewritten as:
using iterator_t = std::const_iterator_t<std::vector<t1>>;
// In principle similar to:
auto iterator_t = std::const_iterator_t(std::vector<t1>);

(*): The syntax for calling a type-level function is what Odin Holmes refers as the “unicorn call syntax” as a reference to the “uniform call syntax” C++ standard proposal. We just replace `using` by `auto` and angle brackets by parentheses to get the normal call syntax.


Injective functions

A function f is injective is for all input x and y, f(x) == f(y) implies x == y. Translated in english, it means that feeding the function with different inputs lead to different outputs. For each outputs of the function, there is only one possible input that could have led to this output.

One interesting consequence is that if a function is not injective, there is no way we can find back the input value that led to a specific output (since there might be several inputs available).

If on the contrary a function is injective, we can build a reverse function on its image (the set of all possible outputs of the function) to find back the input element for a given output.


Type level function are not necessarily injective

Now the problem is that upon encountering a dependent type name, the compiler has no guaranty that the corresponding type-level function is injective or not. In fact, we have seen two examples of type-level functions, with one of them (std::common_type) clearly not being injective:

//Clearly not injective
using result_t = std::common_type_t<t1, t2>;
//Most likely injective
using iterator_t = std::const_iterator_t<std::vector<T>>;

In fact, and if we consider that std::vector has an additional template parameters for the allocator, the const_iterator_t type-level function is clearly not injective either. We do not expect the iterator type to be different for different type of allocator.


The compiler cannot deduce the template parameter of a dependent type

To summarize, the compiler is pretty much unable to ensure that a type-level function is injective (*). So it cannot reasonably invert the type-level function and deduce a parameter type T given only a type which depends on that parameter (for there might be several valid T for this same output).

As a consequence, and given our bad for_each function template, the compiler will not be able to deduce the template parameter T given only an iterator:

template<typename T, typename Consumer>
void for_each(
typename std::vector<T>::const_iterator first, //dependent type on T
typename std::vector<T>::const_iterator last, //dependent type on T
Consumer consumer)
for (;first != last; ++first)
view raw BadForEach.cpp hosted with ❤ by GitHub

There might be several T matching the const_iterator type provided as parameter, and consequently, the compiler cannot know which overload to select.

(*): And this is not even taking into account the possibility of explicit template specialization, which basically means that even so we could ensure a type-level function is injective, we could not guaranty it would stay that way.


This issue is not specific to C++

All languages that offer the possibility to compute types depending on some other value or types will face the same kind of issue. For instance, in Haskell, the same issue appears, although in a slightly different form.

The following code declares a type-class (interface or type-trait, if you wish) named Func, with a template parameter a. This type-class exposes a type alias Res which depends on the type parameter a.

class Func a where
type Res a :: *

We provide two instances (specialization, or implementation of the interface, if you wish) of this type-class for integer and string, which show how it looks like practically:

instance Func Int where
type Res Int = Int -- Res Int is an alias for Int
instance Func String where
type Res String = String -- Res String is an alias for String

The “equivalent” (in very loose terms) code in terms of C++ would be something like:

template<typename T>
struct Func {};
struct Func<int> {
using Res = int;
struct Func<std::string> {
using Res = std::string;

Now if we try to define a function which takes a Res a as input, we get a compilation error which says that we cannot deduce the type parameter a from Res a:

-- Equivalent to
-- void f(typename Func<a>::Res)
f :: Res a -> IO ()
f _ = print "Does not compile (type `a` is ambiguous)"

The main difference with Haskell is that we get the compilation error at the very definition of the function, while the error occurs at the call site in C++.


Ways to circumvent the issue

There are different ways we can resolve the ambiguity on the compiler side, by giving it some hints on which specialization should be selected. Let us review some of them.


Relying on additional parameters

While the compiler cannot deduce the template parameter of a dependent type name, it is still perfectly able to deduce a template parameter if it appears somewhere else in the signature of the function.

In short, there is no need to give an hint to the compiler if there is something else in the template definition that allows to deduce the type, as shown in this awkward implementation of std::accumulate:

template<typename T, typename BinaryOp>
T accumulate(
typename std::vector<T>::const_iterator first,
typename std::vector<T>::const_iterator last,
T init,
BinaryOp op)
for (;first != last; ++first)
init = op(init, *first);
return init;

Thanks to the init parameter, the compiler is able to deduce the template parameter T. The following code compiles, and will correctly output 6:

std::vector<int> ints = {1, 2, 3};
accumulate(ints.begin(), ints.end(), 0, [](int res, int i) {
return res + i;

But we do not always have this luxury of having this additional parameter that makes sense.


Explicit template specialization

If we cannot rely on an additional parameter to help the compiler deduce a template parameter, we can always help the compiler and explicitly provide it the template parameter it cannot infer.

We can for instance correct our previous example by explicitly requiring for the specialization of for_each for elements of type integers, and it will compile just fine:

std::vector<int> ints = {1, 2, 3};
for_each<int>(ints.begin(), ints.end(), [](int i) {
std::cout << i << '\n';

But this is kind of annoying, and likely indicates a design issue. In general, a good rule of thumb is to try to fix our design by removing constraints, making the algorithm more generic (the less constraints, the more use cases an algorithm can satisfy), usually removing dependent type names along the way.

In our specific case, we can generalize our for_each function to take the iterator type as template parameter, just like as the STL does:

template<typename Iterator, typename Consumer>
void for_each(Iterator first, Iterator last, Consumer consumer)
for (;first != last; ++first)

In addition, and in some instances, relying on explicit specialization is not very practical either: what if the template parameter to explicitly specialize is not the first one?


Proxy parameters

In some languages, such as Haskell, we cannot ask for an explicit template specialization: the template parameters have to be deduced from the arguments. The solution then is to fall back on the idea of providing the compiler an additional parameter, whose only purpose is to guide the compiler.

This parameter does not carry any runtime value. It is parameterized on the type needed to guide the type deduction, and its only purpose is to carry this type. We usually call it a proxy parameter:

template<typename T>
struct proxy {}
view raw Proxy.cpp hosted with ❤ by GitHub

Or, equivalently, in Haskell:

data Proxy a = Proxy
view raw Proxy.hs hosted with ❤ by GitHub

Thanks to the proxy guiding type deduction, the following code now compiles fine:

f :: Proxy a -> Res a -> IO ()
f _ _ = print "Useless function, but compiles fine"
view raw ProxyUsage.hs hosted with ❤ by GitHub

In some instances, this trick is useful in C++ as well, especially when explicit specialization is awkward (for instance if the template parameter to specialize is not the first one).


Injective type-level functions (Haskell only)

The last solution is to find a way to inform the compiler that the type-level function is injective.

Haskell gives us a way to do so, by letting us explicitly require that the dependent type has to be a brand new type, specific to the instantiation of the type-class, and not an alias to an existing type (by using data instead of type in the declaration below).

class Func a where
data Res a :: *

Here are two examples of instances (specialization, or implementation of the interface, if you wish) of this type-class for integer and string. In each case, we are required to create a new type (ResInt and ResString here) as output to the type-level function Res:

instance Func Int where
data Res Int = ResInt { wrappedInt :: Int }
instance FuncInj String where
data Res String = ResString { wrappedString :: String }

Now, and because the Haskell compiler knows that the Res type-level function is injective, it accepts the following function and will be able to automatically deduced a from its dependent type.

f :: Res a -> ()
f _ = ()

This is not the perfect solution: creating a new type is a sufficient condition for injectivity, but not a necessary one. So it is a bit over-constraining, but at least offers a solution to this annoying issue.

3 thoughts on “Why template parameters of dependent type names cannot be deduced, and what to do about it

Add yours

  1. Oh hey, you’re talking about my talk! I’m glad you liked it 🙂

    This is an interesting take, I hadn’t thought about metafunctions in terms of injectiveness like that. I think it’s a much stronger point than the one I made in my talk that deducing template parameters of dependent typenames could require arbitrary computations, including some which may not halt, since templates are Turing-complete.


    1. Oh yeah, another point — from another part of my talk, another reason that it’s generally a bad idea to call template functions with explicitly passed template parameters is that it hems maintainers of the function to a specific interpretation of the template parameter. They may want it to mean something later to improve the implementation for some reason.


      1. Indeed, I did not thought about the maintainability over time of this solution, which I do not like much either. This is a good point.

        As for myself, I share the Haskell mindeet that template parameters should be deduced, although sometimes it requires some bit more work to get to this point (by generalizing some more for instance).

        In any case, I am the one that should thank you for the inspiration on this topic (and the good laugh when you asked for a selfie at the end of the talk), as it was quite an interesting topic to research on 🙂


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: