0

我有以下问题：考虑这个（简化的）结构：

struct Task {
    int priority;
    std::string description;
    // Some other fields
};

现在我想要一组所有的任务并用它做一些工作。因此我有一个相等运算符，它检查每个元素是否相等。

bool isEqual(const Task& lhs, const Task& rhs) {
    return lhs.priority == rhs.priority &&
        lhs.description == rhs.description &&
        // Some other fields
        ;
}

为此，我使用了 std::unordered_set，效果很好。

但是现在我希望这些任务按它们在集合中的优先级（以获得最高优先级的任务）进行排序。显然，这对于 std::unordered_set 是不可能的，所以我尝试了一个带有以下 less 运算符的 std::set：

bool lessTask(const Task& lhs, const Task& rhs) {
    return lhs.priority < rhs.priority;
}

但这意味着通过严格的弱排序，当优先级相等时，两个任务是相等的，这是我不想要的（我想维护我的 isEqual 方法进行相等性检查）。

完成一组任务的最佳方法是什么，我可以非常快速地插入元素并且没有重复条目（由我的 isEqual 函数定义），但能够非常快速地检索具有最高优先级的任务？
我没有绑定到任何特定的 STL 容器，但不想使用任何第三方库（甚至没有提升）。

4

2 回答 2

1

当你把一个元素放到地图上时，你通常需要将类的所有成员添加到less. 否则将无法正常工作。当我必须创建一个包含大约 15 个不同的、不断变化的类的系统时，这是一个巨大的挑战，这也是我真正开始怀念编译时反射的时候。

附带说明一下，您可以使用优先级队列( )代替地图std::make_heap。优先级堆不关心是否相等，它会给你优先级最高的任务。

于 2015-11-03T18:46:48.113 回答
1

先写get_tie：

// auto or decltype(auto)
auto get_tie(const Task& task) {
  return std::tie(lhs.priority, lhs.description, /* some other fields */ );
}

在 C++11 中，您必须使用->decltype尾随返回类型重复主体，或使用宏来避免重复：

#define RETURNS(...) decltype(__VA_ARGS__) { return __VA_ARGS__; }
auto get_tie(const Task& task)->
RETURNS( std::tie(lhs.priority, lhs.description, /* some other fields */ ) )

一旦我们有一个简单的get_tie，你的问题就会消失。

bool isEqual( Task const& lhs, Task const& rhs ) {
  return get_tie(lhs)==get_tie(rhs);
}
bool isLess( Task const& lhs, Task const& rhs ) {
  return get_tie(lhs) < get_tie(rhs);
}

只需使用 . 传递isLess给std::set或构建一个std::vector和std::sort它isLess。

现在，如果您的比较在原始引用上不起作用tie，您可能必须get_tie用更复杂的东西替换。

于 2015-11-03T20:23:34.390 回答