首页 文章

我如何（C STL）抽象类的binary_search？

提问于
浏览 次
1

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

我想在给定时间内搜索第一个Derived的向量 . 我是否可以在不随意挑选和实例化我的许多继承类之一的情况下执行此操作？

#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\n",data,time); 
  }
};

class Derived : public Base {
public:
  Derived(double t, int d) : Base(t,d) {}
  virtual void print() { 
    printf("Derived: data=%d, time=%.1f\n",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:\n");
  pLow->print();
}

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

c++ stl abstract binary-search

3 回答

  • 1

    比较的目标不必与容器的内容类型相同，只需要与容器进行比较即可：

    #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 .

    下面的评论也是错误的，因为这个更复杂的例子表明：

    #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 ）：

    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 示例提供了与多态性的比较：

    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
    回复于
  • 1

    您可以传递一个空指针，并设计您的比较函数忽略它，并仅测试另一个对象的特定属性 .

    回复于
  • 3

    在某种程度上，您可以使用静态方法：

    class Base {
...
public:
  static Base *newSearchInstance(double t, int d) {return new Base(t,d);};
...
};

    并在对LowerBound的调用中：

    Base* pLow = *(lower_bound(v.begin(),v.end(),
                         Base::newSearchInstance(3.5,0), //<------
                         BaseTimeComp()));

    这意味着您不必了解任何派生类，但是获取Base类的实例会首先破坏Base的抽象目的 . 你也可以将构造函数公开 .

    回复于

相关问题