c++ - 类似容器的 C++ multimap 对键的一部分执行搜索

Question

我想将数据存储在某种键（一些位数组）-> 值（整数）映射容器中。Bitarray 最大可以达到 32 字节（并且可能是一个恒定的大小）。

当然，它可以是标准的 std::multimap。

std::multimap my_map;

但我还必须搜索密钥的一部分（几个位置上的 1 或 0 位），而不关心它的其余部分。例如：

插入地图：

• 键 b“1010001”下的值 1，
• 键 b“1010001”下的值 2，
• 键 b“1000001”下的值 3
• 键 b“0000001”下的值 4

然后我应该收到值：

• 1、2、3 和 4 如果我寻找 b"0000001"，
• 1、2 和 3 如果我寻找 b"1000000"，
• 1和2如果我寻找b“1010001”

拥有精确匹配键值的能力也是一件好事。

如何在 boost 支持的 C++ 中以最简单（但仍然有效）的方式实现它？我关心性能（可能有数百万个键）。

Answer 1

最好使用前缀树。您可以轻松地修改实现以满足您只关心密钥的某些部分的需要。此外，搜索时间非常快。

对于您的示例，树的高度为 8，如果键中的当前位为 0，您将探索左子树，如果它是 1，则探索右子树。您可以修改实现以不关心零并通过在您尝试与搜索键中的 0 匹配的每个点进行分支（探索左子树和右子树）返回所有结果。