Я переношу некоторый код С++ на c. Что такое жизнеспособный эквивалент std:: map в c? Я знаю, что нет эквивалента в c.
Вот что я думаю об использовании:
В С++:
std::map< uint, sTexture > m_Textures;
В c:
typedef struct
{
uint* intKey;
sTexture* textureValue;
} sTMTextureMap;
Является ли это жизнеспособным или я слишком упрощаю карту? На всякий случай, если вы не достигли цели своей карты текстур.
uthash "простая в использовании хэш-таблица для структур C".
через: http://en.wikipedia.org/wiki/Hash_table
Многие реализации C поддерживают tsearch (3) или hsearch (3). tsearch (3) является двоичным деревом, и вы можете предоставить обратный вызов компаратора. Я думаю, что примерно так же, как вы собираетесь добраться до std:: map.
Вот пример кода 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;
}
Почему вы просто не переносите интерфейс C вокруг std::map? Т.е. написать несколько С++-функций в их собственном модуле:
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"
И затем перейдите в свое приложение C.
Это, безусловно, одна из возможных реализаций. Возможно, вам захочется рассмотреть, как вы будете внедрять индексирование и какое влияние на производительность. Например, у вас может быть список intKey - отсортированный список ключей. Поиск ключа будет O (log N), но вставка нового элемента будет O (N).
Вы можете реализовать его как дерево (например, std:: map), а затем у вас будет O (log N) вставка и поиск.
Другой альтернативой было бы реализовать его как хеш-таблицу, которая имела бы лучшую производительность во время выполнения, предполагая хорошую хеш-функцию и достаточно разреженный массив intKey.
Вы можете реализовать его, как только вы выберете. Если вы используете подход с привязкой, ваша вставка будет O (1), но ваш поиск и удаление будет O (n). Если вы используете что-то более сложное, как красно-черное дерево, вы получите гораздо лучшую среднюю производительность.
Если вы его реализуете, сам связанный список, вероятно, самый простой, в противном случае захват какого-либо подходящего лицензированного красно-черного или другого типа дерева из Интернета будет лучшим вариантом. Реализация собственного красно-черного дерева не рекомендуется... Я сделал это и предпочел бы не делать этого снова.
И чтобы ответить на вопрос, который вы не спросили: возможно, вам стоит пересмотреть, переносит ли портирование на C из С++ все преимущества, которые вы хотели. Конечно, есть ситуации, когда это может быть необходимо, но их немного.
Я попытался реализовать карту в C, она основана на void *
https://github.com/davinash/cstl
Это работа в процессе, но карта завершена.
https://github.com/davinash/cstl/blob/master/src/c_map.c
Написано на основе Red Black Tree.
В C нет стандартной библиотеки, которая обеспечивает функциональность, аналогичную карте. Вам нужно будет реализовать свою собственную функцию, подобную карте, используя ту или иную форму контейнера, которая поддерживает доступ к элементам через ключи.
человек dbopen
Предоставить NULL в качестве аргумента файла, и он будет контейнером только в памяти для данных ключа/значения.
Существуют также различные библиотеки библиотек базы данных Беркли с аналогичной функциональностью key/value (man dbm, выйдите из BerkeleyDB из Sleepycat, попробуйте некоторые поиски и т.д.).