www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - removing an item from a dynamic array

reply maarten van damme <maartenvd1994 gmail.com> writes:
--0016e6dab59eaa923e04b0127c98
Content-Type: text/plain; charset=ISO-8859-1

I've stumbled in an annoying error while trying to remove an item from a
dynamic array.
It's an array of Loc and a Loc is a simple struct of two integers.
when I used remove from std.algorithm I get
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5948): Error:
incompatible types for ((pos) <= (from)): 'uint' and 'Loc'
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5949): Error:
incompatible types for ((pos) < (from)): 'uint' and 'Loc'

is it suposed to do this?

--0016e6dab59eaa923e04b0127c98
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

I&#39;ve stumbled in an annoying error while trying to remove an item from =
a dynamic array.<div>It&#39;s an array of Loc and a Loc is a simple struct =
of two integers.</div><div>when I used remove from std.algorithm I get</div=

or: incompatible types for ((pos) &lt;=3D (from)): &#39;uint&#39; and &#39;= Loc&#39;</div><div>C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5= 949): Error: incompatible types for ((pos) &lt; (from)): &#39;uint&#39; and= &#39;Loc&#39;</div> </div><div><br></div><div>is it suposed to do this?</div> --0016e6dab59eaa923e04b0127c98--
Oct 24 2011
next sibling parent reply simendsjo <simendsjo gmail.com> writes:
On 24.10.2011 23:55, maarten van damme wrote:
 I've stumbled in an annoying error while trying to remove an item from a
 dynamic array.
 It's an array of Loc and a Loc is a simple struct of two integers.
 when I used remove from std.algorithm I get
 C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5948): Error:
 incompatible types for ((pos) <= (from)): 'uint' and 'Loc'
 C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5949): Error:
 incompatible types for ((pos) < (from)): 'uint' and 'Loc'

 is it suposed to do this?

Could you add some sample code? I think remove wants indexes, not values: import std.stdio, std.algorithm; struct S { int a, b; } void main() { auto arr = [S(0,1), S(2,3), S(4,5)]; writeln(arr); arr = arr.remove(0, 2); writeln(arr); } prints: [S(0, 1), S(2, 3), S(4, 5)] [S(4, 5)]
Oct 24 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
maarten van damme:

 import std.algorithm;
 struct Loc {
 uint row;
 uint col;
 }
 void main(){
 Loc[] testArray;
 Loc a={3,2};
 Loc b={5,3};
 testArray~=a;
 testArray~=b;
 remove(testArray,a);
 }
 gives the same error

The second argument of remove() needs to be an index, a size_t. This works: import std.stdio, std.algorithm; struct Loc { uint row, col; } void main() { auto a = Loc(3, 2), b = Loc(5, 3); auto data = [a, b]; writeln(remove(data, 0)); writeln(data); } It prints: [Loc(5, 3)] [Loc(5, 3), Loc(5, 3)] So curiously remove() doesn't work in-place, I think this is a bug or a design bug. Bye, bearophile
Oct 25 2011
next sibling parent reply simendsjo <simendsjo gmail.com> writes:
On 25.10.2011 11:51, bearophile wrote:
 maarten van damme:

 import std.algorithm;
 struct Loc {
 uint row;
 uint col;
 }
 void main(){
 Loc[] testArray;
 Loc a={3,2};
 Loc b={5,3};
 testArray~=a;
 testArray~=b;
 remove(testArray,a);
 }
 gives the same error

The second argument of remove() needs to be an index, a size_t. This works: import std.stdio, std.algorithm; struct Loc { uint row, col; } void main() { auto a = Loc(3, 2), b = Loc(5, 3); auto data = [a, b]; writeln(remove(data, 0)); writeln(data); } It prints: [Loc(5, 3)] [Loc(5, 3), Loc(5, 3)] So curiously remove() doesn't work in-place, I think this is a bug or a design bug. Bye, bearophile

Yes, probably a bug. This example from the documentation fails: import std.stdio, std.algorithm; void main() { int[] a = [ 0, 1, 2, 3 ]; assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]); }
Oct 25 2011
parent bearophile <bearophileHUGS lycos.com> writes:
I have written this:
http://d.puremagic.com/issues/show_bug.cgi?id=6849

Bye,
bearophile
Oct 25 2011
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 25.10.2011 13:51, bearophile wrote:
 maarten van damme:

 import std.algorithm;
 struct Loc {
 uint row;
 uint col;
 }
 void main(){
 Loc[] testArray;
 Loc a={3,2};
 Loc b={5,3};
 testArray~=a;
 testArray~=b;
 remove(testArray,a);
 }
 gives the same error

