Сортировка только с использованием оператора меньше чем по сравнению с функцией сравнения трех значений

Question

В C ++ / STL сортировка выполняется с использованием только оператора меньше.Хотя я понятия не имею, как на самом деле реализованы алгоритмы сортировки, я предполагаю, что другие операции создаются неявно:

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

По сравнению с использованием функции сравнения trivalue *, как, например, Java, это хорошопроизводительность или почему было принято это проектное решение?

Я предполагаю, что любая функция сравнения trivalue по-прежнему должна реализовывать эти сравнения сама по себе, что приводит к той же производительности.

** при сравнении трех значенийЯ имею в виду функцию сравнения, которая возвращает -1, 0 и 1 для значений, меньших, равных и превышающих *

Обновление: Кажется, оператор космического корабля <=> прибывает в C++ 20, так что, очевидно, комитет счел, что есть минусы использования только operator<.

Answer 1

В некотором смысле два других являются неявными, но более точным было бы сказать, что сортировка сравнения на самом деле не требует трехзначного компаратора, а сортировки C ++ реализованы таким образом, что не используйте один, чтобы минимизировать поведение, требуемое компаратором.

Было бы неправильно, чтобы std :: sort определял и использовал исключительно что-то вроде этого:

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

... потому что вы получите неэффективный алгоритм с точки зрения количества вызовов на lessthan. Если ваш алгоритм не делает ничего полезного с разницей между возвратом 1 и возвратом 0, то вы потратили впустую сравнение.

C ++ относится к "строгим слабым порядкам". Если < является строгим слабым порядком и !(a < b) && !(b < a), он не обязательно обязательно следует за a == b. Они просто "в том же месте" в порядке, и !(a < b) && !(b < a) является отношением эквивалентности. Таким образом, компаратор, необходимый для sort порядков классов эквивалентности объектов, не обеспечивает общий порядок.

Единственная разница, которую вы делаете, это то, что вы говорите, когда !(a < b). Для строгого общего порядка вы должны вывести b <= a, читать «меньше или равно». Для строгого слабого порядка вы не можете определить b <= a как означающее b < a || b == a, и это должно быть правдой. C ++ педантичен по этому поводу, и, поскольку он допускает перегрузку операторов, это должно быть достаточно, поскольку люди, перегружающие операторы, нуждаются в жаргоне, чтобы сообщить пользователям своего кода, что они могут ожидать с точки зрения отношения операторов. Java действительно говорит о том, что компаратор и хеш-код соответствуют равным, и это все, что вам нужно. C ++ должен иметь дело с <,>, ==, <=,> =, последующим условием присваивания и т. Д.

C ++ использует довольно чистый математический подход к этому в API, поэтому все определяется в терминах одного бинарного отношения. В некоторых отношениях Java более дружественна и предпочитает трехсторонние сравнения, где определение фундаментальной единицы (сравнение) немного сложнее, но логика, вытекающая из этого, проще. Это также означает, что алгоритм сортировки получает больше информации за сравнение, что иногда полезно. Например, см. Оптимизацию быстрой сортировки «голландский флаг», которая является преимуществом, когда в данных много дубликатов «в одном и том же месте».

В этом случае трехзначный компаратор представляет собой увеличение скорости. Но C ++ использует непротиворечивое определение компаратора для сортировки, а также для set и map, lower_bound и т. Д., Которые едва ли выигрывают от трехзначного компаратора (возможно, сохраните одно сравнение, а может и нет). Я предполагаю, что они решили не усложнять их хороший, общий интерфейс в интересах конкретного или ограниченного потенциального повышения эффективности.

Answer 2

Я предполагаю, что в C ++ это было сделано только для того, чтобы уменьшить дублирование кода: как только вы определили опцию сравнения для класса / типа, вы не только сможете сравнивать эти объекты, просто написав Что касается сортировки, нам нужен только оператор меньше, зачем вводить дополнительные вещи?:)

Answer 3

если вы ссылаетесь на std :: sort (), он использует только оператор less (), потому что ему не нужно сохранять относительное упорядочение эквивалентного элемента, поэтому ему потребуется оператор less () и неявно больший ( ) оператор.

пока std :: stable_sort сохранит его, но это медленнее. для построения функции сравнения "trivalue" * требуется оператор less () и двунаправленный итератор в обмен на оператор equal ()