Sorted set without a strict weak ordering

问题:

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).

回答1:

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.

回答2:

When you put an element to the map, you usually need to add ALL members of the class to less. Otherwise it won't work properly. When I had to create a system of about 15 different constantly changing classess contained in maps, that was the big challenge, and this was when I really started to miss compile-time reflection.

On a side note, instead of the map you can use priority queue (std::make_heap). Priority heap does not care about equality and will give you the task with highest priority first.