views:

533

answers:

4

I read C++ Primer, and it says function template specialization is an advanced topic, but I am totally lost. Can anybody offer an example why function template specialization is important and necessary?

Why don't function templates support partial specialization while class templates do? What's the underlying logic?

+2  A: 

Basically the idea is that you can write templates that behave in a generic way for the general case, but can still handle special cases. One example of where specialization is used is in std::vector. std::vector<bool> is a specialization that packs the bool elements such that they only use one bit per element, not one byte. std::vector<T> works like a normal dynamic array for all other types.

The more advanced use for specialization is metaprogramming. For example, here's an example (from Wikipedia) of how to use template specialization to compute factorials at compile time.

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};
dsimcha
Curses, `vector<bool>`.
GMan
Yeh, vector<bool> is not the greatest example :)
Nikolai N Fetissov
Not *function* template specialization that was asked about.
Roger Pate
Have to agree with Roger Pate sorry, -1.
j_random_hacker
+3  A: 

Your question of why functions do not support partial specialization can be answered here. The code below shows how to implement the different specializations.

template<typename T>
bool Less(T a, T b)
{
    cout << "version 1 ";
    return a < b;
}
// Function templates can't be partially specialized they can overload instead.
template<typename T>
bool Less(T* a, T* b)
{
    cout << "version 2 ";
    return *a < *b;
}

template<>
bool Less<>(const char* lhs, const char* rhs)
{
    cout << "version 3 ";
    return strcmp(lhs, rhs) < 0;
}

int a = 5, b = 6;

