• "nobody" <somebody somewhere.com> Feb 03 2009
• "Denis Koroskin" <2korden gmail.com> Feb 03 2009
• "nobody" <somebody somewhere.com> Feb 03 2009
• Frank Benoit <keinfarbton googlemail.com> Feb 03 2009
• "nobody" <somebody somewhere.com> Feb 03 2009
• "Steven Schveighoffer" <schveiguy yahoo.com> Feb 03 2009
• "nobody" <somebody somewhere.com> Feb 03 2009
• "Saaa" <empty needmail.com> Feb 04 2009
• Jarrett Billingsley <jarrett.billingsley gmail.com> Feb 03 2009
• Jarrett Billingsley <jarrett.billingsley gmail.com> Feb 03 2009
• "nobody" <somebody somewhere.com> Feb 03 2009
• Jarrett Billingsley <jarrett.billingsley gmail.com> Feb 03 2009
• "nobody" <somebody somewhere.com> Feb 03 2009
• Sergey Gromov <snake.scaly gmail.com> Feb 21 2009

"nobody" <somebody somewhere.com> writes:

What is the best way to completely remove an element from an array?

For example you have an array:
[1,2,3,4,5,6]
and want to remove element "3" in such a way that the resulting array is:
[1,2,4,5,6]

Thanks. 

"Denis Koroskin" <2korden gmail.com> writes:

On Tue, 03 Feb 2009 15:46:52 +0300, nobody <somebody somewhere.com> wrote:

 What is the best way to completely remove an element from an array?

 For example you have an array:
 [1,2,3,4,5,6]
 and want to remove element "3" in such a way that the resulting array is:
 [1,2,4,5,6]

 Thanks.


import std.array;

auto arr = [0, 1, 2, 3, 4, 5];

int lowerBound = 2;
int upperBound = 4;

// erases elements [lowerBound, upperBound),
// total of upperBound - lowerBound elements
arr.erase(lowerBound, upperBound);

assert(arr == [0, 1, 4, 5]);

"nobody" <somebody somewhere.com> writes:

"Denis Koroskin" <2korden gmail.com> wrote in message 
news:op.uor1gzqho7cclz korden-pc...
 On Tue, 03 Feb 2009 15:46:52 +0300, nobody <somebody somewhere.com> wrote:

 What is the best way to completely remove an element from an array?

 For example you have an array:
 [1,2,3,4,5,6]
 and want to remove element "3" in such a way that the resulting array is:
 [1,2,4,5,6]

 Thanks.


 import std.array;

 auto arr = [0, 1, 2, 3, 4, 5];

 int lowerBound = 2;
 int upperBound = 4;

 // erases elements [lowerBound, upperBound),
 // total of upperBound - lowerBound elements
 arr.erase(lowerBound, upperBound);

 assert(arr == [0, 1, 4, 5]);


Ah I'm sorry, I forgot to mention I'm using D1, not D2.

Thanks for the reply though :) 

Frank Benoit <keinfarbton googlemail.com> writes:

nobody schrieb:
 "Denis Koroskin" <2korden gmail.com> wrote in message 
 news:op.uor1gzqho7cclz korden-pc...
 On Tue, 03 Feb 2009 15:46:52 +0300, nobody <somebody somewhere.com> wrote:

 What is the best way to completely remove an element from an array?

 For example you have an array:
 [1,2,3,4,5,6]
 and want to remove element "3" in such a way that the resulting array is:
 [1,2,4,5,6]

 Thanks.



 auto arr = [0, 1, 2, 3, 4, 5];

 int lowerBound = 2;
 int upperBound = 4;

 // erases elements [lowerBound, upperBound),
 // total of upperBound - lowerBound elements
 arr.erase(lowerBound, upperBound);

 assert(arr == [0, 1, 4, 5]);


 Ah I'm sorry, I forgot to mention I'm using D1, not D2.
 
 Thanks for the reply though :) 
 
 


arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];

"nobody" <somebody somewhere.com> writes:

"Frank Benoit" <keinfarbton googlemail.com> wrote in message 
news:gm9n0e$314n$1 digitalmars.com...
 nobody schrieb:
 "Denis Koroskin" <2korden gmail.com> wrote in message
 news:op.uor1gzqho7cclz korden-pc...
 On Tue, 03 Feb 2009 15:46:52 +0300, nobody <somebody somewhere.com> 
 wrote:

 What is the best way to completely remove an element from an array?

 For example you have an array:
 [1,2,3,4,5,6]
 and want to remove element "3" in such a way that the resulting array 
 is:
 [1,2,4,5,6]

 Thanks.



 auto arr = [0, 1, 2, 3, 4, 5];

 int lowerBound = 2;
 int upperBound = 4;

 // erases elements [lowerBound, upperBound),
 // total of upperBound - lowerBound elements
 arr.erase(lowerBound, upperBound);

 assert(arr == [0, 1, 4, 5]);


 Ah I'm sorry, I forgot to mention I'm using D1, not D2.

 Thanks for the reply though :)


 arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];


Slicing, I always forget it exists..

And wow, I was afraid I would have to do some array length checks in case 
the element to be removed is the last one, but it even works with lowerBound 
= 5 and upperBound = 6.

Splendid, thanks! 

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

"Frank Benoit" wrote
 nobody schrieb:
 "Denis Koroskin" <2korden gmail.com> wrote in message
 news:op.uor1gzqho7cclz korden-pc...
 On Tue, 03 Feb 2009 15:46:52 +0300, nobody <somebody somewhere.com> 
 wrote:

 What is the best way to completely remove an element from an array?

 For example you have an array:
 [1,2,3,4,5,6]
 and want to remove element "3" in such a way that the resulting array 
 is:
 [1,2,4,5,6]

 Thanks.



 auto arr = [0, 1, 2, 3, 4, 5];

 int lowerBound = 2;
 int upperBound = 4;

 // erases elements [lowerBound, upperBound),
 // total of upperBound - lowerBound elements
 arr.erase(lowerBound, upperBound);

 assert(arr == [0, 1, 4, 5]);


 Ah I'm sorry, I forgot to mention I'm using D1, not D2.

 Thanks for the reply though :)


 arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];


Or, if you want to avoid heap activity, use memmove:

memmove(arr.ptr + lowerBound, arr.ptr + upperBound, sizeof(*arr.ptr) * 
(arr.length - upperBound));
arr.length = arr.length - (upperBound - lowerBound);

Unfortunately, doing a slice assign doesn't work on overlapping regions 
(shouldn't there be a lib function for this?), otherwise, the following 
would be braindead simple:

arr[lowerBound..$-(upperBound-lowerBound)] = arr[upperBound..$];
arr.length = arr.length - (upperBound - lowerBound);

-Steve 

"nobody" <somebody somewhere.com> writes:

"Jarrett Billingsley" <jarrett.billingsley gmail.com> wrote in message 
news:mailman.635.1233675301.22690.digitalmars-d-learn puremagic.com...
 On Tue, Feb 3, 2009 at 10:14 AM, Frank Benoit
 <keinfarbton googlemail.com> wrote:
 arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];


 That's simple enough, but inefficient.

 Something like this:

 import std.c.string; // or import tango.stdc.string;

 T[] erase(T)(ref T[] arr, size_t idx)
 {
    if(arr.length == 0)
        throw new Exception("FAILCOPTER");

    if(idx < arr.length - 1)
        memmove(&arr[idx], &arr[idx + 1], T.sizeof * (arr.length - idx - 
 1));

    arr.length = arr.length - 1;
    return arr;
 }


Let's see if I understand memmove..
The way it's used here, it copies the tail of an array onto that same array, 
only starting one index earlier, thus removing the undesired element?
Neat.

