Re: [Boost-users] [Fusion] Runtime complexity of boost::fusion::find?

Subject: Re: [Boost-users] [Fusion] Runtime complexity of boost::fusion::find?
From: Joel de Guzman (joel_at_[hidden])
Date: 2010-12-10 03:20:24

On 12/10/2010 12:12 PM, Clinton Mead wrote:
> Hi everyone
>
> On the following documentation page:
>
> http://www.boost.org/doc/libs/1_45_0/libs/fusion/doc/html/fusion/algorithm/query/functions/find.html
>
> It mentions that the computational complexity for "find" is linear. However, I can not
> understand how this is the case.
>
> As far as I understand all find needs to do is to look through types, simply iterating
> through the sequence types at compile time using result_of::next<X>::type where where X is
> initially result_of::begin<SEQ>::type. So I can't see how any actual work is done by find.
>
> Am I missing something here? I'm working on a parameter library, and I assumed things like
> "find" used constant or no time to execute. Could people please explain how find could use
> linear time?

Technically, it is linear. There will still be at most N *inlined*
function calls that advance the iterators to the desired position.
In real life, however, this will be optimized away by the compiler
thus giving you O(1) lookup. What's mising in the docs is that if the
container is random access (e.g. fusion vector), then find is really
O(1).

Perhaps this note should be added to the docs to make this point
clear.

Regards,
-- 
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net