Okay, let's be precise. *Technically*, at<0, myvec> is O(X) -- where X is the number of prior instantiations of at<i,v> -- on most existing compilers, but note that v doesn't have to be myvec nor does X have any relation to size<myvec>::value.
Yes.
Okay, that's one way to look at it. The reasons it is faster are not so important for the purposes of this analysis, so I prefer to say that it can be very difficult to observe this X because the constant is so low compared to the cost of instantiating a single template.
Yes.
Metrowerks seems to be bringing the elements accessed to the front af the list, even.
I think GCC does it too.
Really? I don't know for sure about Metrowerks, but reordering the list would explaint the jumpy behaviour. In any case the strategies of both compilers are different.
Even without some weird O(N)->O(1) cases, memoization has a sw engineering impact. As it's said in the book, it's easier to avoid blobs, for example, because there's no speed hit.
The book says that?
Sorry for putting words in your mouth.
I guess you're suggesting that instantiating N templates with 1 nested typedef might be presumed to be slower than instantiating 1 template with N nested typedefs?
No, that's not what I'm trying to say. Let me put an example, in Haskell notation. blob :: Int -> (Int, Int> first :: Int -> Int second :: Int -> Int In a strict language the fastest implementation is: first i = func1 (commonfunc i) second i = func2 (commonfunc i) blob i = (func1 aux, func2 aux) where aux = commonfunc i The client does different calls depending on if it needs first i, second i or both. In a lazy language this way is just as fast: first i = r where (r, _) = blob i second i = r where (_, r) = blob i blob i = (func1 aux, func2 aux) where aux = commonfunc i The client can just call blob and then extract one of the results without paying for the other. With tmp I can go even further: first i = func1 (commonfunc i) second i = func2 (commonfunc i) blob i = (first i, second i) So blob can disappear without affecting performance. Bruno