Porting std :: map to C?

Question

Estoy portando algún código de C++ a c. ¿Qué es un equivalente viable de std :: map en c? Sé que no hay equivalente en c.

Esto es lo que estoy pensando en usar:

en C++:

std::map< uint, sTexture > m_Textures; 

en C:

typedef struct 
{ 
    uint* intKey; 
    sTexture* textureValue; 
} sTMTextureMap; 

¿Eso es viable o estoy simplificando mapa demasiado? En caso de que no haya obtenido el propósito, es un Mapa de Textura.

Answer 1

uthash "una tabla hash fácil de usar para las estructuras C".
a través de: http://en.wikipedia.org/wiki/Hash_table

Answer 2

No hay una biblioteca estándar en C que proporcione una funcionalidad análoga a un mapa. Deberá implementar su propia funcionalidad tipo mapa utilizando algún tipo de contenedor que admita el acceso a los elementos a través de las claves.

Answer 3

Sin duda es una posible implementación. Es posible que desee considerar cómo implementará la indexación y qué impacto en el rendimiento tendrá. Por ejemplo, puede hacer que la lista intKey sea una lista ordenada de las claves. Buscar una clave sería O (registrar N) tiempo, pero insertar un nuevo elemento sería O (N).

Podrías implementarlo como un árbol (como std :: map), y luego tendrías la inserción O (registro N) y la búsqueda.

Otra alternativa sería implementarlo como una tabla hash, que tendría un mejor rendimiento en tiempo de ejecución, asumiendo una buena función hash y una matriz intKey bastante dispersa.

Answer 4

hombre dbopen

Proporcionar NULL como el argumento de archivo y va a ser una en memoria solamente contenedor de datos clave/valor.

También hay varias interfaces de biblioteca de base de datos Berkeley con una funcionalidad similar de clave/valor (dbm de hombre, echa un vistazo a BerkeleyDB desde Sleepycat, pruebe algunas búsquedas, etc.).

Answer 5

Puede implementarlo como lo desee. Si usa un enfoque de lista enlazada, su inserción será O (1) pero su recuperación y eliminación será O (n). Si usa algo más complejo como un árbol rojo-negro, tendrá un rendimiento promedio mucho mejor.

Si lo está implementando usted mismo, la lista enlazada es probablemente la más fácil, de lo contrario, la mejor opción sería obtener de la red un árbol rojinegro u otro tipo de árbol debidamente autorizado. No se recomienda implementar su propio árbol rojo-negro ... Lo he hecho y preferiría no volver a hacerlo.

Y para responder a una pregunta que no ha preguntado: tal vez debería volver a examinar si la migración a C desde C++ realmente proporciona todos los beneficios que deseaba. Ciertamente hay situaciones en las que podría ser necesario, pero no hay muchas.

Answer 6

Muchas implementaciones C admiten tsearch (3) o hsearch (3). tsearch (3) es un árbol binario y puede proporcionar una devolución de llamada del comparador. Creo que eso es lo más cerca que llegarás a un std :: map.

Aquí hay un código de ejemplo C99

#include <search.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 

typedef struct 
{ 
     int key; 
     char* value; 
} intStrMap; 

int compar(const void *l, const void *r) 
{ 
    const intStrMap *lm = l; 
    const intStrMap *lr = r; 
    return lm->key - lr->key; 
} 

int main(int argc, char **argv) 
{ 
    void *root = 0; 

    intStrMap *a = malloc(sizeof(intStrMap)); 
    a->key = 2; 
    a->value = strdup("two"); 
    tsearch(a, &root, compar); /* insert */ 

    intStrMap *find_a = malloc(sizeof(intStrMap)); 
    find_a->key = 2; 

    void *r = tfind(find_a, &root, compar); /* read */ 
    printf("%s", (*(intStrMap**)r)->value); 

    return 0; 
} 

Answer 7

¿Por qué no acaba de envolver alrededor de una interfaz de C std::map? Es decir, escribir algunas funciones de C++ en su propio módulo:

typedef std::map<int, char*> Map; 

extern "C" { 

void* map_create() { 
    return reinterpret_cast<void*> (new Map); 
} 

void map_put(void* map, int k, char* v) { 
    Map* m = reinterpret_cast<Map*> (map); 
    m->insert(std::pair<int, char*>(k, v)); 
} 

// etc... 

} // extern "C" 

Y luego vincular a su aplicación C.

Answer 8

He intentado implementar un mapa en C, que se basa en void *

http://code.google.com/p/cstl/

Es un trabajo en progreso, pero es un mapa completo.

http://code.google.com/p/cstl/source/browse/src/c_map.c

Escrito está basado en árbol Negro Rojo.