An Idiot's Guide to C++ Templates - Part 1(codeproject.com)
codeproject.com
An Idiot's Guide to C++ Templates - Part 1
http://www.codeproject.com/Articles/257589/An-Idiots-Guide-to-Cplusplus-Templates-Part-1
32 comments
> For example suppose that I have a class that has reference members. Those are fields specified with & - they are kind of like a pointer except that you can't change them, and you use . instead of ->. Because you can't change them, operator= is not generated for you. I didn't notice this until I tried to use one in an std::map< ... > and everything blew up.
This is what std::reference_wrapper is for.
> I don't care what kind of data structure this came from
Fortunately, neither does the STL.
for_each(begin(foo_container), end(foo_container), some_foo_op);
Do you know what kind of container foo_container is? It doesn't matter. It can be a set, vector, list, or even a plain array.
> And then you can dream up things like the ability to take an iterator< foo > and a method on foo that will return a bar, to get an iterator< bar >
You can do this with std::transform.
transform(begin(foo_container), end(foo_container), begin(bar_container), op_to_make_foo_into_bar);
edit: I see from your other response that what you actually want is streams or generators, not an iterator.
This is what std::reference_wrapper is for.
> I don't care what kind of data structure this came from
Fortunately, neither does the STL.
for_each(begin(foo_container), end(foo_container), some_foo_op);
Do you know what kind of container foo_container is? It doesn't matter. It can be a set, vector, list, or even a plain array.
> And then you can dream up things like the ability to take an iterator< foo > and a method on foo that will return a bar, to get an iterator< bar >
You can do this with std::transform.
transform(begin(foo_container), end(foo_container), begin(bar_container), op_to_make_foo_into_bar);
edit: I see from your other response that what you actually want is streams or generators, not an iterator.
As I said, my C++ experience is limited.
Thank you for demonstrating a better way to do it. Hopefully I'll remember that the next time that I need it. (Which is likely to be several years from now.)
Also you're right that I would like streams and generators. But, to me, it is the same abstraction as iteration. See, for instance, how Python does it.
Thank you for demonstrating a better way to do it. Hopefully I'll remember that the next time that I need it. (Which is likely to be several years from now.)
Also you're right that I would like streams and generators. But, to me, it is the same abstraction as iteration. See, for instance, how Python does it.
You should check out the boost iterator library. Depending on the application, you might be looking for either the function input iterator or the counting iterator.
I have avoided learning boost for the simple reason that on the rare occasions when I need C++, it has been apparent to me that I could easily spend longer trying to evaluate whether anything that is available would be a good fit for my problem, than it would take to be done.
Put another way, the effort of learning something needs to be amortized over all of the times that you'll likely use that knowledge. I use C++, rarely enough that I won't get much amortization. (And when I do use it, it is painful enough that I don't want to explore it just for personal enjoyment. Leading to my avoiding C++...)
Put another way, the effort of learning something needs to be amortized over all of the times that you'll likely use that knowledge. I use C++, rarely enough that I won't get much amortization. (And when I do use it, it is painful enough that I don't want to explore it just for personal enjoyment. Leading to my avoiding C++...)
"However luckily confusing backtrace message plus google usually leads to a useful stack overflow answer, else I'd find this process much more painful."
Template related error messages have historically been a huge pain, but modern versions of Clang and g++ are doing a much better job than they used to. If you haven't tried C++ recently (say last year or two), you might try again with a newer version of Clang.
Template related error messages have historically been a huge pain, but modern versions of Clang and g++ are doing a much better job than they used to. If you haven't tried C++ recently (say last year or two), you might try again with a newer version of Clang.
The iterator typing is much improved in C++11. It's just auto adt.begin().
There is less verbose repeating of verbosity. But the types did not change in anything like the way that I would like.
Try to translate http://perl.plover.com/Stream/stream.html into C++ iterators to see how the current abstraction limits the ways you can think about a program. By contrast suppose that my hypothetical iterator< foo > type was required to have a pointer overload, and supported the methods done() and next(). Now go back and try to translate that article - you'll find that it is pretty easy.
Try to translate http://perl.plover.com/Stream/stream.html into C++ iterators to see how the current abstraction limits the ways you can think about a program. By contrast suppose that my hypothetical iterator< foo > type was required to have a pointer overload, and supported the methods done() and next(). Now go back and try to translate that article - you'll find that it is pretty easy.
Instead of me trying to understand Perl, tell me what problem you are trying to solve that having an hypothetical iterator<foo> would help solve.
The interface that I describe can be backed by a collection, data streamed externally (eg from a file), or by something generated on the fly. Therefore you can write code for all three cases that looks very similar.
That article demonstrated the power of this idea by writing code that fairly efficiently generates the Hamming sequence, which consists of all positive integers whose only divisors are 2, 3, and 5. (So 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, ...)
That article demonstrated the power of this idea by writing code that fairly efficiently generates the Hamming sequence, which consists of all positive integers whose only divisors are 2, 3, and 5. (So 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, ...)
You can create your own type of iterator that when dereferenced spits out the next number/item, So long as your "end" iterator never matches your "current" iterator it will continue going on. Your "done" function is when "current" and "end" match. "next()" is "++current".
Indeed. First off, it is unrealistic to expect to rewrite perl/python scripts (much higher level scripting languages) in C++ and expect the same level of succinctness.
C++ is for larger , high performance applications.
The piper needs to be paid one way or another. If you rewrite a perl script in C++ for performance, the relative increase in verbosity is the price you pay.
C++ is for larger , high performance applications.
The piper needs to be paid one way or another. If you rewrite a perl script in C++ for performance, the relative increase in verbosity is the price you pay.
I accept that a price has to be paid for performance.
However I believe that a substantial amount of verbosity could be removed without impacting said performance. In fact C++11 removes some with type deduction.
I also get tired of typing some_big_type foo = some_big_type(); - is there a way to say, "I want this thing, and I want it to get the obvious default initialization?" Because what I type now is straight from the redundant department of redundancy department. (Yes, a typedef can make that shorter. You still write the idea twice.)
However I believe that a substantial amount of verbosity could be removed without impacting said performance. In fact C++11 removes some with type deduction.
I also get tired of typing some_big_type foo = some_big_type(); - is there a way to say, "I want this thing, and I want it to get the obvious default initialization?" Because what I type now is straight from the redundant department of redundancy department. (Yes, a typedef can make that shorter. You still write the idea twice.)
Try auto foo = some_big_type();
If you're not talking about initialization, but instead talking about construction, just do some_big_type foo; (no parens needed).
If you're not talking about initialization, but instead talking about construction, just do some_big_type foo; (no parens needed).
If you're not talking about initialization...
I thought I was very clear when I said: "I want this thing, and I want it to get the obvious default initialization?"
I often wound up typing something like this:
std::vector< my_big_type > list_foo = std::vector< my_big_type >();
It seemed useless the first time, and just got sillier as time went on.
I thought I was very clear when I said: "I want this thing, and I want it to get the obvious default initialization?"
I often wound up typing something like this:
std::vector< my_big_type > list_foo = std::vector< my_big_type >();
It seemed useless the first time, and just got sillier as time went on.
some_big_type foo;
Now foo has been created.
Want to pass parameters to its constructor:
some_big_type foo(parameters, go, here);
foo has been initialised.
Need a pointer?
auto *foo = new some_big_type foo(parameters, go, here);
Now foo has been created.
Want to pass parameters to its constructor:
some_big_type foo(parameters, go, here);
foo has been initialised.
Need a pointer?
auto *foo = new some_big_type foo(parameters, go, here);
[deleted]
The thing about a "generic" iterator is that not all iterators have the same capabilities. So while you might not care about the difference between a bidirectional iterator and a random access iterator, there are people who do and algorithms that can be implemented much more efficiently with the right iterator capabilities.
There are examples of iterators that use type erasure, but they still incorporate the iterator category in the type.
There are examples of iterators that use type erasure, but they still incorporate the iterator category in the type.
any_range covers the use-case of a generic iterator that doesn't care about the source: http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/ran...
In practice, it's not really useful all that often. It has non-zero overhead so it's not good default choice, and you rarely absolutely need it. Most situations where you'd want to return a value then do something with it can be transformed into passing a callback to the function instead, which lets you use a templated operator() to achieve the same result without the runtime overhead.
In practice, it's not really useful all that often. It has non-zero overhead so it's not good default choice, and you rarely absolutely need it. Most situations where you'd want to return a value then do something with it can be transformed into passing a callback to the function instead, which lets you use a templated operator() to achieve the same result without the runtime overhead.
The article does not describe the primary issue with using templates: that using templates leads to hard-to-manage non-modular code. Templates have their uses, but a big problem is that any change in template code means recompile of any code that uses it. Additionally, the interface contract is not well defined. Adopting an interface/inheritance approach generally leads to much more maintainable code.
And yes, you can use namespaces and careful template programming to give some modularity to the code, but in the end, if one code line change in one template header, that is used by multiple other template headers, and in turn by multiple libraries, means you have to recompile thousands of files and dozens of libraries, this is a very big price to pay.
The article starts with function templates, which are tricky, with function overrides interfering with template instantiations. The article seems oblivious to this issue.
"You should have noticed that I used typename, instead of class. No, it is not required to use typename keyword if a function returning something. For template programming, these two keywords are very much the same."
I have generally used <class X> rather than <typename X>, following a comment by David Abrahams to that effect on the boost list a long time ago. I think it has to do with the fact that typename does have multiple meanings inside the angle brackets.
And yes, you can use namespaces and careful template programming to give some modularity to the code, but in the end, if one code line change in one template header, that is used by multiple other template headers, and in turn by multiple libraries, means you have to recompile thousands of files and dozens of libraries, this is a very big price to pay.
The article starts with function templates, which are tricky, with function overrides interfering with template instantiations. The article seems oblivious to this issue.
"void PrintTwice(const TYPE& data)"
"You should have noticed that I used typename, instead of class. No, it is not required to use typename keyword if a function returning something. For template programming, these two keywords are very much the same."
I have generally used <class X> rather than <typename X>, following a comment by David Abrahams to that effect on the boost list a long time ago. I think it has to do with the fact that typename does have multiple meanings inside the angle brackets.
"int tSum = int();"
For an old language as C++, templates have a way of staying new, exciting and hard at times.
I have respect for people who can explain the deep intricacies of the vastness of C++. Good article.
I have respect for people who can explain the deep intricacies of the vastness of C++. Good article.
I might have been just lucky but I have not yet seen a C++ programmer who passes a job interview yet is unable to comprehend the simple template syntax.
The opposition to templates that I have seen is not based on the ignorance of the basic template concepts. Quite the opposite - it's based on the partial knowledge of the advanced templates. Usually such people are cool with STL or STL-like home-brew collections but when they hear "metaprogramming" they immediately start having kittens :)
Essentially (class) templates are meta-functions over C++ types and templates themselves and the article describes only their basic application i.e. linear functions, over concrete types only and without any control structures. It's almost exactly as same as explaining Haskell without recursion and pattern matching.
The opposition to templates that I have seen is not based on the ignorance of the basic template concepts. Quite the opposite - it's based on the partial knowledge of the advanced templates. Usually such people are cool with STL or STL-like home-brew collections but when they hear "metaprogramming" they immediately start having kittens :)
Essentially (class) templates are meta-functions over C++ types and templates themselves and the article describes only their basic application i.e. linear functions, over concrete types only and without any control structures. It's almost exactly as same as explaining Haskell without recursion and pattern matching.
I like templates for code reduction. By using a template, I turned about 12 functions into 1 function once. Makes code maintainability much easier.
"It is also true that code size would increase, since there are now two function definitions...
...But, on a positive side, when you manually define N different overloads (say N=10), those N different overloads would be anyway be compiled,linked and packed in binary (the executable). However, with templates, only the required instantiations of function would get into final executable. With templates, the overloaded copies of function might be less than N, and it can be more than N - but exactly the number of required copies - no more no less!"
There are times when every byte counts. Most of them were before the second Clinton administration. Odds are that with RAM at $20 a Gig, a few dozen bytes isn't the difference between your program being memory constrained or well tuned. Contemporary memory issues tend to be orders of magnitude larger.
...But, on a positive side, when you manually define N different overloads (say N=10), those N different overloads would be anyway be compiled,linked and packed in binary (the executable). However, with templates, only the required instantiations of function would get into final executable. With templates, the overloaded copies of function might be less than N, and it can be more than N - but exactly the number of required copies - no more no less!"
There are times when every byte counts. Most of them were before the second Clinton administration. Odds are that with RAM at $20 a Gig, a few dozen bytes isn't the difference between your program being memory constrained or well tuned. Contemporary memory issues tend to be orders of magnitude larger.
There are times when every byte counts. Most of them were before the second Clinton administration.
The CPU caches on a modern computer disagree with your snark. As http://everythingisdata.wordpress.com/2009/10/17/numbers-eve... shows, there is a huge performance benefit when you can stay inside of cache. (Note, those numbers are from Jeff Dean, who is widely lauded within Google for building the infrastructure that makes Google possible.)
Therefore when you're squeezing performance, precise control of memory layout matters a lot. That said, most of us don't need to worry about it. But when you do need to worry about it, there is absolutely no way to get it if you've already given up control.
I am averaging needing to worry about it about once every 5 years. So I need to care for perhaps 3% of my coding time. That percentage varies greatly by developer. Most developers that I know don't have the necessary skills to consider tackling issues at that level and so by definition can never take on projects for which they would care. Some developers work on stuff for which they need to care all of the time.
But even if you don't personally need that, it still is good to recognize that there are some who really do.
The CPU caches on a modern computer disagree with your snark. As http://everythingisdata.wordpress.com/2009/10/17/numbers-eve... shows, there is a huge performance benefit when you can stay inside of cache. (Note, those numbers are from Jeff Dean, who is widely lauded within Google for building the infrastructure that makes Google possible.)
Therefore when you're squeezing performance, precise control of memory layout matters a lot. That said, most of us don't need to worry about it. But when you do need to worry about it, there is absolutely no way to get it if you've already given up control.
I am averaging needing to worry about it about once every 5 years. So I need to care for perhaps 3% of my coding time. That percentage varies greatly by developer. Most developers that I know don't have the necessary skills to consider tackling issues at that level and so by definition can never take on projects for which they would care. Some developers work on stuff for which they need to care all of the time.
But even if you don't personally need that, it still is good to recognize that there are some who really do.
The Neil Conway blog begins:
Good intuition is the result of completing Norvig's ten year course. Identifying performance bottlenecks requires running code.
Neither is relevant during the "Template administration." Back of envelop calculations are about determining architecture, not the specific lines of text to be compiled. It's a look at efficient gross resource consumption, not tweeking handfuls of bytes. Tweeking, when it must occur - per your experience more than an order of magnitude less frequently than non-performance sensitive applications - is well after the "Template adminstration".
My criticism is literary. The article throws in byte sized boogie men. These are the sort of things that Google pays gurus to deal with. Not the sort of work for which they hire C++ programmers who need an idiot's guide to templates.
To a first approximation, memory isn't precious any more. Even when programming in C++. Writing as if it is, develops bad intuitions of the sort that lead to concern over templates during the Design phase.
I suspect that your first line of defense against running out of memory was not looking template construction, but compiler optimizations. Managing memory manually in C++ is hard enough without creating a mindset which encourages premature optimization.
When you’re designing a performance-sensitive
computer system...
Good intuition is the result of completing Norvig's ten year course. Identifying performance bottlenecks requires running code.
Neither is relevant during the "Template administration." Back of envelop calculations are about determining architecture, not the specific lines of text to be compiled. It's a look at efficient gross resource consumption, not tweeking handfuls of bytes. Tweeking, when it must occur - per your experience more than an order of magnitude less frequently than non-performance sensitive applications - is well after the "Template adminstration".
My criticism is literary. The article throws in byte sized boogie men. These are the sort of things that Google pays gurus to deal with. Not the sort of work for which they hire C++ programmers who need an idiot's guide to templates.
To a first approximation, memory isn't precious any more. Even when programming in C++. Writing as if it is, develops bad intuitions of the sort that lead to concern over templates during the Design phase.
I suspect that your first line of defense against running out of memory was not looking template construction, but compiler optimizations. Managing memory manually in C++ is hard enough without creating a mindset which encourages premature optimization.
My personal anecdote disagrees with you.
I do not make the decision to write performance critical code in C++ until I have an analysis of the problem which includes a prototype in a slower language. Therefore I do not start writing C++ templates until after I already have a specific problem, and a pretty detailed layout of how I want my data to be laid out in memory. The details of how my code gets laid out in memory I gladly leave to the compiler. But it is important for me to know that I can use templates and I won't have to worry about it either.
I suspect that your first line of defense against running out of memory was not looking template construction, but compiler optimizations. Managing memory manually in C++ is hard enough without creating a mindset which encourages premature optimization.
Not true!
In the latest project that this came up in, one of the first templates that I wrote in C++ allows me to replace things that can go into a std::map with 4-byte objects that are simply indexes into a deduped vector. (This is on Linux, so I don't have to worry about dword alignment. Thus 4-byte objects only take 4 bytes.) Given that I have a very large number of these, often need to compare two to know if they are the same or different, and only seldom need to get at the actual value, this gives huge memory and performance benefits.
Of course doing this kind of thing for a general-purpose application would be horribly premature optimization. Which is why I only considered going to C++ after analyzing where the issues were in my first two Perl versions.
And I am an example showing that it isn't just C++ gurus who find themselves needing to write performance critical code in C++. In fact my desire to avoid premature optimization means that when I do need to write performance critical code in C++, I do not know the language very well because I use it so seldom!
I do not make the decision to write performance critical code in C++ until I have an analysis of the problem which includes a prototype in a slower language. Therefore I do not start writing C++ templates until after I already have a specific problem, and a pretty detailed layout of how I want my data to be laid out in memory. The details of how my code gets laid out in memory I gladly leave to the compiler. But it is important for me to know that I can use templates and I won't have to worry about it either.
I suspect that your first line of defense against running out of memory was not looking template construction, but compiler optimizations. Managing memory manually in C++ is hard enough without creating a mindset which encourages premature optimization.
Not true!
In the latest project that this came up in, one of the first templates that I wrote in C++ allows me to replace things that can go into a std::map with 4-byte objects that are simply indexes into a deduped vector. (This is on Linux, so I don't have to worry about dword alignment. Thus 4-byte objects only take 4 bytes.) Given that I have a very large number of these, often need to compare two to know if they are the same or different, and only seldom need to get at the actual value, this gives huge memory and performance benefits.
Of course doing this kind of thing for a general-purpose application would be horribly premature optimization. Which is why I only considered going to C++ after analyzing where the issues were in my first two Perl versions.
And I am an example showing that it isn't just C++ gurus who find themselves needing to write performance critical code in C++. In fact my desire to avoid premature optimization means that when I do need to write performance critical code in C++, I do not know the language very well because I use it so seldom!
The disagreeable anecdote shows that the scale upon which memory efficiency matters is significantly greater than that of the example where the issue is raised. It matters for "very large number[s]" not when a template is used to overload a function for numeric types - it matters when memory constraints appear on the back of the envelop...or in the profile.
What bothered me about that section of the article is related to your comment "I won't have to worry about it either."
Templates are syntactic sugar. Cancer of the semicolon I can understand. But, why would one be fearful that a standard feature of C++ is grossly memory inefficient?
The answer I believe goes back to the time of expensive kilobytes - when allocating an array of 500 versus 200 was usually a big deal (whereas today it rarely is). CPU caches for performance driven applications are often larger than the total memory of systems from the time when C++ was designed. An idiot's guide should focus on draining the swamp and not seek to raise worries around the incubation of alligator eggs.
Even if that is the template for articles about the language.
What bothered me about that section of the article is related to your comment "I won't have to worry about it either."
Templates are syntactic sugar. Cancer of the semicolon I can understand. But, why would one be fearful that a standard feature of C++ is grossly memory inefficient?
The answer I believe goes back to the time of expensive kilobytes - when allocating an array of 500 versus 200 was usually a big deal (whereas today it rarely is). CPU caches for performance driven applications are often larger than the total memory of systems from the time when C++ was designed. An idiot's guide should focus on draining the swamp and not seek to raise worries around the incubation of alligator eggs.
Even if that is the template for articles about the language.
The disagreeable anecdote shows that the scale upon which memory efficiency matters is significantly greater than that of the example where the issue is raised. It matters for "very large number[s]" not when a template is used to overload a function for numeric types - it matters when memory constraints appear on the back of the envelop...or in the profile.
Wrong.
It is true that computers are fast enough that lack of performance will not be an issue unless the volume of work to be done is very, very large. However once you look at performance, you find that memory access patterns in the small matter a great deal.
For instance take a recent Intel Sandy Bridge CPU has, per core, 64KB L1 cache, 256 KB L2 cache, and 1 to 8 MB L3 cache. Half of each cache is available for code, the other half for data. If hyperthreading is turned on, these caches may be split by two concurrent processes. So if either the data accessed in, or the code for, a particular loop exceeds 32KB, you will experience a noticeable slowdown, and if possible you'd like to keep it under 16 KB. So it is better to do sequential access of large data structures, and avoid random access.
Note that is KB, not MB. Memory efficiency matters on very small data structures. You won't notice until you have a lot of data. But when you have to fix it, you have to think at multiple scales.
Templates are syntactic sugar. Cancer of the semicolon I can understand. But, why would one be fearful that a standard feature of C++ is grossly memory inefficient?
There historically have been a lot of complaints floating around about how nice templated code blew up into monstrosities when compiled. Given that, rumor control does not seem unwarranted.
Wrong.
It is true that computers are fast enough that lack of performance will not be an issue unless the volume of work to be done is very, very large. However once you look at performance, you find that memory access patterns in the small matter a great deal.
For instance take a recent Intel Sandy Bridge CPU has, per core, 64KB L1 cache, 256 KB L2 cache, and 1 to 8 MB L3 cache. Half of each cache is available for code, the other half for data. If hyperthreading is turned on, these caches may be split by two concurrent processes. So if either the data accessed in, or the code for, a particular loop exceeds 32KB, you will experience a noticeable slowdown, and if possible you'd like to keep it under 16 KB. So it is better to do sequential access of large data structures, and avoid random access.
Note that is KB, not MB. Memory efficiency matters on very small data structures. You won't notice until you have a lot of data. But when you have to fix it, you have to think at multiple scales.
Templates are syntactic sugar. Cancer of the semicolon I can understand. But, why would one be fearful that a standard feature of C++ is grossly memory inefficient?
There historically have been a lot of complaints floating around about how nice templated code blew up into monstrosities when compiled. Given that, rumor control does not seem unwarranted.
I've seen dramatic speedups reducing an array from ~10mb to ~1mb. The problem was that the algorithm did multiple passes over the array, and each pass it would pull in blocks from main memory, only to evict them later on before they could be reused.
It depends a lot on the workload, but you'll see dramatic performance differences well before you fill up main memory.
It depends a lot on the workload, but you'll see dramatic performance differences well before you fill up main memory.
And even when every byte does count, it's usually possible to make only a single real template expansion for an opaque handle type like pointer-to-void. This breaks type safety and has other issues but generally works well.
However the biggest frustration for me (aside from the verbosity) is that things work until they suddenly don't work, and then it isn't obvious why they don't work from the debugging stack you get back. They often don't work for good reason - but unless you're a C++ expert you don't know that reason.
For example suppose that I have a class that has reference members. Those are fields specified with & - they are kind of like a pointer except that you can't change them, and you use . instead of ->. Because you can't change them, operator= is not generated for you. I didn't notice this until I tried to use one in an std::map< ... > and everything blew up.
However luckily confusing backtrace message plus google usually leads to a useful stack overflow answer, else I'd find this process much more painful.
My one remaining frustration is that I hate how the STL did iterators. In the STL, if you have a data_type< foo > template, you iterate over it with a data_type< foo >::iterator. So you get a std::vector< foo >::iterator, a std::set< foo >::iterator, a std::dequeue< foo >::iterator, etc.
This is great for the compiler, but as a programmer it is backwards. I don't care what kind of data structure this came from, I care what kind of data type I get out. I'd like to see those three examples produce an iterator< foo >. And then you can dream up things like the ability to take an iterator< foo > and a method on foo that will return a bar, to get an iterator< bar >. I am used to having map/grep/etc, and it would be nice to be able to translate list-oriented thinking into C++ with less verbose boilerplate.