Сортировка только использования меньше оператор по сравнению с trivalue сравнивает функцию
В C++ / сортировка STL сделан при помощи только меньше оператор. Altough я понятия не имею, как алгоритмы сортировки на самом деле реализованы, я предполагаю, что другие операции создаются implicite:
a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)
По сравнению с использованием trivalue* сравнивают функцию, как, например, Java, действительно ли это хорошо для производительности, или почему это проектное решение было сделано?
Мое предположение - то, что любой trivalue compareto функция все еще должен реализовать эти сравнения сам по себе, приведя к той же производительности.
** trivalue сравнивают функцию, я имею в виду сравнить функцию, которая возвращается-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 говорится о том, что компаратор и хэш-код согласуются с equals, и это все, что вам нужно. В C++ приходится иметь дело с <, >, ==, <=, >=, постусловием присваивания и так далее.
C++ использует довольно чистый математический подход к этому в API, поэтому все определяется в терминах единственного бинарного отношения. Java в некоторых отношениях более дружелюбна и предпочитает трехсторонние сравнения, где определение фундаментальной единицы (сравнения) немного сложнее, но логика, вытекающая из него, проще. Это также означает, что алгоритм сортировки получает больше информации на одно сравнение, что иногда бывает полезно. В качестве примера можно привести оптимизацию сортировки по "голландскому флагу", которая помогает, когда в данных много дубликатов "в одном и том же месте".
В этом случае компаратор с тремя значениями - это выигрыш в скорости. Но C++ использует последовательное определение компаратора для sort, а также для set и map, lower_bound и так далее, которые едва ли выигрывают от трехзначного компаратора (может быть, экономят одно сравнение, может быть, нет). Я полагаю, что они решили не усложнять свой хороший, общий интерфейс в интересах конкретного или ограниченного потенциального повышения эффективности.
, если вы имеете в виду std :: sort (), он использует только оператор less (), потому что ему не нужно сохранять относительный порядок эквивалентных элементов, поэтому для него потребуется только оператор less () и неявно больший ().
, а std :: stable_sort сохранит его, но работает медленнее. ему нужен оператор less () и двунаправленный итератор в обмен на оператор equal () для создания функции сравнения "trivalue"
Я предполагаю, что в C ++ это было сделано только для уменьшения дублирования кода: как только вы определите операцию сравнения для класса / типа, вы не только сможете сравнивать их объекты, просто написав a Что касается сортировки, нам нужен только оператор «меньше», зачем вводить дополнительные вещи? :)