在 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 以来的新功能，并且花了我比我愿意承认理解的时间更长的时间。 这篇文章是一个很好的心理破冰者，一旦我理解了这个问题就很好了。

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

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

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

事实上，透明运算符函子的技术很聪明，但确实依赖于程序员提供不比子排序更糟糕的功能。

Answer 1

在 c++14 中，您可以使用重载来搜索部分键：

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来忽略元组中的第三个字段。