Before C++, many coders thought that even though they were dangerous, #define macros were valuable. They were right in that they allowed code to be more "meta", but their price was high. With the advent of templates however, there is the opportunity for the same level of hard coded efficiency without the same dangerous lack of safety mechanisms.
Templates are compile time macros just like #define, but they are type safe, and can be used with C++ constructs better as they allow for overloading. Using a template can help you set some compile time asserts too, such as making sure that two arguments have the same type (like when you want to do a swap). All this is done at compile time and not with any hand waving either, it's just C++ compiler unrolling the code for you then compiling it as usual, just like a #define macro. The difference really is that the #define macro stuff doesn't know about C,C++,Pascal,Java, so can cause arbitrary damage.
So, if you're thinking that a piece of code might be better templated, but are worried about any overheads, don't.