c++ - 在 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 .我可以(笨拙地)找到 C 的值这比我的数据中的任何数据都低，尽管随着时间的推移这很脆弱。我可以自己编写该函数，尽管它可能取决于我当前对 std::map 的本地实现。 .

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

更新

我接受的解决方案是在比较函数(透明运算符仿函数)中使用部分键数学，这是自 C++14 以来的新功能，我花了比我愿意承认理解的时间更长的时间。 This article是一个很好的精神破冰者和this SO question很好，一旦我明白了。

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

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

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

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

Answer 1

在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 时使用上面的比较器来忽略元组中的第三个字段。