将std :: map移植到C？

Question

我正在将一些c ++代码移植到c。什么是c中std :: map的可行等价物？我知道c中没有等价物。

这就是我想要使用的：

在c ++中：

std::map< uint, sTexture > m_Textures;

在c：

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

这是可行的还是我过分简化地图？万一你没有达到目的，它的纹理贴图。

Answer 1

许多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;
}

Answer 2

你为什么不在std::map周围包装一个C接口？即在自己的模块中编写一些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应用程序。

Answer 3

这当然是一种可能的实施方式。您可能想要考虑如何实现索引以及将产生的性能影响。例如，您可以将intKey列表作为键的排序列表。查找密钥将是O（log N）时间，但插入新项目将是O（N）。

您可以将其实现为树（如std :: map），然后您将进行O（log N）插入和查找。

另一个替代方案是将其实现为哈希表，假设良好的哈希函数和足够稀疏的intKey数组，它将具有更好的运行时性能。

Answer 4

您可以选择实施它。如果使用链表方法，则插入将为O（1），但您的检索和删除将为O（n）。如果你使用像红黑树这样更复杂的东西，你的平均表现会更好。

如果您自己实现链接列表可能是最简单的，否则从互联网上获取一些适当许可的红黑或其他类型的树将是最佳选择。不推荐实施自己的红黑树...我已经这样做了，不想再这样做了。

并回答一个你没有问过的问题：也许你应该重新审视从C ++移植到C是否真的能提供你想要的所有好处。当然有些情况可能是必要的，但并不多。

Answer 5

我试过在C中实现一个地图，它是基于void *

https://github.com/davinash/cstl

它正在进行中，但地图已完成。

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

它是基于红黑树写的。

Answer 6

C中没有标准库提供类似于地图的功能。您需要使用支持通过键访问元素的某种形式的容器来实现您自己的类似地图的功能。

Answer 7

男人dbopen

提供NULL作为文件参数，它将是键内/值数据的仅内存容器。

还有各种具有类似键/值功能的Berkeley数据库库接口（man dbm，从Sleepycat查看BerkeleyDB，尝试一些搜索等）。