Как найти объект с определенными значениями поля в std :: set? - PullRequest
Новая
       26

Как найти объект с определенными значениями поля в std :: set?

6 голосов
/ 12 августа 2011

Я вызываю метод, который возвращает std::set<T> const&, где T - это тип класса. Я пытаюсь добиться того, чтобы проверить, содержит ли набор объект типа T с конкретными значениями поля для утверждения в автоматическом тесте. Эта проверка должна быть выполнена для нескольких объектов.

Вот простой пример: Пусть тип T будет Car, поэтому пример set содержит несколько машин. Теперь я хочу найти автомобиль определенного цвета и с определенным количеством дверей и с определенной максимальной скоростью в этом наборе. Если этот автомобиль найден, первое утверждение верно, и следующий автомобиль с другими значениями поля должен быть найден.

Мне не разрешено изменять реализацию T. Использование Boost будет в порядке.

Как бы вы это сделали?

Ответы [ 5 ]

16 голосов
/ 12 августа 2011

Это зависит от реализации T.Давайте придерживаться вашего примера класса Car.Предположим, что класс выглядит примерно так: 

class Car {
public:
    Car(std::string color, unsigned int number_of_doors,
        unsigned int top_speed);
    // getters for all these attributes
    // implementation of operator< as required for std::set
};

operator< должен упорядочить экземпляры Car на основе всех атрибутов , чтобы сделать поиск всех атрибутов возможным.В противном случае вы получите неверные результаты.

Таким образом, вы можете создать экземпляр автомобиля, используя только эти атрибуты.В этом случае вы можете использовать std::set::find и предоставить временный экземпляр Car с атрибутами, которые вы ищете: 

car_set.find(Car("green", 4, 120));

Если вы хотите найти экземпляр Car, указав толькоподмножество его атрибутов, как и все зеленые автомобили, вы можете использовать std::find_if с пользовательским предикатом: 

struct find_by_color {
    find_by_color(const std::string & color) : color(color) {}
    bool operator()(const Car & car) {
        return car.color == color;
    }
private:
    std::string color;
};

// in your code

std::set<Car>::iterator result = std::find_if(cars.begin(), cars.end(), 
                                              find_by_color("green"));
if(result != cars.end()) {
    // we found something
}
else {
    // no match
}

Обратите внимание, что второе решение имеет линейную сложность, поскольку оно не может полагаться на любой порядок,может не существовать для предиката, который вы используете.Первое решение, однако, имеет логарифмическую сложность, так как оно может выиграть от порядка std::set.

Если, как предлагает @Betas комментарий к вашему вопросу, вы хотите составить предикаты во время выполнения, вы бынужно написать несколько вспомогательных классов для составления разных предикатов.

1 голос
/ 12 августа 2011

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

struct FindCar {
    FindCar(Colour colour, int doors, double top_speed) :
        colour(colour), doors(doors), top_speed(top_speed) {}

    bool operator()(Car const & car) const {
        return car.colour == colour
            && car.doors == doors
            && car.top_speed == top_speed;
    }

    Colour colour;
    int doors;
    double top_speed;
};

std::set<Car> const & cars = get_a_set_of_cars();
std::set<Car>::const_iterator my_car =
    std::find_if(cars.begin(), cars.end(), FindCar(Red, 5, 113));

В C ++ 0x вы можете заменить класс «FindCar» на лямбду, чтобы сделать код немного короче.

1 голос
/ 12 августа 2011

Когда я сталкиваюсь с такими проблемами, я обычно говорю:

  • A std::deque или std::vector автомобилей
  • Для каждого свойства, с которым вы хотите посмотреть, a std::multiset указателей на автомобили, отсортированные по значению свойства.

Я тщательно скрываю эти контейнеры внутри класса, который позволяет мне вставлять автомобили.

Интерфейс запросов может отличаться, нокак правило, вы получаете преимущество multiset::equal_range, std::sort и std::set_intersection.

Если вы хотите красный Volvo независимо от ... автомобиля, вы

  1. извлекаете equal_range все красные машины, давая вам пару итераторов
  2. извлеките на equal_range все автомобили Volvo, давая вам пару итераторов
  3. ...
  4. Сортируйте все этидиапазоны по общему предикату, скажем по адресу указателя
  5. Применить несколько раз set_intersection в std::deque.

Другой способ - сохранить автомобили в перечислении dequeих и выберите тот, который удовлетворяет всем вашим свойствам, используя std::find.Однако это может иметь худшую сложность (это зависит от того, сколько красных машин у вас есть на время)

0 голосов
/ 12 августа 2011

std :: set позволяет вам предоставить собственную функцию сравнения, как в 

template < class Key, class Compare = less<Key>,
       class Allocator = allocator<Key> > class set;

Сравнивайте только те значения, которые вас интересуют, и все будет работать так, как будто объекты с этими значениями = Обратите внимание, что для этого вам, вероятно, понадобится мультимножество.

Это был бы способ сделать это, если вы действительно заботитесь о производительности входа в систему.

0 голосов
/ 12 августа 2011

Вы можете попробовать переопределить оператор <(const T & a, const T & b), чтобы наложить порядок на эти атрибуты, поэтому std :: set: find (const T & x) вернет первое не менее x. </p>

Ej: 

bool operator<(const Car& a, const Car& b)
{
    return a.color<b.color || (a.color==b.color && a.doors<b.doors) || (a.color==b.color && a.doors==b.doors && a.top_speed<b.top_speed);
}

std::set<Car> cars;
Car x;
cars.find(x);
...