2

我正在尝试重构一些不使用 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 来做到这一点，而不必引入“虚拟”对象？谢谢

4

3 回答 3

4

如果您的范围是根据 的值排序的A::i，这可以通过自定义比较器轻松完成，但请注意比较器必须能够比较两种方式：

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。

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

于 2013-09-11T19:45:07.830 回答
1

通常，您也可以使用std::binary_search()定义的 in<algorithm>进行二分搜索。原型是：

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);

或者：

template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);
于 2013-09-11T19:50:40.113 回答
0

您可以定义一个转换运算符（我猜这更像是一个 hack）

class A
{
    private:
        int i;
    public:
        A(int x) : i(x){}
        operator int(){
            return i;
        }
};

如果这样做了，您不必在结构中定义 operator<。

于 2013-09-11T20:14:14.580 回答