Skip to main content

Function Template Overload Resolution and Specialization Anomaly

I recently realized that function template overloading and function template specialization can interact with each other in complex ways giving rise to quite surprising C++ programs. Consider,

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

int main (void) {
int *p = 0;
f(p);
}

Output of the above program is "f(T *)" (i.e. (c) is invoked in main). Now simply swap the order in which (b) and (c) are written. The output of the program changes! This time it invokes (b) giving output as "f(int *) specilization".

The reason behind it is that when the integer full specilization (b) of f is defined in the order shown above, it is a full specialization of (a). But (c) is a better match as it is an overloaded primary template defined afterwards and we get "f(T *)" as an output.

When (b) is defined after (c), (b) is an integer full specilization of (c) and hence the specilization is chosen as expected.

An excerpt from the book "C++ Templates - The Complete Guide" helps explain what is really happening here.

"Partial specialization doesn't introduce a completely new template: It is an extension of an existing template (the primary template). When a CLASS template is looked up, only primary templates are considered at first. If, after the selection of a primary template, it turns out that there is a partial specialization of that template with a template argument pattern that matches that of the instantiation, its definition (in other words, its body) is instantiated instead of the definition of the primary template. (Full template specializations work exactly the same way.)"

(Added this para on May-05-2008)
Note that the above paragraph applies to class templates only. But when full specializations are in consideration, the above paragraph applies to function templates as well. Full function template specialization is supported by C++98 standard but not partial function template specialization. A better alternative to partial function template specialization is to use plain old function overloading. Having said that, as far as I know, there are efforts begin made towards standardizing partial function template specialization for C++09 standard. (please see comments for more discussion on this.)

The program clearly shows that the order of definition of specilizations and overloads affects primary template lookup. As a result, interestingly enough, you can define the f<>(int *) full specialization twice in the program. One after (a) and another one after (c) and program compiles just fine!

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

template<>
void f<>(int*) { // (d) another identical explicit specialization
std::cout << "f(int *) another specilization\n";
}

int main (void) {
int *p = 0;
f(p);
}

What is the output here? Any guesses?

This program is an example of complexity that results due to orthogonality of C++ language. In simple terms, number of C++ features can co-exist and their interplay can baffle any uninitiated C++ programmer! I wonder how complex it would be once we have partial function template specialization support in standard C++ in 2009.

Comments

Anonymous said…
Yes. It's interesting behavior.
As for me, I prefer to use not explicit specializations, but pure overloaded functions instead.

If you'll replace

template<>
void f<>(int*) { /*bla-bla-bla*/ }

with

void f(int*) { /*bla-bla-bla*/ }

problem will gone.

Not-template functions have always better match for compiler.

But.... I don't know... May be there are some situations, when we'll have to use only template specializations, and pure functions overloads wouldn't work?
Not sure, though, if you quoted the right excerpt. There is no partial specialisation for functions in the current standard. That excerpt applies to class templates only.

There is no reason for void f<>(int*) to be a full function template specialisation. If you make it just a function overload, as girman suggested, reordering the declarations will not produce surprising results.
Sumant said…
Good point! Using good old function overloading makes perfect sense and solves the problem of reordering. But after all the fun is in the least explored corners of C++. I added a para in the original post describing the better alternative of overloading. Having said that, is it a violation of Onde Definition Rule (ODR) to allow two identical full explicit function template specializations (f<>(int *))?
A quote from the blessed standard §3.2 One definition rule, clause 5:

There can be more than one definition of a class type (clause 9), enumeration type (7.2), inline function with external linkage (7.1.2), class template (clause 14), non-static function template (14.5.5), static data member of a class template (14.5.1.3), member function of a class template (14.5.1.1), or template specialization for which some template parameters are not specified (14.7, 14.5.4) in a program provided that each definition appears in a different translation unit, and provided the definitions satisfy the following requirements...

The implication of this clause is that full function specialisations obey the same rules as regular (non-template) functions, not function templates.

Here is an example:

// foo.h
template<class T> void foo(T) {}
template<> void foo(int) {}

If this header is included in more than one translation unit (.cc/.cpp), the linker complains about foo(int) being defined in several translation units, even if that specialisation is never used (called, or the address is taken).

To fix this, foo(int) specialisation needs to be declared inline, or static, or its definition must be removed from the header. On the other hand, function template need not be inline, as the standard provides relaxed one definition rules for templates.

The latter is often exploited to put static members in the headers. Exampe:

// some.h
struct some
{
static int member;
};
int some::member = 0;

This header is going to cause multiple some::member definition linker error when included in more than one translation unit. A workaround:

template<class T>
struct static_member
{
static T member;
};

// static data member of a class template (14.5.1.3),
// can be defined in many translation units.
template<class T>
T static_member<T>::member = T();

struct some : static_member<int>
{
// not a template, but still has its static member declared in the header.
};

Returning back to function templates, function overloading is often easier to deal with and can be used to simulate (non-existent) partial function specialisation:

template<class T> struct type {}; // boost::type<>
// generic implementation
template<class T, class U> void foo_impl(type<T>, type<U>);
// "partial" overload for second argument int
template<class T> void foo_impl(type<T>, type<int>);

template<class T, class U>
void foo() // interface for foo_impl
{
// convert template arguments to typed values,
// so that regular function overloading can be used.
foo_impl(type<T>(), type<U>());
}

int main()
{
foo<void, void>();
foo<void, int>();
}

Popular Content

Unit Testing C++ Templates and Mock Injection Using Traits

Unit testing your template code comes up from time to time. (You test your templates, right?) Some templates are easy to test. No others. Sometimes it's not clear how to about injecting mock code into the template code that's under test. I've seen several reasons why code injection becomes challenging. Here I've outlined some examples below with roughly increasing code injection difficulty. Template accepts a type argument and an object of the same type by reference in constructor Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one Template accepts a type argument and instantiates multiple interrelated templates without virtual functions Lets start with the easy ones. Template accepts a type argument and an object of the same type by reference in constructor This one appears straight-forward because the unit test simply instantiates the template under test with a mock type. Some assertion might be tested in

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example. struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together. It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array? int native[3][4]; std::array<std::array<int, 3>, 4> arr; No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is: std::array<std::array<int, 4>, 3> arr; That's quite annoying for