fast way to insert element at index 0

[Steven Schveighoffer via Digitalmars-d-learn]

On 6/23/15 1:51 AM, jkpl wrote:
> On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:
>> What's a fast way to insert an element at index 0 of array? now that
>> the code is working I want to clean this:
>>
>> void push(T val)
>>     {
>>         T[] t = new T[buffer.length + 1];
>>         t[0] = val;
>>         t[1 .. $] = buffer;
>>         buffer = t;
>>     }
>>
>> I did this because I didn't find any suble built-in data structure
>> that let me insert an item into a specific index at first search.
>> Slist does have insertFron(), exactly what I'm looking for it's a
>> linked list.
>
> * Option 1/
>
> if most of the time you have to insert at the beginning, then start
> reading from the end and append to the end, so that the existing block
> has not to be moved. You just have to add val at the end.
>
> * Option 2/
>
> better way to move the whole block (this can be done with memmove too).
>
> ---
> void push(T val)
> {
>      buffer.length += 1;
>      buffer[1..$] = buffer[0..$-1];

This will fail.

http://dlang.org/arrays.html#overlapping-copying

I will note, dcollections had a deque, which allowed insertion at the 
front in O(1) (amortized) time. It basically worked by having 2 arrays 
front to front.

-Steve