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

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

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?

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
>>
>>
> There is no allocation, so no significant runtime overhead ( assert([]
> 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

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

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

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

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

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

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