Iterator Pattern

This is a discussion on Iterator Pattern within the C Programming forums, part of the General Programming Boards category; Hello! I'm trying to write a library to implement iterators in C. The iterators should work on classical linked lists ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    12

    Iterator Pattern

    Hello!
    I'm trying to write a library to implement iterators in C. The iterators should work on classical linked lists written in C, with each node being an instance of a struct containing a pointer to the following node. If I delegate to the library also the work of building the list the solution is clear, but I'd like to know if it's possibile to do something better. In particular, is it possible to create a general purpose function that receives as a parameter the head of a list created in the usual way (plus eventually other informations about it) and then is able to iterate on it without being bound to the specific implementation of that list?
    Thanks in advance for any help!

    P.S.: I know that using the C language for this task may seem mad, but this is part of an university work about studying the possibilities to implement the design patterns of object oriented languages even in languages without objects like C.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,313
    In general, implementing something to "iterate over list" requires specific knowledge of how the particular list is implemented. For example, is the "next" element obtained via a pointer called "next", via increasing some index by 1, through a pointer called "nxt", or by some other mechanism?

    Providing the "head of a list" to your function is not enough. You also need to provide some means so the implementer of the list can pass information about the meaning of things like "iterate to next". A function pointer comes to mind as one possible means of providing that type of information.
    Right 98% of the time, and don't care about the other 3%.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    12
    You mean a pointer to a function that implements how to move from a node to the next one? I didn't think about that, that's a nice idea!
    The only problem is that, in theory, the iterator pattern should hide from the user the internal structure of the list, but in this case the user is asked to write a procedure that explicitly tells the library informations about the internal structure. But it's still an useful information for my work, thanks!
    Anyone has other ideas?

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,499
    Function pointers are the way to go. Your iterator pattern is basically an interface that you're trying to implement in C. The person coding a specific list, who wants to use your iterator pattern has to code it to some sort of specification however. There is no way for you to write magical code that just "knows" how to go from element to element in any possible kind of list.

    As far as hiding goes, you are hiding the details of the iterator itself, which is what you should do. You only give the user access to iterator.start(), iterator.end() and iterator.next() for example. Also, (as it often happens in the real world), the list may come from a 3rd party, and all you care about is if the list provided obeys the rules of your iterator.start, iterator.end and iterator.next functions. So the inner workings of the list may also be hidden from the end user.

    I think in your case, however, it's confusing since you may be playing the role of multiple parties, i.e. you're writing the iterator, the list and whatever code consumes these two things.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    12
    Thanks, that's exactly what I needed to know!

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21