Портирование std :: map на C? - PullRequest
Новая
       45

Портирование std :: map на C?

20 голосов
/ 15 марта 2009

Я портирую код на c ++ на c. Что является жизнеспособным эквивалентом std :: map в c? Я знаю, что нет эквивалента в с.

Вот о чем я думаю:

В c ++: 

std::map< uint, sTexture > m_Textures;

В к: 

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

Это жизнеспособно или я слишком упрощаю карту? На всякий случай, если вы не поняли цель, это Карта текстуры.

Ответы [ 7 ]

24 голосов
/ 15 марта 2009

Многие реализации 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;
}
16 голосов
/ 01 октября 2010

Почему бы вам просто не обернуть интерфейс C вокруг std::map? Т.е. написать несколько функций C ++ в своем собственном модуле: 

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.

5 голосов
/ 15 марта 2009

Это, безусловно, одна из возможных реализаций. Возможно, вы захотите подумать о том, как реализовать индексацию и какое влияние это окажет на производительность. Например, список intKey может быть отсортированным списком ключей. Поиск ключа был бы O (log N) времени, но вставка нового элемента будет O (N).

Вы можете реализовать его в виде дерева (например, std :: map), и тогда у вас будет O (log N) вставка и поиск.

Другой альтернативой может быть реализация ее в виде хеш-таблицы, которая будет иметь лучшую производительность во время выполнения при условии хорошей хеш-функции и достаточно разреженного массива intKey.

3 голосов
/ 12 апреля 2011

Я пытался реализовать карту в C, она основана на void *

https://github.com/davinash/cstl

Идет работа, но карта завершена.

https://github.com/davinash/cstl/blob/master/src/c_map.c

Написано на основе Красного черного дерева.

3 голосов
/ 15 марта 2009

Вы можете реализовать его по своему усмотрению. Если вы используете подход со связанным списком, то ваша вставка будет O (1), а поиск и удаление будут O (n). Если вы используете что-то более сложное, например, красно-черное дерево, у вас будет гораздо лучшая средняя производительность.

Если вы реализуете его самостоятельно, то, вероятно, самый простой - это связанный список, в противном случае лучшим вариантом будет получение из Интернета соответствующего лицензированного красно-черного или другого типа дерева. Реализация собственного красно-черного дерева не рекомендуется ... Я сделал это и предпочел бы не делать это снова.

И чтобы ответить на вопрос, который вы не задавали: возможно, вам следует еще раз проверить, действительно ли перенос на C из C ++ дает все те преимущества, которые вы хотели. Конечно, бывают ситуации, когда это может быть необходимо, но таких не так много.

0 голосов
/ 15 марта 2009

человек дбопен

В качестве аргумента файла укажите NULL, и это будет контейнер только для оперативной памяти для данных ключ / значение.

Существуют также различные интерфейсы библиотек баз данных Berkeley с аналогичной функциональностью ключ / значение (man dbm, посмотрите BerkeleyDB из Sleepycat, попробуйте выполнить некоторые операции поиска и т. Д.).

0 голосов
/ 15 марта 2009

Нет стандартной библиотеки в C, которая обеспечивает функциональность, аналогичную карте. Вам нужно будет реализовать свою собственную функциональность, подобную карте, используя контейнер в некоторой форме, который поддерживает доступ к элементам через ключи.

...