Successively prepending to slices.

[Steven Schveighoffer]

On Wed, 09 Apr 2014 19:18:25 -0400, dnspies <dspies at ualberta.ca> 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?

I would recommend appending, and then using std.range.retro to access, or  
reversing the array afterwards.

Another possibility, if you know the final array size, is to reserve and  
then fill the array:

int[] x;
x.length = 1000;
for(int i = 0; i < 1000; ++i)
{
    x[$-1-i] = i;
    // or (I think this works)
    retro(x)[i] = i;
}

I don't know the use case (how do you use it after creation?)

Note, I create a deque class in dcollections which maintains 2 arrays, one  
for prepending (and is in reverse order), and one for appending. The class  
handles the indexing so that it looks like a standard array. But  
prepending is also amortized O(1)

Also note, [i] ~ x will first allocate on the heap an array with a single  
element value of i, then allocate ANOTHER array on the heap which can  
contain all the elements in x + 1, and copy i and x to it.

The code is extremely inefficient, and should be avoided.

-Steve