排序集没有严格的弱排序 [英] Sorted set without a strict weak ordering

问题描述

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

  struct任务{
 int优先级； 
 std :: string说明； 
 //其他一些字段
}; 
  

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

  bool isEqual（const Task& lhs，const Task& rhs）{
 return lhs.priority == rhs.priority&& 
 lhs.description == rhs.description&& 
 //其他一些字段
; 
} 
  

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

但是现在我希望这些任务按集合中的优先级排序（以获得最高优先级的任务）。显然，这对于std :: unordered_set是不可能的，因此我尝试了使用以下较少运算符的std :: set：

  bool lessTask（const Task& lhs，const Task& rhs）{
 return lhs.priority< rhs.priority; 
} 
  

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

什么是完成一组任务的最佳方法，我可以在其中真正快速地插入元素并且没有重复的条目（由isEqual函数定义），但是能够真正快速地检索具有最高优先级的任务吗？

我没有绑定到任何特定的STL容器，但不想使用任何第三方库（甚至都不使用Boost）。

解决方案

首先写入 get_tie ：

  // auto或decltype（auto）
 auto get_tie（const Task& task）{
 return std :: tie（lhs.priority，lhs.description，/ *其他一些字段* /）; 
} 
  

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

  #define RETURNS（...）decltype（__ VA_ARGS__）{return __VA_ARGS__; } 
 auto get_tie（const Task& task）-> 
 RETURNS（std :: tie（lhs.priority，lhs.description，/ *其他一些字段* /））
  

一旦我们有一个简单的 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 。

I have the following problem: Consider this (simplified) structure:

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

Now I want to have a set of all tasks and do some work with it. Therefore I have an equality operator, which checks that every element is equal.

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

For this I have used the std::unordered_set, which worked fine.

But now I want these tasks to be sorted by their priority(to get the highest priority task) in the set. Obviously this is not possible with an std::unordered_set, so I tried a std::set with the following less operator:

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

But this implies by the strict weak ordering, that two tasks are equal, when the priority is equal, which I don't want(I want to maintain my isEqual method for equality checking).

What's the best way to accomplish a set of tasks, where I can insert elements really fast and have no duplicate entries(defined by my isEqual function), but are able to retrieve a task with the highest priority really fast?
I am not bound to any specific STL container, but doesn't want to use any third party libraries(not even boost).

解决方案

First write get_tie:

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

in C++11 you have to repeat the body with a ->decltype trailing return type, or use a macro to avoid the repetition:

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

once we have an easy get_tie, your problem evaporates.

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

simply pass isLess to std::set, or build a std::vector and std::sort it using isLess.

Now, if your comparison doesn't really work on a raw tie of references, you may have to replace get_tie with something more complex.

这篇关于排序集没有严格的弱排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！