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