在 O(n) 中搜索 std::map 的部分密钥

Question

我有一个 (C++ 14) 映射

using MyTuple = tuple<A, B, C>;
map<MyTuple, MyData>

其中 MyTuple 有明显的 operator<() 比较第一个 A，然后是 B，然后是 C。

我想O(ln N) 搜索与某个常量(a, b) 匹配的键。显然，如果存在，它们将是连续的。所以基本上我想要

map<MyTuple, MyData> my_map = GetMyData();
tuple<A, B> my_key = make_tuple(a, b);
auto iter = my_map.lower_bound_if([my_key](const MyTuple& key) {
    if (get<0>(my_key) == get<0>(key) &&
        get<1>(my_key) == get<1>(key)) {
        return true;
    }
    return false;
});
while( /* iter.first is still an (a,b) */) {
    // Do something with iter.
    // Increment iter.
}

但是没有函数 map::lower_bound_if，但是 map::find 和 map::lower_bound 占用了完整的 MyTuple。我可以（hackishly）找到一个 C 的值，它比我的数据中的任何值都低，尽管随着时间的推移这很脆弱。我可以自己编写该函数，尽管它可能取决于我当前对 std::map.

的本地实现

我是否错过了一个明显的解决方案？

更新

我接受的解决方案是在比较函数（透明运算符仿函数）中使用部分键数学，这是自 C++14 以来的新功能，我花了比我愿意承认理解的时间更长的时间。 This article was a good mental ice breaker and this SO question一听就很好

基本的见解是考虑一组对象，这些对象按作为对象一部分的某个键排序。例如，排序键为 employee.id 的一组员工。我们希望能够搜索员工或整数 ID。所以我们制作了一个 bool operator()() 的结构，它包含了我们可能想要比较的各种方式。然后重载解析完成剩下的工作。

在我的例子中，这意味着我可以提供使我的代码工作所需的严格总排序，但也可以提供一个比较器，它只强加一个我只用于 lower_bound() 查找的部分排序。因为额外的比较器不提供严格的总排序，所以它不适合，比如说，find()，除非我们的意思是“找到一个”。

顺便说一句，在提出我的问题后我意识到这在某种程度上有点愚蠢。我想要 O(ln n) 查找，但想使用不同的排序函数。这不能保证有效：这取决于我是否提供了一个真正提供排序的排序函数，该排序是严格总排序的子排序。如果我不这样做，它显然会失败。所以这就是为什么没有 O(ln n) 函数 find_if()，因为那只能是线性的。

的确，透明运算符仿函数的技术很聪明，但确实取决于程序员提供的不比子排序更差的技术。

Answer 1

如果您有这样的顺序，当 f(xa, xb) 时 x {xa, xb, xc} 总是 < 而不是 y {ya, yb, yc}（反之 >），这就变得容易了.将其视为“首先按 A 和 B 排序”。

那么您只需要知道您的最大和最小 C 值。

在 lower_bound(a, b, MIN_C) 和 upper_bound(a, b, MAX_C) 之间搜索。或者，如评论中所建议的那样

A map of tuple<A, B> to map of C to MyData? – Vlad Feinstein

会起作用。

Answer 2

在 c++14 中，您可以使用 search on a partial key:

的重载

struct CompareFirstTwo {
    using is_transparent = void;
    bool operator()(const tuple<A, B, C>& lhs, const tuple<A, B, C>& rhs) const ...
    bool operator()(const tuple<A, B>& lhs, const tuple<A, B, C>& rhs) const ...
    bool operator()(const tuple<A, B, C>& lhs, const tuple<A, B>& rhs) const ...
};

在对 equal_range 的调用中使用上面的比较器来忽略元组中的第三个字段。

Answer 3

一种方法是为 C 设置“您喜欢的任何值”，使用 lower_bound，并注意您要查找的值可能在 lower_bound 之前，也可能在之后，所以你可能需要做一些运算符--来找到第一个，就像你使用 operator++ 来找到最后一个一样？提前找到范围的操作数不会改变，但是如果你想遍历它们并动态测试的结束，就会有一个预先的开销。

显然，如果 C 是一个“hacky”值，与最低可能的 C 进行比较，这将很方便，但不是必需的，因为这会使向后搜索更快，但我们已经降低了脆弱性的风险？

另一种选择是制作自己的容器，即地图中的地图。外部地图将由索引，内部地图将由 < C > 索引。

然后您可以添加自己的方法来使用实现全图索引和迭代；并使用现有的方法在索引时 return 内部映射，或者 return 您的迭代器作为 lower_bound 和 upper_bound 的结果，然后可以用作所有的范围。

在 O(n) 中搜索 std::map 的部分密钥

Searching std::map in O(n) for a partial key

c++

stl

c++14

更新