fast way to insert element at index 0

[Steven Schveighoffer via Digitalmars-d-learn]

On 6/23/15 8:12 AM, Baz wrote:
> On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer wrote:
>> On 6/23/15 1:51 AM, jkpl wrote:
>>> On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:
>>>> [...]
>>>
>>> * 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.
>>
>
> according to the C library, memmove handle overlapps, you mismatch with
> memcpy which does not.
>

The above is not memmove, it's slice assignment, which is specifically 
illegal for overlaps:

$ cat testsliceassign.d
void buffer[100];

void main()
{
     buffer[1..$] = buffer[0..$-1];
}

$ dmd testsliceassign.d
$ ./testsliceassign
object.Error@(0): Overlapping arrays in copy: 98 byte(s) overlap of 99

-Steve