www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Deleting an element from an array

reply "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.
Feb 03 2009
parent reply "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]);
Feb 03 2009
parent reply "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 :)
Feb 03 2009
parent reply 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.


 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 :) 
 
 


arr = arr[ 0 .. lowerBound ] ~ arr[ upperBound .. $ ];
Feb 03 2009
next sibling parent reply 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;
}
Feb 03 2009
parent reply "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?
Feb 03 2009
next sibling parent reply 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 ;)
Feb 03 2009
parent reply "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);
}
Feb 03 2009
parent reply 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.
Feb 03 2009
parent reply "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 :)
Feb 03 2009
parent 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;
Feb 21 2009
prev sibling parent "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.




Because it loops over arr.length-2 and copies the pointers.
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)




Where can I read about this variaidic type usage... looks awesome
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;
 }




What you are doing here is the same as the above but forcing the two
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?


This will copy the pointer of the last element to the to-be-replaced element
Will the GC actually delete the element with the unreferenced pointer 
arr[ind].ptr?
Feb 04 2009
prev sibling next sibling parent "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.


 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 :)


 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!
Feb 03 2009
prev sibling parent "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.


 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 :)


 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
Feb 03 2009