Сортировка только с использованием оператора меньше чем по сравнению с функцией сравнения трех значений
В C++/STL сортировка выполняется с использованием только оператора меньше. Хотя я понятия не имею, как на самом деле реализованы алгоритмы сортировки, я предполагаю, что другие операции создаются имплицитно:
a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)
По сравнению с использованием функции сравнения trivalue*, как, например, Java, это хорошо для производительности, или почему было принято это дизайнерское решение?
Я предполагаю, что любая трехзначная функция сравнения по-прежнему должна реализовывать эти сравнения сама по себе, что приводит к той же производительности.
** под функцией сравнения трех значений я подразумеваю функцию сравнения, которая возвращает -1, 0 и 1 для значений меньше, равных и выше *
Обновление: кажется, космический корабль <=> операторы приходят в C++20, так что, очевидно, комитет решил, что есть только недостатки использования operator<,
3 ответа
В некотором смысле два других являются неявными, но более точным было бы сказать, что сортировка сравнения на самом деле не нуждается в трехзначном компараторе, а сортировки в 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 и так далее, которые едва ли выигрывают от компаратора с тремя значениями (возможно, сохраните одно сравнение, а может и нет). Я предполагаю, что они решили не усложнять их хороший, общий интерфейс в интересах конкретного или ограниченного потенциального повышения эффективности.
Я предполагаю, что в C++ это было сделано только для того, чтобы уменьшить дублирование кода: как только вы определили опцию сравнения для класса / типа, вы не только сможете сравнивать эти объекты, просто написав Что касается сортировки, нам нужен только оператор меньше, зачем вводить дополнительные вещи?:)
Если вы ссылаетесь на std::sort(), то в нем используется только оператор less (), поскольку ему не нужно сохранять относительное упорядочение эквивалентного элемента, поэтому ему понадобится просто оператор less () и неявно больший оператор ().
в то время как std::stable_sort сохранит его, но он медленнее. для построения функции сравнения "trivalue" требуется оператор less () и двунаправленный итератор в обмен на оператор equal ()