title: How do I (C++ STL) binary_search for Abstract classes?
body: <p>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.</p>
  
  <p>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?</p>
  
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;stdio.h&gt;
  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-&gt;time &lt; b-&gt;time; }
  };
  
  int main()
  {
    vector&lt;Base*&gt; v;
    for(int i=0; i&lt;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-&gt;print();
  }
  </code></pre>
  
  <p>The program prints:
  lower bound for time=3.5:
  Derived: data=4, time=4.4</p>