Sorted set without a strict weak ordering

Question

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

I would just make a comparison operator that compares priority first and then other fields. — David Schwartz, Nov 03 '15 at 18:41

SergeyA · Answer 1 · 2015-11-03T18:57:31.017

1

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.

edited Nov 03 '15 at 18:57

answered Nov 03 '15 at 18:46

SergeyA

61,605
5
78
137

Priority queues are different; for one, they do require a strict weak ordering. – Lightness Races in Orbit Nov 03 '15 at 19:06
@LightnessRacesinOrbit, not sure if I follow. If I understood OP correctly, it will give exactly what is needed - an ability to put an item into container, define ordering based on priority alone and pop the item with largest priority. Why do you think it won't solve OP's question? – SergeyA Nov 03 '15 at 19:09
Because a priority queue requires a strict weak ordering. That means the comparator cannot _only_ consider the `priority` field. Operations on your container will have undefined behaviour if it does. Fortunately, `std::make_heap` is unrelated to priority queues, which is my main point. – Lightness Races in Orbit Nov 03 '15 at 23:48
@LightnessRacesinOrbit A heap also requires a strict weak ordering comperator(see http://www.cplusplus.com/reference/algorithm/make_heap/). But also I have no non-duplicate guarantee, which is not covered by this solution. – darkbit Nov 04 '15 at 09:35
@LightnessRacesinOrbit, what do you mean by `std::make_heap` unrelated to priority queues? It makes a heap in a container, and heap is another name for priority queue. – SergeyA Nov 04 '15 at 14:14
@SergeyA: `std::priority_queue` is a specific thing. Don't confuse the two! – Lightness Races in Orbit Nov 04 '15 at 16:57
@LightnessRacesinOrbit, ok, we fell the victim of confusion between general definition and C++ standard definition. In C++ standard, as you correctly point out, priority queue is a specific container (or rather adapter). However, `std::make_heap` produces what is called max heap, and max heap, in a data structures lingo, is another name for priority queue (which has nothing to do with C++ `std::priority_queue`!). Should we agree on that? – SergeyA Nov 04 '15 at 17:00
Yes - I'm just saying be careful in your answer because of the ambiguity. – Lightness Races in Orbit Nov 04 '15 at 17:55

score 1 · Accepted Answer · answered Nov 03 '15 at 20:23

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.

Sorted set without a strict weak ordering

2 Answers2

Linked