However I just realized that order does not matter in the array I'm using, 
so I guess I could use something like:
arr[ind] = arr[$-1];
arr.length = arr.length -1;
Seeing how this only copies once, I'm guessing this is more efficient? 

"Saaa" <empty needmail.com> writes:

Please tell me when I got something wrong : )

 arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];


 That's simple enough, but inefficient.




Will the compiler optimize by not copying the [0..lowerbound] part?
And will the compiler get that it can do
arr[x]=arr[x+difference]
for the [upperBound .. $] part
iso creating a temporary array (not doing in place is what this is called I 
think)

 Something like this:

 import std.c.string; // or import tango.stdc.string;

 T[] erase(T)(ref T[] arr, size_t idx)




And, when do I need to use size_t?

 {
    if(arr.length == 0)
        throw new Exception("FAILCOPTER");

    if(idx < arr.length - 1)
        memmove(&arr[idx], &arr[idx + 1], T.sizeof * (arr.length - idx - 
 1));

    arr.length = arr.length - 1;
    return arr;
 }




optimizations.

 Let's see if I understand memmove..
 The way it's used here, it copies the tail of an array onto that same 
 array, only starting one index earlier, thus removing the undesired 
 element?
 Neat.

 However I just realized that order does not matter in the array I'm using, 
 so I guess I could use something like:
 arr[ind] = arr[$-1];
 arr.length = arr.length -1;
 Seeing how this only copies once, I'm guessing this is more efficient?


Will the GC actually delete the element with the unreferenced pointer 
arr[ind].ptr?

Jarrett Billingsley <jarrett.billingsley gmail.com> writes:

On Tue, Feb 3, 2009 at 10:14 AM, Frank Benoit
<keinfarbton googlemail.com> wrote:
 arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];


That's simple enough, but inefficient.

Something like this:

import std.c.string; // or import tango.stdc.string;

T[] erase(T)(ref T[] arr, size_t idx)
{
    if(arr.length == 0)
        throw new Exception("FAILCOPTER");

    if(idx < arr.length - 1)
        memmove(&arr[idx], &arr[idx + 1], T.sizeof * (arr.length - idx - 1));

    arr.length = arr.length - 1;
    return arr;
}

Jarrett Billingsley <jarrett.billingsley gmail.com> writes:

On Tue, Feb 3, 2009 at 10:54 AM, nobody <somebody somewhere.com> wrote:
 Let's see if I understand memmove..
 The way it's used here, it copies the tail of an array onto that same array,
 only starting one index earlier, thus removing the undesired element?
 Neat.


Right.

 However I just realized that order does not matter in the array I'm using,
 so I guess I could use something like:
 arr[ind] = arr[$-1];
 arr.length = arr.length -1;
 Seeing how this only copies once, I'm guessing this is more efficient?


Way more efficient ;)

"nobody" <somebody somewhere.com> writes:

"Jarrett Billingsley" <jarrett.billingsley gmail.com> wrote in message 
news:mailman.636.1233678501.22690.digitalmars-d-learn puremagic.com...
 On Tue, Feb 3, 2009 at 10:54 AM, nobody <somebody somewhere.com> wrote:
 Let's see if I understand memmove..
 The way it's used here, it copies the tail of an array onto that same 
 array,
 only starting one index earlier, thus removing the undesired element?
 Neat.


 Right.

 However I just realized that order does not matter in the array I'm 
 using,
 so I guess I could use something like:
 arr[ind] = arr[$-1];
 arr.length = arr.length -1;
 Seeing how this only copies once, I'm guessing this is more efficient?


 Way more efficient ;)


Would you also happen to know why the following gives an error?

import std.stdio;

void main()
{
 int[3][] arr = [ [0,1,2], [3,4,5], [6,7,8], [9,10,11] ];

 writefln(arr);

 arr[1] = arr[$-1];    // main.d(11): Error: cannot assign to static array 
arr[cast(uint)1]

 //arr[1][0] = arr[$-1][0];    // I could do it manually like this instead, 
or with a loop, but that seems rather silly.
 //arr[1][1] = arr[$-1][1];
 //arr[1][2] = arr[$-1][2];

 arr.length = arr.length - 1;

 writefln(arr);
}

