Iterator en lenguaje C

Question

¿Alguien ha intentado proporcionar soporte para Iterator en C. No estoy buscando exactamente C++ STL :: Iterator, pero el soporte mínimo para una idea para comenzar sería un buen punto para mí.

Estoy desarrollando una biblioteca de contenedores igual que stl pero con un soporte mínimo, así que necesito este tipo de funcionalidad en esos contenedores.

Espero con interés la definición de ciertos conjuntos de interfaces de algoritmos (similar a STL). Por ejemplo, ordenar, que tomará el iterador de inicio y fin y debería funcionar con cualquier contenedor.

Answer 1

Si se le permite usar el código GPL en su proyecto, eche un vistazo a GLib en lugar de volver a inventar la rueda. GLib también permite desarrollar de una manera bastante portátil a nivel de código fuente. Tenga en cuenta que si usa esto, debe liberar el código también bajo GPL.

Eche un vistazo a g_list_first() y g_list_next() que implementan la funcionalidad de un iterador en la lista. Hay incluso un g_list_foreach() `

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

Answer 2

Necesitará una forma estandarizada de incrementando el iterador. En C++, eso es solo el operator++() sobrecargado. Su contenedor necesita una función asociada que devuelva un puntero al siguiente elemento. Esta función incremental tendría que pasarse como un puntero a cualquier rutina generalizada que pueda aceptar un iterador en su biblioteca.

Por ejemplo, si quiero escribir una función que devuelve el elemento máximo del contenedor, no necesito solamente la función de comparación (el equivalente a operator<()), necesito una función de iterador de incremento (el equivalente de operator++()).

Asegurándome de que puedo aceptar un puntero a su función de incremento es el requisito clave.

Answer 3

Tome un vistazo a las listas enlazadas. Un nodo incluye un puntero "siguiente" que se puede utilizar para recorrer la lista, de manera análoga a los iteradores de 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 */ 
} 

No es un C++ iterador, pero espero que esto da una idea de una forma de acercarse esto en C.

Answer 4

Los apuntadores pueden cumplir esta función. container.begin() es fácil, y container.end() no requiere mucho trabajo.

Considere

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

Para otros envases como listas, puede utilizar NULL como fin. Lo mismo para árboles, pero la función next necesita mantener el estado. (o el iterador es un puntero a una estructura con estado actualizado mediante llamadas al next(it)).

Answer 5

Encontré un proyecto de código abierto que es la implementación de STL en lenguaje C.

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

Answer 6

Esto es lo que ocurrió:

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 es nuestro prefijo proyecto. Solo necesitábamos un diccionario (un mapa de cadena de cadenas) como contenedor.