如何在 std::set 中查找具有特定字段值的对象?

2022-01-07 00:00:00 set find c++ stl

我调用一个返回 std::set 的方法；const& 其中 T 是类类型.我想要实现的是检查该集合是否包含类型为 T 的对象，该对象具有自动化测试中断言的特定字段值.应该对多个对象进行此检查.

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.

这是一个简单的例子:假设类型 T 是 Car 所以一个例子 set 包含一堆汽车.现在我想在该集合中找到具有特定颜色和特定门数和特定最高速度的汽车.如果找到那辆汽车，则第一个断言为真，应找到具有其他字段值的下一辆汽车.

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.

我不允许更改 T 的实现.使用Boost就可以了.

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

你会怎么做?

推荐答案

这取决于T的实现.让我们继续使用 Car 类的示例.假设这个类看起来像这样:

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

operator< 应根据所有属性对 Car 的实例进行排序，以便搜索所有属性.否则你会得到错误的结果.

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.

所以基本上，您可以仅使用这些属性来构建汽车实例.在这种情况下，您可以使用 std::set::find 并提供具有您要查找的属性的 Car 临时实例:

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

如果您想搜索 Car 的实例，仅指定其属性的一个子集，就像所有绿色汽车一样，您可以使用带有自定义的 std::find_if谓词:

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
}

请注意，第二个解决方案具有线性复杂性，因为它不能依赖于您使用的谓词可能存在或不存在的任何排序.然而，第一个解决方案具有对数复杂性，因为它可以从 std::set 的顺序中受益.

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.

如果，正如@Betas 对您的问题的评论所建议的那样，您想在运行时组合谓词，则必须编写一些辅助类来组合不同的谓词.

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.

相关文章