Posts

Showing posts from January, 2012

Array-like access and Iterators for Homogeneous Tuples

Question often comes up whether tuples can have traditional iterators? In general, the answer is: No! They cannot. That's because tuples typically contain different types and traditional iterators, which are modeled after pointers, can not dereference to objects of multiple types. However, homogeneous tuples can have iterators. So I thought it would be a fun exercise to write one. I wonder why one would use a homogeneous tuples instead of just plain arrays. But lets do it anyways because we can.

Although this exercise sounds rather naive and unnecessary, I stumbled upon two very interesting topics along the way.

A need for new iterator concepts to separate the notions of element access from iterator traversal. Yes! iterators for homogeneous tuples can't be modeled accurately using conventional iterator categories. Don't believe me? Please read on...
How inherited constructors may be simulated on compilers that don't support them today.

From this point onward a tuple is ass…

General-purpose Automatic Memoization for Recursive Functions in C++11

Memoization is a widely known optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Repeated calculations are avoided by reusing previously computed results, which must be cached such that look-up is faster than recomputing.

Consider a simple fibonacci program
unsigned long fibonacci(unsigned n)
{
return (n < 2) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}This algorithm is a frustratingly slow way of computing the Nth fibonacci number (N starting at 0). It does a lot of redundant recomputations. But the beauty of this program is that it is really simple. To speed it up without changing its logic significantly, we could use memoization.

Using some clever C++11 techniques, it is possible to memoize this function, which looks like below.
unsigned long fibonacci(unsigned n)
{
return (n < 2) ? n :
memoized_recursion(fibonacci)(n - 1) +
memoized_recursion(fibonacc…