View mode: basic / threaded / horizontal-split · Log in · Help
August 01, 2012
containers, iteration, and removal
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?
August 01, 2012
Re: containers, iteration, and removal
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.
August 24, 2012
Re: containers, iteration, and removal
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
August 24, 2012
Re: containers, iteration, and removal
I feel kinda stupid here, what's wrong with C++ remove_if ( 
http://www.cplusplus.com/reference/algorithm/remove_if/ )?
August 27, 2012
Re: containers, iteration, and removal
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
August 27, 2012
Re: containers, iteration, and removal
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.
August 27, 2012
Re: containers, iteration, and removal
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()));
August 27, 2012
Re: containers, iteration, and removal
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?
Top | Discussion index | About this forum | D home