Re: [boost] Random access and memoization in TMP

From: Larry Evans (cppljevans_at_[hidden])
Date: 2005-08-17 13:29:51

On 08/17/2005 12:41 PM, Bruno Martínez wrote:
> I was pondering the other day about the unique built in memoization  
> capabilities of templates.
[snip]
> If I construct a list in O(n) and then take the last element with at, 
> also  in O(n), then access to every element becomes O(1), because 
> traversing to  the last element precalculated all the other positions.
[snip]
> I've been thinking the past days of other functions like drop that 
> could  be improved in a similar way, but they have eluded me.  I didn't 
> find  mention of similar techniques in the MPL book, so I wonder if I'm 
> making  any sense.

Makes perfect sense to me.  The fold metafunction calculates
a sequence of partial results which can then be accessed with
child_i_depth_j as shown in test driver in:

http://boost-sandbox.sourceforge.net/vault/index.php?&direction=0&order=&directory=cppljevans/mpl

There's another application in the cppljevans/mpl directory which
can calculate the strides in a multi-dimentional array with constant
sizes for each dimention.  There's also another application which
calculates offsets of elements in a tuple.  I can envision another
which calculates the closure of a bool matrix, but that would
probably tax the compiler a bit much ;(