没有严格弱排序的有序集合

Question

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

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 是不可能的，所以我尝试使用 std::set 和以下 less 运算符：

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

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

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

Answer 1

当您将一个元素放入地图时，通常需要将 class 的所有成员添加到 less。否则将无法正常工作。当我不得不创建一个包含大约 15 个不同的不断变化的系统时 classess 包含在地图中，这是一个巨大的挑战，这是我真正开始怀念编译时反射的时候。

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

Answer 2

先写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 尾随 return 类型重复主体，或者使用宏来避免重复：

#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，或者使用 isLess.

构建一个 std::vector 和 std::sort

现在，如果您的比较在原始 tie 参考文献上不起作用，您可能需要用更复杂的东西替换 get_tie。

没有严格弱排序的有序集合

Sorted set without a strict weak ordering

c++

containers

c++11

strict-weak-ordering