Всегда ли эффективен трехсторонний оператор сравнения?

Question

Херб Саттер в своем предложении об операторе "космический корабль" (раздел 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,

Я что-то здесь упускаю?

Answer 1

Определил бы operator>(a,b) как a<=>b > 0 не приводит к большим накладным расходам?

Это привело бы к некоторым накладным расходам. Однако величина накладных расходов относительна - в ситуациях, когда затраты на выполнение сравнений незначительны по сравнению с остальной частью программы, приемлемым компромиссом может быть уменьшение дублирования кода путем внедрения одного оператора вместо пяти.

Однако в предложении не предлагается удалять другие операторы сравнения в пользу <=>: если вы хотите перегружать другие операторы сравнения, вы можете это сделать:

Будьте общими: не ограничивайте то, что присуще. Не произвольно ограничивайте полный набор использования. Избегайте особых случаев и частичных особенностей. - Например, этот документ поддерживает все семь операторов и операций сравнения, включая добавление трехстороннего сравнения с помощью <=>, Он также поддерживает все пять основных категорий сравнения, включая частичные заказы.

Answer 2

Для некоторого определения большого. Есть накладные расходы, потому что в частичном порядке, a == b тогда и только тогда a <= b а также b <= a, Сложность будет такой же, как топологическая сортировка, O(V+E), Конечно, современный подход C++ состоит в том, чтобы писать безопасный, чистый и читаемый код, а затем оптимизировать. Вы можете сначала внедрить оператор космического корабля, а затем специализироваться после определения узких мест в производительности.

Answer 3

Вообще говоря, перегрузка <=> Имеет смысл, когда вы имеете дело с типом, где выполнение всех сравнений одновременно либо просто тривиально дороже, либо стоит столько же, сколько их сравнение по-разному.

Со строками, <=> кажется дороже, чем прямой == тест, так как вы должны вычесть каждую пару из двух символов. Однако, поскольку вам уже пришлось загружать каждую пару символов в память, добавление вычитания поверх этого является тривиальным расходом. Действительно, сравнение двух чисел на равенство иногда реализуется компиляторами как вычитание и проверка на ноль. И даже для компиляторов, которые этого не делают, вычитание и сравнение с нулем, вероятно, не значительно менее эффективно.

Так что для таких базовых типов, вы более или менее хороши.

Когда вы имеете дело с чем-то вроде упорядочивания деревьев, вам действительно нужно заранее знать, какая операция вас интересует. Если все, что вы просили, было == Вы действительно не хотите искать остальную часть дерева просто чтобы знать, что они неравны.

Но лично... я бы никогда не реализовал что-то вроде упорядочения дерева с операторами сравнения для начала. Зачем? Потому что я считаю, что подобные сравнения должны быть логически быстрыми операциями. Принимая во внимание, что поиск по дереву является настолько медленной операцией, что вы действительно не хотите делать это случайно или в любое время, кроме случаев, когда это абсолютно необходимо.

Просто посмотрите на это дело. Что на самом деле означает сказать, что человек в генеалогическом древе "меньше" другого? Это означает, что один является ребенком другого. Разве не было бы более читабельным в коде просто задать этот вопрос непосредственно с is_transitive_child_of?

Чем сложнее логика сравнения, тем менее вероятно, что то, что вы делаете, действительно является "сравнением". Вероятно, есть какое-то текстовое описание, которое может вызвать эта операция "сравнения", которая была бы более читабельной.

О, конечно, такой класс может иметь функцию, которая возвращает partial_order представляя отношения между двумя объектами. Но я бы не назвал эту функцию operator<=>,

Но в любом случае это <=> нулевая накладная абстракция сравнения? Нет; Вы можете построить случаи, когда вычисление порядка обходится значительно дороже, чем определение конкретного отношения, о котором вы просили. Но лично в этом случае есть хороший шанс, что вам вообще не следует сравнивать такие типы через операторы.