Iterator in linguaggio C

Question

Qualcuno ha provato a fornire supporto per Iterator in C. Non sto cercando C++ STL :: Iterator, ma il supporto minimo per l'idea di iniziare sarebbe un buon punto per me.

Sto sviluppando libreria contenitore come stl ma con supporto minimo, quindi ho bisogno di questo tipo di funzionalità in quei contenitori.

Non vedo l'ora di definire determinati gruppi di interfacce di algoritmi (simili a STL). Ad esempio ordina, che prenderà inizio e fine iteratore e dovrebbe funzionare con qualsiasi contenitore.

Answer 1

Se si è autorizzati a utilizzare il codice GPL nel proprio progetto, dare un'occhiata a GLib anziché reinventare la ruota. GLib consente inoltre di svilupparsi in modo abbastanza portatile a livello di codice sorgente. Nota che se lo usi devi rilasciare il codice anche sotto GPL.

Dai un'occhiata a g_list_first() e g_list_next() che implementano la funzionalità di un iteratore nell'elenco. C'è anche un g_list_foreach() `

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

Answer 2

Avresti bisogno di un modo standardizzato di incrementando l'iteratore. In C++, questo è solo il sovraccarico operator++(). Il tuo contenitore ha bisogno di una funzione associata che restituisca un puntatore all'elemento successivo. Questa funzione di incremento dovrebbe essere passata come puntatore a qualsiasi routine generalizzata che possa accettare un iteratore nella libreria.

Per esempio, se voglio scrivere una funzione che restituisce il max elemento dal contenitore, non ho bisogno solo la funzione di confronto (l'equivalente di operator<()), ho bisogno di una funzione iteratore-incremento (l'equivalente di operator++()).

Quindi assicurarmi di poter accettare un puntatore alla funzione di incremento è il requisito chiave.

Answer 3

Date un'occhiata a liste collegate. Un nodo include un puntatore "next" che si può utilizzare per scorrere l'elenco, in modo analogo a iteratori C++:

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 */ 
} 

Non è un iteratore C++, ma eventualmente questo dà un'idea di un modo per avvicinarsi questo in C.

Answer 4

I puntatori possono servire a questa funzione. container.begin() è facile, e container.end() non richiede troppo lavoro.

consideri

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; 
} 

Per altri contenitori come le liste, è possibile utilizzare NULL come fine. Lo stesso vale per gli alberi, ma la funzione next deve mantenere lo stato. (o l'iteratore è un puntatore a una struttura con stato aggiornato dalle chiamate a next(it)).

Answer 5

Ho trovato un progetto open source che è l'implementazione STL in linguaggio C.

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

Answer 6

Questo è ciò che mi si avvicinò con:

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 è il nostro prefisso progetto. Abbiamo solo bisogno di un dizionario (mappa stringa di stringa) come contenitore.