将 std::map 移植到 C？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/647054/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Porting std::map to C?
提问by kthakore
I am porting some c++ code to c. What is a viable equivalent of std::map in c? I know there is no equivalent in c.
我正在将一些 c++ 代码移植到 c。c 中 std::map 的可行等价物是什么？我知道在 c 中没有等价物。
This is what I am thinking of using:
这就是我正在考虑使用的：
In c++:
在 C++ 中：
std::map< uint, sTexture > m_Textures;
In c:
在 c:
typedef struct
{
uint* intKey;
sTexture* textureValue;
} sTMTextureMap;
Is that viable or am I simplifying map too much? Just in case you did not get the purpose its a Texture Map.
这是可行的还是我过于简化地图？以防万一你没有得到纹理贴图的目的。
回答by matt_h
Many C implementations support tsearch(3) or hsearch(3). tsearch(3) is a binary tree and you can provide a comparator callback. I think that's about as close as you're going to get to a std::map.
许多 C 实现支持 tsearch(3) 或 hsearch(3)。tsearch(3) 是一个二叉树，你可以提供一个比较器回调。我认为这与您将要获得的 std::map 差不多。
Here's some c99 example code
这是一些 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;
}
回答by ehren
Why don't you just wrap a C interface around std::map? Ie write a few C++ functions in their own module:
你为什么不只包装一个 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"
And then link into your C app.
然后链接到您的 C 应用程序。
回答by Mr Fooz
That is certainly one possible implementation. You might want to consider how you'll implement the indexing and what performance impact that will have. For example, you could have the intKey list be a sorted list of the keys. Looking up a key would be O(log N) time, but inserting a new item would be O(N).
这当然是一种可能的实现方式。您可能需要考虑如何实施索引以及这会对性能产生什么影响。例如，您可以让 intKey 列表成为键的排序列表。查找一个键是 O(log N) 时间，但插入一个新项目将是 O(N)。
You could implement it as a tree (like std::map), and then you'd have O(log N) insertion and lookup.
您可以将它实现为一棵树（如 std::map），然后您将进行 O(log N) 插入和查找。
Another alternative would be to implement it as a hash table, which would have better runtime performance, assuming a good hash function and a sparse enough intKey array.
另一种替代方法是将其实现为一个哈希表，假设一个好的哈希函数和一个足够稀疏的 intKey 数组，它会有更好的运行时性能。
回答by Avinash
I have tried implementing a map in C, it is based on void *
我曾尝试在 C 中实现地图，它基于 void *
https://github.com/davinash/cstl
https://github.com/davinash/cstl
It is work in progress, but map is complete.
它正在进行中，但地图已完成。
https://github.com/davinash/cstl/blob/master/src/c_map.c
https://github.com/davinash/cstl/blob/master/src/c_map.c
It is written based on Red Black Tree.
它是基于红黑树编写的。
回答by Dan Olson
You can implement it however you choose. If you use a linked-list approach your insertion will be O(1) but your retrieval and deletion will be O(n). If you use something more complex like a red-black tree you'll have much better average performance.
您可以根据自己的选择实施它。如果您使用链表方法，您的插入将是 O(1)，但您的检索和删除将是 O(n)。如果你使用更复杂的东西，比如红黑树，你会有更好的平均性能。
If you're implementing it yourself linked-list is probably the easiest, otherwise grabbing some appropriately licensed red-black or other type of tree from the internet would be the best option. Implementing your own red-black tree is not recommended... I've done this and would prefer not to do it again.
如果你自己实现它，链表可能是最简单的，否则从互联网上获取一些适当许可的红黑树或其他类型的树将是最好的选择。不推荐实现你自己的红黑树......我已经这样做了，并且不想再这样做了。
And to answer a question you didn't ask: maybe you should reexamine whether porting to C from C++ really provides all the benefits you wanted. Certainly there are situations where it could be necessary, but there aren't many.
并回答一个你没有问过的问题：也许你应该重新审视从 C++ 移植到 C 是否真的提供了你想要的所有好处。当然，有些情况可能是必要的，但这种情况并不多。
回答by brlcad
man dbopen
人 dbopen
Provide NULL as the file argument and it'll be an in-memory only container for key/value data.
提供 NULL 作为文件参数，它将成为键/值数据的仅内存容器。
There is also various Berkeley database library interfaces with similar key/value functionality (man dbm, check out BerkeleyDB from Sleepycat, try some searches, etc).
还有各种具有类似键/值功能的 Berkeley 数据库库接口（man dbm，从 Sleepycat 查看 BerkeleyDB，尝试一些搜索等）。
回答by Andrew Grant
There is no standard library in C that provides functionality analogous to a map. You will need to implement your own map-like functionality using some form of container that supports accessing elements via keys.
C 中没有提供类似于地图的功能的标准库。您将需要使用某种形式的支持通过键访问元素的容器来实现您自己的类似地图的功能。
