iterate and delete

[bob]

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.

[JJ]

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.

[Rui Maciel]

It isn't rocket surgery.

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


Rui Maciel

[bob]

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.

[malcolm...@btinternet.com]

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.

[BartC]

<malcolm...@btinternet.com> wrote in message
news:72265d42-b411-47e2...@googlegroups.com...

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