From: Sohail Somani (sohail_at_[hidden])
Date: 2008-04-12 17:55:41
> On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail_at_[hidden]>
>> Correct me if my thinking is incorrect but I think a solution using a
>> variable number of template specialization has an implicit O(f(N))
>> complexity where f(N) is some non-constant function of N. The compiler
>> needs to iterate through all the specializations in order to find the
>> match, which is the same as you explicitly iterating through some sort
>> of fusion data structure. It may optimize this somehow but it still
>> isn't O(1).
>> Interesting puzzle. Can't wait to see all the answers.
> Your concern is sensible, and someone with a more insight than me on
> how a compiler works should give an answer, here.
> Anyway this is my point of view: the compiler has to do O(N)
> comparisons to find the right match but only the matching template
> specialization will be instantiated, so actually we need O(1) template
> instantiation only.
Clearly, I misread the O(1) template instantiations requirement. Thanks
for clarifying for me. And to reply to Eric, it is also my experience
that O(N) comparisons (would probably actually be O(N*MAX_TYPES)
comparisons) are better than O(N) instantiations, but I'm sure the
"Proto"-typical C++ guru (Eric) knows about that ;-)
-- Sohail Somani http://uint32t.blogspot.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk