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

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

Вот что я думаю об использовании:

В С++:

std::map< uint, sTexture > m_Textures;

В c:

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

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

Ответы

Ответ 2

Многие реализации 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;
}

Ответ 3

Почему вы просто не переносите интерфейс 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.

Ответ 4

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

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

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

Ответ 5

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

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

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

Ответ 7

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

Ответ 8

человек dbopen

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

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