Как мне (C ++ STL) binary_search для абстрактных классов? - PullRequest
Новая
       12

Как мне (C ++ STL) binary_search для абстрактных классов?

1 голос
/ 30 апреля 2011

Можно использовать алгоритмы двоичного поиска STL (binary_search, upper_bound, lower_bound) для поиска вектора базовых указателей для производного объекта, как показано ниже. Поскольку Base является абстрактным (защищенный конструктор), необходимо создать экземпляр производного объекта для функций поиска, что немного уродливо.

Я хочу найти вектор для первого Производного выше заданного времени. Могу ли я сделать это без произвольного выбора и создания одного из моих многих унаследованных классов? 

#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

Ответы [ 3 ]

3 голосов
/ 30 апреля 2011

Цель сравнения не обязательно должна быть того же типа, что и содержимое контейнера, она просто должна быть чем-то, что вы можете сравнить с контейнером: 

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

A 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 голос
/ 30 апреля 2011

Вы можете, в некотором смысле, используя статический метод: 

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 была абстрактной в первую очередь .Точно так же вы бы сделали конструктор общедоступным.

1 голос
/ 30 апреля 2011

Вы можете передать нулевой указатель, и ваша функция сравнения может игнорировать его и проверять другой объект только на предмет определенного атрибута.

...