Re: [boost] A C++ puzzler

From: Marco (mrcekets_at_[hidden])
Date: 2008-04-12 16:50:32

On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail_at_[hidden]>  
wrote:

> Marco wrote:
>> On Sat, 12 Apr 2008 21:13:40 +0200, Anand Shankar
>> <anand.shankar.k_at_[hidden]> wrote:
>>
>>> Hi,
>>>
>>> Here's a solution similar to Marco's - finds the first non default type
>>> using template specialization.
>>> It uses sizeof to check whether the types following first non-default
>>> type
>>> are conforming.
>>>
>>> Anand.
>>>
>>
>> Really a nice solution!
>
> 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.

Marco

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/