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.
Hi, have you ever heard of the STL?
/syle
Java's everything-inherits-from-Object model is annoying & sometimes rather ugly. There is a vocal group of Java programmers trying to add templates to Java, you should check it out before declaring templates an unnecessary evil.
Is this another book in their Professional Computing Series?
I've found several of them that I've read to be excellent references. They aren't textbooks, but they contain lots of information that is accessible and useable to people who write lots of code and want it to be understandable and maintainable.
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.
What idiot modded this down? It's a genuine question...
Templates are great because you can program generically but take none of the speed hit of using inheritance and virtual function calls.
Whereas in Java you get such abominations as an array of Integer objects, C++ templates allow you to have an array (or vector) of ints.
In theory, Java's approach looks nicer. But then in theory Java should not have atomic types (int, byte etc) - and yet we're stuck with them for performance reasons. Templates are all about performance.
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 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!
[and here's that once again with feeling (and better HTML)]
OK. Could someone please offer some informed comment on the following. (thanks in advance).
If I template a two-argument function in C++ to (e.g.) compare two instances of a class for equality (using the == operator) and print them to an ostream if they fail to match (using the << operator) [why yes, I was writing some unit testing infrastructure, why do you ask?] then:
- my template function will fail to compile if called with two instances of objects which lack the == and << operators.
- this is a broadly equivalent approach to defining a virtual base class (java interface) requiring implementation of these two operators and re-writing the template function to take pointers to the relevant base class. Users would need to derive from my base class to call my function (and hence would have to implement those two operators).
The latter approach (derivation) is more coding for the caller.
The former approach (templating) requires the coder to inspect my entire template function (or read the Fine Docs) to determine the interface s/he needs to implement to use it.
Both approaches are compile-time type safe.
Given that the two approaches are in some sense equivalent, are there good guidelines on when to use derivation instead of templates or vice versa?
PS. The equivalent for the STL would be that the list<type T> template was actually a class which manipulated objects which derive from a "Listable" interface.
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.
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.
Greg Comeau's is pretty damned good. Any compiler built off of EDG's (Edison Design Group) stuff is going to be compliant (including the export keyword)
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.
There is no reason why you can't have multiple inheritance if everything inherits from a single base class.
C++ might have problems because it would have to use virtual inheritance which probably hurt performance. Eiffel has a base class called ANY which is like Java's Object class. So you can declare lists like LIST[ANY] if you want, but it also has genericity allowing you to declare your list as LIST[INTEGER].
So, in other words, while your compiler is chugging along on Foo.cpp - it treats your template functions as Declarations, and won't instantiate the code until it knows what this code should look like (and it won't know this until parameter T is defined!).
Depending on class T (in this case an int, but say it's something that overloads the assignment operator), the implementation will be made.
"Doesn't a .h cause bloat in instances of Foo for each .cpp that uses it?"
Putting this in the header file would cause bloat, but only in your .o/.obj files since the linker will only pick one instance of your templatized Foot and use that to link, the others are ignored
(much like you can override the library malloc (or any other function) with your own, should you be so inclined).
"So why don't linkers get smarter"
Because if you were to put templates in your linker, you're actually postponing compilation into the linker -- in other words, you're doing away your linker and building one compiler that treats everything as "sort of" an include file.
Still do-able, but problematic for larger projects of a couple of hundred/thousand files.
Hope that answers the question.
(I wrote the book, so I'm hardly objective.)
We didn't include many references to specific compilers because version change so quicly.
However, we do point out various shortcomings of compilers (without naming them) and, when feasible, we present alternative programming techniques to work around the limitation. It's certainly not the main emphasis of the book, but you'll find such things sprinkled throughout.
However if you want more user friendly compiler error messages, that's another matter. A lot of work has gone into "compile time asserts", to catch as many problems as possible at compile time and give more intuitive errorts (in this case you got an error, but consider the problems if the classes supported the operators you needed but made them do something entirely different).
Instead of deriving, you could for instance check for an enum "supports_someinterface" in the types using a standard assert.
This allow you to use "assert(Foo::supports_interface_Bar);" in the functions that have specific requirements. Note that the value of the enum is irelevant as long as it's non-null, and since the enum is a constant value known at compile time, there should be no runtime overhead (neither space nor performance) of the assert at all if your compiler is reasonably smart.
With GCC, this gives me the reasonably friendly error message: "'supports_interface_Bar' is not a member of type `Foo'" instead of (or rather, in addition to) some hopelessly cryptic error message if I try to instantiate a template with the above assert on a type that doesn't have the enum.
Of course, you might not have the luxury of changing all types you might want to use with your template, and some of them may already fulfill the requirements even if they don't contain the enum.
Fear not, that's what traits are for. Declare a template. Specialize the template for any type that supports your interface, and instead of "assert(Foo:supports_interface_Bar)", you might do "assert(Supports<Foo>::interface_Bar)" or "assert(Supports<Foo>::requirement_HasOutputOperat or)".
Strategically placing these at the top of your functions also serve to document the requirements.
Ok, so I saved the simplest option for your case until last (the above is better suited for complex requirements, not something as simple as "this templates needs member functions A,B and C to be implemented) :
assert(&Foo::operator<<)
With GCC, this produces the error message "`operator<<' is not a member of type `A'" if the operator isn't supported. Place asserts covering all the member functions you need at the head of your function and you both have documentation and reasonable error messages.
The above should have no runtime cost at all provided that the compiler at compile time is willing to guarantee that Foo::operator<< will never occupy address 0. However, don't assume your C++ compiler that smart (GCC 2.96 doesn't appear to be, I haven't checked any newer versions), so one improvement: "assert(sizeof(&Foo::operator<<))". sizeof is evaluated at compiletime, resulting in a constant that in this case must be non-null, meaning the assert will neven trigger, meaning the compiler will discard the code (this was enough to make GCC optimize the thing away).
This leaves us with this nice little macro (who I'm sure someone will find a nasty problem with :-):
#define REQUIRE_MEMBER(expr__) assert(sizeof(&(expr__)))
Which can be used like this:
REQUIRE_MEMBER(Foo::operator<<);
Hot tip: sizeof() is extremely versatile for compile time testing whenever you can reduce the problem to either making code illegal in one case or return a constant expression (which is needed to apply sizeof to it), or when you an reduce a problem into a constant expression that will be a different size (that you can compare with a known quantity) depending on the outcome.
The book being reviewed contains at least one good example of this.
What development environment are you using?
All the ones I use do work transparently. Certainly, my debuggers demangle the names on the fly (I need extra effort to find the mangled name) and stepping simply steps through the generic code (or specialization if applicable).
This has been like that for at least 5 years.
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.
Actually, the C++ standard specifically does NOT require all pointers to be the same size. One of the reasons for this is that not all hardware platforms allow you to directly address every single byte, so that for instance a char pointer might need a pointer to the word a character is contained in and an offset into the word, or similar. The C++ standard only guarantee that all pointers to the same type are the same size.
Comeau C++ is standards compliant. Most compilers based off of the EDG front-end are very compliant. This includes Intel, Comeau's and SGI's C++ compilers. It does not include MS C++ 6 or Sun's C++ compiler, and look at how standards-compliant those are (on the other hand, Borland's compiler is quite good and it's not EDG-based).
Spirit has to be seen to be believed. Basically you contruct a parser which looks like normal extended Backus-Normal Form (EBNF) but the source you write is 100% C++ source code - not run through a preprocessor:
struct calculator : public grammar<calculator> {
template <typename ScannerT>
struct definition {
definition(calculator const& self) {
expression = term
>> *( ('+' >> term)[&do_add]
| ('-' >> term)[&do_subt]
);
term = factor
>> *( ('*' >> factor)[&do_mult]
| ('/' >> factor)[&do_div]
);
factor = lexeme_d[(+digit_p)[&do_int]]
| '(' >> expression >> ')'
| ('-' >> factor)[&do_neg]
| ('+' >> factor);
}
rule<ScannerT> expression, term, factor;
rule<ScannerT> const& start() const { return expression; }
};
};
This is truly a testimony to the power and expressiveness of C++ operator overloading and templates.
As an aside, Perl6 is slated to have lexer/yaccer rule syntax built into the language itself. It's really an exciting time for users of computer languages.
There is no difference at all in performance cost of a template function versus a non-template function. The generated code is exactly the same as if you had explicitly written a non-template function to do the same thing. So there is no performance loss at all due to template. (There might be due to some poor usage of templates, but you could say that about anything, even assembly language!)
On the other hand, templates allow a style of code that retains some flavour of OO polymorphism while being very fast, as all of the function calls etc are resolved at compile-time. The alternatives are to use dynamic polymorphism (slow), or bloat the source code by manually writing stupid functions like
void foo_SomeType(SomeType x) { ... }
... }
...
void foo_SomeOtherType(SomeOtherType x) {
Templates in C++ go much beyond typesafe collections. As an earlier poster commented, in technical circles it's referred to as "parametric polymorphism". For the layperson, you can think of it as a form of specialized code generation.
The best example of how much bigger they are than typesafe collections is the use of templates for traits and policies. Take the classic reference counted smart pointer, which usually looks like this:
SmartPtr<int> i_sp = new int(5);
cout << *i_sp << endl;
What about the question of whether SmartPtrs should be allowed to hold null pointers? Maybe in some case it's appropriate, but in others an exception should be thrown if it's attempted. Rather than having two different SmartPtr implementation, you add a new template parameters, the OwnershipPolicy type. The SmartPtr author than provides types like AssertCheckStrict and NoCheck. So then your code looks like this:
SmartPtr<int, NoCheck> i_sp = new int(5);
SmartPtr<int, AssertCheckStrict> j_sp new int(6);
This example comes from Alexandrescu's Modern C++ Design, and his Loki framework.
Though personally, I find little bloat to speak of. It has been literally a decade since I had to worry about memory size. (As opposed to worrying about speed literally yesterday.)
The largest C++ project I'm working on write now is about 7,000 lines of code. It makes heavy use of both the STL and templates. It runs about 500k on disk and seems to take between one and three megabytes of memory when run.
The cake is a pie