Когда вы вызываете stable_sort () для скаляров?
Это когда-нибудь хорошо, чтобы позвонить stable_sort вместо sort на скалярных типах (т.е. int, longи т.д.) с компаратором по умолчанию?
Если так, когда вы должны это сделать?
Если нет, то почему стандартные библиотеки просто не пересылают такие вызовы sort? Разве это не будет намного быстрее?
Решение
Стабильные сортировки действительно полезны только тогда, когда сортируемые элементы имеют спутниковая информация.
От CLRS (Введение в алгоритмы, 3-е изд.):
«На практике сортируемые числа редко бывают изолированными значениями.
из коллекции данных, называемых записью. Каждая запись содержит ключ, который является
значение для сортировки. Остальная часть записи состоит из спутниковых данных, которые
обычно носят с собой ключ. На практике, когда алгоритм сортировки переставляет
ключи, он должен также переставлять спутниковые данные «.
Когда сортировка стабильна, это означает, что связи разбиты в отсортированном массиве по оригинальному порядку элементов. Если вы только сортируете int а также long типы, вам не нужна стабильная сортировка.
Другие решения
Не должно быть никакой разницы (возможно, за исключением таких вещей, как -0.0 и 0.0). Однако я не думаю, что есть необходимость перенаправлять такие вызовы, потому что std :: sort или std :: stable_sort не должны знать, что они сортируют, до тех пор, пока выполняется операция сравнения. Эти функции не должны быть слишком умными.
С дефолт компаратор конкретно (подразумевается естественный строгий порядок)? Я не вижу никакой пользы для стабильной сортировки по скалярам в этом случае. Стабильная сортировка не может дать никаких дополнительных преимуществ в ситуациях, когда эквивалентные значения (по мнению компаратора) неразличимы. (Хотя @ Андрей Туганов в своем ответе делает интересное и актуальное замечание об отрицательных нулях).
Тем не менее, стабильная сортировка по скалярам может быть полезна, когда критерий упорядочения слабее естественного строгого упорядочения. Например, вы можете написать предикат сравнения, который скажет, что любое нечетное число больше любого четного числа. В этом случае результирующий порядок просто разделит массив на смежные блоки четных и нечетных чисел (в этом порядке). Если вы заинтересованы в сохранении относительного порядка этих чисел без изменений, вам нужен стабильный алгоритм сортировки.