我可以使用STL进行这种二进制搜索吗？ [英] can I do this binary search using the STL?

问题描述

我试图重构一些不使用STL的代码，使用它提供的通用算法。
我有一个这样的结构：

I am trying to refactor some code that doesn't use the STL to use the generic algorithms it provide. I have a struct like this :

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 。

there is then a function that was coded that takes A, n and an integer k, whose purpose is to give me pointers to to the first and the last element of the array that have their i member equal to k.

这是通过二进制搜索的方式实现的。我正在考虑使用 std :: equal_range 。问题是，它需要一个类型A的对象工作，它强迫我引入一个虚拟A对象与它的 i 成员等于 k 。

This is implemented by hand in terms of binary search. I was thinking about using std::equal_range. The problem is that it requires an object of type A to work, and it forces me to introduce a "dummy" A object with it's i member equal to k.

有没有办法使用STL，而不必引入一个虚拟对象？
感谢

Is there a way to do this using the STL, without having to introduce a "dummy" object? thanks

推荐答案

如果您的范围根据 A :: i ，这是一个简单的自定义比较器，但请注意，比较器必须能够比较两种方式：

Provided your range is sorted according to the value of A::i, this is trivially done with a custom comparator, but note that the comparator must be able compare both ways:

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 的元素。

Now the range [p.first, p.second) contains the elements with A::i equal to 5.

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

The linked page contains more or less exactly this example.

这篇关于我可以使用STL进行这种二进制搜索吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！