Re: [boost] [mpl] sort algorithm complexity

From: David Abrahams (dave_at_[hidden])
Date: 2005-08-05 21:29:20

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

> On 8/5/05, David Abrahams <dave_at_[hidden]> wrote:
>> Felipe Magno de Almeida <felipe.m.almeida_at_[hidden]> writes:
>> 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
>
> Is there any reason why the code above compiled in less than 5
> seconds, while the other I used wasnt compiling at all, the compiler
> complained about insuficient memory(it used about 500MB).

Maybe because you violated the requirements of the algorithm by not
using a strict weak ordering?

> I can see that the other way it needed more template instantiations,
> but it seemed to me like the number of instantiations should be
> linearly bigger, but that not what it seems at all... I'm testing it
> with a vector of 15 types only.

If you pass sort a bogus criterion, all bets are off.

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