How to find an object with specific field values in a std::set?

Question

I call a method which returns std::set<T> const& where T is a class type. What I'm trying to achieve is to check whether the set contains an object of type T with specific field values for an assertion in a automated test. This check should be done for multiple objects.

Here is a simple example: Let the type T be Car so an example set contains a bunch of cars. Now I want to find a car with a specific color and a specific number of doors and a specific top speed in that set. If that car is found the first assertion is true and the next car with other field values should be found.

I'm not allowed to change the implementation of T. The usage of Boost would be OK.

How would you do that?

Answer 1

You'll want std::find_if, with a predicate function object that checks the properties you're interested in. It might look something like this:

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

In C++0x, you could replace the "FindCar" class with a lambda to make the code a bit shorter.

Answer 2

This depends on the implementation of T. Let's stick with your example of a class Car. Suppose that class looks something like this:

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

The operator< should order instances of Car based on all attributes in order to make searching for all attributes possible. Otherwise you will get incorrect results.

So basically, you can construct an instance of car using just these attributes. In that case, you can use std::set::find and supply a temporary instance of Car with the attributes you are looking for:

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

If you want to search for an instance of Car specifying only a subset of its attributes, like all green cars, you can use std::find_if with a custom predicate:

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
}

Note that the second solution has linear complexity, because it cannot rely on any ordering that may or may not exists for the predicate you use. The first solution however has logarithmic complexity, as it can benefit from the order of an std::set.

If, as suggested by @Betas comment on your question, you want to compose the predicates at runtime, you would have to write some helper-classes to compose different predicates.