The second argument of remove() needs to be an index, a size_t. This works: import std.stdio, std.algorithm; struct Loc { uint row, col; } void main() { auto a = Loc(3, 2), b = Loc(5, 3); auto data = [a, b]; writeln(remove(data, 0)); writeln(data); } It prints: [Loc(5, 3)] [Loc(5, 3), Loc(5, 3)] So curiously remove() doesn't work in-place, I think this is a bug or a design bug. Bye, bearophile

No, it's not a bug. It's the same as c++ STL remove - it operates on range but not on container. To shrink container, update it's length. -- Dmitry Olshansky
Oct 25 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Dmitry Olshansky:

 No, it's not a bug. It's the same as c++ STL remove - it operates on 
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2. Bye, bearophile
Oct 25 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/25/2011 08:38 PM, Graham Fawcett wrote:
 On Tue, 25 Oct 2011 13:11:20 -0400, bearophile wrote:

 Dmitry Olshansky:

 No, it's not a bug. It's the same as c++ STL remove - it operates on
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2.

I think I'd like to see std.array.replaceInPlace grow a three-parameter version, so you could write: replaceInPlace(arr, f, t); // del arr[f:t] ...instead of: replaceInPlace(arr, f, t, cast(typeof(arr)) []); ...and skip the pointless allocation of the empty array. Graham

There is no allocation, so no significant runtime overhead ( assert([] is null); ) I can see how the functionality of the overload would be useful, but I think it should get a more descriptive name as there is no more parameter that specifies with what to _replace_ arr[f..t] with. removeInPlace?
Oct 25 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Steven Schveighoffer:

 Note that there *is* overhead, even if it's not significant.  I highly  
 recommend never to use [] and use null instead.

In Bugzilla I did ask for the opposite (but not on a performance basis) :-) null is less specific than [] because a null is also used for pointers and references, while [] is only for empty associative arrays and empty dynamic arrays. An empty dynamic array is a 2-words struct, so representing its literal with just a null (that is a single word) looks misleading and doesn't help D novices remember what a dynamic array is. I have even suggested to use [:] as empty associative array literal in D. Regarding the difference in [] and null performance, I think adding a small optimization to the front-end is a better solution to this little problem. Bye, bearophile
Oct 26 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

 It operates on a range. It can't do anything else. It has no access to the 
 underlying container and can't remove anything from it.

Thank you for explaining me this stuff again. I have updated the enhancement request 6849 with a note. Bye, bearophile
Oct 25 2011
prev sibling parent simendsjo <simendsjo gmail.com> writes:
On 25.10.2011 18:23, Dmitry Olshansky wrote:
 On 25.10.2011 13:51, bearophile wrote:
 maarten van damme:

 import std.algorithm;
 struct Loc {
 uint row;
 uint col;
 }
 void main(){
 Loc[] testArray;
 Loc a={3,2};
 Loc b={5,3};
 testArray~=a;
 testArray~=b;
 remove(testArray,a);
 }
 gives the same error

The second argument of remove() needs to be an index, a size_t. This works: import std.stdio, std.algorithm; struct Loc { uint row, col; } void main() { auto a = Loc(3, 2), b = Loc(5, 3); auto data = [a, b]; writeln(remove(data, 0)); writeln(data); } It prints: [Loc(5, 3)] [Loc(5, 3), Loc(5, 3)] So curiously remove() doesn't work in-place, I think this is a bug or a design bug. Bye, bearophile

No, it's not a bug. It's the same as c++ STL remove - it operates on range but not on container. To shrink container, update it's length.

If it's not a bug, there's a bug in the documentation (see my previous post)
Oct 25 2011
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--0016e65b581685c9de04b018e3a4
Content-Type: text/plain; charset=ISO-8859-1

import std.algorithm;
struct Loc {
uint row;
uint col;
}
void main(){
Loc[] testArray;
Loc a={3,2};
Loc b={5,3};
testArray~=a;
testArray~=b;
remove(testArray,a);
}
gives the same error

