www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - remove from array

reply Thorsten <toki78 usenet.cnntp.org> writes:
How can I remove values from an array ?
Feb 27 2007
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Thorsten,


 How can I remove values from an array ?
 


<totaly untested code>

T[] Remove(T)(T[] arr, int i)
{
   return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
}
Feb 27 2007
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
BCS wrote:

 Reply to Thorsten,
 

 How can I remove values from an array ?


 
 <totaly untested code>
 
 T[] Remove(T)(T[] arr, int i)
 {
   return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }
 
 


This has the function you're looking for and a number of others you'll 
probably be looking for soon after.  :-)

http://www.dsource.org/projects/cashew/browser/trunk/cashew/utils/array.d

--bb
Feb 27 2007
next sibling parent reply Thorsten <toki782 usenet.cnntp.org> writes:
Bill Baxter Wrote:


 This has the function you're looking for and a number of others you'll 
 probably be looking for soon after.  :-)
 
 http://www.dsource.org/projects/cashew/browser/trunk/cashew/utils/array.d
 
 --bb


Yeah thanks, it's the drop-function.
Will this be added to phobos once ?
Feb 27 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Thorsten wrote:

 Bill Baxter Wrote:
 

 This has the function you're looking for and a number of others you'll 
 probably be looking for soon after.  :-)

 http://www.dsource.org/projects/cashew/browser/trunk/cashew/utils/array.d

 --bb


 
 Yeah thanks, it's the drop-function.
 Will this be added to phobos once ?
 


Maybe in theory, but it's doubtful.  There is only one person able to 
make commits to Phobos, Walter, and his time is taken up by making 
changes to the compiler that /cannot/ be worked around by library code. 
  That plus now there's Tango, which *is* an open and collaborative 
standard library effort.

There's probably something like drop in Tango already.  If not they'd 
probably be willing to add it.  I see they have a remove() function that 
is like a combination of find()+drop(), and they have find() but no drop.

--bb
Feb 27 2007
prev sibling parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bill Baxter wrote:

 BCS wrote:

 Reply to Thorsten,


 How can I remove values from an array ?


 <totaly untested code>

 T[] Remove(T)(T[] arr, int i)
 {
   return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }


 
 This has the function you're looking for and a number of others you'll 
 probably be looking for soon after.  :-)
 
 http://www.dsource.org/projects/cashew/browser/trunk/cashew/utils/array.d
 
 --bb


Hmm, wow, I really need to revisit Cashew...  think I'll go do that now.  :) 
So much left 
unfinished and unwritten on there.  Bad me.  But thanks for the promotion. 
Good to know 
I'm not the only one who uses it.

-- Chris Nicholson-Sauls
Feb 28 2007
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Chris Nicholson-Sauls wrote:

 
 Bill Baxter wrote:

 BCS wrote:

 Reply to Thorsten,


 How can I remove values from an array ?


 <totaly untested code>

 T[] Remove(T)(T[] arr, int i)
 {
   return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }


 This has the function you're looking for and a number of others you'll 
 probably be looking for soon after.  :-)

 http://www.dsource.org/projects/cashew/browser/trunk/cashew/utils/array.d

 --bb


 
 Hmm, wow, I really need to revisit Cashew...  think I'll go do that 
 now.  :)  So much left unfinished and unwritten on there.  Bad me.  But 
 thanks for the promotion.  Good to know I'm not the only one who uses it.
 
 -- Chris Nicholson-Sauls


And there is now a new version in SVN (v0.10.4) which has some little cleanups.

-- Chris Nicholson-Sauls
Feb 28 2007
prev sibling next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
BCS wrote:

 Reply to Thorsten,
 

 How can I remove values from an array ?


 
 <totaly untested code>
 
 T[] Remove(T)(T[] arr, int i)
 {
   return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }
 
 


Using ~ works, but it's slower than using memmorve (what's in Cashew utils).

--bb
Feb 27 2007
parent BCS <ao pathlink.com> writes:
Reply to Bill,


 Using ~ works, but it's slower than using memmorve (what's in Cashew
 utils).
 


Good point. OTOH if you want to keep the source untouched, you need to allocate 
anyway. Thinking of that, a dup is needed to keep things consistent

T[] Remove(T)(T[] arr, int i)
{
return i==arr.length-1 ? arr[0..$-1].dup : arr[0..i] ~ arr[i+1 .. $];
}
Feb 27 2007
prev sibling parent reply Thorsten <toki782 usenet.cnntp.org> writes:
 <totaly untested code>
 
 T[] Remove(T)(T[] arr, int i)
 {
    return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }


Sorry, I tried that, and it is too expensive !!
Because it creates about 3 temporary instances.
I would say :

void Remove(T)(inout T[] arr, int i)
{
  for(uint j = i;j < arr.length-1;++j)
    arr[j] = arr[j+1];
  arr.length = arr.length - 1;
}

