Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3281 > unrolled thread

iterate and delete

Back to article view | Back to comp.programming

Contents

  iterate and delete bob <bob@coolfone.comze.com> - 2013-05-06 11:13 -0700
    Re: iterate and delete JJ <duh@nah.meh> - 2013-05-07 03:35 +0700
    Re: iterate and delete Rui Maciel <rui.maciel@gmail.com> - 2013-05-07 09:39 +0100
      Re: iterate and delete bob <bob@coolfone.comze.com> - 2013-05-08 07:54 -0700
    Re: iterate and delete malcolm.mclean5@btinternet.com - 2013-05-09 07:58 -0700
      Re: iterate and delete "BartC" <bc@freeuk.com> - 2013-05-09 22:53 +0100

#3281 — iterate and delete

Does computer science in general ever address the issue of when you are iterating over a collection and deleting elements from it?  If you are just using a counter, this can be tricky as the deletions can mess up the indices.

Thanks.

[toc] | [next] | [standalone]

#3282

On Mon, 6 May 2013 11:13:35 -0700 (PDT), bob wrote: 
> Does computer science in general ever address the issue of when you are
> iterating over a collection and deleting elements from it?  If you are
> just using a counter, this can be tricky as the deletions can mess up the
> indices. 

Use pointers to the actual data instead of element location. By enclosing
the actual values with objects or memory blocks, and use the pointers as the
element values. Thus you can add, delete, sort the collection without
worrying about bounds errors from cached indexes since the pointers point
directly to the actual values instead of the element location. Of course,
element addition/deletion should be followed by allocating/deallocating the
memory that encloses the actual element value.

Technically, this would be an array of pointers where each points to an
allocated memory that contains the element value.

[toc] | [prev] | [next] | [standalone]

#3283

bob wrote:

> Does computer science in general ever address the issue of when you are
> iterating over a collection and deleting elements from it?  If you are
> just using a counter, this can be tricky as the deletions can mess up the
> indices.

It isn't rocket surgery.

http://en.wikipedia.org/wiki/Iterator


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#3284

On Tuesday, May 7, 2013 3:39:35 AM UTC-5, Rui Maciel wrote:
> bob wrote:
> 
> 
> 
> > Does computer science in general ever address the issue of when you are
> 
> > iterating over a collection and deleting elements from it?  If you are
> 
> > just using a counter, this can be tricky as the deletions can mess up the
> 
> > indices.
> 
> 
> 
> It isn't rocket surgery.
> 
> 
> 
> http://en.wikipedia.org/wiki/Iterator
> 
> 
> 
> 
> 
> Rui Maciel

Removing elements can result in non-trivial modifications to the data structure and mess up the iterator.  I think a binary tree is a good example where the modification is often non-trivial.

If you look here:

http://docs.oracle.com/javase/6/docs/api/java/util/Iterator.html

You will see next to remove():

(optional operation)


I guess the general solution is "mark-and-sweep".  In one phase you mark the objects that will be deleted.  Then in the next phase you sweep.  Sweeping could involve creating a whole new data structure and adding one-by-one the elements that were spared.

[toc] | [prev] | [next] | [standalone]

#3286

On Monday, May 6, 2013 7:13:35 PM UTC+1, bob wrote:
> Does computer science in general ever address the issue of when you are 
> iterating over a collection and deleting elements from it?  If you are just 
> using a counter, this can be tricky as the deletions can mess up the indices.
> 
It's something that people who teach computer science in universities are 
well aware of.
However it tends to be glossed over at an introductory level to avoid 
overloading students with difficulties. Deleting or, more rarely, adding
elements can make it very difficult to keep iterators up to date.

[toc] | [prev] | [next] | [standalone]

#3287

<malcolm.mclean5@btinternet.com> wrote in message 
news:72265d42-b411-47e2-bd5b-8b4929059354@googlegroups.com...
> On Monday, May 6, 2013 7:13:35 PM UTC+1, bob wrote:
>> Does computer science in general ever address the issue of when you are
>> iterating over a collection and deleting elements from it?  If you are 
>> just
>> using a counter, this can be tricky as the deletions can mess up the 
>> indices.
>>
> It's something that people who teach computer science in universities are
> well aware of.
> However it tends to be glossed over at an introductory level to avoid
> overloading students with difficulties. Deleting or, more rarely, adding
> elements can make it very difficult to keep iterators up to date.

Surely it's impossible to deal with it in general? Since any collection 
could be transformed, in between one iteration and the next, into a totally 
different collection. The current position or element in the old collection 
might then be meaningless.

-- 
Bartc

 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web