--0016e65b581685c9de04b018e3a4
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div>import std.algorithm;</div><div>struct Loc {</div><div><span class=3D"=
Apple-tab-span" style=3D"white-space:pre">	</span>uint row;</div><div><span=
 class=3D"Apple-tab-span" style=3D"white-space:pre">	</span>uint col;</div>=
<div>
}</div><div>void main(){</div><div><span class=3D"Apple-tab-span" style=3D"=
white-space:pre">		</span>Loc[] testArray;</div><div><span class=3D"Apple-t=
ab-span" style=3D"white-space:pre">		</span>Loc a=3D{3,2};</div><div><span =
class=3D"Apple-tab-span" style=3D"white-space:pre">		</span>Loc b=3D{5,3};<=
/div>
<div><span class=3D"Apple-tab-span" style=3D"white-space:pre">		</span>test=
Array~=3Da;</div><div><span class=3D"Apple-tab-span" style=3D"white-space:p=
re">		</span>testArray~=3Db;</div><div><span class=3D"Apple-tab-span" style=
=3D"white-space:pre">		</span>remove(testArray,a);</div>
<div><span class=3D"Apple-tab-span" style=3D"white-space:pre">		</span>}</d=
iv><div>gives the same error</div>

--0016e65b581685c9de04b018e3a4--
Oct 24 2011
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--0016e6dab59e54aec104b020a0db
Content-Type: text/plain; charset=ISO-8859-1

thank you, meanwhile I'll just use find + remove the index.

--0016e6dab59e54aec104b020a0db
Content-Type: text/html; charset=ISO-8859-1

thank you, meanwhile I&#39;ll just use find + remove the index.

--0016e6dab59e54aec104b020a0db--
Oct 25 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, October 25, 2011 10:11 bearophile wrote:
 Dmitry Olshansky:
 No, it's not a bug. It's the same as c++ STL remove - it operates on
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2.

It operates on a range. It can't do anything else. It has no access to the underlying container and can't remove anything from it. The best that it can do is move the removed elements to the end of the range and then return a slice which is that many elements shorter. C++'s erase has the exact same problem. And as long as the range (or iterator) does not have access to its underlying container to do make calls on it, that's the best that can be done. At least in D, you get a shortened range. With iterators, the situation isn't quite as clean. So, D's remove still manages to improve over C++'s erase at least somewhat. - Jonathan M Davis
Oct 25 2011
prev sibling next sibling parent Graham Fawcett <fawcett uwindsor.ca> writes:
On Tue, 25 Oct 2011 13:11:20 -0400, bearophile wrote:

 Dmitry Olshansky:
 
 No, it's not a bug. It's the same as c++ STL remove - it operates on
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2.

I think I'd like to see std.array.replaceInPlace grow a three-parameter version, so you could write: replaceInPlace(arr, f, t); // del arr[f:t] ...instead of: replaceInPlace(arr, f, t, cast(typeof(arr)) []); ...and skip the pointless allocation of the empty array. Graham
Oct 25 2011
prev sibling next sibling parent Graham Fawcett <fawcett uwindsor.ca> writes:
On Tue, 25 Oct 2011 20:52:57 +0200, Timon Gehr wrote:

 On 10/25/2011 08:38 PM, Graham Fawcett wrote:
 On Tue, 25 Oct 2011 13:11:20 -0400, bearophile wrote:

 Dmitry Olshansky:

 No, it's not a bug. It's the same as c++ STL remove - it operates on
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2.

I think I'd like to see std.array.replaceInPlace grow a three-parameter version, so you could write: replaceInPlace(arr, f, t); // del arr[f:t] ...instead of: replaceInPlace(arr, f, t, cast(typeof(arr)) []); ...and skip the pointless allocation of the empty array. Graham

is null); )

Ah, my mistake; that makes sense.
 I can see how the functionality of the overload would be useful, but I
 think it should get a more descriptive name as there is no more
 parameter that specifies with what to _replace_ arr[f..t] with.
 removeInPlace?

Good point -- that would get my vote. Got time for a pull request? :) Graham
Oct 25 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 25 Oct 2011 05:51:25 -0400, bearophile <bearophileHUGS lycos.com>  
wrote:

 maarten van damme:

 import std.algorithm;
 struct Loc {
 uint row;
 uint col;
 }
 void main(){
 Loc[] testArray;
 Loc a={3,2};
 Loc b={5,3};
 testArray~=a;
 testArray~=b;
 remove(testArray,a);
 }
 gives the same error

The second argument of remove() needs to be an index, a size_t. This works: import std.stdio, std.algorithm; struct Loc { uint row, col; } void main() { auto a = Loc(3, 2), b = Loc(5, 3); auto data = [a, b]; writeln(remove(data, 0)); writeln(data); } It prints: [Loc(5, 3)] [Loc(5, 3), Loc(5, 3)] So curiously remove() doesn't work in-place, I think this is a bug or a design bug.

