从C++降级到C：std::map的替代方案是什么？

Question

从C++降级到C：std::map的替代方案是什么？

c++cstdmapwdk

7

我正在寻找一种替代std::map<long, int>的极简方案，它将用于Windows内核驱动程序，因此应该非常快速。它预计将保存相对较小（工作集中的约200个）的键和大量插入操作。

我正在寻找可以减少键搜索成本的解决方案。

- kagali-san

如果你感到大胆，你可以实现自己的哈希表 - 如果它有非常特定的用途，你可以使它非常高效并且尽可能地精简。 - RageD

1

这意味着大部分键值都是不变的，但是有许多使用相同键的插入操作会频繁改变值？ - user395760

3

你已经证明了 std::map 太慢了吗？ - AJG85

我会选择AVL树，但我会留给其他人为您提供一个适用于Windows的链接来回答。 - Per Johansson

2

@AJG85：STL 代码可能会引发异常，他说他想把这段代码放在驱动程序中，所以最好不要使用STL（如果他理智的话）。 - James

显示剩余2条评论

7个回答

3

你也可以在 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;
}

- Nawaz

3

如果键的数量非常少，例如只有10个或更少，也许您可以仅使用线性搜索来查找。如果您注意保持键空间在内存中压缩以最大化缓存命中率，则速度可能会很快，并且在内存分配方面具有非常低的开销。

- unwind

3

如果你将键保持有序，就可以进行二分查找而无需特殊的数据结构。插入可能会稍微费些时间（但实际上并不是很费），但查找速度快且存储高效。 - Kerrek SB

如果节点被间隔开，插入操作的时间复杂度可以接近O(log(n))，只要树保持至少半满状态，这对查找操作几乎没有影响。 - Mooing Duck

3

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

- Goz

如果您为地图使用更快的分配器，则情况就不是这样。GCC（__gnu_cxx :: pool_allocator）和MSVC（stdext :: allocator_variable_size）都带有专为此目的设计的分配器。但我不明白何时使用MSVC的哪个分配器，我得找时间测试一下。 - Mooing Duck

2

STL中的map实现是红黑树。你可以参考以下链接了解更多信息：http://en.wikipedia.org/wiki/Map_%28C%2B%2B%29和http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree。

- Bob Yoplait

如果你知道节点数量的上限，静态分配它们并拥有一个空闲节点堆栈，而不是每次插入时都使用malloc()函数会更好。对于树形结构的操作，加1！ - Brian McFarland

@Brian：树结构对于内核模块来说是一个可怕的结构（有很多指针）。在内核模式下，您应该优先选择固定大小的结构（或者只有非常少的移动部分）。虽然您可以使用数组实现平衡树。 - Martin York

请解释一下。在C语言中，数组只不过是指针的语法糖而已。关于固定大小，这就是为什么我建议静态分配一个节点池的原因。 - Brian McFarland

@Brian：数组会衰变成指针，但它们并不相同。 - Martin York

1

在C语言中，您需要两个伴随数组：一个用于键，另一个用于值。如果您能封装这两个数组，让用户可以遵循映射语义，那将会很有帮助。

- duffymo

2

我会选择一个由 'struct {long Key, int value}' 组成的数组。 - Martin York

1

如果你需要在 C 语言中实现一个简单的字典，那么有一天用 C 语言实现一个字典会更有趣……但我们并不总有时间去做。

所以你可以尝试看看 iniparser 模块，它是一个适用于内核和/或嵌入式世界的小型字典。

- Cédric Julien

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mheyman · Accepted Answer

这些已经为您准备好了。

请查看RtlXxxGenericTable和RtlXxxGenericTableAvl调用。

RtlInitializeElementGenericTable
RtlDeleteElementGenericTable
RtlEnumerateGenericTable
RtlEnumerateGenericTableWithoutSplaying
RtlGetElementGenericTable
RtlInsertElementGenericTable
RtlLookupElementGenericTable
RtlNumberGenericTableElements
RtlInitializeElementGenericTableAvl
RtlDeleteElementGenericTableAvl
RtlEnumerateGenericTableAvl
RtlGetElementGenericTableAvl
RtlInitializeGenericTable
RtlInsertElementGenericTableAvl
RtlLookupElementGenericTableAvl
RtlNumberGenericTableElementsAvl