Сортированный набор без строгой слабой упорядоченности

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, поэтому я попытался использовать std :: set со следующим оператором less:

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

Но это подразумевает строгий слабый порядок, что две задачи равны, когда приоритет равен, чего я не хочу (я хочу сохранить свой метод isEqual для проверки равенства).

Каков наилучший способ выполнить набор задач, когда я могу очень быстро вставлять элементы и не иметь повторяющихся записей (определяется моей функцией isEqual), но могу действительно быстро получить задачу с самым высоким приоритетом?
Я не привязан к какому-либо конкретному контейнеру STL, но не хочу использовать какие-либо сторонние библиотеки (даже не boost).

0

c++c++11 containers strict-weak-ordering

Решение

Другие решения

Когда вы помещаете элемент на карту, вам обычно нужно добавлять ВСЕХ членов класса в less, В противном случае это не будет работать должным образом. Когда мне пришлось создать систему из примерно 15 различных постоянно меняющихся классов, содержащихся в картах, это было большой проблемой, и именно тогда я действительно начал пропускать отражение во время компиляции.

На заметку, вместо карты вы можете использовать приоритетная очередь (std::make_heap). Приоритетная куча не заботится о равенстве и даст вам задачу с наивысшим приоритетом.

1

Источник

Accepted Answer

Сначала напиши 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 с чем-то более сложным.

1