Introduction
The C++ function overloading rules are far from simple, complicated by special rules about template and non-template functions, implicit conversions, automatic template argument deduction, etc. This article describes a lesser-known and seemingly minor part of these rules, which conceals a true gem for generic programming. In a nutshell, these rules allow template functions to be selectively included in or excluded from the overload resolution. Any properties of the argument types that can be expressed as compile-time Boolean constants can be used as criteria in this selection.
This article builds on the (independent) findings of Paul Mensonides and Jason Shirk. They showed how to manipulate the overload resolution set [1, 2] and used this result to define traits classes, such as is_class for testing whether a given type is a class type and has_member for testing whether a class type has a member function of a given name and type. This article generalizes the technique, packages it into an easy-to-use template, and, more importantly, demonstrates its significant implications for generic programming.
The technique allows overloading a function for a set of types that do not derive from a common base class. Thus a generic library author can overload operators and other functions with a fully generic interface, but still have them match only the types for which they are designed. As an example, we define a flexible Java-style string concatenation operator that automatically converts a non-string operand into a string. The programmer has full control over the set of types the concatenation operator matches. This same technique solves the problems with the relational operators in the infamous rel_ops namespace. As another example application, the article shows an alternative mechanism for tag dispatching, an idiom for statically dispatching from an interface function to specialized implementation functions. In general, the technique is useful in disambiguating conflicting function overloads.
Background
It is easy to end up with invalid type expressions while instantiating function templates. As an example, consider the following two overloaded functions:
int negate(int i) { return -i; }
template <class F>
typename F::result_type
negate(const F& f) { return -f(); }
The latter overload is meant to work with standard function objects where the
member type result_type specifies the return type. Now examine a call,
such as:
negate(1)The first overload is clearly a better match, but the compiler must nevertheless make an attempt to instantiate the second overload as well. This results in the prototype:
int::result_type negate(const int&);The return type int::result_type is obviously invalid. A compile-time error here would undoubtedly annoy the programmer as a valid and better matching overload exists, and indeed, the code compiles fine. The compiler removes the erroneous prototype from the overload resolution set, and thus the invalid return type does not cause an error.
Instantiating a function template is a two-phase process. First, the template argument values are deduced from the types of the actual arguments passed in to the function. Second, these deduced values are substituted for all occurrences of the template parameters in the return and parameter types of the function. As an example, in the call negate(1), the value of the template argument F is deduced to be int based on the type of the function argument. The value int is then substituted for all occurrences of F, leading to the return type int::result_type.
If the substitution process leads to an invalid type, argument deduction fails, and the function is not added to the overload resolution set. Hence, if we can find a controlled way to make this substitution process result in an invalid type, we have a tool that can remove a function from the overload resolution set. The Standard contains nine rules describing explicitly what an invalid type means in this context. One of the cases is an attempt to refer to a nested typedef that does not exist, as in expression int::result_type. A pointer to a reference type and a function type in which a parameter has void type are other examples of invalid types that cause type deduction to fail.
The above described parts of the overload resolution rules are well hidden in the Standard, but a careful reading of sections 14.8.2 (paragraphs 2 and 4) and 14.8.3 should assure you that a Standard-conforming C++ compiler must behave as explained above.
Function Enablers and Disablers
We have packaged the enabling/disabling functionality into two easy-to-use templates, enable_if and disable_if. The definition of enable_if is as follows:
template <bool B, class T = void>
struct enable_if {
typedef T type;
};
template <class T>
struct enable_if<false, T> {};
This template takes two parameters, a Boolean constant B and a type T.
Depending on the value of B, enable_if either defines a nested typedef
named type as T (true case) or defines no such typedef
(false case). In other words, enable_if<true, T>::type equals
T, whereas enable_if<false, T>::type is an expression that
refers to a nonexistent nested type (which is one of the special invalid types
that lead to removing the function from the overload resolution set). The rationale
for the default value void for parameter T is explained in the end
of this section.
The disable_if template can be defined similarly, except for the negated condition. It is not strictly necessary to have both the enabler and disabler; one can always negate the conditional expression at the site of using enable_if. However, in some cases, it is more intuitive to think of disabling a function under particular conditions, instead of enabling it under the negated conditions.
To use the packaged enablers (the term enabler refers to both the enable_if and disable_if templates), you simply wrap the function's actual return type in an enable_if or disable_if template. In the following example, the foo function is always enabled, whereas bar is never enabled:
template <class T>
typename enable_if<true, T>::type
foo(T t) { return t; }
template <class T>
typename enable_if<false, T>::type
bar(T t) { return t; }
A call to foo with any (copy-constructible) argument type succeeds, but
all calls to bar fail because bar will never be added to the overload
resolution set. It is as if no definition for bar existed.
foo(1); // ok, returns 1 bar(1); // fails, no such functionIn real code, it would be pointless to write enablers where the condition always evaluates to the same truth value. Enablers become useful when the truth value of their condition depends on the properties of one or more template arguments. To write such expressions, we need compile-time reflection mechanisms. Reflection means the ability to query and operate on properties of language constructs within the language itself. The direct support for reflection is limited in C++, but with some inventive template techniques, a notable set of compile-time reflection tools can be implemented as a template library. These tools come in the form of traits classes. In Table 1, we describe some of the traits classes from the Boost type traits library [3, 4].
As an example, the following function template is only enabled for arithmetic types:
template <class T> typename enable_if<is_arithmetic<T>::value, T>::type foo(T t);We have also found compile-time if statements and other tools for template metaprogramming helpful in writing the enabler conditions (see for example [5, 6]).
Note that instead of the return type, you can place the enabler into a function's parameter type. Typically, you would introduce an extra parameter and give it a default value so that the call sites of the function would not be affected. For example:
template <class T>
T foo (T t,
typename enable_if<is_arithmetic<T>::value>::type* = 0);
Note that when enable_if is used as an argument type, the nested typedef
in enable_if can always have the same type void making the second
argument to enable_if unnecessary. This is the reason why void is
the default value for the second argument of enable_if.
We prefer to use enablers in the return type, particularly as an important application of enablers is operator functions, where the number of parameters is fixed. On the other hand, the technique works with member function templates, such as templated constructors. Constructors do not have return types; thus, an enabler in a constructor must be placed into a parameter.
Applications
Java-Style String Concatenation
Java provides special support for the string concatenation operator (+). This operator requires that at least one of the operands is of type String. The other operand is converted to String if necessary. For example:
1 + " is less than " + 2evaluates to the string "1 is less than 2". Function enablers provide a convenient way to implement this same behavior in C++. Unlike in Java, all objects in C++ are not convertible to strings by default. Therefore, we first need a function to convert objects of other types to strings:
template <class T>
std::string to_string(const T& t) {
std::ostringstream s;
s << t;
return s.str();
}
Any output streamable type (any type that can be written into an output
stream) can be converted to a string with this function. Next we need a traits
class telling which types are output streamable:
template <class T>
struct is_output_streamable {
static const bool value =
is_arithmetic<T>::value;
};
This primary template specifies that all arithmetic types are output streamable.
By default, any other type is thus not output streamable. By adding specializations
for this template, we can declare any type output streamable.
The next task is to write the enabling condition for the concatenation operator. The operator should be enabled as long as at least one of its arguments is a string, and any non-string argument is output streamable. The following traits class implements this logic:
template <class A, class B>
struct can_concatenate {
static const bool value =
( is_same<A, string>::value &&
is_output_streamable<B>::value)
||
( is_same<B, string>::value &&
is_output_streamable<A>::value);
};
With the above tools, just one definition of the concatenation function suffices:
template <class A, class B>
typename enable_if<
can_concatenate<A, B>::value,
string>::type
operator+(const A& a, const B& b) {
return to_string(a) + to_string(b);
}
The enabler template evaluates the can_concatenate condition, and either
allows operator+ to be considered for overload resolution or not. The primary
template of is_output_streamable defines all arithmetic types to be output
streamable, so the expression (corresponding to the Java example above):
1 + string(" is less than ") + 2
evaluates to the string "1 is less than 2".
Consider a user-defined class my_class that supports writing to an output stream:
class my_class { ... };
ostream& operator<<(ostream& o, const my_class& a) {
return (o << "my_class!");
}
A new specialization for is_output_streamable is enough to make operator+
accept objects of this type:
template <>
struct is_output_streamable<my_class> {
static const bool value = true;
};
For example, the expression
string("This is ") + my_class()
now evaluates to the string "This is my_class!".
Operators in rel_ops
The standard library provides default implementations for !=, >, <=, and >= based on the two operators == and <. The definition of operator!= serves as an example:
template <class T>
bool operator!=(const T& x, const T& y)
{ return !(x == y); }
The intention behind these operators was to save programmers from writing boilerplate
code. During the standardization process, it was realized that these operators
match too greedily and were thus placed into a separate namespace std::rel_ops.
The idea was that the programmer would implement operator== and operator<
for some class T and import the other relational operators into T's
namespace with using directives. It turned out, however, that the introduction
of the rel_ops subnamespace did not solve the approach's fundamental problems.
Legitimate uses of the rel_ops operators can still lead to subtle ambiguity
errors or worse, errors in program logic due to the best matching function not
being what the programmer expects. In general, namespaces are too coarse a mechanism
for controlling when operators with fully generic interfaces should be available
and when not.
Function enablers give the fine-grained control that is required [7]. The solution is analogous to the Java-style string concatenation implementation above. An enabler is added to each relational operator definition in rel_ops. For example, here is the definition of the != operator:
template <class T>
inline typename enable_if<
use_rel_ops<T>::value,
bool>::type
operator!=(const T& t, class T& u)
{ return !(t == u); }
The traits class use_rel_ops controls whether the default definitions should
be used or not:
template <class T>
struct use_rel_ops {
static const bool value = false;
};
The primary template sets the default to false, and the default definitions
for relational operators are thus only enabled for types that specialize the use_rel_ops
template.
Resolving Ambiguities
Consider the following scenario: you have a function template with, say, two parameters and a set of overloads for different types of the first parameter:
template <class A, class B> void foo(A a, B b); template <class B> void foo(int a, B b); template <class B> void foo(float a, B b);Further, suppose there is some type Special_B that is a special case for the second argument. You want to add an overload for this case, such that it would always be chosen, whatever the type of the first argument. Adding just the definition:
template <class A> void foo(A a, Special_B b);does not give the desired result; calls where both arguments are one of the special cases would be ambiguous. The call foo(1, Special_B()) is an example of one such call.
The traditional way to solve the ambiguities is to add a disambiguating overload for each ambiguous case:
template <> void foo(int a, Special_B b); template <> void foo(float a, Special_B b);Two additional overloaded functions are enough here, but with more arguments and more special argument types, this solution does not scale well.
Function enablers can control which functions are considered for overload resolution and can thus help in resolving ambiguities. In the following set of overloaded functions, the cases where the first argument has type int or float are only considered if the second argument is not of type Special_B:
template <class A, class B> void foo(A a, B b); template <class B> typename disable_if<is_same<B, Special_B>, void>::type foo(int a, B b); template <class B> typename disable_if<is_same<B, Special_B>, void>::type foo(float a, B b); template <class A> void foo(A a, Special_B b);Note that overload resolution is an interplay between function enablers and traditional overload resolution, and thus not all definitions need to use the enable_if or disable_if templates.
The Standard pow function is a prime example of the case outlined above. The standard library contains 10 pow overloads, attempting to cover floats, doubles, long doubles, and instances of std::complex. The Standard Library also provides overloads for the cases where the exponent is of an integral type, as this case allows a more efficient implementation. Even with the 10 overloads, some reasonable calls result in compile-time errors, or even worse, silently give incorrect results. As an example, the call
std::pow(std::complex<float>(9, 0), 0.5)ends up converting the second argument to the integer 0 and thus produces 1 as the result, rather than the correct answer 3. The call
std::pow(9.0, std::complex<float>(0.5))fails to compile altogether, as does the call std::pow(1, 1). Using function enablers, just 3 overloads, compared to the current 10, are enough to cover all the currently supported cases, fix the error cases and unintuitive behavior, and add support for integral types. A bit of extra machinery is required to deduce the return types correctly, though.
Tag Dispatching
Tag dispatching is a common technique used in generic algorithms to select an appropriate implementation based on properties of argument types. For example, the standard library defines a set of iterator categories, such as Input Iterator and Random Access Iterator, and defines a tag class for each category. Furthermore, the library provides a traits class for querying the tag of a particular iterator type so that a generic algorithm can choose the most efficient implementation for each iterator type. For example, advancing n steps is a constant-time operation for random access iterators, but a linear-time one for input iterators.
Indeed, many of the function templates implementing the standard algorithms are just dispatching functions that delegate the work to different implementation functions based on the implementation in the iterator categories of the argument types. The advance function (based on the implementation in the GNU C++ Standard Library v3) is one such example:
template <class It, class Dist>
inline void advance(It& i, Dist n) {
typedef typename
iterator_traits<It>::iterator_category Cat;
__advance(i, n, Cat());
}
The first line resolves the iterator category of the first argument and forwards
the call to the __advance function, which is overloaded for different iterator
categories. We omit the __advance implementations for brevity.
Tag dispatching with function enablers lets us do without a separate interface function and dispatch directly into the implementation templates:
template <class It, class Dist>
inline typename enable_if<
is_random_access_iter<It>::value,
void>::type
advance(It& i, Dist n) { i += n; }
template <class It, class Dist>
inline typename enable_if<
is_input_iter<It>::value &&
!is_random_access_iter<It>::value,
void>::type
advance(It& i, Dist n)
{ while (n--) ++i; }
We omit the implementations of the is_input_iter and is_random_access_iter
traits classes here for brevity. Note that the latter advance function
is enabled if It is at least an input iterator and not a random access
iterator. This is because both definitions of advance are fully generic.
If they were ever enabled at the same time, the definitions would be ambiguous.
Consequently, you need to exercise some care in designing the enabling rules.
Tag dispatching is a well-established idiom in modern template libraries, and we are not suggesting replacing the current dispatching scheme, say, in standard library implementations with function enablers. Using function enablers can, however, be more intuitive in some situations. Particularly, different functions can have different return types with no extra effort, whereas combining different return types into one interface function can be cumbersome.
Conclusions
This article describes an obscure part of the C++ overload resolution rules, which under special conditions leads to the removal of template functions from the overload resolution set. With the tools described in this article, these conditions can be created with ease, giving the programmer the means to enable and disable function templates based on properties of the argument types.
Function enablers and disablers provide solutions to several problems in generic programming in C++, such as disambiguating otherwise ambiguous overloaded declarations and doing static dispatching without an intermediate dispatcher function. In general, the tools presented allow a generic function to be overloaded for a set of types that do not have a common base class.
The possibility to enable and disable functions on (almost) arbitrary properties of function arguments is a powerful tool. We suspect that this article is a starting point rather than a comprehensive list of the technique's applications.
Future Work
Matching partial specializations of class templates is performed with the same set of rules as function template argument deduction. This means that a partial specialization of a class template can only match if template argument deduction does not fail, and thus the set of rules we describe in the background section can be exploited to enable and disable class template specializations. Richard Smith reported this finding [9]. Our general-purpose enablers work out-of-the-box; all that is needed is one extra template parameter with the default value void. In specializations, this extra parameter is a condition wrapped inside an enabler template. For example:
template <class T, class U = void> class A;
template <class T>
class A<vector<T>,
typename enable_if<is_arithmetic<T>::value>::type>;
template <class T>
class A<vector<T>,
typename disable_if<is_arithmetic<T>::value>::type>;
Here, A<vector<float> > matches the first specialization, while
A<vector<string> > matches the second one. As with function
templates, the condition can be any expression that depends on the template arguments
to the class and can be evaluated at compile time. Exploring the consequences
and applications of this kind of "conditional specialization" remains as future
work.
Workarounds for Too Eager Compilers
We successfully tested function enablers using the GCC 3.2, Metrowerks 8.1, Intel 6.0 for Linux, and KAI C++ 4.0 compilers. However, in some cases the compiler needed guidance to get on the right path. With enable_if and disable_if, two overloaded function templates can have identical formal parameter lists but still not be ambiguous. For example:
template <class T> typename enable_if<cond, T>::type foo(T t); template <class T> typename disable_if<cond, T>::type foo(T t);Even though these two functions can never be enabled simultaneously, some compilers tend to just look at the parameter lists at the time of compiling the definitions of the functions, and an error occurs if identical parameter lists are found. If this issue arises, there are two easy workarounds:
namespace A {
template <class T>
typename enable_if<cond, T>::type foo(T t);
}
namespace B {
template <class T>
typename disable_if<cond, T>::type foo(T t);
}
using A::foo;
using B::foo;
Notes and References
[1] Paul Mensonides. "is_enum<T> ATTN: Andrei Alexandrescu and ilk," thread of Usenet articles in comp.lang.c++.moderated, March 2002.
[2] Jason Shirk. "has_member?," thread of articles in the C++ Boost mailing list <www.boost.org> (message 27342), March 2002.
[3] The Boost type traits library, <www.boost.org/libs/type_traits>, 2002.
[4] John Maddock and Steve Cleary. "C++ Type Traits," Dr. Dobb's Journal, October 2000.
[5] Krzysztof Czarnecki and Ulrich W. Eisenecker. Generative Programming: Methods, Tools, and Applications (Addison-Wesley, 2000).
[6] Aleksei Gurtovoy and David Abrahams. The Boost C++ Metaprogramming Library, 2002.
[7] There are other approaches to safely "import" default definitions for a set of operators, see the Boost Operators library [8].
[8] The Boost Operators library, <www.boost.org>, 2002.
[9] Richard Smith. "A default_constructible traits," thread of Usenet articles in comp.lang.c++.moderated, January 2002.
About the Authors
Howard Hinnant is a refugee from the aerospace industry. He holds a B.S. in Aerospace Engineering from Texas A&M University and an M.S. in the same field from Stanford University. For the past five years, he has been responsible for the C++ Standard library that ships with Metrowerks CodeWarrior on GameCube, Macintosh, Palm, PlayStation 2, Windows, etc. Howard is also active in the C++ Standards committee. He can be contacted at [email protected].
Jaakko Järvi is currently a post-doctoral researcher in the Open Systems Laboratory within the Pervasive Technology Laboratories at Indiana University. He has a Ph.D. in Computer Science from the University of Turku, Finland. He's a contributing member of the C++ Boost community and actively participates in C++ standardization work.
Andrew Lumsdaine received the Ph.D. from MIT in 1992. He is currently an Associate Professor in the Computer Science Department at Indiana University, where his teaching and research interests include numerical analysis, mathematical software, parallel processing, generic programming, software engineering, and cluster computing. He is concurrently the associate director of the Open Systems Laboratory, one of the IU Pervasive Technology Laboratories funded by the Lilly Endowment. The mission of the Open Systems Lab is to improve programmer productivity through better practices, tools, and languages -- and to develop and promote these technologies in an open fashion. He is a member of IEEE, SIAM, and ACM.
Jeremiah Willcock is currently a graduate student at Indiana University and is working in the Open Systems Laboratory within the Pervasive Technology Laboratories. He has an M.S. in Computer Science and Engineering degree from the University of Notre Dame du Lac, 2002.
