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

Question

我正在尝试找到一种优雅的方法来完成以下操作：

举个例子，我有以下类：

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

为了保持简单，我选择用int替换SomeType，但假设关系运算符(<、<=、>、>=(对这种类型没有意义。

所以，我想我在问这个问题的时候找到了一个解决方案，有更好的方法吗？

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

注意：如果vec为空，则选择const Foo&意味着findFoo为UB。我会返回std::vector<Foo>::const_iterator，或者返回template <typename ForwardIterator> ForwardIterator findFoo(ForwardIterator, ForwardIterator)以匹配其他搜索算法