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/