C++ multimap like container 对键的一部分执行搜索

Question

我想将数据存储在某种键(一些位数组)->值(整数)映射容器中。位数组最大可达 32 字节(并且可能是一个常量大小)。

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

std::multimap my_map;

但我还必须搜索 key 的一部分(几个位置上的 1 或 0 位)并且不关心其余部分。例如:

插入 map :

• 键 b"1010001"下的值 1,
• 键b下的值2"1010001",
• 键 b"1000001"下的值 3
• 在键 b"0000001"下的值 4

然后我应该收到值:

• 1、2、3 和 4 如果我寻找 b"0000001",
• 如果我寻找 b"1000000"，则为 1、2 和 3，
• 1，如果我寻找 b"1010001"则为 2

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

我怎样才能在 boost 支持的 C++ 中以最简单(但仍然有效)的方式实现它？我关心性能(可能有多达数百万个键)。

Answer 1

你最好使用 prefix tree .您可以轻松修改实现以满足您只关心 key 的某些部分的需要。此外，搜索时间非常快。

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