Iterator in C language

Has anyone tried providing support for Itera开发者_如何学Gotor in C. I am not looking for exact C++ STL::Iterator but minimal support for some idea to start would be good point for me .

I am developing container library same like stl but with minimal support, So I need this kind of functionality in those container.

I am looking forward of defining certain sets of algorithms interfaces ( similar to STL ). For example sort , which will take begin and end iterator and should work with any container.

---

Pointers can serve this function. container.begin() is easy, and container.end() doesn't take too much work.

Consider

Value array[N];
typedef Value* iterator;
iterator array_begin(Value a[]){ return &a[0];}
iterator array_end(Value a[], int n){ return &a[n];}
iterator array_next(iterator i) { return ++i;}

iterator it = array_begin(a);
iterator end = array_end(a,N);
for (;it < end; it=array_next(it))
{
    Value v = *it;
}

For other containers like lists, you can use NULL as end. Same for trees, but the next function needs to maintain state. (or the iterator is a pointer to a struct with state updated by calls to next(it)).

---

Take a look at linked lists. A node includes a "next" pointer that one can use to iterate through the list, in a manner analogous to C++ iterators:

typedef struct Node {
    ...                                                                                                                                                           
    struct Node *next;                                                                                                                                                          
} Node;  

...

Node *iter, *firstNode, *nodeList; 

/* set firstNode and populate nodeList */

for (iter = firstNode; iter != NULL; iter = iter->next) {
    /* iterate through list */
}

It's not a C++ iterator, but hopefully this gives an idea of one way to approach this in C.

---

If you are allowed to use LGPL code in your project have a look at GLib instead of re-inventing the wheel. GLib allows also to develop in a quite portable way at source code level.

Have a look at g_list_first() and g_list_next() which implement the functionality of an iterator on the list. There is even a g_list_foreach()`

http://library.gnome.org/devel/glib/stable/glib-Doubly-Linked-Lists.html

---

You'd need a standardized way of incrementing the iterator. In C++, that's just the overloaded operator++(). Your container needs an associated function that returns a pointer to the next element. This incrementing function would need to be passed as a pointer to any generalized routine that can accept an iterator in your library.

For example, If I want to write a function that returns the max element from the container, I need not only the comparison function (the equivalent of operator<()), I need an iterator-incrementing function (the equivalent of operator++()).

So ensuring that I can accept a pointer to your incrementing function is the key requirement.

---

This is what I came up with:

typedef struct PWDict PWDict;
typedef struct PWDictIterator PWDictIterator;

typedef struct PWDictImplementation
{
    PWDict *(*create)(const struct PWDictImplementation *impl, size_t elements);
    void (*destroy)(PWDict *dict);

    unsigned int (*size)(const PWDict *dict);
    unsigned int (*sizeInBytes)(const PWDict *dict);

    int (*get)(const PWDict *dict, const char *key, char *output, size_t size);
    int (*set)(PWDict *dict, const char *key, const char *value);

    PWDictIterator *(*iteratorCreate)(const PWDict *dict);
    void (*iteratorBegin)(PWDictIterator *it);
    void (*iteratorEnd)(PWDictIterator *it);
    void (*iteratorDestroy)(PWDictIterator *it);

    const char *(*iteratorGetKey)(const PWDictIterator *it);
    const char *(*iteratorGetValue)(const PWDictIterator *it);
    int (*iteratorSetValue)(PWDictIterator *it, const char *value);
    void (*iteratorNext)(PWDictIterator *it);
}
PWDictImplementation;

struct PWDict
{
    PWDictImplementation *impl;
};

struct PWDictIterator
{
    PWDict *dict; /* get iterator implementation from the dict implementation */
};

PW is our project prefix. We just needed a dictionary (string-string map) like container.

---

I found one open source project which is STL implementation in C language.

http://sourceforge.net/projects/tstl2cl/