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

Можно использовать алгоритмы двоичного поиска 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


c++ abstract stl binary-search
person reasgt    schedule 29.04.2011    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

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

Пример 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
person Ben Jackson    schedule 30.04.2011
comment
-1: Это не работает. В этом конкретном примере 1.5 будет просто преобразован в int в качестве аргумента lower_bound. В более сложном примере он просто не компилируется. - person Oliver Charlesworth; 30.04.2011
comment
Я предлагаю вам составить более сложный пример или объяснить, насколько он должен быть сложнее ... - person Ben Jackson; 30.04.2011
comment
@Ben: А теперь попробуйте это с upper_bound или binary_search, или с пользовательской функцией / функтором компаратора ... - person Oliver Charlesworth; 30.04.2011
comment
@Ben: Интересно. Я не думал, что это будет компилироваться (хотя я считаю, что он компилируется только с использованием конкретной реализации lower_bound и т. Д.). Хорошо, последний вопрос перед тем, как я отменю свой отрицательный голос: binary_search с настраиваемым компаратором? - person Oliver Charlesworth; 30.04.2011
comment
@Oli: Я предполагал, что вы спросите, так что я уже работал над этим. Обратите внимание, что в классе сравнения не было бы необходимости, если бы я реализовал автономные operator<(double, A) и operator<(A, double - person Ben Jackson; 30.04.2011
comment
@Ben: Тогда я исправлюсь! Я собираюсь поменять свой -1 на +1. Все эти эксперименты, вероятно, можно было бы свести в один пример, хотя для ясности ... - person Oliver Charlesworth; 30.04.2011
comment
@Ben: Даже в случае, скажем, lower_bound, я думаю, было бы безопаснее определить обе перестановки компаратора. Технически реализация STL может выбирать для сравнения в любом направлении. - person Oliver Charlesworth; 30.04.2011
comment
@Ben: И на самом деле, я думаю, что для случая OP функтор является обязательным, потому что оба типа будут примитивами, для которых нельзя объявлять перегрузки операторов. - person Oliver Charlesworth; 30.04.2011
comment
Мне еще предстоит проработать ваши примеры, но небольшое замечание: мне не нравится перегрузка оператора ‹, даже если он работает. Мой конкретный базовый класс имеет несколько членов с плавающей запятой, и без имени функции было бы неоднозначно, какие поля сравниваются с оператором ‹(double, Base). Я бы предпочел использовать функтор, который я могу назвать BaseTimeComparator. - person reasgt; 30.04.2011
comment
@Ben: Вы правы насчет моего недоразумения и решения - я по какой-то причине предположил, что алгоритм выполняет сравнения между членами контейнера, что, конечно же, нонсенс. Спасибо за помощь и обсуждение, Оли и Бен. - person reasgt; 30.04.2011

arrow_upward
1
arrow_downward

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

person Benjamin Lindley    schedule 29.04.2011
comment
+1: Мрачно! Но я полагаю, это сработает. Функтору придется каждый раз проверять, какой из его аргументов был NULL, и соответственно менять логику. - person Oliver Charlesworth; 30.04.2011

arrow_upward
1
arrow_downward

В каком-то смысле вы могли бы, используя статический метод:

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

person Zilchonum    schedule 29.04.2011
comment
Да, это действительно противоречит цели. - person Oliver Charlesworth; 30.04.2011