On Wed, 17 Aug 2005 15:29:51 -0300, Larry Evans <cppljevans@cox-internet.com> 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