«

On Thu, 28 Jan 2010 18:02:06 +0000, Richard Harter wrote:

> Stepping through a container is a common task and there are a variety of
> common idioms for doing just that. For example you see code like:
>
> Arrays
> for (i=0;i<n;i++) // operate on a[i] for (ptr=a;ptr;ptr++) //
> operate on *ptr for (ptr=a;ptr++ // variant
> Linked list
> for (ptr=first;ptr;ptr=ptr->link) // operate on *ptr
>
> Now suppose that you want to do a bit of abstraction. That is, suppose
> the data is stored within some container - storage method carefully
> hidden and subject to change. Now you need an API, and an idiom for
> stepping through the container using the API.
>
> Here is the outline of an example. Let foo be the type of container.
> For notation I usually append the operation name to the container type -
> you may prefer a different notation. Thus
>
> foo_open // create a foo container, returns handle foo_close
> // deletes a foo container foo_add // adds an item to the
> container foo_delete // removes an item from the container
>

> for (foo_begin(handle); ptr = foo_next(handle) {...}
>
> Returning pointers can be a security issue; an alternative is to return
> a copy of the instance. One way to handle this is:
>
> for(foo_begin(handle); foo_more(handle){
> x=foo_get(handle)
> ...
> }
>

IMHO the biggest choice you have to make, when designing your "API"
and iterator, is whether you want what SQL-people call "stable cursors".
(a cursor is in fact an iterator)

In the program fragment:

it = foo_iterator(&foo);
this = foo_fetch( it );
foo_delete ( this) ;
this = foo_fetch( it );

, you want the iterator to keep working, even after the "previous" element
has been deleted. This can be trivial for an array, but it gets difficult with
linked lists, trees or hashtables (which all can change "shape" as a result
of the delete)

This would cause your iterator to need maintaining more and more state.
(how do you find the successor for a deleted node ? maybe remember the key ?
what if the key is not necessarily unique ? Maintain its rank ?)

This has been an issue for a lot of "iterators": opendir() / readdir()
, stdlib's FILE abstraction has some iterator semantics (solution: it is not
possible to "delete" a "record" from the middle of a FILE)
, and strtok() is in fact a tiny iterator, with the state-variable provided by
the caller.

/2cts
AvK