Re: [boost] [mpl] sort algorithm complexity

From: David Abrahams (dave_at_[hidden])
Date: 2005-08-05 09:06:11

Felipe Magno de Almeida <felipe.m.almeida_at_[hidden]> writes:

> In the page it is informed that sort has an average complexity of
> O(nlog n), but I'm writing this:
>
>   template <typename T, typename U>
>   struct sort_hierarchy_pred : mpl::not_<
>       boost::is_base_and_derived<T, U>
>     >::type
>   {
>   };

I don't think that's a valid strict weak ordering criterion, because
for two classes unrelated by inheritance it produces true in either
argument order.

>
>   typedef mpl::back_inserter< mpl::vector<> > aux_in;
>   template <typename SequenceT>
>   struct sort_hierarchies : public mpl::sort<SequenceT,
                              ^^^^^^
It's up to you of course, but I'd leave that out.
>       typename mpl::lambda<sort_hierarchy_pred<mpl::_, mpl::_> >::type
        ^^^^^^^^^^^^^^^^^^^^^                                    ^^^^^^^

This is just a waste of code; sort already invokes lambda on its
predicate internally, as do all MPL algorithms accepting lambda
expressions.  As a matter of fact, they all use applyN<...>, which
invokes lambda internally.  Invoking lambda on the outside may be
costing you some significant compilation speed, because the resulting
metafunction class is a large nested type.  The fastest thing would
probably be to make sort_hierarchy_pred a metafunction class itself.

[Aleksey, I'm not sure why the sort Expression Semantics uses explicit
lambda and apply_wrap2; I don't think it helps to make anything
clearer]

>       , aux_in>
>   {};
>
> and for a sequence of 5 or more, the compile time and memory usage
> gets too huge. To became unuseable.
>
> What I'm trying to achieve is a sequence of types that are sorted
> with the bases first...

  mpl::sort<Seq, boost::is_base_and_derived<_,_> >::type

is the simplest way, if Seq is a mutable sequence.  Otherwise,

  mpl::sort<
      Seq
    , boost::is_base_and_derived<_,_>
    , mpl::back_inserter<mpl::vector<> > 
  >::type

HTH,

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com