www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - containers, iteration, and removal

reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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?
Aug 01 2012
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Aug 01 2012
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Aug 24 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Aug 27 2012
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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.
Aug 27 2012
prev sibling parent reply "JN" <666total wp.pl> writes:
I feel kinda stupid here, what's wrong with C++ remove_if ( 
http://www.cplusplus.com/reference/algorithm/remove_if/ )?
Aug 24 2012
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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()));
Aug 27 2012
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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?
Aug 27 2012