Function overloading allows the same function name to be used for multiple functions, so long as those functions are distinguished by their parameter types. For example:
void f (int);
void f (char const*);
With function templates, one overloads on type patterns such as pointer-to-T or Array<T>:
template<typename T> void f(T*);
template<typename T> void f(Array<T>);
Given the prevalence of type traits (discussed in Chapter 19), it is natural to want to overload function templates based on the properties of the template arguments. For example:
template<typename Number> void f(Number); // only for numbers
template<typename Container> void f(Container);// only for containers
However, C++ does not currently provide any direct way to express overloads based on type properties. In fact, the two f function templates immediately above are actually declarations of the same function template, rather than distinct overloads, because the names of template parameters are ignored when comparing two function templates.
Fortunately, there are a number of techniques that can be used to emulate overloading of function templates based on type properties. These techniques, as well as the common motivations for such overloading, are discussed in this chapter.
One of the common motivations behind overloading of function templates is to provide more specialized versions of an algorithm based on knowledge of the types involved. Consider a simple swap() operation to exchange two values:
template<typename T>
void swap(T& x, T& y)
{
T tmp(x);
x = y;
y = tmp;
}
This implementation involves three copy operations. For some types, however, we can provide a more efficient swap() operation, such as for an Array<T> that stores its data as a pointer to the array contents and a length:
template<typename T>
void swap(Array<T>& x, Array<T>& y)
{
swap(x.ptr, y.ptr);
swap(x.len, y.len);
}
Both implementations of swap() will correctly exchange the contents of two Array<T> objects. However, the latter implementation is more efficient, because it makes use of additional properties of an Array<T> (specifically, knowledge of ptr and len and their respective roles) that are not available for an arbitrary type.1 The latter function template is therefore (conceptually) more specialized than the former, because it performs the same operation for a subset of the types accepted by the former function template. Fortunately, the second function template is also more specialized based on the partial ordering rules for function templates (see Section 16.2.2 on page 330), so the compiler will pick the more specialized (and, therefore, more efficient) function template when it is applicable (i.e., for Array<T> arguments) and fall back to the more general (potentially less efficient) algorithm when the more specialized version is not applicable.
The design and optimization approach of introducing more specialized variants of a generic algorithm is called algorithm specialization. The more specialized variants apply to a subset of the valid inputs for the generic algorithm, identifying this subset based on the specific types or properties of the types, and are typically more efficient than the most general implementation of that generic algorithm.
Crucial to the implementation of algorithm specialization is the property that the more specialized variants are automatically selected when they are applicable, without the caller having to be aware that those variants even exist. In our swap() example, this was accomplished by overloading the (conceptually) more specialized function template (the second swap()) with the most general function template (the first swap()), and ensuring that the more specialized function template was also more specialized based on C++’s partial ordering rules.
Not all conceptually more specialized algorithm variants can be directly translated into function templates that provide the right partial ordering behavior. For our next example, consider
However, the alternative presented here is more broadly applicable.
the advanceIter() function (similar to std::advance() from the C++ standard library), which moves an iterator x forward by n steps. This general algorithm can operate on any input iterator:
template<typename InputIterator, typename Distance>
void advanceIter(InputIterator& x, Distance n)
{
while (n > 0) { //linear time
++x;
--n;
}
}
For a certain class of iterators—those that provide random access operations—we can provide a more efficient implementation:
template<typename RandomAccessIterator, typename Distance>
void advanceIter(RandomAccessIterator& x, Distance n) {
x += n; // constant time
}
Unfortunately, defining both of these function templates will result in a compiler error, because— as noted in the introduction—function templates that differ only based on their template parameter names are not overloadable. The remainder of this chapter will discuss techniques that emulate the desired effect of overloading these function templates.
One approach to algorithm specialization is to “tag” different implementation variants of an algorithm with a unique type that identifies that variant. For example, to deal with the advanceIter() problem, just introduced, we can use the standard library’s iterator category tag types (defined below) to identify the two implementation variants of the advanceIter() algorithm:
template<typename Iterator, typename Distance>
void advanceIterImpl(Iterator& x, Distance n, std::input_iterator_tag)
{
while (n > 0) { //linear time
++x;
--n;
}
}
template<typename Iterator, typename Distance>
void advanceIterImpl(Iterator& x, Distance n,
std::random_access_iterator_tag) {
x += n; // constant time
}
Then, the advanceIter() function template itself simply forwards its arguments along with the appropriate tag:
template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n)
{
advanceIterImpl(x, n,
typename
std::iterator_traits<Iterator>::iterator_category());
}
The trait class std::iterator_traits provides a category for the iterator via its member type iterator_category. The iterator category is one of the _tag types mentioned earlier, which spec-ifies what kind of iterator the type is. Inside the C++ standard library, the available tags are defined as follows, using inheritance to reflect when one tag describes a category that is derived from another:2
namespace std {
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
}
The key to effective use of tag dispatching is in the relationship among the tags. Our two variants of advanceIterImpl() are tagged with std::input_iterator_tag and with std::random_access_iterator_tag, and because std::random_access_iterator_tag inherits from std::input_iterator_tag, normal function overloading will prefer the more specialized algorithm variant (which uses std::random_access_iterator_tag) whenever advanceIterImpl() is called with a random access iterator. Therefore, tag dispatching relies on delegation from the single, primary function template to a set of _impl variants, which are tagged such that normal function overloading will select the most specialized algorithm that is applicable to the given template arguments.
Tag dispatching works well when there is a natural hierarchical structure to the properties used by the algorithm and an existing set of traits that provide those tag values. It is not as convenient when algorithm specialization depends on ad hoc type properties, such as whether the type T has a trivial copy assignment operator. For that, we need a more powerful technique.
Algorithm specialization involves providing different function templates that are selected on the basis of the properties of the template arguments. Unfortunately, neither partial ordering of function templates (Section 16.2.2 on page 330) nor overload resolution (Appendix C) is powerful enough to express more advanced forms of algorithm specialization.
One helper the C++ standard library provides for this is std::enable_if, which is introduced in Section 6.3 on page 98. This section discusses how this helper can be implemented by introducing a corresponding alias template, which we’ll call EnableIf to avoid name clashes.
Just like std::enable_if, the EnableIf alias template can be used to enable (or disable) a specific function template under specific conditions. For example, the random-access version of the advanceIter() algorithm can be implemented as follows:
template<typename Iterator>
constexpr bool IsRandomAccessIterator =
IsConvertible<
typename std::iterator_traits<Iterator>::iterator_category,
std::random_access_iterator_tag>;
template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n){
x += n; // constant time
}
The EnableIf specialization here is used to enable this variant of advanceIter() only when the iterator is in fact a random access iterator. The two arguments to EnableIf are a Boolean condition indicating whether this template should be enabled and the type produced by the EnableIf expansion when the condition is true. In our example above, we used the type trait IsConvertible, introduced in Section 19.5 on page 428 and Section 19.7.3 on page 447, as our condition, to define a type trait IsRandomAccessIterator. Thus, this specific version of our advanceIter() implementation is only considered if the concrete type substituted for Iterator is usable as a random-access iterator (i.e., it is associated with a tag convertible to std::random_access_iterator_tag.
EnableIf has a fairly simple implementation:
typeoverload/enableif.hpp
template<bool, typename T = void>
struct EnableIfT {
};
template< typename T>
struct EnableIfT<true, T> {
using Type = T;
};
template<bool Cond, typename T = void>
using EnableIf = typename EnableIfT<Cond, T>::Type;
EnableIf expands to a type and is therefore implemented as an alias template. We want to use partial specialization (see Chapter 16) for its implementation, but alias templates cannot be partially specialized. Fortunately, we can introduce a helper class template EnableIfT, which does the actual work we need, and have the alias template EnableIf simply select the result type from the helper template. When the condition is true, EnableIfT<…>::Type (and therefore EnableIf<…>) simply evaluates to the second template argument, T. When the condition is false, EnableIf does not produce a valid type, because the primary class template for EnableIfT has no member named Type. Normally, this would be an error, but in a SFINAE (substitution failure is not an error, described in Section 15.7 on page 284) context—such as the return type of a function template—it has the effect of causing template argument deduction to fail, removing the function template from consideration.3
For advanceIter(), the use of EnableIf means that the function template will be available (and have a return type of void) when the Iterator argument is a random access iterator, and will be removed from consideration when the Iterator argument is not a random access iterator. We can think of EnableIf as a way to “guard” templates against instantiation with template arguments that don’t meet the requirements of the template implementation, because this advanceIter() can only be instantiated with a random access iterator as it requires operations only available on a random access iterator. While using EnableIf in this manner is not bulletproof—the user could assert that a type is a random access iterator without providing the necessary operations—it can help diagnose common mistakes earlier.
We now have established how to explicitly “activate” the more specialized template for the types to which is applies. However, that is not sufficient: We also have to “de-activate” the less specialized template, because a compiler has no way to “order” the two and will report an ambiguity error if both versions apply. Fortunately, achieving that is not hard: We just use the same EnableIf pattern on the less specialized template, except that we negate the condition expression. Doing so ensures that exactly one of the two templates will be activated for any concrete Iterator type. Thus, our version of advanceIter() for an iterator that is not a random access iterator becomes the following:
template<typename Iterator, typename Distance>
EnableIf<!IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n)
{
while (n > 0) {//linear time
++x;
--n;
}
}
The previous pattern generalizes to cases where more than two alternative implementations are needed: We equip each alternative with EnableIf constructs whose conditions are mutually exclusive for a specific set of concrete template arguments. Those conditions will typically make use of various properties that can be expressed via traits.
Consider, for example, the introduction of a third variant of the advanceIter() algorithm: This time we want to permit moving “backward” by specifying a negative distance.4 That is clearly invalid for an input iterator, and clearly valid for a random access iterator. However, the standard library also includes the notion of a bidirectional iterator, which allows backward movement without requiring random access. Implementing this case requires slightly more sophisticated logic: Each function template must use EnableIf with a condition that is mutually exclusive with the conditions of all of the other function templates that represent different variants of the algorithm. This results in the following set of conditions:
• Random access iterator: Random access case (constant time, forward or backward)
• Bidirectional iterator and not random access: Bidirectional case (linear time, forward or backward)
• Input iterator and not bidirectional: General case (linear time, forward)
The following set of function templates implements this:
typeoverload/advance2.hpp
#include <iterator>
// implementation for random access iterators:
template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
x += n; // constant time
}
template<typename Iterator>
constexpr bool IsBidirectionalIterator =
IsConvertible<
typename std::iterator_traits<Iterator>::iterator_category,
std::bidirectional_iterator_tag>;
// implementation for bidirectional iterators:
template<typename Iterator, typename Distance>
EnableIf<IsBidirectionalIterator<Iterator> &&
!IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
if (n > 0) {
for ( ; n > 0; ++x, --n) { //linear time
}
} else {
for ( ; n < 0; --x, ++n) { //linear time
}
}
}
// implementation for all other iterators:
template<typename Iterator, typename Distance>
EnableIf<!IsBidirectionalIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
if (n < 0) {
throw "advanceIter(): invalid iterator category for negative n";
}
while (n > 0) { //linear time
++x;
--n;
}
}
By making the EnableIf condition of each function template mutually exclusive with the EnableIf conditions of every other function template, we ensure that, at most, one of the function templates will succeed template argument deduction for a given set of arguments.
Our example illustrates one of the disadvantages of using EnableIf for algorithm specialization: Each time a new variant of the algorithm is introduced, the conditions of all of the algorithm variants need to be revisited to ensure that all are mutually exclusive. In contrast, introducing the bidirectional-iterator variant using tag dispatching (Section 20.2 on page 467) requires just the addition of a new advanceIterImpl() overload using the tag std::bidirectional_iterator_tag.
Both techniques—tag dispatching and EnableIf—are useful in different contexts: Generally speaking, tag dispatching supports simple dispatching based on hierarchical tags, while EnableIf supports more advanced dispatching based on arbitrary sets of properties determined by type traits.
EnableIf is typically used in the return type of the function template. However, this approach does not work for constructor templates or conversion function templates, because neither has a specified return type.5 Moreover, the use of EnableIf can make the return type very hard to read. In such cases, we can instead embed the EnableIf in a defaulted template argument, as follows:
typeoverload/container1.hpp
#include <iterator>
#include "enableif.hpp"
#include "isconvertible.hpp"
template<typename Iterator>
constexpr bool IsInputIterator =
IsConvertible<
typename std::iterator_traits<Iterator>::iterator_category,
std::input_iterator_tag>;
template<typename T>
class Container {
public:
// construct from an input iterator sequence:
template<typename Iterator,
typename = EnableIf<IsInputIterator<Iterator>>>
Container(Iterator first, Iterator last);
// convert to a container so long as the value types are convertible:
template<typename U, typename = EnableIf<IsConvertible<T, U>>>
operator Container<U>() const;
};
However, there is a problem here. If we attempt to add yet another overload (e.g., a more efficient version of the Container constructor for random access iterators), it will result in an error:
// construct from an input iterator sequence:
template<typename Iterator,
typename = EnableIf<IsInputIterator<Iterator> &&
!IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);
template<typename Iterator,
typename = EnableIf<IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last); // ERROR: redeclaration
// of constructor template
The problem is that the two constructor templates are identical except for the default template argument, but default template arguments are not considered when determining whether two templates are equivalent.
We can alleviate this problem by adding yet another defaulted template parameter, so the two constructor templates have a different number of template parameters:
// construct from an input iterator sequence:
template<typename Iterator,
typename = EnableIf<IsInputIterator<Iterator> &&
!IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);
template<typename Iterator,
typename = EnableIf<IsRandomAccessIterator<Iterator>>,
typename = int> // extra dummy parameter to enable both constructors
Container(Iterator first, Iterator last); //OK now
It’s worth noting here that C++17’s constexpr if feature (see Section 8.5 on page 134) avoids the need for EnableIf in many cases. For example, in C++17 we can rewrite our advanceIter() example as follows:
typeoverload/advance3.hpp
template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n) {
if constexpr(IsRandomAccessIterator<Iterator>) {
// implementation for random access iterators:
x += n; // constant time
}
else if constexpr(IsBidirectionalIterator<Iterator>) {
// implementation for bidirectional iterators:
if (n > 0) {
for ( ; n > 0; ++x, --n) { //linear time for positive n
}
} else {
for ( ; n < 0; --x, ++n) { //linear time for negative n
}
}
}
else {
// implementation for all other iterators that are at least input iterators:
if (n < 0) {
throw "advanceIter(): invalid iterator category for negative n";
}
while (n > 0) { //linear time for positive n only
++x;
--n;
}
}
}
This is much clearer. The more-specialized code paths (e.g., for random access iterators) will only be instantiated for types that can support them. Therefore, it is safe for code to involve operations not present on all iterators (such as +=) so long as it is within the body of an appropriately-guarded if constexpr.
However, there are downsides. Using constexpr if in this way is only possible when the difference in the generic component can be expressed entirely within the body of the function template. We still need EnableIf in the following situations:
• Different “interfaces” are involved
• Different class definitions are needed
• No valid instantiation should exist for certain template argument lists.
It is tempting to handle that last situation with the following pattern:
template<typename T>
void f(T p) {
if constexpr (condition<T>::value) {
// do something here…
}
else {
// not a T for which f() makes sense:
static_assert(condition<T>::value, "can’t call f() for such a T");
}
}
Doing so is not advisable because it doesn’t work well with SFINAE: The function f<T>() is not removed from the candidates list and therefore may inhibit another overload resolution outcome. In the alternative, using EnableIf f<T>() would be removed altogether when substituting EnableIf<…> fails substitution.
The techniques presented so far work well, but they are often somewhat clumsy, may use a fair amount of compiler resources, and, in error cases, may lead to unwieldy diagnostics. Many generic library authors are therefore looking forward to a language feature that achieves the same effect more directly. A feature called concepts will likely be added to the language for that reason; see Section 6.5 on page 103, Section 18.4 on page 377, and Appendix E.
For example, we expect our overloaded container constructors would simply look as follows:
typeoverload/container4.hpp
template<typename T>
class Container {
public:
//construct from an input iterator sequence:
template<typename Iterator>
requires IsInputIterator<Iterator>
Container(Iterator first, Iterator last);
// construct from a random access iterator sequence:
template<typename Iterator>
requires IsRandomAccessIterator<Iterator>
Container(Iterator first, Iterator last);
// convert to a container so long as the value types are convertible:
template<typename U>
requires IsConvertible<T, U>
operator Container<U>() const;
};
The requires clause (discussed in Section E.1 on page 740) describes the requirements of the template. If any of the requirements are not satisfied, the template is not considered a candidate. It is therefore a more direct expression of the idea expressed by EnableIf, supported by the language itself.
The requires clause has additional benefits over EnableIf. Constraint subsumption (described in Section E.3.1 on page 744) provides an ordering among templates that differ only in their requires clauses, eliminating the need for tag dispatching. Additionally, a requires clause can be attached to a nontemplate. For example, to provide a sort() member function only when the type T is comparable with <:
template<typename T>
class Container {
public:
…
requires HasLess<T>
void sort() {
…
}
};
Class template partial specializations can be used to provide alternate, specialized implementations of a class template for specific template arguments, much like we used overloading for function templates. And, like overloaded function templates, it can make sense to differentiate those partial specializations based on properties of the template arguments. Consider a generic Dictionary class template with key and value types as its template parameters. A simple (but inefficient) Dictionary can be implemented so long as the key type provides just an equality operator:
template<typename Key, typename Value>
class Dictionary
{
private:
vector<pair<Key const, Value>> data;
public:
//subscripted access to the data:
value& operator[](Key const& key)
{
// search for the element with this key:
for (auto& element : data) {
if (element.first == key){
return element.second;
}
}
// there is no element with this key; add one
data.push_back(pair<Key const, Value>(key, Value()));
return data.back().second;
}
…
};
If the key type supports a < operator, we can provide a more efficient implementation based on the standard library’s map container. Similarly, if the key type supports hashing operations, we can provide an even more efficient implementation based on the standard library’s unordered_map.
The way to enable/disable different implementations of class templates is to use enabled/disabled partial specializations of class templates. To use EnableIf with class template partial specializations, we first introduce an unnamed, defaulted template parameter to Dictionary:
template<typename Key, typename Value, typename = void>
class Dictionary
{
… //vector implementation as above
};
This new template parameter serves as an anchor for EnableIf, which now can be embedded in the template argument list of the partial specialization for the map version of the Dictionary:
template<typename Key, typename Value>
class Dictionary<Key, Value,
EnableIf<HasLess<Key>>>
{
private:
map<Key, Value> data;
public:
value& operator[](Key const& key) {
return data[key];
}
…
};
Unlike with overloaded function templates, we don’t need to disable any condition on the primary template, because any partial specialization takes precedence over the primary template. However, when we add another implementation for keys with a hashing operation, we need to ensure that the conditions on the partial specializations are mutually exclusive:
template<typename Key, typename Value, typename = void>
class Dictionary
{
… // vector implementation as above
};
template<typename Key, typename Value>
class Dictionary<Key, Value,
EnableIf HasLess Key> && !HasHash Key>>> {
{
… // map implementation as above
};
template typename Key, typename Value>
class Dictionary Key, Value,
EnableIf HasHash Key>>>
{
private:
unordered_map Key, Value> data;
public:
value& operator[](Key const& key) {
return data[key];
}
…
};
Tag dispatching, too, can be used to select among class template partial specializations. To illustrate, we define a function object type Advance<Iterator> akin to the advanceIter() algorithm used in earlier sections, which advances an iterator by some number of steps. We provide both the general implementation (for input iterators) as well as specialized implementations for bidirectional and random access iterators, relying on an auxiliary trait BestMatchInSet (described below) to pick the best match for the iterator’s category tag:
// primary template (intentionally undefined):
template<typename Iterator,
typename Tag =
BestMatchInSet<
typename std::iterator_traits<Iterator>
::iterator_category,
std::input_iterator_tag,
std::bidirectional_iterator_tag,
std::random_access_iterator_tag>>
class Advance;
// general, linear-time implementation for input iterators:
template<typename Iterator>
class Advance<Iterator, std::input_iterator_tag>
{
public:
using DifferenceType =
typename std::iterator_traits<Iterator>::difference_type;
void operator() (Iterator& x, DifferenceType n) const
{
while (n > 0) {
++x;
--n;
}
}
};
// bidirectional, linear-time algorithm for bidirectional iterators:
template<typename Iterator>
class Advance<Iterator, std::bidirectional_iterator_tag>
{
public:
using DifferenceType =
typename std::iterator_traits<Iterator>::difference_type;
void operator() (Iterator& x, DifferenceType n) const
{
if (n > 0) {
while (n > 0) {
++x;
--n;
}
} else {
while (n < 0) {
--x;
++n;
}
}
}
};
// bidirectional, constant-time algorithm for random access iterators:
template<typename Iterator>
class Advance<Iterator, std::random_access_iterator_tag>
{
public:
using DifferenceType =
typename std::iterator_traits<Iterator>::difference_type;
void operator() (Iterator& x, DifferenceType n) const
{
x += n;
}
}
This formulation is quite similar to that of tag dispatching for function templates. However, the challenge is in writing the trait BestMatchInSet, which intends to determine which is the most closely matching tag (of the input, bidirectional, and random access iterator tags) for the given iterator. In essence, this trait is intended to tell us which of the following overloads would be picked given a value of the iterator’s category tag and to report its parameter type:
void f(std::input_iterator_tag);
void f(std::bidirectional_iterator_tag);
void f(std::random_access_iterator_tag);
The easiest way to emulate overload resolution is to actually use overload resolution, as follows:
// construct a set of match() overloads for the types in Types…:
template<typename… Types>
struct MatchOverloads;
// basis case: nothing matched:
template<>
struct MatchOverloads<> {
static void match(…);
};
// recursive case: introduce a new match() overload:
template<typename T1, typename… Rest>
struct MatchOverloads<T1, Rest…> : public MatchOverloads<Rest…> {
static T1 match(T1); // introduce overload for T1
using MatchOverloads<Rest…>::match;// collect overloads from bases
};
// find the best match for T in Types…
: template<typename T, typename… Types>
struct BestMatchInSetT {
using Type = decltype(MatchOverloads<Types…>::match(declval<T>()));
};
template<typename T, typename… Types>
using BestMatchInSet = typename BestMatchInSetT<T, Types…>::Type;
The MatchOverloads template uses recursive inheritance to declare a match() function with each type in the input set of Types. Each instantiation of the recursive MatchOverloads partial specialization introduces a new match() function for the next type in the list. It then employs a using declaration to pull in the match() function(s) defined in its base class, which handles the remaining types in the list. When applied recursively, the result is a complete set of match() overloads corresponding to the given types, each of which returns its parameter type. The BestMatchInSetT template then passes a T object to this set of overloaded match() functions and produces the return type of the selected (best) match() function.6 If none of the functions matches, the void-returning basis case (which uses an ellipsis to capture any argument) indicates failure.7 To summarize, BestMatchInSetT translates a function-overloading result into a trait and makes it relatively easy to use tag dispatching to select among class template partial specializations.
The essence of the EnableIf technique is to enable a particular template or partial specialization only when the template arguments meet some specific criteria. For example, the most efficient form of the advanceIter() algorithm checks that the iterator argument’s category is convertible to std::random_access_iterator_tag, which implies that the various random-access iterator operations will be available to the algorithm.
What if we took this notion to the extreme and encoded every operation that the template performs on its template arguments as part of the EnableIf condition? The instantiation of such a template could never fail, because template arguments that do not provide the required operations would cause a deduction failure (via EnableIf) rather than allowing the instantiation to proceed. We refer to such templates as “instantiation-safe” templates and sketch the implementation of such templates here.
We start with a very basic template, min(), which computes the minimum of two values. We would typically implement such as a template as follows:
template<typename T>
T const& min(T const& x, T const& y)
{
if (y < x) {
return y;
}
return x;
}
This template requires the type T to have a < operator able to compare two T values (specifically, two T const lvalues) and then implicitly convert the result of that comparison to bool for use in the if statement. A trait that checks for the < operator and computes its result type is analogous to the SFINAE-friendly PlusResultT trait discussed in Section 19.4.4 on page 424, but we show the LessResultT trait here for convenience:
typeoverload/lessresult.hpp
#include <utility> // for declval()
#include <type_traits> // for true_type and false_type
template<typename T1, typename T2>
class HasLess {
template<typename T> struct Identity;
template<typename U1, typename U2> static std::true_type
test(Identity<decltype(std::declval<U1>() < std::declval<U2>())>*);
template<typename U1, typename U2> static std::false_type
test(…);
public:
static constexpr bool value = decltype(test<T1, T2>(nullptr))::value;
};
template<typename T1, typename T2, bool HasLess>
class LessResultImpl {
public:
using Type = decltype(std::declval<T1>() < std::declval<T2>());
};
template<typename T1, typename T2>
class LessResultImpl<T1, T2, false> {
};
template<typename T1, typename T2>
class LessResultT
: public LessResultImpl<T1, T2, HasLess<T1, T2>::value> {
};
template<typename T1, typename T2>
using LessResult = typename LessResultT<T1, T2>::Type;
This trait can then be composed with the IsConvertible trait to make min() instantiation-safe:
typeoverload/min2.hpp
#include "isconvertible.hpp"
#include "lessresult.hpp"
template<typename T>
EnableIf<IsConvertible<LessResult<T const&, T const&>, bool>,
T const&>
min(T const& x, T const& y)
{
if (y < x) {
return y;
}
return x;
}
It is instructive to try to call this min() function with various types with different < operators (or missing the operator entirely), as in the following example:
typeoverload/min.cpp
#include"min.hpp"
struct X1 { };
bool operator< (X1 const&, X1 const&) { return true; }
struct X2 { };
bool operator<(X2, X2) { return true; }
struct X3 { };
bool operator<(X3&, X3&) { return true; }
struct X4 { };
struct BoolConvertible {
operator bool() const { return true; } // implicit conversion to bool
};
struct X5 { };
BoolConvertible operator< (X5 const&, X5 const&)
{
return BoolConvertible();
}
struct NotBoolConvertible { // no conversion to bool
};
struct X6 { };
NotBoolConvertible operator< (X6 const&, X6 const&)
{
return NotBoolConvertible();
}
struct BoolLike {
explicit operator bool() const { return true; } // explicit conversion to bool
};
struct X7 { };
BoolLike operator< (X7 const&, X7 const&) { return BoolLike(); }
int main()
{
min(X1(), X1()); // X1 can be passed to min()
min(X2(), X2()); // X2 can be passed to min()
min(X3(), X3()); // ERROR: X3 cannot be passed to min()
min(X4(), X4()); // ERROR: X4 can be passed to min()
min(X5(), X5()); // X5 can be passed to min()
min(X6(), X6()); // ERROR: X6 cannot be passed to min()
min(X7(), X7()); // UNEXPECTED ERROR: X7 cannot be passed to min()
}
When compiling this program, notice that while there are errors for four of the different min() calls—for X3, X4, X6, and X7—the errors do not come from the body of min(), as they would have with the non-instantiation-safe variant. Rather, they complain that there is no suitable min() function, because the only option has been eliminated by SFINAE. Clang produces the following diagnostic:
min.cpp:41:3: error: no matching function for call to ’min’
min(X3(), X3()); // ERROR: X3 cannot be passed to min
^~~
./min.hpp:8:1: note: candidate template ignored: substitution failure
[with T = X3]: no type named ’Type’ in
’LessResultT<const X3 &, const X3 &>’
min(T const& x, T const& y)
Thus, the EnableIf is only allowing instantiation for those template arguments that meet the requirements of the template (X1, X2, and X5), so we never get an error from the body of min(). Moreover, if we had some other overload of min() that might work for these types, overload resolution could have selected one of those instead of failing.
The last type in our example, X7, illustrates some of the subtleties of implementing instantiation-safe templates. In particular, if X7 is passed to the non-instantiation-safe min(), instantiation will succeed. However, the instantiation-safe min() rejects it because BoolLike is not implicitly convertible to bool. The distinction here is particularly subtle: An explicit conversion to bool can be used implicitly in certain contexts, including in Boolean conditions for control-flow statements (if, while, for, and do), the built-in !, &&, and || operators, and the ternary operator ?:. In these contexts, the value is said to be contextually converted to bool.8
However, our insistence on having a general, implicit conversion to bool has the effect that our instantiation-safe template is overconstrained; that is, its specified requirements (in the EnableIf) are stronger than its actual requirements (what the template needs to instantiate properly). If, on the other hand, we had entirely forgotten the conversion-to-bool requirement, our min() template would have been underconstrained, and it would have allowed some template arguments that could cause an instantiation failure (such as X6).
To fix the instantiation-safe min(), we need a trait to determine whether a type T is contextually convertible to bool. The control-flow statements are not helpful in defining this trait, because statements cannot occur within a SFINAE context, nor are the logical operations, which can be overloaded for an arbitrary type. Fortunately, the ternary operator ?: is an expression and is not overloadable, so it can be exploited to test whether a type is contextually convertible to bool:
typeoverload/iscontextualbool.hpp
#include <utility> // for declval()
#include <type_traits> // for true_type and false_type
template<typename T>
class IsContextualBoolT {
private:
template<typename T> struct Identity;
template<typename U> static std::true_type
test(Identity<decltype(declval<U>()? 0 : 1)>*);
template<typename U> static std::false_type
test(…);
public:
static constexpr bool value = decltype(test<T>(nullptr))::value;
};
template<typename T>
constexpr bool IsContextualBool = IsContextualBoolT<T>::value;
With this new trait, we can provide an instantiation-safe min() with the correct set of requirements in the EnableIf:
typeoverload/min3.hpp
#include "iscontextualbool.hpp"
#include "lessresult.hpp"
template<typename T>
EnableIf<IsContextualBool<LessResult<T const&, T const&>>,
T const&>
min(T const& x, T const& y)
{
if (y < x) {
return y;
}
return x;
}
The techniques used here to make min() instantiation-safe can be extended to describe requirements for nontrivial templates by composing various requirement checks into traits that describe some class of types, such as forward iterators, and combining those traits within EnableIf. Doing so has the advantages of both better overloading behavior and the elimination of the error “novel” that compilers tend to produce while printing errors deep within a nested template instantiation. On the other hand, the error messages provided tend to lack specificity regarding which particular operation failed. Moreover, as we have shown with our small min() example, accurately determining and encoding the exact requirements of the template can be a daunting task. We explore debugging techniques that make use of these traits in Section 28.2 on page 654.
The C++ standard library provides iterator tags for input, output, forward, bidirectional, and random-access iterator tags, which we have used in our presentation. These iterator tags are part of the standard iterator traits (std::iterator_traits) and the requirements placed on iterators, so they can be safely used for tag dispatching purposes.
The C++11 standard library std::enable_if class template provides the same behavior as the EnableIfT class template presented here. The only difference is that the standard uses a lowercase member type named type rather than our uppercase Type.
Algorithm specialization is used in a number of places in the C++ standard library. For example, both the std::advance() and std::distance() have several variants based on the iterator category of their iterator arguments. Most standard library implementations tend to use tag dispatching, although, more recently, some have adopted std::enable_if to implement this algorithm specialization. Moreover, a number of C++ standard library implementations also use these techniques internally to implement algorithm specialization for various standard algorithms. For example, std::copy() can be specialized to call std::memcpy() or std::memmove() when the iterators refer to contiguous memory and their value types have trivial copy-assignment operators. Similarly, std::fill() can be optimized to call std::memset(), and various algorithms can avoid calling destructors when a type is known to have a trivial destructor. These algorithm specializations are not mandated by the C++ standard in the same way that they are for std::advance() or std::distance(), but implementers have chosen to provide them for efficiency reasons.
As introduced in Section 8.4 on page 131, the C++ standard library also hints strongly at the required use of std::enable_if<> or similar SFINAE-based techniques in its requirements. For example, std::vector has a constructor template to allow a vector to be built from an iterator sequence:
template<typename InputIterator>
vector(InputIterator first, InputIterator second,
allocator_type const& alloc = allocator_type());
with the requirement that “if the constructor is called with a type InputIterator that does not qualify as an input iterator, then the constructor shall not participate in overload resolution” (see §23.2.3 paragraph 14 of [C++11]). This phrasing is vague enough to allow the most efficient techniques of the day to be used for the implementation, but at the time it was added to the standard, the use of std::enable_if<> was envisioned.
Tag dispatching has been known in C++ for a long time. It was used in the original implementation of the STL (see [StepanovLeeSTL]), and is often used alongside traits. The use of SFINAE and EnableIf is much newer: The first edition of this book (see [VandevoordeJosuttisTemplates1st]) introduced the term SFINAE and demonstrated its use for detecting the presence of member types (for example).
The “enable if” technique and terminology was first published by Jaakko J¨arvi, Jeremiah Will-cock, Howard Hinnant, and Andrew Lumsdaine in [OverloadingProperties], which describes the EnableIf template, how to implement function overloading with EnableIf (and DisableIf) pairs, and how to use EnableIf with class template partial specializations. Since then, EnableIf and similar techniques have become ubiquitous in the implementation of advanced template libraries, including the C++ standard library. Moreover, the popularity of these techniques motivated the extended SFINAE behavior in C++11 (see Section 15.7 on page 284). Peter Dimov was the first to note that default template arguments for function templates (another C++11 feature) made it possible to use EnableIf in constructor templates without introducing another function parameter.
The concepts language feature (described in Appendix E) is expected in the next C++ standard after C++17. It is expected to make many techniques involving EnableIf largely obsolete. Meanwhile, C++17’s constexpr if statements (see Section 8.5 on page 134 and Section 20.3.3 on page 474) is also gradually eroding their pervasive presence in modern template libraries.
1 An better option for swap(), specifically, is to use std::move() to avoid copies in the primary template.
2 The categories in this case reflect concepts, and inheritance of concepts is referred to as refinement. Concepts and refinement are detailed in Appendix E.
3 EnableIf can also be placed in a defaulted template parameter, which has some advantages over placement in the result type. See Section 20.3.2 on page 472 for a discussion of EnableIf placement.
4 Usually, algorithm specialization is used only to provide efficiency gains, either in computation time or resource usage. However, some specializations of algorithms also provide more functionality, such as (in this case) the ability to move backward in a sequence.
5 While a conversion function template does have a return type—the type it is converting to—the template parameters in that type need to be deducible (see Chapter 15) for the conversion function template to behave properly.
6 In C++17, one can eliminate the recursion with pack expansions in the base class list and in a using declaration (Section 4.4.5 on page 65). We demonstrate this technique in Section 26.4 on page 611.
7 It would be slightly better to provide no result in the case of failure, to make this a SFINAE-friendly trait (see Section 19.4.4 on page 424). Moreover, a robust implementation would wrap the return type in something like Identity, because there are some types—such as array and function types—that can be parameter types but not return types. We omit these improvements for the sake of brevity and readability.
8 C++11 introduced the notion of contextual conversion to bool along with explicit conversion operators. Together, they replace uses of the “safe bool” idiom ([KarlssonSafeBool]), which typically involves an (implicit) user-defined conversion to a pointer-to-data member. The pointer-to-data member is used because it can be treated as a bool value but doesn’t have other, unwanted conversions, such as bool being promoted to int as part of arithmetic operations. For example, BoolConvertible() + 5 is (unfortunately) well-formed code.