Hello.

Today I was thinking about Java. Specifically, java.util.Iterator and the pattern

while(iter.hasNext()) {
	Object item = iter.next();
	if(predicate(item)) {
		iter.remove();
	}
}

You can do this in Java. Easily. You can also do this in C++ with iterators and erase. Bit more cumbersome, bit more dangerous, but it's possible.

And D?

auto r = container[];
while(!r.empty) {
	auto item = r.front;
	if(predicate(item)) {
		r = container.linearRemove(take(r, 1));
	}else {
		r.popFront();
	}
}

wut?

The java version exhibits two properties of interest
A) the iterator knows when to stop, and it's kind of hard for the programmer to screw that aspect up.
B) the whole thing is pretty flexible for selecting the elements you want [to get rid of]

The C++ version, were it shown, would keep (B), but loses (A).
The D version above keeps (B), but somewhat loses (A). The range knows when to stop, but it seems so easy for the programmer to mess up placement of that popFront.

I also take (erk) issue with the implementation of linearRemove. It depends on an interface from the container range that is not part of the general range interface. This poses problems. You can't wrap the container range with another range and pass the result to linearRemove. The special interface is gone. Case in point, there is a specific overload for Take!Range, which also uses nonstandard interface.

This doesn't fit the range philosophy. You can't do this

container.linearRemove(filter!predicate(r));

or this

container.linearRemove(takeOne(r));

or this

container.linearRemove(chain(r1,r2,r3));

But what if you could? It would give you (A) and (B) back.

Suppose you define

// look at me! I'm a really fat pointer (kind of)
class Position {
	Value v;
	private:
		<container guts>
}

and expose a way to get a range of positions from a container

container.position_range();

Then your linearRemove can accept any range of element type Position, and your user can compose the position range to her heart's content (predicates are a few characters longer), but cannot access the container internals.


What of this? Are there any downsides to this approach that I haven't thought of?

On Wednesday, 1 August 2012 at 07:44:49 UTC, Ellery Newcomer wrote:
> I also take (erk) issue with the implementation of linearRemove. It depends on an interface from the container range that is not part of the general range interface. This poses problems. You can't wrap the container range with another range and pass the result to linearRemove. The special interface is gone. Case in point, there is a specific overload for Take!Range, which also uses nonstandard interface.

Err, in C++ neither.

If you want to remove an element from a vector, you use "vector::iterator". A *would be* filter_iterator wouldn't work.

----
Regarding the "special overload", it is only present for containers that don't provide ranges with opSlice, such as DList.

Now in C++, you'd have both functions for containers:
Remove(it); //Removes element at it
and
Remove(first, last)//removes the range

In D, you also have 1-2 functions, but they carry the same name:

Remove(range); //removes the range.
Remove(Take!Range); //Optional: removes elements from the take range.

If you compare both, you'll see (IMO) that not only does the interface provided by D gives just as much functionality for no extra cost, it also provides MORE functionality:
In the case of forwardRange, remove(Take!Range) can be used to delete an indiscriminate amount of elements, not just one!
C++ doesn't have that, and neither does java, I believe.

----
But I'll kind of agree, in C++ just like in D, while iterators/ranges work nice when you manipulate just them, you always lose a bit of abstraction when you want to re-interface with the underlying container.

On Wed, 01 Aug 2012 03:44:47 -0400, Ellery Newcomer <ellery-newcomer@utulsa.edu> wrote:

> Hello.
>
> Today I was thinking about Java. Specifically, java.util.Iterator and the pattern
>
> while(iter.hasNext()) {
> 	Object item = iter.next();
> 	if(predicate(item)) {
> 		iter.remove();
> 	}
> }
>
> You can do this in Java.

You can do this just as easy in dcollections:

foreach(bool doRemove, item; container)
{
   doRemove = predicate(item);
}

In fact, this little feature is one of the major reasons I wanted to create a collections library.  Tango's container library was modeled after Doug Lea's (not the Java adaptation of it), and it did not include a way to remove during iteration.

-Steve

I feel kinda stupid here, what's wrong with C++ remove_if ( http://www.cplusplus.com/reference/algorithm/remove_if/ )?

On Fri, 24 Aug 2012 13:35:57 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:


> foreach(bool doRemove, item; container)
> {
>     doRemove = predicate(item);
> }

Whoops, should be

foreach(ref bool doRemove, item; container)

-Steve

On 08/27/2012 06:27 AM, Steven Schveighoffer wrote:
> On Fri, 24 Aug 2012 13:35:57 -0400, Steven Schveighoffer
> <schveiguy@yahoo.com> wrote:
>
>
>> foreach(bool doRemove, item; container)
>> {
>>     doRemove = predicate(item);
>> }
>
> Whoops, should be
>
> foreach(ref bool doRemove, item; container)
>
> -Steve

Right, I totally forgot about that one.

On 08/24/2012 12:23 PM, JN wrote:
> I feel kinda stupid here, what's wrong with C++ remove_if (
> http://www.cplusplus.com/reference/algorithm/remove_if/ )?
>

you mean something like

c.erase(remove_if(c.begin(), c.end(), predicate), c.end())

?

That actually is the sort of thing one could accomplish with position ranges:

c.remove(filter!(anti_predicate)(c.position_range()));

On 08/27/2012 12:46 PM, Ellery Newcomer wrote:
> On 08/24/2012 12:23 PM, JN wrote:
>> I feel kinda stupid here, what's wrong with C++ remove_if (
>> http://www.cplusplus.com/reference/algorithm/remove_if/ )?
>>
>
> you mean something like
>
> c.erase(remove_if(c.begin(), c.end(), predicate), c.end())
>
> ?
>
> That actually is the sort of thing one could accomplish with position
> ranges:
>
> c.remove(filter!(anti_predicate)(c.position_range()));

Doh.

import std.stdio;
import std.container;

void main(){
    auto sl = SList!int([1,2,3,4,5,6,7,8]);
    auto rng = sl[];
    writeln(sl[]);
    sl.linearRemove(remove_if!"a % 2 == 1"(sl[]));
    writeln(sl[]);
}

auto remove_if(alias _pred, Rng)(Rng rng) {
    import std.functional;
    alias unaryFun!_pred pred;
    Rng res = rng.save();
    while(!rng.empty) {
        if(!pred(rng.front)) {
            res.front = rng.moveFront();
            res.popFront();
        }
        rng.popFront();
    }
    return res;
}


Hmm. In multi_index,

 res.front = rng.moveFront();

has some slightly nasty ramifications which I am not sure how to get around (without access to the node pointer of the element being assigned, multi_index has to remove the element and then add it back in). I wonder what boost::multi_index does?