我如何 (C++ STL) binary_search 抽象类? [英] How do I (C++ STL) binary_search for Abstract classes?

问题描述

可以使用 STL 二进制搜索算法(binary_search、upper_bound、lower_bound)来搜索派生对象的 Base 指针向量，如下所示.由于 Base 是抽象的(受保护的构造函数)，因此必须为搜索函数实例化一个 Derived 对象，这有点难看.

One can use the STL binary search algorithms (binary_search, upper_bound, lower_bound) to search a vector of Base pointers for a derived object, as shown below. Since Base is abstract (protected constructor), one has to instantiate a Derived object for the search functions, which is slightly ugly.

我想在给定时间以上的第一个 Derived 中搜索向量.我可以在不随意选择和实例化我的众多继承类之一的情况下做到这一点吗?

I want to search the vector for the first Derived above a given time. Can I do this without arbitrarily picking and instantiating one of my many inherited classes?

#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;

class Base {
protected:
  Base(double t, int d) : data(d), time(t) {}
public:
  double time;
  int data;
  virtual void print() { 
    printf("Base: data = %d, time = %.1f
",data,time); 
  }
};

class Derived : public Base {
public:
  Derived(double t, int d) : Base(t,d) {}
  virtual void print() { 
    printf("Derived: data=%d, time=%.1f
",data,time);
  }
};

struct BaseTimeComp {
  bool operator()(Base* a, Base* b) { return a->time < b->time; }
};

int main()
{
  vector<Base*> v;
  for(int i=0; i<5; i++) { v.push_back(new Derived(i+0.4,i)); }

  Base* pLow = *(lower_bound(v.begin(),v.end(),
                             new Derived(3.5,0), //NOT "new Base(3.5,0)"
                             BaseTimeComp()));
  printf("lower bound for time=3.5:
");
  pLow->print();
}

程序打印:时间下限=3.5:派生:数据=4，时间=4.4

The program prints: lower bound for time=3.5: Derived: data=4, time=4.4

推荐答案

比较的目标不必与容器内容的类型相同，它只需要您可以比较 到容器:

The target of the comparison doesn't have to be the same type as the contents of the container, it just has to be something you can compare to the container:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    int i = *(lower_bound(v.begin(), v.end(), 1.5));  // <<< NOTE: floating point "value"

    cout << i << endl;
}

您认为必须制作某种Base 的假设是错误的.只要您的显式(或隐式)比较运算符知道要做什么，您就可以定义一个适合您的比较的 BaseKey.

Your assumption that you have to make some kind of Base is wrong. You can define a BaseKey which is suitable for your comparisons as long as your explicit (or implied) comparison operator knows what to do.

下面的评论也是错误的，正如这个更复杂的例子所展示的:

The comment below is also wrong, as this more complex example demonstrates:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct A {
    int x;
    A(int _x) :x(_x) { }

    bool operator < (double d) { return x < d; }
};

int main()
{
    vector<A> v;

    v.push_back(A(1));
    v.push_back(A(2));
    v.push_back(A(3));

    int i = (lower_bound(v.begin(), v.end(), 1.5))->x;

    cout << i << endl;
}

您还可以显式使用比较类型(这有助于解决操作顺序问题，例如您可能会在 upper_bound 中发现的问题):

You can also use a comparision type explicitly (which helps with order of operations problems such as you might find with upper_bound):

class CompareADouble {
public:
    bool operator () (const double d, A& a) { return d < a.x; }
};

int main()
{
    vector<A> v;

    v.push_back(A(1));
    v.push_back(A(2));
    v.push_back(A(3));

    int i = (upper_bound(v.begin(), v.end(), 1.5, CompareADouble()))->x;

    cout << i << endl;
}

一个 binary_search 示例，提供了多态性的两种比较:

A binary_search example providing both comparisons with polymorphism:

class CompareADouble {
public:
    bool operator () (const double d, A& a) { return d < a.x; }
    bool operator () (A& a, const double d) { return a.x < d; }
};

...

    bool exists = binary_search(v.begin(), v.end(), 1.5, CompareADouble());
    cout << exists << endl; // false

    exists = binary_search(v.begin(), v.end(), 1.0, CompareADouble());
    cout << exists << endl; // true because 1.0 < 1 == false && 1 < 1.0 == false

这篇关于我如何 (C++ STL) binary_search 抽象类?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！