Я знаю, что должен следовать строгому слабому порядку для компаратора c ++. И главная причина в том, что !(a > b) && !(b > a)
должен действовать как оператор эквивалентности.
Но проблема заключается только в сортировке, где вам не нужен оператор эквивалентности, а не как std::set
,
Например, существует вектор множеств, и если множество A является правильным подмножеством B, то после сортировки индекс множества A должен быть меньше индекса множества B.
Итак, предположим, что вы пишете компаратор, как это
bool comparator(vector<int> &A, vector<int> &B) const {
// if A is proper subset of B, return true
// otherwise, return false
}
Тогда делает std::sort
с этим компаратором всегда работать как топологическая сортировка?
плюс)
спасибо Оливеру Чарльзуорту за недостающую информацию.
Я действительно хочу знать, что такой компаратор работает как быстрая сортировка или сортировка вставкой (некоторые известные алгоритмы сортировки на основе сравнения) как топологическая сортировка.
Нет, скорее всего, это не сработает. std::sort
контракт требует строгого слабого заказа компаратора; нарушение его приводит к неопределенному поведению. Кстати, я видел несколько раз libstdc ++ std::sort
жестоко сбой (чтение элементов вне контейнера, IIRC) для такого рода компаратора «расслабления».
Других решений пока нет …