Re: [boost] A C++ puzzler

From: Sohail Somani (sohail_at_[hidden])
Date: 2008-04-12 17:55:41

Marco wrote:
> On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail_at_[hidden]>  
> wrote:
> 
>> 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