Boost logo

Boost :

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

> , 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,

    , boost::is_base_and_derived<_,_>
    , mpl::back_inserter<mpl::vector<> >


Dave Abrahams
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at