Slashdot Mirror
C++ Templates: The Complete Guide
The C++ programming language is widely regarded as a good systems programming language, albeit a complex one fraught with low-level details and issues (though arguably this is what makes it good for certain kinds of systems programming). For perhaps a decade now, C++ has had a template mechanism - in programming language circles, it might more properly be called a form of parametric polymorphism. The template mechanism, like many other forms of parametric polymorphism, is potentially extremely powerful, but the complexity of C++ makes it tough to thoroughly master. That's where this book comes in.
Most likely, an experienced C++ programmer has at least used templates. If nothing else, use of the Standard Template Library (or STL) requires at least knowledge of how to use templates. If you use C++ enough to care about templates, you probably know what they are, at least roughly, and if you don't, this isn't the book from which to learn about them. It very clearly requires (and explicitly states in the introduction) that you need to know C++ before making effective use of the book.
Designing template classes, however, is another kettle of fish, and if you're in a position where you're building template classes for someone else to use, you probably need this book. Unless, like the book's authors, you moderate comp.lang.c++.moderated. If you are such a super C++ guru, you may still find this book useful - it is a truly stupendous catalog of the capabilities and subtleties of C++ templates. If nothing else, you'll find examples for well nigh every use to which you are likely to put C++ templates.
The book's strengths, then, are its authoritative and exhaustive detail. On the downside, its examples are dry and flavorless. Perhaps this is intentional, as a way to suggest how some feature can be used in a variety of situations. I prefer a combination of specific, concrete examples, followed by a generic example. The specifics motivate the need for a capability, while the generic showcases the broad, interrelated aspects of the capability. The authors didn't follow that approach. I would suspect this comes in part from their mutual roles in C++ standards bodies - a specific example could be seen as too limiting, and so were left out.
Another drawback, to my thinking, is its resolute focus on C++ to the exclusion of all other languages. Don't get me wrong - I read the title, and it's a C++ book, so I don't expect it to teach me Scheme, much less Haskell. However, I think the complexities of C++ templates might have been easier to tackle and understand with at least pointers to other ways it could have been (and has been) done. If nothing else, citations of alternative approaches would be a useful source for the motivated reader. As it is, it doesn't even deal with differences between C++ implementations - it doesn't even list GCC in the index.
All in all, though, C++ Templates: The Complete Guide is exactly what it claims to be. It's an in-depth treatment of C++ templates and how they work. It isn't a cookbook for practical applications, nor is it a guide to further in-depth exploration of parametric polymorphism. But it is definitely a handy reference for the working C++ programmer to have on her shelf. If you're a working C++ programmer, I'd recommend it. If you aren't, you might want to pass on this one.
You can purchase C++ Templates: The Complete Guide from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
But then you loose the flexibility of multiple inheritance if everything ultimately has a single parent. It's always going to be a trade-off. If there was "one right way" to do everything, we'd all be out of jobs within the next decade :-)
Well, I'm going against my grain here (being a Java lover), but templates mean that you ensure cast.
For example, I make a stack in C++:
Stack bleh<int> = new Stack();
int i = 1;
bleh.push( i );
(excuse my syntax, I havne't C++'ed in a few years) and I have a stack full of ints.
If i use a java container:
Stack javaStack = new Stack();
javaStack.push( new Integer( 12 ) );
I lose cast. If I pop from C++'s bleh, I'm guaranteed to have an int. If I pop from Java's javaStack, I'm getting a java.lang.Object. I have to force cast and have a chance of a runtime exception.
That is one major reason why templates are a good thing.
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
You are forgetting one of the biggest advantages to generics such as templates, speed. When templates are used much if not all of the binding is accomplished statically at compile time, when inheritance is used much if not all of the binding occurs at runtime. When you use inheritance every call to a virtual method requires a lookup to the vtable, this overhead is non-exsistent in templates. This is not an issue if you are writing bloated desktop apps in Java, but embedded or system-level applications demand the highest speeds possible.
a fairly well thought out, educated, concise, relevant comment on the article..
WHO ARE YOU AND WHAT HAVE YOU DONE WITH SLASHDOT!?
I'm just throwing this out there but anyone that knows any better please feel free to present an argument:
... check out blitz++. :) And the errors you can get when compiling are simply astounding. AFAICT, though, it's damn fast.
We use the blitz++ library in our laboratory due to benchmark findings that it is an extraordinarily fast package of matrix-type operations. It has been repeatedly argued that the speed of the library is due to the fact that it is entirely (I believe) implemented with templates.
If you'd like to read some hairy code
So, no, templates don't necessarily lead to bloating/ugliness/slowdowns/whatever if done properly.
As my father lik@(munch munch)...
One of the major strengths of templates is to avoid exactly the situation that Java everything-from-Object inheritance causes in collections.
In other words, this code:
gets boring really quickly. Templates in collections saves you all that downcasting.In fact, it's so useful, it's appearing in Java in JDK1.5, courtesy of JSR 14.
But far beyond convenience when typing, the important point is that using templates or generics in collections turns the typesafety of collections into a compile-time check rather than a runtime exception. Which is a Good Thing.
check out this extension:
http://www.cis.unisa.edu.au/~pizza/gj/
if (!signature) { throw std::runtime_error("No sig!"); }
I use templates with virtually every class and method I write: the STL. I couldn't live without it. It simplifies my development efforts, and helps me produce C++ solutions faster and with greater reliability. So far none of the applications have needed performance tuning. I'm sure there are situations where it is in appropriate, just not in my circles. I shudder when I think back to my C++ days prior to using the STL. So, I'm all for it and the ditching of the pre-processor and basing things on void*.
I should have completed my thoughts before posting.
I wanted to conclude that the only way to ensure cast with java's is either
A.) Write a wrapper around the collection/map (where the accessors cast to the object, eg:
public void setStack( Integer input )
).
B.) Use arrays
The big downfall of java.lang.Object is unsure cast (so you have to be careful with your coding, and follow good polymorphic code styles).
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
You imply that inheriting from a base class is always better, but that's not necessarially true.
The guy(s) who wrote the STL Containter Classes did it that way (using templates) because they think it's better than having all the objects inherit from one base. It's a style of programming called Generic Programming.
The basis of Java is dynamic run-time polymorphism. Using templates and generic programming techinques most run-time polymorphic algorithims can be reimplemented using compile-time polymorphism, which is much faster. That's what the C++ STL container classes are. That's where the power of templates are.
p.s. I've looked at the book in the article and I would describe it as an entire book of special cases. It explains things like recursive template definitions. Things that are so confusing that I try and stay away from most of them. They make code un-readable to anyone but a template expert. Then again, I don't write templated libraries either.
Aw crap, ninjas!
"If you'd like to read some hairy code ... check out blitz++. :) And the errors you can get when compiling are simply astounding."
That is my biggest complaint with templates. Compilation errors can be horrendous, especially as they often appear far from point where you've made the error. My second biggest complaint are the debugger symbols that get produced for templates.
If the only thing you're ever pushing on the stack is an Integer, then there is no risk of error from casting back to Integer when you pop off.
But you can't be absolutely sure. Yes, in practice, we generally assume everything is ok, and we rarely have trouble, but when you get down to reuse things can get hairy (hey, the compiler isn't stopping me from adding my String into the Stack, so why not?).
The nice thing about Java to counter, though, is reflection. You can always check the class type and methods before casting.
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
Templates only seem to be a necessary evil in OO languages that don't ultimately inherit all objects from one object.
This is a naive view that circa 1992 C++ collection class designers used to share. The OO-container strategy was proven to be slow and not type-safe. The designer of the C++ Standard Template Library (STL) Stepanov does not even believe in OO programming - he calls OO a hoax. I personally would not go that far, but I appreciate that OO and generics are completely independent concepts. Furthermore, an STL map or vector working on types directly is much more space efficient than any OO container-based approach because each object contained does not require OO overhead. Indeed, native types (ints, doubles, etc) in vectors can be nearly as efficiently stored and accessed under STL as would C style arrays. No need for awkward casting or unnecessary and slow boxing/unboxing. To sumamrize, C++ templates and the STL fit in perfectly with the C++'s "zero overhead" principle.
Microsoft just doesnt't compile them properly and it is very frustrating to all C++ programmers. Chances are, if you write C++ in the commercial world, your company has the very wise policy of making sure you stay roughly within the capabilities of the most popular compilers. This basically means you can use STL's vector, string, and list, and a pretty small collection of others. This, in my opinion, is a programmer's tragedy.
Utility C++ templates allow it to create and use some amazing things. I personally rarely write anything but the most simple ones, but when I'm allowed, there are huge libraries of amazing template classes. I learned ML at some point, and I remember the wonder when I happened upon the tuple template class for c++. With the exception of the fact you are forced to carry the type around (as a typedef of course), it works exactly like an ML tuple, a tool I came to love in my short time with ML. Someone simply wrote the template, and it was in C++ too! (a tuple is like an STL pair, but has an arbitrary number of members, set on construction).
Of course, even VC7 doesn't compile it. If you work at Microsoft in the Visual Studio area, PLEASE tell them to get standard compliant already! Yeah yeah templates can be slow to compile, but give us the option at least!
Your signatures belong to me.
Can I just point out that as well as people who don't program in C++, "C++ Templates: The Complete Guide" will also be of limited interest to those who can't read, as well as those who can but read only Cantonese, not English. It is of limited use for those looking for a guid on changing the timing belts in '98 Pintos, and as a guide to the wines of the Alsace region it is sadly lacking. Dr Aloquin Samovar reports from the Naval Hospital that the book is not suitable for use by transplant surgeons as a temporary heart.
~~~~~ BigLig2? You mean there's another one of me?
Just like macros can bloat your code, so can templates. If you put "real" code in templates, it will be duplicated; however, consider that you would have probably had to write it anyway, and having template instances is FAR better than having cut-n-paste code. STL instances can get pretty big because they have lots of memory management code in there and type-specific operations; this is good because it gives you type safety and proper element assignments. You can implement it another way, but you have to sacrifice something. Either it is type safety (like Java does with its containers), or correct element handling (escuse the shameless plug for my own ustl library).
That's too bad, because 9 out of 10 times when I've had troubles with templates it's because of differences between C++ implementations. Beautiful, well thought out, intricate standards-compliant examples are useless if I can't actually get them to compile with my real-world compiler!
The book I'm looking for is the one that gives me real-world recipes for getting around bone-headded compilers. For example, there are at least 3 different ways to declare templatized friend functions depending on the compiler. Only one is correct according to the standard, but the standard isn't worth a whole lot to me today if the compilers I'm stuck using don't follow it. And likewise, an advanced templates book isn't of much use to me today if the examples won't compile on my compilers.
First, there are some significant errata (and a lot of minor typos). Get the errata list and the code for all of the examples from one of the authors at his website. Second, some of these techniques depend on features that aren't yet available in many compilers. Don't expect them all to work yet. They do discuss that in the book.
With that said, I'm not sure that I would have rated this book a 10, but it's close enough that I'm not arguing. It is not a light read, nor should it be. This book and Andrei Alexandrescu's Modern C++ Design have convinced me that C++ templates are much more powerful, useful and complex than I realized. In fact, if I hadn't read Alexandrescu's book first, I wouldn't have thought C++ Templates was missing anything. These two books should be on the shelf of anyone who wants to use the full power of templates.
The net will not be what we demand, but what we make it. Build it well.
GJ is the old implementation of Java Generics. It has since evolved into JSR-014. Sun has a prototype implementation of a compiler that supports generics, and there's even an entire forum for discussing Java generics.
What a fool believes, he sees, no wise man has the power to reason away.
True that. Not using the STL is like saying you will rewrite the entire Java API for your application, save the base Object.
Some people say they use the good ole void* instead of a template. Those people sometimes do memory debugging for months.
--------
Free your mind.
No, templates are often anti-bloat. With a good optimizing compiler, a dizzying heirarchy of layers of abstraction can often compile down to 2 or 3 machine opcodes. If you understand how to use STL properly (which includes double-checking your results by disassembling critical points in the binary and inspecting them) you can often get code that is almost as fast as hand-coded assembly. I think that in general, if you use the other main approach to abstraction in C++ (virtual method calls), it's harder for the compiler to crush all of the layers of abstraction down to zero.
The main problem with C++ templates IMO is that they feel "brittle". It's hard to create large modular programs because of C++ #include dependencies and binary interface difficulties. I think that the best approach for large programs is to identify the performance-critical pieces and code them up in C++/STL as native modules for a nice high-level language like Python, then use the high-level language to glue everything together.
You're also being left behind in the dust. Modern C++ is all about exploiting templates to simplify development, and even reduce code bloat (by making it easier to reuse common code) and increase performance (through automatic compile time generation of heavily inlined versions of algorithms).
If you make a huge template with lots of code that could be easily generalized for all types, then you're writing a bad template: You should factor all common code into a base class and make a template that contain the few parts of the code that are type specific. On the other hand, if your code can't easily be generalized for the types you need, templates save you the tedious and error prone task of maintaining multiple versions of your code specialized for multiple types.
In that respect templates dramatically reduce the amount of work you need to do, if applied properly.
As mentioned above, template techniques can dramatically improve performance over a generic algorithm by providing you with an automated way of generating heavily optimized inlined versions of an algorithm. The C++ template syntax is not really ideal for this, but the benefits from using templates for this are tremendous enough to make it worthwhile. Do a search for Vandevoorde's work on expression templates, or for Alexander Alexandrescu on Google to find more, or read Alexandrescu's articles in CUJ.
Continue to believe your prejudices if you want, but consider that if you can't use or write templates you've essentially shut yourself out of a huge segment of the C++ development job market. I would certainly never hire a "C++ developer" that don't at the very least have thorough experience with the STL, and preferrably understand how to write (and when to write) templates.
if (x instanceof Number) {
Number n = (Number) x;
}
Now time how much slower it is...
What a fool believes, he sees, no wise man has the power to reason away.
Debugging heavily templatized code is thoroughly nasty. Names are mangled beyond recognition for anyone not using a 500 column display or lots of scroll bars. Stepping through code in the debugger often yields senseless results -- you often cannot see the source for the instructions being generated without manually tracing through the headers and looking for every overload and template body declaration. Templates thorougly ambiguate linker symbols. Templates slow compiles to a crawl, often adding tens or hundreds of thousands of lines to every inclusion of a given header in order to define the types it uses. With subtly improper use, templates can bloat code size astronimically and create horrendous execution bloat.
I don't know how many weeks I've lost to helping others debug or rewrite their code because they thought they would do something "clever" with templates and they ended up creating a maze. And bringing in third-party code with templatized interfaces has frequently required more time to debug and adapt than it would have taken to create the code anew.
If you're going to use templates, stick to simple container classes for now. Anything else should be considered theoretical research until the tools catch up. Let me repeat: development tools HAVE NOT CAUGHT UP WITH C++ TEMPLATES. There is no debugger available which makes templates as transparent as normal code, inline functions or even #defines.
And please save your first forray into templates for private projects. Don't inject your template experiments into code others are trying to use!
about templates is why this doesn't work:
main.cpp has never seen the implementation detials of the Foo constructor or the getFoo method, because g++ compiles each compilation unit in isolation. Conversely, no real code actually got generated when g++ compiled Foo.cpp, because that didn't contain a particular instantiation of a template, only the generic template definition.
The typical idiom is to put a '#include "Foo.cpp"' at the bottom of Foo.h. Then, when g++ compiles main.cpp, it will have seen the template's implementation in order to turn it into code.
This actually is explained in the book in question (chapter 6, I think).
However, it's nearly always fatal to mistake a tool (in this case, templates) for an end in itself (a functioning, maintainable codebase). No programming technology, be it HLL in general, objects, inheritance, or even templates will replace the need to think intelligently and make sound engineering decisions. You cannot build a skyscraper without the proper knowledge, no matter how excellent your hammer is.
The company I work for is among the few remaining who produce large-scale Windows products written entirely (ok, 99.9%) in C. My work is in a totally different world than the object oriented people, yet I still manage to accomplish everything an OO programmer could do. The secret here is not cute little language features, but discipline and correct design.
IMHO, templates do not deserve a book quite this large. Clearly, the author has had enormous experience in various situations, and knows how to solve all kinds of problems with templates, BUT -- remember the famous words passed down from people wiser than ourselves: "When all you have is a hammer, everything starts to look like a nail." Make sure the hammer isn't the only thing in your toolbox.
If you want to be able to recognize what is the truth and what are lies (more lies) with Sun's J2EE and Microsoft .NET proprietary frameworks (however, they have and will have place in computing) study Standard C++ with the STL. Just reading Bjarne Stroustrup's interviews you will avoid shortsightedness and you will learn much more about computing then reading anything else.
Doing work near the hardware is no excuse not to use templates. On the contrary, I'd say that when you work on extremely performance critical code there is one thing you don't want your developers to do: reinventing the wheel over and over for non trivial parts of code - reinventing the wheel is something that's all too often done badly. A well written template will allow you to reuse well written, well tested efficient and small code over and over again for different types and different conditions without that risk.
Another reason to use templates in an embedded system is that it allow you to easily write reusable components that can be adapted to a particular situation at compile time instead of runtime, opening up reuse opportunities across projects that would otherwise be difficult. This is often done with traits classes or policy classes that allow you to turn on and off functionality of a template at compile time, leaving out any code that isn't actually used.
In fact, this is an important property of templates in C++: Code that isn't used isn't even semantically analysed, and certainly not included in the generated executable, while the same is not true for members of any class that is externally visible. So you might actually reduce your code size merely by changing some classes into templates even if they don't depend on any type parameter.
Oh, and I've worked on embedded systems, using exactly the above techniques, including one platform that had 4MB flash and 4MB RAM that we ran Linux on together with FTP and SNMP servers that I wrote (in C++) as well as various other application code, a shell, etc., so I am familiar with how to make C++ code small, and that is one of the reasons I love templates.
So, instead of void Sort(int array[], size_t count) { ... } to sort an array of ints, you have template <typename T> Sort(T array[], size_t count) { ... } and the means to define a function that can sort an array of anything, with complete type-safety. Naturally, this generates a Sort function for each kind of array of things you need to sort... hmmm, there's room for improvement, no?
If you don't get the "there's room for improvement" part, and use templates to get nice type-specific varients of common functions, you will get code bloat, and that is one of the things that give templated-code a bad reputation. But, we're Slashdotters, we're smarter than that.
Recalling our C days, we immediately code void Sort(void *array, size_t count, int (*compare)(void *, void *)){ ... } where we pass a generic array pointer, and an additional pointer to a function that knows how to compare generic elements -- the specific call will then be something like: Sort((void *)pFoo, count, (int (*)(void *, void *))FooCompare). Gee, where did all our typesafety go? [Java programmers who are otherwise typesafety puristis grind their teeth at this point].
If you can imagine a generic implementation, you can combine the best of both approaches: hiding the type downcasting inside the generic templated definition:
inline void template <typename T> Sort(T array[], size_t count)
{
genericSort((void *)array, count, (int (*)(void *, void *)SortCompare<T>);
}
and for every array of type T you need to sort, define a int SortCompare<T>(T *arg1, T *arg2). (You could, alternately still pass that function to the generic sort routine, if you had different comparison functions for the same types of data (say, case-sensitive and case-insensitive sorting, or lexicographic vs. ASCII text sorting, etc.).)
Note the inline declaration. This lets a smart compiler code the call to the generic function inline, avoiding a double function call. In practice, if the only thing you are doing is some type casting, no additional code is generated.
So, you still have the potentially dangerous downcasting, but you've encapsulated it inside a template definition, relieving the application programmer to have to worry about it. Does all this mean extra work? It sure looks that you have to come up with a generic implementation and then make a nice and pretty templated type-safe wrapper around it.
This is true, and well worth the effort for code that has to be robust and easy to use, particularly by others. Library writers know this rule all too well.
Of course, in a pinch, or when a generic implementation is not obvious, or known to be non-existent, or when a particulary implementation exists for some types of objects, you can punt and let the compiler generate multiple instances of type-safe code, without a generic back-end implementation, accepting the code bloat that results.
In the end, it becomes a matter of compromise and wise design decisions. Unfortunately, with choice, comes the effort to chose, and to chose wisely. It is the unwise use of templates that leads to their sometimes ill-deserved "code bloat" reputation. One of the differences between the skilled and less-skilled programmer is the ability to make these choices correctly and quickly, leveraging the language features that let the corresponding design decisions be put into practice.
Other related C++ topics would include the notions that "multiple inheritence leads to slow code," "exception handling and run-time type information have high overhead". Again, one has to weigh the advantages offered by these techinques against the skill needed to use them wisely, and the performance penalty paid. I'll let someone else chime in now.
You could've hired me.
In other words, you better hope that your testing is good and that the bug that causes a string to get put on the stack doesn't only appear in a rare set of conditions.
The cake is a pie
This whole compile-time vs. run-time error business is a red herring.
When you say getting an error at compile-time is better, you are just saying that C++ ensures that your program fits in the straitjacket that you made for it, ignoring the fact that you've made a straitjacket in the first place!
Making a stack which is "int only" is totally specialized. How are you "accidentally" going to write code that asks for something else, if your problem is so focussed that it only needs ints?
You really think that using strings by mistake is going to be a major source of bugs?
The real problem is that C++ operations are type-specialized at compile time. C++ compilers, for instance, don't know how to add numbers unless they know the type at compile time. In a dynamic language, the addition operator knows how to add whatever numbers it sees at run-time.
For every set of bugs that a compile-time error catches, there is a corresponding set of desirable program behaviors that become more difficult to explain to the compiler. That's why the whole idea of "design patterns" caught fire in the C++ world. These design patterns are like a phrase book translating your desire into the C++ language. If you have a more flexible language, you don't need a phrase book as often!