Re: [boost] Random access and memoization in TMP

From: Bruno Martínez (br1_at_[hidden])
Date: 2005-08-18 00:07:14

On Wed, 17 Aug 2005 15:29:51 -0300, Larry Evans  
<cppljevans_at_[hidden]> wrote:

> 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:

The recursion in child_i_depth_j is a tail call.  IIUC, the recursion is  
like the first drop, so increasing depths don't share part of the  
calculation.  However, it could be written in the other style.

Bruno