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

Question

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();
}

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

Ben Jackson Ben Jackson · Accepted Answer · 2011-04-30T00:07:00

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;
}

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;
}

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

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

3 Answers