Re: [Boost-users] [fusion] complexity of filter_view

Subject: Re: [Boost-users] [fusion] complexity of filter_view
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-03-25 21:30:43

AMDG

er wrote:
> If say vector_type has N elements and predicate is true only for one 
> of them.
>
> O(N)?
>
> typedef filter_view<vector_type const, predicate > view_t
>
> O(1)?
>
> view_t view(v);

both of these should incur O(1) template instantiations.
Iterating over the sequence requires O(N) template instantiations
but the runtime complexity may be O(1) depending on
compiler optimizations.

In Christ,
Steven Watanabe