c++ - 如何在成对集合上使用 lower_bound()？

Question

我给了一个std::set<std::pair<int,int>>和一个整数 x ，我必须找到第一个元素大于或等于给定整数 x 的第一对的迭代器.

我了解到如果s是 set<pair<int, int>>和 {x, y}是一对然后我可以使用 s.lower_bound({x, y}) .但是，就我而言，我只需要关心第一个元素 x .所以，我的问题是如何使用 lower_bound在 set<pair<int, int>>当我只关心第一个元素时？

Answer 1

核心问题是你的std::set实例已经排序，但默认为 std::pair operator< .您不能直观地使用成员函数 std::set::lower_bound ，因为它使用了其类类型的比较函数。你不能使用 std::lower_bound自定义谓词也不是，因为这假定一个排序范围 - 但是根据给定谓词排序，事实并非如此。

但是对于这种特定情况有一个解决方法。请注意，对于 x 的每个值在集合中，y 的最小关联值是 int 类型的最小值.作为 std::pair 的比较运算符instances 进行成员比较，您可以将其组合为:

#include <set>
#include <limits>

const std::set<std::pair<int,int>> s{
   {42, 0}, {42, 1}, {43, 0}, {43, 1}
};

const auto entry = s.lower_bound({43, std::numeric_limits<int>::min()});

这将始终在子集中找到与 std::pair::first 的给定值相对应的第一个 或最小 所需条目数据成员。只有第一个值很重要，因为第二个值立即不小于 std::numeric_limits<int>::min() ，这就是lower_bound正在寻找。

如果您多次需要此功能，可能值得将其放入自己的辅助函数(模板)中，例如

template <class T>
auto lower_bound_first(const std::set<std::pair<T, T>>& s, T first)
{
   static constexpr T min = std::numeric_limits<T>::min();

   return s.lower_bound({first, min});
}

你可以调用它

const auto entry = lower_bound_first(s, 43);

对于 std::numeric_limits 的任何基础值类型特化是可用的。