может std :: sort с не строгим компаратором слабого порядка работать как топологическая сортировка?

Я знаю, что должен следовать строгому слабому порядку для компаратора 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 с этим компаратором всегда работать как топологическая сортировка?

плюс)

спасибо Оливеру Чарльзуорту за недостающую информацию.

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

0

Решение

Нет, скорее всего, это не сработает. std::sort контракт требует строгого слабого заказа компаратора; нарушение его приводит к неопределенному поведению. Кстати, я видел несколько раз libstdc ++ std::sort жестоко сбой (чтение элементов вне контейнера, IIRC) для такого рода компаратора «расслабления».

1

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

Других решений пока нет …

По вопросам рекламы [email protected]