can someone accelerate this ???
Feb 27 2007
next sibling parent torhu <fake address.dude> writes:
Thorsten wrote:

 <totaly untested code>
 
 T[] Remove(T)(T[] arr, int i)
 {
    return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }


 
 Sorry, I tried that, and it is too expensive !!
 Because it creates about 3 temporary instances.
 I would say :
 
 void Remove(T)(inout T[] arr, int i)
 {
   for(uint j = i;j < arr.length-1;++j)
     arr[j] = arr[j+1];
   arr.length = arr.length - 1;
 }
 
 can someone accelerate this ???


I see Bill already told you about cashew, but here's an answer anyway.

You can use memmove to do the copying.  Using memmove also seems to be 
the fastest way to insert elements in the middle of an array, if you 
need that too.

void Remove(T)(inout T[] arr, int i)
{
   assert(arr && i < arr.length);
   memmove(arr.ptr + i, arr.ptr + i + 1, (arr.length - i - 1) * T.sizeof);
   arr.length = arr.length - 1;
}

If you don't care about the order, you can of course just do this:

arr[i] = arr[$-1];
arr.length = arr.length - 1;
Feb 27 2007
prev sibling next sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Thorsten wrote:

 <totaly untested code>

 T[] Remove(T)(T[] arr, int i)
 {
    return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }


 
 Sorry, I tried that, and it is too expensive !!
 Because it creates about 3 temporary instances.


Nonsense.
First of all, only one of the last two clauses is even evaluated.
And second, only the second clause allocates, and even then only once. 
Slicing an array doesn't create a copy, it just creates a new (length, 
pointer) pair. Only the '~' allocates, and this is not a temporary but 
the return value.

That function might be improved a bit by also returning a plain slice 
for the case i == 0, but with that change it's perfectly fine as long as 
copy-on-write is acceptable.

If you are certain no copies of the original array (including 
overlapping arrays) will be kept, you can use something like your 
suggestion:


 I would say :
 
 void Remove(T)(inout T[] arr, int i)
 {
   for(uint j = i;j < arr.length-1;++j)
     arr[j] = arr[j+1];
   arr.length = arr.length - 1;
 }
 
 can someone accelerate this ???


Using memmove to replace the loop has already been suggested, that 
should usually be fast.
Though consider checking if the removed element is closer to the 
beginning of the array, and if so moving the first part instead of the 
second part followed by "arr = arr[1 .. $]":
---
// warning: untested code
void Remove(T)(inout T[] arr, int i)
{
   if (i < (arr.length / 2)) {
     for(uint j = i; j > 0; --j)
       arr[j] = arr[j-1];
     arr = arr[1 .. $];
   } else {
     for(uint j = i; j < arr.length-1; ++j)
       arr[j] = arr[j+1];
     arr.length = arr.length - 1;
   }
}
---
where the for loops may also be replaced by memmove.
This should perform less memory operations for first-half removals.
However, this has the nasty side effect that using ~= on the resulting 
array will _reallocate_.
Feb 27 2007
prev sibling parent BCS <ao pathlink.com> writes:
Reply to Thorsten,


 <totaly untested code>
 
 T[] Remove(T)(T[] arr, int i)
 {
 return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
 }


 Sorry, I tried that, and it is too expensive !!
 Because it creates about 3 temporary instances.
 I would say :
 void Remove(T)(inout T[] arr, int i)
 {
 for(uint j = i;j < arr.length-1;++j)
 arr[j] = arr[j+1];
 arr.length = arr.length - 1;
 }
 can someone accelerate this ???
 


It would be kida slow wouldn't it. 

I only see one allocate and it's not a temp, where are the others? (BTW slicing 
doesn't allocate)
Feb 27 2007
prev sibling next sibling parent Kyle Furlong <kylefurlong gmail.com> writes:
Thorsten wrote:

 How can I remove values from an array ?


Queries of this kind belong in D.learn or Google. :D

http://www.google.com/search?hl=en&safe=off&q=remove+values+from+array+d+programming&btnG=Search
Feb 27 2007
prev sibling parent "David L. Davis" <SpottedTiger yahoo.com> writes:
"Thorsten" <toki78 usenet.cnntp.org> wrote in message 
news:es2e19$1a6m$1 digitalmars.com...

 How can I remove values from an array ?


    Have a look at the "del" function in the XArrayT.d code...but I think 
you'll find that all the functions do be very useful. I've just tested this 
code against dmd v1.007 on WinXP SP2 and it worked fine.

* XArrayT.d - D array extenders. A set of template functions to handle array 
overlapping slices by Andrew Fedoniouk, with the indexr() function added by 
Chris, and some minor bug fixes along with a unittest done by me. 
http://spottedtiger.tripod.com/D_Language/D_Sourcery_XArrayT.html

David L.

-------------------------------------------------------------------
"Dare to reach for the Stars...Dare to Dream, Build, and Achieve!"
-------------------------------------------------------------------
MKoD: http://spottedtiger.tripod.com/D_Language/D_Main_XP.html
Feb 27 2007