c++ - 我可以使用 STL 进行二分查找吗？

Question

我正在尝试重构一些不使用STL的代码以使用它提供的通用算法。 我有一个这样的结构:

struct A {
int i;
//other stuff...
};
// ...
A* array; // array of A objects, sorted by A::i member
int n = ...; // array size

然后有一个函数被编码为 A , n和一个整数 k ，其目的是为我提供指向数组中第一个和最后一个元素的指针，这些元素的 i成员等于 k .

这是通过二分查找手动实现的。我正在考虑使用 std::equal_range 。问题是它需要 A 类型的对象才能工作，并且它迫使我引入一个“虚拟”A 对象，其值为 i成员等于 k .

有没有办法使用 STL 来做到这一点，而不必引入“虚拟”对象？ 谢谢

Answer 1

如果您的范围是根据 A::i 的值排序的，则可以使用 custom comparator 轻松完成此操作。 ，但请注意，比较器必须能够比较两种方式:

struct AComp
{
    bool operator()(int n, A const & a) const { return n < a.i; }
    bool operator()(A const & a, int n) const { return a.i < n; }
};

auto p = std::equal_range(array, array + n, 5, AComp());

现在范围[p.first, p.second)包含A::i等于5的元素。

链接页面或多或少包含此示例。