Porting std :: map to C?

Question

Sto eseguendo il porting di un codice C++ in c. Qual è un equivalente valido di std :: map in c? So che non esiste un equivalente in c.

Questo è quello che sto pensando di utilizzare:

in C++:

std::map< uint, sTexture > m_Textures; 

in C:

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

È che fattibile o sto semplificando mappa troppo? Nel caso in cui non hai ottenuto lo scopo è una mappa delle texture.

Answer 1

uthash "un hash di facile utilizzo per le strutture in C".
via: http://en.wikipedia.org/wiki/Hash_table

Answer 2

Non esiste una libreria standard in C che fornisce funzionalità analoghe a una mappa. È necessario implementare la propria funzionalità simile alla mappa utilizzando una forma di contenitore che supporta l'accesso agli elementi tramite le chiavi.

Answer 3

Questa è certamente una possibile implementazione. Potresti considerare come implementerai l'indicizzazione e quale impatto sulle prestazioni avrà. Ad esempio, è possibile che l'elenco intKey sia un elenco ordinato delle chiavi. Cercare una chiave sarebbe O (log N) tempo, ma inserire un nuovo elemento sarebbe O (N).

Si potrebbe implementarlo come un albero (come std :: map), e quindi si avrà O (log N) inserimento e ricerca.

Un'altra alternativa sarebbe implementarla come tabella hash, che avrebbe prestazioni migliori in fase di esecuzione, presupponendo una buona funzione di hash e una matrice spettrale sparsa sufficiente.

Answer 4

uomo dbopen

Fornire NULL come argomento di file e sarà un in-memory unico contenitore per i dati chiave/valore.

Esistono anche varie interfacce di librerie di database Berkeley con funzionalità chiave/valore simili (man dbm, controlla BerkeleyDB da Sleepycat, prova alcune ricerche, ecc.).

Answer 5

È possibile implementarlo come desiderato. Se utilizzi un approccio basato su elenchi collegati, il tuo inserimento sarà O (1) ma il tuo recupero e la cancellazione saranno O (n). Se usi qualcosa di più complesso come un albero rosso-nero, avrai prestazioni medie molto migliori.

Se lo stai implementando, la lista dei collegamenti è probabilmente la più semplice, altrimenti l'accesso migliore ad un albero rosso-nero o ad altro tipo con licenza appropriata da Internet sarebbe l'opzione migliore. Non è consigliabile implementare il tuo albero rosso-nero ... L'ho fatto e preferirei non farlo di nuovo.

E per rispondere a una domanda che non hai chiesto: forse dovresti riesaminare se il porting to C di C++ offre davvero tutti i vantaggi che desideri. Certamente ci sono situazioni in cui potrebbe essere necessario, ma non ce ne sono molti.

Answer 6

Molte implementazioni C supportano tsearch (3) o hsearch (3). tsearch (3) è un albero binario e puoi fornire un callback di confronto. Penso che sia tanto vicino quanto stai per arrivare a una std :: map.

Ecco qualche esempio di codice 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

Perché non basta avvolgere un'interfaccia C intorno std::map? Vale a dire scrivere un paio di C++ funzioni nel loro modulo:

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" 

e quindi collegare nella vostra C app.

Answer 8

Ho provato attuazione di una mappa in C, esso si basa sulla void *

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

È in corso di lavorazione, ma la mappa è completa.

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

Si è scritto sulla base di Red Tree nero.