Всегда ли работает оператор трехстороннего сравнения?

Herb Sutter, в своем предложении для оператора "космического корабля" (раздел 2.2.2, внизу страницы 12), говорит:

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

[...]

(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), и это вообще невозможно оптимизировать. Как отмечает Каминьски, абстракция с нулевым потоком является столпом С++, и достижение ее для сравнений в первый раз является значительным преимуществом этого дизайна на основе <=>.

Но затем он приводит этот пример (раздел 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.

Я что-то пропустил?

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

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

Итак, для базовых типов, которые вы используете, вы более или менее точны.

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

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

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

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

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

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