c++ - 使用多组件键进行快速部分匹配

Question

我有一大堆多组件键，由定义了比较运算符的 poi 数据类型:

typedef boost::tuple<int, char, unsigned long> Key;

我想将这些键与固定的设置模式进行匹配，它由相同的组件组成，但特别是pattern 一些组件可以省略:

typedef boost::tuple<
    boost::optional<int>
    , boost::optional<char>
    , boost::optional<unsigned long> > Pattern;

boost::optional with value unset 表示星号，“匹配一切”:

Key(1, 2, 3) match Pattern(1, 2, *)
Key(1, 2, 3) match Pattern(*, 2, 3)

而且我想比 O(N) 更快地执行匹配，其中N为模式数量。

我已经开始为模式自定义比较运算符 1将它们存储在排序的 vector 中。 Operator1 只是排序其他一切之后的星号。然后执行查询带有自定义比较运算符 2 的 std::lower_bound。Operator2 在比较过程中省略了未设置的关键组件。但我想我无法摆脱单一排序的 vector 因为如果第二个组件是 * 而我忽略了它不保证第三方组件的“切片”已排序我通过 std::lower_bound 得到了一些有用的东西。

Answer 1

按某种顺序对键进行排序。为每个组件建立索引，保持相同的排序顺序。

使用索引为每个组件查找下一个项目。如果索引指向相同的项目，则您有一个匹配项。如果没有选择指向最小项目的组件(按排序顺序)并跳过，直到您至少到达最大项目(std::lower_bound 会这样做)。

这与相交排序列表的算法相同。

速度取决于数据的密度。如果你搜索 (*, *, true) 并且 95% 的数据匹配你将是 O(N)。如果数据足够稀疏，这可能会非常快。