我如何（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.

我想搜索向量的第一个在给定时间之上导出。我可以这样做而不用任意选择和实例化我的许多继承类之一？

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\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：
Derived：data = 4，time = 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;
}

A 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屋！