Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk