25

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

这就是我正在考虑使用的：

在 C++ 中：

std::map< uint, sTexture > m_Textures;

在 c 中：

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

这是可行的还是我过于简化地图？以防万一您没有得到纹理贴图的目的。

4

7 回答 7

34

许多 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;
}
于 2009-03-15T02:18:39.873 回答
18

你为什么不直接包装一个 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 应用程序。

于 2010-10-01T15:19:04.607 回答
5

这当然是一种可能的实现方式。您可能需要考虑如何实现索引以及这将对性能产生什么影响。例如，您可以让 intKey 列表成为键的排序列表。查找一个键需要 O(log N) 时间，但插入一个新项目需要 O(N)。

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

另一种选择是将其实现为哈希表，这将具有更好的运行时性能，假设一个好的哈希函数和一个足够稀疏的 intKey 数组。

于 2009-03-15T01:30:39.800 回答
3

您可以根据自己的选择实施它。如果您使用链表方法，您的插入将是 O(1)，但您的检索和删除将是 O(n)。如果您使用更复杂的东西，例如红黑树，您将获得更好的平均性能。

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

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

于 2009-03-15T02:08:50.910 回答
3

我尝试在 C 中实现地图，它基于 void *

https://github.com/davinash/cstl

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

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

它是基于红黑树编写的。

于 2011-04-12T13:41:01.567 回答
0

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

于 2009-03-15T01:13:49.593 回答
0

人 dbopen

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

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

于 2009-03-15T01:46:49.590 回答