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