Как использовать STL-карты в C-программировании? [Дубликат]

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

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

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

Выполняется работа, но карта завершена.

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

Это написано на основе Red Black Tree.

man dbopen

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

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

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

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

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

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

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

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

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

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