从C++下去到 C: std::map 的替代品？

Question

我正在寻找 std::map 的简约替代方案，它将进入 Windows 内核驱动程序，因此它应该相当快..预计它会容纳相对较小的数量（工作集中约为 200）键和大量的插入件。

寻找可以降低关键搜索成本的解决方案。

Answer 1

已经为你做好了。

请参阅 RtlXxxGenericTable 和 RtlXxxGenericTableAvl 调用。

• RtlInitializeElementGenericTable
• RtlDeleteElementGenericTable
• RtlEnumerateGenericTable
• RtlEnumerateGenericTableWithoutSplaying
• RtlGetElementGenericTable
• RtlInsertElementGenericTable
• RtlLookupElementGenericTable

• RtlNumberGenericTableElements

• RtlInitializeElementGenericTableAvl

• RtlDeleteElementGenericTableAvl
• RtlEnumerateGenericTableAvl
• RtlGetElementGenericTableAvl
• RtlInitializeGenericTable
• RtlInsertElementGenericTableAvl
• RtlLookupElementGenericTableAvl
• RtlNumberGenericTableElementsAvl

Answer 2

如果键的数量非常很小，例如10个左右，也许您可​​以只进行线性搜索。如果您注意将键空间压缩在内存中以最大限度地提高缓存命中率，那么它会非常快，并且在内存分配等方面的开销非常低。

Answer 3

过去，对于少于几千个对象的映射，我发现创建一个按键值排序的 std::vector，然后使用二分搜索进行搜索比使用 std::map 快得多。

Answer 4

您也可以用 C 实现 std::map 语义。只是它不会是模板。

这是开始：

struct KeyValuePair
{
   KeyType key;
   ValueType value;
};

struct Map
{
   KeyValuePair *list; //it can be linkedlist as well
};

//these are the interfaces which operate on map
void Insert(Map * map, KeyType key, ValueType value);
void Update(Map * map, KeyType key, ValueType value);
int Find(Map * map, KeyType key, ValueType *outValue);

//Implement Get in terms of Find
ValueType Get(Map * map, KeyType key)
{
     ValueType value;
     Find(map, key, &value);
     return value;
}

Answer 5

我相信STL地图实现是一棵红黑树

http://en.wikipedia.org/ wiki/Map_%28C%2B%2B%29

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Answer 6

在 C 中，您需要两个伴随数组：一个用于键，另一个用于值。如果您可以封装这两者，以便用户可以坚持使用地图语义，那将会有所帮助。

Answer 7

如果您需要用 C 语言实现字典的简单实现，那么有一天用 C 语言实现字典会更有趣……但我们并不总是有时间这样做。

所以你可以尝试看看 iniparser module one，它是一个可在内核中使用的小字典和/或嵌入式世界。