Re: [Boost-users] [Variant] Time complexity of apply_visitor

From: Eric Friedman (ebf_at_[hidden])
Date: 2006-05-25 01:47:25

Hi Scott,

The short answer is that, assuming everything is inlined by the 
compiler, the way to think of apply visitor is something like:

   switch (myVariant.which())
   {
   case 0: myVisitor(get<T0>(myVariant)); break;
   case 1: myVisitor(get<T1>(myVariant)); break;
   ...
   case n: myVisitor(get<Tn>(myVariant)); break;
   default: {
       switch (myVariant.which())
       {
       case n+1: myVisitor(get<Tn+1>(myVariant)); break;
       case n+2: myVisitor(get<Tn+2>(myVariant)); break;
       ...
       // and so on
       }
     }
   }

Note that the secondary switches (i.e., in the default switch case) may 
in fact not be inlined by the compiler, in which case there would be a 
function call followed by another switch.

HTH,

Eric

Scott Meyers wrote:
> If I invoke apply_visitor, what is the time complexity wrt the number of types 
> that may be in the variant?  The doc doesn't seem to address this.  I looked at 
> the source code, but all I can remember before my head exploded due to exposure 
> to the MPL and the PPL was "switch" (which suggests constant time) and 
> "unrolling" which suggests either linear or constant time, depending on what is 
> being unrolled.  Does anybody know what the time complexity of apply_visitor is?
> 
> My real question is whether applying a visitor to a variant is more efficient 
> than a cascading series of calls to get.  I know that the following runs in 
> linear time wrt the number of types in the variant,
> 
>    if (T1 *p = get<T1>(&myVariant)) ...
>    else if (T2 *p = get<T2>(&myVariant)) ...
>    else ...
>    else if (Tn *p = get<Tn>(&myVariant)) ...
> 
> but what about this?
> 
>    apply_visitor(myVisitor, myVariant);
> 
> Thanks for any enlightenment.
> 
> Scott