nextPermutation and ranges

[Dmitry Olshansky]

08-Feb-2013 00:04, H. S. Teoh пишет:
> On Thu, Feb 07, 2013 at 08:40:25PM +0100, Peter Alexander wrote:
> [...]
>>> 1) To avoid excessive allocations, it would have to be a transient
>>> range. Which means it may have unexpected results if you use it with
>>> an algorithm that doesn't handle transient ranges correctly.
>>
>> This has been discussed previously. bearophile suggested a policy to
>> control whether the buffer is permuted in-place, with it defaulting
>> to creating duplicates. The slow down from duplicates on DMD was
>> ~3x.
>
> Hmm. There's also the problem that there is no generic way to duplicate
> a range.  Only arrays are guaranteed to support .dup and .idup. So you'd
> have to allocate an array to store each permutation, and return that
> instead of the original range. This could be a major problem (one might
> expect to get elements of the same type as the original range, instead
> of arrays!).
>

I had long thougth of primitive like:

build!Container(range);

And if Container is not important then this :
build(range); //okay here build might be worse then dup

and it peeks the right container inside of it based on power of range

Such as:

random access - deque (or array)
forward - unrolled s-list (or  deque)
bidirectional - deque

After typing this it seems like Phobos is in dire need of deque ;)

-- 
Dmitry Olshansky