Всегда ли эффективен трехсторонний оператор сравнения?
Херб Саттер, в его предложение для оператора «космический корабль» (раздел 2.2.2, внизу страницы 12), говорит:
Основывая все на
[…]<=>и его тип возврата: Эта модель имеет основные преимущества, некоторые уникальные для этого предложения по сравнению с предыдущими предложениями для C ++ и возможностями других языков:(6) Эффективность, включая, наконец, достижение абстракции с нулевыми издержками для сравнений: Подавляющее большинство сравнений всегда однопроходные. Единственное исключение генерируется
<=а также>=в случае типов, которые поддерживают как частичное упорядочение, так и равенство. За<однопроходный режим необходим для достижения принципа нулевых издержек, чтобы избежать повторения сравнений на равенство, таких какstruct Employee { string name; /*more members*/ };используется вstruct Outer { Employeee; /*more members*/ };— сегодняшние сравнения нарушают абстракцию с нулевыми накладными расходами, потому чтоoperator<наOuterвыполняет избыточные сравнения равенства, потому что он выполняетif (e != that.e) return e < that.e;который проходит равный префикс
e.nameдважды (и если имя совпадает, обходит равные префиксы других членовEmployeeвдвое больше), и это вообще нельзя оптимизировать. Как отмечает Каминьски, абстракция с нулевыми накладными расходами — это столп C ++, и достижение его для сравнений в первый раз является существенным преимуществом этого дизайна, основанного на<=>,
Но затем он приводит этот пример (раздел 1.4.5, стр. 6):
class PersonInFamilyTree { // ...
public:
std::partial_ordering operator<=>(const PersonInFamilyTree& that) const {
if (this->is_the_same_person_as ( that)) return partial_ordering::equivalent;
if (this->is_transitive_child_of( that)) return partial_ordering::less;
if (that. is_transitive_child_of(*this)) return partial_ordering::greater;
return partial_ordering::unordered;
}
// ... other functions, but no other comparisons ...
};
Определил бы operator>(a,b) как a<=>b > 0 не приводит к большим накладным расходам? (хотя в другой форме, чем он обсуждает). Этот код будет сначала проверять на равенство, а затем для lessи, наконец, для greater, а не только и непосредственно тестирование greater,
Я что-то здесь упускаю?
Решение
Определил бы
operator>(a,b)какa<=>b > 0не приводит к большим накладным расходам?
Это привело бы к немного накладные расходы. Однако величина накладных расходов относительна — в ситуациях, когда затраты на выполнение сравнений незначительны по сравнению с остальной частью программы, приемлемым компромиссом может быть уменьшение дублирования кода путем внедрения одного оператора вместо пяти.
Однако в предложении не предлагается удалять другие операторы сравнения в пользу <=>: если вы хотите перегружать другие операторы сравнения, вы можете это сделать:
Быть генералом: Не ограничивайте то, что присуще. Не произвольно ограничивайте полный набор использования. Избегайте особых случаев и частичных особенностей. — Например, этот документ поддерживает все семь операторов и операций сравнения, включая добавление трехстороннего сравнения с помощью
<=>, Он также поддерживает все пять основных категорий сравнения, включая частичные заказы.
Другие решения
Для некоторого определения большого. Есть накладные расходы, потому что в частичном порядке, a == b тогда и только тогда a <= b а также b <= a, Сложность будет такой же, как топологическая сортировка, O(V+E), Конечно, современный подход C ++ состоит в том, чтобы писать безопасный, чистый и читаемый код и затем оптимизирующий. Вы можете сначала внедрить оператор космического корабля, а затем специализироваться после определения узких мест в производительности.
Вообще говоря, перегрузка <=> Имеет смысл, когда вы имеете дело с типом, где выполнение всех сравнений одновременно либо просто тривиально дороже, либо стоит столько же, сколько их сравнение по-разному.
Со строками, <=> кажется дороже, чем прямой == тест, так как вы должны вычесть каждую пару из двух символов. Однако, поскольку вам уже пришлось загружать каждую пару символов в память, добавление вычитания поверх этого является тривиальным расходом. Действительно, сравнение двух чисел на равенство иногда реализуется компиляторами как вычитание и проверка на ноль. И даже для компиляторов, которые этого не делают, вычитание и сравнение с нулем, вероятно, не значительно менее эффективно.
Так что для таких базовых типов, вы более или менее хороши.
Когда вы имеете дело с чем-то вроде упорядочивания деревьев, вам действительно нужно заранее знать, какая операция вас интересует. Если все, что вы просили, было ==, вы действительно Я не хочу искать остальную часть дерева, просто чтобы знать, что они неравны.
Но лично … я бы никогда не реализовал что-то вроде упорядочения дерева с операторами сравнения для начала. Зачем? Потому что я считаю, что подобные сравнения должны быть логически быстрыми операциями. В то время как поиск по дереву является такой медленной операцией, что вы действительно не хочу делать это случайно или в любое другое время, кроме случаев, когда это абсолютно необходимо.
Просто посмотрите на это дело. Что на самом деле означает сказать, что человек в генеалогическом древе «меньше» другого? Это означает, что один является ребенком другого. Разве не было бы более читабельным в коде просто задать этот вопрос непосредственно с is_transitive_child_of?
Чем сложнее логика сравнения, тем менее вероятно, что то, что вы делаете, действительно является «сравнением». Вероятно, есть какое-то текстовое описание, которое может вызвать эта операция «сравнения», которая была бы более читабельной.
О, конечно, такой класс может иметь функцию, которая возвращает partial_order представляя отношения между двумя объектами. Но я бы не назвал эту функцию operator<=>,
Но в любом случае это <=> нулевая накладная абстракция сравнения? Нет; Вы можете построить случаи, когда вычисление порядка обходится значительно дороже, чем определение конкретного отношения, о котором вы просили. Но лично в этом случае есть хороший шанс, что вы не должны сравнивать такие типы через операторы. совсем.