c++ - 根据条件和优先级搜索容器中的项目

Question

我正在尝试找到一种优雅的方式来执行以下操作:

假设我有以下类(class):

class Foo {
    public: 
        SomeType bar;
}

foo.bar可以等于以下任何常量:BAR1 , BAR2 , BAR3 , ..., BARN

现在我有了一个包含这些元素的容器:std::vector<Foo> fooVec;我想找到 foo.bar 的第一个元素等于BAR1 ，如果没有，那么我想要 foo.bar 的第一个元素等于BAR2 , 等等。

下面是一个测试算法的示例代码:

#include <iostream>
#include <vector>

class Foo {
private:
    static int id_counter;
public:
    enum class Bar { _1, _2, _3, _4 };

    Bar bar;
    int id;

    Foo(Foo::Bar bar) : bar(bar), id(id_counter++) {}
};
int Foo::id_counter = 0;

const Foo& findFoo(const std::vector<Foo>& vec) {
    // Find first element verifying foo.bar == 1, or first verifying foo.bar == 2, etc...
}

int main() {
    std::vector<Foo> fooVec1({Foo(Foo::Bar::_2),
                              Foo(Foo::Bar::_4),
                              Foo(Foo::Bar::_1),
                              Foo(Foo::Bar::_3)});

    std::vector<Foo> fooVec2({Foo(Foo::Bar::_3),
                              Foo(Foo::Bar::_2),
                              Foo(Foo::Bar::_4),
                              Foo(Foo::Bar::_2)});

    std::cout << findFoo(fooVec1).id << std::endl; //Expected output: 2
    std::cout << findFoo(fooVec2).id << std::endl; //Expected output: 5

    return 0;
}

我选择替换SomeType与 int为简单起见，假设关系运算符( < 、 <= 、 > 、 >= )对这种类型没有意义。

所以，我想我在提出问题时找到了解决方案，有没有更好的方法？

#include <iostream>
#include <vector>
#include <functional>
#include <unordered_map>

class Foo {
private:
    static int id_counter;
public:
    enum class Bar { _1, _2, _3, _4 };

    Bar bar;
    int id;

    Foo(Foo::Bar bar) : bar(bar), id(id_counter++) {}
};
int Foo::id_counter = 0;

struct EnumClassHash {
    template<typename T>
    std::size_t operator()(T t) const {
        return static_cast<std::size_t>(t);
    }
};

const Foo& findFoo(const std::vector<Foo>& vec) {
    std::unordered_map<Foo::Bar, int, EnumClassHash> priority;
    priority[Foo::Bar::_1] = 1;
    priority[Foo::Bar::_2] = 2;
    priority[Foo::Bar::_3] = 3;
    priority[Foo::Bar::_4] = 4;

    std::reference_wrapper<const Foo> bestFoo = vec.front();
    int bestPriority = priority[bestFoo.get().bar];

    for(const Foo& foo : vec) {
        if(priority[foo.bar] < bestPriority) {
            bestFoo = foo;
            bestPriority = priority[foo.bar];
        }
    }

    return bestFoo;
}

int main() {
    std::vector<Foo> fooVec1({Foo(Foo::Bar::_2),
                              Foo(Foo::Bar::_4),
                              Foo(Foo::Bar::_1),
                              Foo(Foo::Bar::_3)});

    std::vector<Foo> fooVec2({Foo(Foo::Bar::_3),
                              Foo(Foo::Bar::_2),
                              Foo(Foo::Bar::_4),
                              Foo(Foo::Bar::_2)});

    std::cout << findFoo(fooVec1).id << std::endl; //Expected output: 2
    std::cout << findFoo(fooVec2).id << std::endl; //Expected output: 5

    return 0;
}

Answer 1

扩展 Slava 的评论:

const Foo& findFoo(const std::vector<Foo>& vec) {
    auto priority_less = [](const Foo & lhs, const Foo & rhs)
    {
        static std::unordered_map<Foo::Bar, int, EnumClassHash> priority {
            { Foo::Bar::_1, 1 },
            { Foo::Bar::_2, 2 },
            { Foo::Bar::_3, 3 },
            { Foo::Bar::_4, 4 },
        };

        return priority[lhs.bar] < priority[rhs.bar];
    };
    return *std::min_element(vec.begin(), vec.end(), priority_less);
}

警告:您选择 const Foo&暗示findFoo如果 vec 是 UB是空的。我会返回 std::vector<Foo>::const_iterator相反，或者 template <typename ForwardIterator> ForwardIterator findFoo(ForwardIterator, ForwardIterator)匹配其他搜索算法