cout << Less<int>(a, b) << endl;
cout << Less<int>(&a, &b) << endl;
cout << Less("abc", "def") << endl;
Jagannath
You can drop the `<int>` on the first two Less calls in the output statements.
Roger Pate
Could you make it clearer: often times specialization is not necessary for functions because there is already overloading that allows a single symbol to represent multiple functions and a decision mechanism to choose (resolve) which function to use based on a set of rules.
Matthieu M.
Great link. For me the most important point of that article was that function specialisations don't influence *which* function gets called -- they come into play only *after* the final template types have been decided. Overloading OTOH introduces a new "competitor" into the "which function should we call" competition.
j_random_hacker
This is a decent example of specialization and the link is great, but on second look I see nothing that says why function specialization is either important or necessary, and that, the way I read it, is what the OP is really asking. (I'm sure their book provides example of how to specialize, for example.)
Roger Pate
A: 

To illustrate why function template specialization is important, consider the std::swap template function. By default, std::swap(x, y) essentially does:

T temp = x;
x = y;
y = temp;

but this can be inefficient since it involves creating an extra copy of x and could do additional copying in the assignments. This is especially bad if x is large (for example, if it's a std::vector with many elements). Additionally, each of the above lines could fail and throw exceptions, potentially leaving x and y in bad, inconsistent states.

To address this, many classes provide their own swap methods (including std::vector) that instead swap the pointers to their internal data. This is more efficient and can be guaranteed to never fail.

But now you have a case where you can use std::swap(x, y) on some types but need to call x.swap(y) on other types. This is confusing, and it's bad for templates since they wouldn't be able to swap two objects in a generic, consistent way.

But std::swap can be specialized so that it calls x.swap(y) when called on specific types. That means you then can use std::swap everywhere and (hopefully) expect it to be well-behaved.

jamesdlin
A little narrow because the standard explicitly forbids overloading std::swap while explicitly allowing specializations (which leaves your own templates out in the cold as you can't partially specialize for them). The solution is to consistently use non-member swap functions (e.g. defined as friends), a `using std::swap;` using-declaration, and invoking ADL (Argument Dependent Lookup) with `swap(a, b)` (note no "std::" in front)---this result is more flexible and more generic for current C++ than specializing std::swap.
Roger Pate
Ah, right, actually specializing `std::swap` for `std::vector` this way would require partial specialization. Argh.
jamesdlin
+3  A: 

I cannot think of an example, and I've been trying nearly since you asked. As pointed out by Jagannath, it's been long-standing advice not to specialize functions, but instead overload them or use a traits class (which can be specialized, even partially specialized).

For example, if you need to swap two items, then relying on overloads is better (more predictable and more extensible):

template<class T>
void f() {
  T a, b;
  using std::swap; // brings std::swap into scope as "fallback"
  swap(a, b); // unqualified call (no "std::") so ADL kicks in
  // also look at boost::swap
}

And how you write a swap for your types:

// the cleanest way to do it for a class template:
template<class T>
struct Ex1 {
  friend void swap(Ex1& a, Ex1& b) { /* do stuff */ }
};

// you can certainly place it outside of the class instead---but in the
// same namespace as the class---if you have some coding convention
// against friends (which is common, but misguided, IMHO):
struct Ex2 {};
void swap(Ex2& a, Ex2& b) { /* do stuff */ }

Both of which allow Argument Dependent Lookup (ADL).

Other functions, such as a stringify/str or a repr (representation) can similarly be non-members and take advantage of ADL through overloading:

struct Ex3 {
  friend std::string repr(Ex3 const&) { return "<Ex3 obj>"; }
};

std::string repr(bool b) { return b ? "true" : "false"; }

// possible fallback:
template<class T>
std::string repr(T const& v) {
  std::ostringstream out;
  out << v;
  return out.str();
}
// but in this particular case, I'd remove the fallback and document that
// repr() must be overloaded appropriately before it can be used with a
// particular type; for other operations a default fallback makes sense

To look at it another way, it would be nice if function templates could serve as a registry for specific implementations, but due to limits (in current C++, not sure exactly what C++0x brings here) they don't work as well as either overloading or class templates for that registry purpose.

There is one use that is convenient but not important: easily defining certain specializations to be in a separate library, possibly a shared library (.so or .dll). This is convenient because it requires minimal changes to the generic template, but not important because it seems rare to me (in the wild, and certainly is rare in my experience) and implementors can still use either overloading or forwarding to a fully-specialized class template's unspecialized method.

Roger Pate
j_random_hacker
@j_random: Nope, all the code is valid and standard as-is; literally copy into a file (after appropriate #includes) and compile it: http://codepad.org/v45tt46L. (That repr isn't a template, btw, but if it was, it wouldn't need that extra syntax either, just like Ex1's swap doesn't need it.)
Roger Pate
Whoops, I somehow missed that you gave an in-place definition for `repr()` -- yes, that's totally valid. But if you had instead given just a declaration, with your "fallback" template definition and an appropriate specialisation declared beforehand, then the standard requires (14.5.3) that your friend declaration use either a *template-id* (e.g. `friend std::string repr<Ex3>(...);`) or a *qualified-id* (e.g. `friend std::string N::repr(...);`, and put the template in namespace `N`). I found compiler support to be very suspect in my tests unfortunately...
j_random_hacker
@j_random: Except I'm *not* specializing. I couldn't find a reason why it's important or necessary, so I'm giving examples of *overloading*.
Roger Pate
Yes I understand that, and agree overloading is appropriate. My 1st comment was a misunderstanding (sorry); my 2nd comment was a quibble with the final part of your prior comment: "(That repr isn't a template, btw, but if it was, it wouldn't need that extra syntax either, just like Ex1's swap doesn't need it.)" I was just pointing out that template friend syntax is weird, and awkwardly different from the syntax allowed when calling a function.
j_random_hacker
@j_random: Ah, now I see what you meant, but weird and awkward isn't required. This is fine: `template<class T> struct Ex4 { friend string repr(Ex4 const } };`. It is fairly intuitive (practically the same as writing a static method, just use 'friend') and requires nothing more, and this is how I recommend to write such overloads by default (compare to Ex1's swap).
Roger Pate