c++ - 没有严格弱排序的有序集合

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 是不可能的，所以我尝试了一个带有以下 less 运算符的 std::set:

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

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

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

Answer 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。