Jarrett Billingsley <jarrett.billingsley gmail.com> writes:

On Tue, Feb 3, 2009 at 11:51 AM, nobody <somebody somewhere.com> wrote:
 Would you also happen to know why the following gives an error?

  arr[1] = arr[$-1];    // main.d(11): Error: cannot assign to static array


arr[1][] = arr[$-1][];

You cannot reassign what fixed-size array references point to, but you
can copy their contents.

If this were an int[][], you would still probably want to do "arr[1][]
= arr[$ - 1][]", since doing "arr[1] = arr[$ - 1]" would make arr[1]
and arr[$ - 1] point to the same data; probably not what you would
expect.

"nobody" <somebody somewhere.com> writes:

"Jarrett Billingsley" <jarrett.billingsley gmail.com> wrote in message 
news:mailman.637.1233680615.22690.digitalmars-d-learn puremagic.com...
 On Tue, Feb 3, 2009 at 11:51 AM, nobody <somebody somewhere.com> wrote:
 Would you also happen to know why the following gives an error?

  arr[1] = arr[$-1];    // main.d(11): Error: cannot assign to static 
 array


 arr[1][] = arr[$-1][];

 You cannot reassign what fixed-size array references point to, but you
 can copy their contents.


Hm, I see.

 If this were an int[][], you would still probably want to do "arr[1][]
 = arr[$ - 1][]", since doing "arr[1] = arr[$ - 1]" would make arr[1]
 and arr[$ - 1] point to the same data; probably not what you would
 expect.


Well in this case I don't think it would be a problem, since right 
afterwards i do
arr.length = arr.length - 1;
But I can see how I have to be careful with this :) 

Sergey Gromov <snake.scaly gmail.com> writes:

Tue, 3 Feb 2009 18:11:35 +0100, nobody wrote:

 "Jarrett Billingsley" <jarrett.billingsley gmail.com> wrote in message 
 news:mailman.637.1233680615.22690.digitalmars-d-learn puremagic.com...
 On Tue, Feb 3, 2009 at 11:51 AM, nobody <somebody somewhere.com> wrote:
 Would you also happen to know why the following gives an error?

  arr[1] = arr[$-1];    // main.d(11): Error: cannot assign to static 
 array


 arr[1][] = arr[$-1][];

 You cannot reassign what fixed-size array references point to, but you
 can copy their contents.


 Hm, I see.
 
 If this were an int[][], you would still probably want to do "arr[1][]
 = arr[$ - 1][]", since doing "arr[1] = arr[$ - 1]" would make arr[1]
 and arr[$ - 1] point to the same data; probably not what you would
 expect.


 Well in this case I don't think it would be a problem, since right 
 afterwards i do
 arr.length = arr.length - 1;
 But I can see how I have to be careful with this :)


There's a gotcha here.  Reducing array length does not reallocate, and
does not clean memory.  This may lead to dangling pointers and zombie
memory.  Here's what I mean:

Let's have an array of four arrays of int.  I'll name them to simplify
explanation:

int[] a, b, c, d; // suppose they're initialized
int[][] arr = [a, b, c, d];

Now delete b:

arr: [a, d, c], d

Above is a pseudo-code showing emory layout after one deletion.  Now
delete the remaining d:

arr: [a, c], c, d

See, arr contains only a and c, but the memory chunk also references c
and d.  GC doesn't know anything about arrays and scans whole chunks, so
from GC's perspective the d array is still alive while you'd probably
expect it be deallocated soon.

To avoid this bug you should zero the last element of your array before
reducing its length:

arr[idx] = arr[$-1];
arr[$-1] = null;
arr.length = arr.length-1;