Re: Idioms for iterators in C

Discussion in 'C Programming' started by Moi, Jan 31, 2010.

  1. Moi

    Moi Guest

    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 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.

    Moi, Jan 31, 2010
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Kai-Uwe Bux
    May 8, 2005
  2. Ben Charrow

    Idioms and Anti-Idioms Question

    Ben Charrow, Jun 22, 2009, in forum: Python
    Lawrence D'Oliveiro
    Jul 4, 2009
  3. Eric Sosman

    Re: Idioms for iterators in C

    Eric Sosman, Jan 28, 2010, in forum: C Programming
  4. Ersek, Laszlo

    Re: Idioms for iterators in C

    Ersek, Laszlo, Jan 28, 2010, in forum: C Programming
    Antoninus Twink
    Jan 29, 2010
  5. ImpalerCore

    Re: Idioms for iterators in C

    ImpalerCore, Jan 29, 2010, in forum: C Programming
    Feb 2, 2010

Share This Page