Template parameter deduction from array dimensions

Score: 4.0/5 (79 votes)

The template facility in C++ doesn't only allow you to parameterise with types (such as the int in std::vector<int>), but also with values. Non-type template parameters can be of the following types^[1]:

Integral (or enum) value
Pointer to object/function
Reference to object/function
Pointer to member

I'm going to look at the first of these types - integers - and how template parameter deduction behaves with arrays.

Template parameter deduction is the facility whereby the compiler determines how to instantiate a template when a template parameter is unspecified, e.g:

1
2

std::vector<int> vi;
std::sort(vi.begin(), vi.end());

Although we aren't specifying the type of iterator for std::sort() to use, the compiler works it out from the parameters we provide.

Array dimensions as template parameters

We can create a function that is templated on an array's dimensions:

#include <iostream>
#include <string>

template<int N>
void fun(std::string s[N])
{
   for (int i(0); i < N; ++i)
      std::cout << i << ": " << s[i] << std::endl;
}

int main()
{
   std::string s[2] = {"hello", "world"};
   fun<2>(s);
}

$> ./a.out
0: hello
1: world

Note that omitting the explicit template parameter in this implementation, calling in fun(s) instead, will yield a build error:

$> g++ broken.cpp 
broken.cpp: In function ‘int main()’:
broken.cpp:14:9: error: no matching function for call to ‘fun(std::string [2])’

This confused me for some time, since I was under the impression that the template parameter was deducible from the array dimension.

(NB: as an aside, the above would also work if you wrote fun<500>(s); I think this is down to the array decaying to a pointer, which can then readily initialise the array parameter.)

Deduction of template parameters from array dimensions

Stroustrup's TCPL states that^[2] "a compiler can deduce..a non-type template argument, I, from a template function argument with a type..type[I]", which implies to me that the above should work fine.
I puzzled for a while over why the parameter couldn't be deduced, and eventually hit on the answer. The standard states that a value of type "array of N T" (e.g. "array of 5 int") can be converted to an rvalue of type "pointer to T".^[3] This means that the array size is lost in the instantiation, and as such the value of N cannot be deduced, the template instantiation fails, and - in our example above - fun() cannot be resolved.

The way to prevent this conversion (known as 'decay') is to declare the function parameter as a reference to an array by changing fun(string s[N]) to fun(string (&s)[N]):

template<int N>
void fun(string (&s)[N])
{
   for (int i(0); i < N; ++i)
      cout << i << ": " << s[i] << endl;
}

int main()
{
   string s[2] = {"hello", "world"};
   fun(s);
}

And it works!

Multi-dimensional arrays

Interestingly, although I haven't declared a reference to an array in this alternate implementation with a multidimensional array, it still works fine:

template<int N>
void fun(string s[1][N])
{
   for (int i(0); i < N; ++i)
      cout << i << ": " << s[0][i] << endl;
}

int main()
{
   string s[1][2] = {{"hello", "world"}};
   fun(s);
}

The reason for this is that array decay does not happen recursively, so in the call to fun(), int[1][2] decays to a pointer to an array of 2 ints, and no further, therefore still carries the size information. (NB: I could not find authoritative evidence of this; it may be implicit in that the standard doesn't state that it should happen recursively.)
This article originally appeared at The other branch.

Footnotes

¹ This is the list as specified for C++98 and 03 (cf. ISO C++ standard 14882 14.1.4); C++11 has a few additions.
² Stroustrup - The C++ Programming Language, Special Edition; Appendix C.13.4 - Deducing Function Template Arguments
³ ISO C++ standard 14882 4.2.1.