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.

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.

I think you want to do something like this:

void main() {

    import std.algorithm;

    auto a = [1, 2, 3];

    int val = 5;

    a = val ~ a; // vector.pushFront();

    assert(equal(a[], [5, 1, 2, 3]));
}

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];
    // or memmove(buffer.ptr + T.sizeof, buffer.ptr, (buffer.length - 1) * T.sizeof);
    buffer[0] = val;
}
---

* Option 3/

linked lists are better to insert/move.

On 06/22/2015 10:16 PM, 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.

If the array is huge, you may find it to be faster to not move any data at all but treat both that single element and the array as one larger range. chain() does that:

import std.algorithm;
import std.range;

void main()
{
    auto arr = [ 0, 1, 2 ];
    auto singleElement = 42.only;
    auto both = chain(singleElement, arr);

    assert(both.equal([ 42, 0, 1, 2 ]));

    // Supports random access as well:
    assert(both[0] == 42);
    // ...
    assert(both[$-1] == 2);
}

As you can see, although what chain() returns is not an array, it is a RandomAccessRange; so, indexing works just fine. However, do test its performance before using it as some of its operations necessarily do more work than a real array (or slice).

Ali

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

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.
>
> -Steve

according to the C library, memmove handle overlapps, you mismatch with memcpy which does not.

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

On Tuesday, 23 June 2015 at 13:29:41 UTC, Steven Schveighoffer wrote:
> On 6/23/15 8:12 AM, Baz wrote:
>> On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer wrote:
>>>[...]
>>
>> 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

ok. i was, wrongly, suposing that this operation uses memmove under the hood.
btw you forgot to grow the array size, if i dare.

On 6/23/15 10:20 AM, Baz wrote:
> On Tuesday, 23 June 2015 at 13:29:41 UTC, Steven Schveighoffer wrote:
>> On 6/23/15 8:12 AM, Baz wrote:
>>> On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer wrote:
>>>> [...]
>>>
>>> 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
>>
>
> ok. i was, wrongly, suposing that this operation uses memmove under the
> hood.
> btw you forgot to grow the array size, if i dare.

Heh, it was just to demonstrate the error :) The code does a whole lot of nothing, actually.

-Steve