From the documentation: "The original array has remained of the same length because all functions in std.algorithm only change content, not topology." In other words, remove just moves unwanted elements to the back of the array, then returns the front of it. It looks like it works as designed. -Steve
Oct 26 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 25 Oct 2011 14:52:57 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 10/25/2011 08:38 PM, Graham Fawcett wrote:
 On Tue, 25 Oct 2011 13:11:20 -0400, bearophile wrote:

 Dmitry Olshansky:

 No, it's not a bug. It's the same as c++ STL remove - it operates on
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2.

I think I'd like to see std.array.replaceInPlace grow a three-parameter version, so you could write: replaceInPlace(arr, f, t); // del arr[f:t] ...instead of: replaceInPlace(arr, f, t, cast(typeof(arr)) []); ...and skip the pointless allocation of the empty array. Graham

There is no allocation, so no significant runtime overhead ( assert([] is null); )

Note that there *is* overhead, even if it's not significant. I highly recommend never to use [] and use null instead. Does replaceInPlace(arr, f, t, null) work? Perhaps replaceInPlace could just default the fourth argument to null. -Steve
Oct 26 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 25 Oct 2011 06:13:09 -0400, simendsjo <simendsjo gmail.com> wrote:

 On 25.10.2011 11:51, bearophile wrote:
 maarten van damme:

 import std.algorithm;
 struct Loc {
 uint row;
 uint col;
 }
 void main(){
 Loc[] testArray;
 Loc a={3,2};
 Loc b={5,3};
 testArray~=a;
 testArray~=b;
 remove(testArray,a);
 }
 gives the same error

The second argument of remove() needs to be an index, a size_t. This works: import std.stdio, std.algorithm; struct Loc { uint row, col; } void main() { auto a = Loc(3, 2), b = Loc(5, 3); auto data = [a, b]; writeln(remove(data, 0)); writeln(data); } It prints: [Loc(5, 3)] [Loc(5, 3), Loc(5, 3)] So curiously remove() doesn't work in-place, I think this is a bug or a design bug. Bye, bearophile

Yes, probably a bug. This example from the documentation fails: import std.stdio, std.algorithm; void main() { int[] a = [ 0, 1, 2, 3 ]; assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]); }

Most certainly this is a bug. Here is the resulting array and final state of a: import std.stdio, std.algorithm; void main() { int[] a = [ 0, 1, 2, 3 ]; writeln( remove!(SwapStrategy.unstable)(a, 1)); writeln(a); } output: [3, 1, 2] [3, 1, 2, 3] Clearly, index 0 was removed, not index 1. Please file a bug. -Steve
Oct 26 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 26 Oct 2011 07:35:02 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 It looks like it works as designed.

...as others have already said Sorry for the added noise, should have read the other responses first. -Steve
Oct 26 2011
prev sibling parent Graham Fawcett <fawcett uwindsor.ca> writes:
On Wed, 26 Oct 2011 07:38:06 -0400, Steven Schveighoffer wrote:

 On Tue, 25 Oct 2011 14:52:57 -0400, Timon Gehr <timon.gehr gmx.ch>
 wrote:
 
 On 10/25/2011 08:38 PM, Graham Fawcett wrote:
 On Tue, 25 Oct 2011 13:11:20 -0400, bearophile wrote:

 Dmitry Olshansky:

 No, it's not a bug. It's the same as c++ STL remove - it operates on
 range but not on container. To shrink container, update it's length.

Thank you for your answer, I didn't know this, and I didn't think about this possibility because it's weird, it's an in-place operation that modifies the data only partially, leaving it in a wrong state. It looks like a bad design, bug prone-too. The design of Python del is better. (Maybe I'll have to bring this in the main D newsgroup too, because Phobos bug reports often get unnoticed). In the meantime I'll add a wrapper function to dlibs2.

I think I'd like to see std.array.replaceInPlace grow a three-parameter version, so you could write: replaceInPlace(arr, f, t); // del arr[f:t] ...instead of: replaceInPlace(arr, f, t, cast(typeof(arr)) []); ...and skip the pointless allocation of the empty array. Graham

is null); )

Note that there *is* overhead, even if it's not significant. I highly recommend never to use [] and use null instead. Does replaceInPlace(arr, f, t, null) work? Perhaps replaceInPlace could just default the fourth argument to null.

Yes, it works with null, although you have to cast it to typeof(arr). Graham
Oct 26 2011