How do I (C++ STL) binary_search for Abstract classes? -


one can use stl binary search algorithms (binary_search, upper_bound, lower_bound) search vector of base pointers derived object, shown below. since base abstract (protected constructor), 1 has instantiate derived object search functions, ugly.

i want search vector first derived above given time. can without arbitrarily picking , instantiating 1 of 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 time=3.5:\n");   plow->print(); } 

the program prints: lower bound time=3.5: derived: data=4, time=4.4

the target of comparison doesn't have same type contents of container, has can compare 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 = *(lower_bound(v.begin(), v.end(), 1.5));  // <<< note: floating point "value"      cout << << endl; } 

your assumption have make kind of base wrong. can define basekey suitable comparisons long explicit (or implied) comparison operator knows do.

the comment below wrong, more complex example demonstrates:

#include <iostream> #include <algorithm> #include <vector>  using namespace std;  struct {     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 = (lower_bound(v.begin(), v.end(), 1.5))->x;      cout << << endl; } 

you can use comparision type explicitly (which helps order of operations problems such might find 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 = (upper_bound(v.begin(), v.end(), 1.5, compareadouble()))->x;      cout << << endl; } 

a binary_search example providing both comparisons 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 

Comments