Successively prepending to slices.

[monarch_dodra]

On Wednesday, 9 April 2014 at 23:18:27 UTC, dnspies wrote:
> I know that D slices are set up so you can successively append 
> to them and it only has to re-allocate infrequently, but what 
> about with prepending?
>
> ie, does D have a way to handle
>
> int[] x;
> for(int i=0; i < 1000; i++) {
>   x = [i] ~ x;
> }
>
> efficiently, or is it better to avoid this sort of thing?

Yeah, that's going to re-allocate every time. At the very least, 
use std.array.insertInPlace, which will do what it can to avoid 
re-allocating, as well as calling un-needed postblits (when 
applicable):

int[] x;
for(int i=0; i < 1000; i++)
     insertInPlace(x, 0, i);

But even then, insertInPlace has a complexity of O(N), so while 
this is "better", it is still far from optimal.

You should try to avoid prepending in a loop altogether if you 
can. Try to prefer a solution where:
- you foreach_reverse and you always append.
- you foreach, but assign to the final location (requires setting 
length first).
- you foreach, but append, and then std.algorithm.reverse once 
done.
Just some ideas.