Операции сравнения в C++20

Автор оригинала: Barry Revzin
  • Перевод
Встреча в Кёльне прошла, стандарт C++20 приведён к более или менее законченному виду (по крайней мере до появления особых примечаний), и я хотел бы рассказать об одном из грядущих нововведений. Речь пойдёт о механизме, который обычно называют operator<=> (стандарт определяет его как «оператор трёхстороннего сравнения», но у него есть неформальное прозвище «космический корабль»), однако я считаю, что область его применения гораздо шире.

У нас не просто будет новый оператор — семантика сравнений претерпит существенные изменения на уровне самого языка.

Даже если ничего больше вы из этой статьи не вынесете, запомните эту таблицу:
Равенство
Упорядочение
Базовые
==
<=>
Производные
!=
<, >, <=, >=

Теперь у нас будет новый оператор, <=>, но, что ещё важнее, операторы теперь систематизированы. Есть базовые операторы и есть производные операторы — каждая группа обладает своими возможностями.

Об этих возможностях мы поговорим коротко во вступлении и рассмотрим подробнее в следующих разделах.

Базовые операторы могут быть обращены (т.е. переписаны с обратным порядком параметров). Производные операторы могут быть переписаны через соответствующий базовый оператор. Ни обращённые, ни переписанные кандидаты не порождают новых функций, они просто являются заменами на уровне исходного кода и отбираются из расширенного набора кандидатов. Например, выражение a < 9 теперь может вычисляться как a.operator<=>(9) < 0, а выражение 10 != b — как !operator==(b, 10). Это значит, что можно будет обойтись одним или двумя операторами там, где для достижения того же поведения сейчас требуется вручную написать 2, 4, 6 или даже 12 операторов. Краткий обзор правил будет представлен ниже вместе с таблицей всех возможных преобразований.

И базовые, и производные операторы можно определять в качестве используемых по умолчанию. В случае базовых операторов это означает, что оператор будет применяться к каждому члену в порядке объявления; в случае производных операторов — что будут использоваться переписанные кандидаты.

Следует отметить, что не существует такого преобразования, при котором оператор одного вида (т.е. равенства или упорядочения) мог бы выражаться через оператор другого вида. Иными словами, столбцы в нашей таблице никак не зависят друг от друга. Выражение a == b никогда не будет вычисляться как operator<=>(a, b) == 0 неявно (но, разумеется, ничто не мешает вам определить свой operator== через operator<=>, если захочется).

Рассмотрим небольшой пример, в котором покажем, как выглядит код до и после применения нового функционала. Мы напишем тип строки, не учитывающий регистр, CIString, объекты которого могут сравниваться как друг с другом, так и с char const*.

В C++17 для нашей задачи потребуется написать 18 функций сравнения:

class CIString {
  string s;

public:
  friend bool operator==(const CIString& a, const CIString& b) {
    return a.s.size() == b.s.size() &&
      ci_compare(a.s.c_str(), b.s.c_str()) == 0;
  }
  friend bool operator< (const CIString& a, const CIString& b) {
    return ci_compare(a.s.c_str(), b.s.c_str()) <  0;
  }
  friend bool operator!=(const CIString& a, const CIString& b) {
    return !(a == b);
  }
  friend bool operator> (const CIString& a, const CIString& b) {
    return b < a;
  }
  friend bool operator>=(const CIString& a, const CIString& b) {
    return !(a < b);
  }
  friend bool operator<=(const CIString& a, const CIString& b) {
    return !(b < a);
  }

  friend bool operator==(const CIString& a, const char* b) {
    return ci_compare(a.s.c_str(), b) == 0;
  }
  friend bool operator< (const CIString& a, const char* b) {
    return ci_compare(a.s.c_str(), b) <  0;
  }
  friend bool operator!=(const CIString& a, const char* b) {
    return !(a == b);
  }
  friend bool operator> (const CIString& a, const char* b) {
    return b < a;
  }
  friend bool operator>=(const CIString& a, const char* b) {
    return !(a < b);
  }
  friend bool operator<=(const CIString& a, const char* b) {
    return !(b < a);
  }

  friend bool operator==(const char* a, const CIString& b) {
    return ci_compare(a, b.s.c_str()) == 0;
  }
  friend bool operator< (const char* a, const CIString& b) {
    return ci_compare(a, b.s.c_str()) <  0;
  }
  friend bool operator!=(const char* a, const CIString& b) {
    return !(a == b);
  }
  friend bool operator> (const char* a, const CIString& b) {
    return b < a;
  }
  friend bool operator>=(const char* a, const CIString& b) {
    return !(a < b);
  }
  friend bool operator<=(const char* a, const CIString& b) {
    return !(b < a);
  }
};

В C++20 можно обойтись всего лишь 4 функциями:

class CIString {
  string s;

public:
  bool operator==(const CIString& b) const {
    return s.size() == b.s.size() &&
      ci_compare(s.c_str(), b.s.c_str()) == 0;
  }
  std::weak_ordering operator<=>(const CIString& b) const {
    return ci_compare(s.c_str(), b.s.c_str()) <=> 0;
  }

  bool operator==(char const* b) const {
    return ci_compare(s.c_str(), b) == 0;
  }
  std::weak_ordering operator<=>(const char* b) const {
    return ci_compare(s.c_str(), b) <=> 0;
  }
};

Я расскажу, что всё это значит, подробнее, но сначала давайте немного вернёмся в прошлое и вспомним, как работали сравнения до стандарта C++20.

Сравнения в стандартах с C++98 по C++17


Операции сравнения почти не менялись с момента создания языка. У нас было шесть операторов: ==, !=, <, >, <= и >=. Стандарт определяет каждый из них для встроенных типов, но в целом они подчиняются одним и тем же правилам. При вычислении любого выражения a @ b (где @ — один из шести операторов сравнения) компилятор ищет функции-члены, свободные функции и встроенные кандидаты с именем operator@, которые могут быть вызваны с типом A или B в указанном порядке. Из них выбирается самый подходящий кандидат. Вот и всё. По сути, все операторы работали одинаково: операция < не отличалась от <<.

Такой простой набор правил легко усвоить. Все операторы абсолютно независимы и эквивалентны. Неважно, что мы, люди, знаем о фундаментальном отношении между операциями == и !=. С точки зрения языка, это одно и то же. Мы же используем идиомы. Например, мы определяем оператор != через ==:

bool operator==(A const&, A const&);

bool operator!=(A const& lhs, A const& rhs) {
  return !(lhs == rhs);
}

Аналогично, через оператор < мы определяем все остальные операторы отношения. Мы пользуемся этими идиомами, потому что, несмотря на правила языка, мы на самом деле не считаем все шесть операторов эквивалентными. Мы принимаем, что два из них являются базовыми (== и <), а через них уже выражаются все остальные.

В самом деле, стандартная библиотека шаблонов (Standard Template Library) целиком построена на этих двух операторах, и огромное количество типов в эксплуатируемом коде содержит определения только одного из них или их обоих.

Однако оператор < не очень-то подходит на роль базового по двум причинам.

Во-первых, через него нельзя гарантированно выразить другие операторы отношения. Да, a > b означает ровно то же, что b < a, но неверно, что a <= b значит ровно то же, что !(b < a). Последние два выражения будут эквивалентны, если имеется свойство трихотомии, при котором для любых двух значений верно только одно из трёх утверждений: a < b, a == b или a > b. При наличии трихотомии выражение a <=b означает, что мы имеем дело либо с первым, либо со вторым случаем… а это эквивалентно утверждению, что мы не имеем дела с третьим случаем. Поэтому (a <= b) == !(a > b) == !(b < a).

Но что если отношение не обладает свойством трихотомии? Это характерно для отношений частичного порядка. Классический пример — числа с плавающей запятой, для которых любая из операций 1.f < NaN, 1.f == NaN и 1.f > NaN даёт ложь. Поэтому 1.f <= NaN также даёт ложь, но при этом !(NaN < 1.f)правда.

Единственный способ реализовать оператор <= в общем виде через базовые операторы — это расписать обе операции как (a == b) || (a <b), что является большим шагом назад в том случае, если нам всё же придётся иметь дело с линейным порядком, поскольку тогда будет вызываться не одна функция, а две (например, выражение «abc..xyz9» <= «abc..xyz1» придётся переписать как («abc..xyz9»== «abc..xyz1») || («abc..xyz9» < «abc..xyz1») и дважды сравнивать всю строку целиком).

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

struct A {
  T t;
  U u;
  
  bool operator==(A const& rhs) const {
    return t == rhs.t &&
      u == rhs.u;
  }
  
  bool operator< (A const& rhs) const {
    return t < rhs.t &&
      u < rhs.u;
  }  
};

Чтобы определить оператор == для коллекции элементов, достаточно один раз применить == к каждому члену, но с оператором < так не получится. С точки зрения этой реализации, множества A{1, 2} и A{2, 1} будут считаться эквивалентными (так как ни одно из них не меньше другого). Чтобы исправить это, следует применить оператор < дважды к каждому члену, кроме последнего:

bool operator< (A const& rhs) const {
  if (t < rhs.t) return true;
  if (rhs.t < t) return false;
  return u < rhs.u;
}

Наконец, чтобы гарантировать правильную работу сравнений разнотипных объектов — т.е. гарантировать, что выражения a == 10 и 10 == a означают одно и то же, — обычно рекомендуют писать сравнения как свободные функции. На самом деле это вообще единственный способ реализовать такие сравнения. Это неудобно, потому что, во-первых, придётся следить за соблюдением этой рекомендации, а во-вторых, обычно такие функции приходится объявлять скрытыми друзьями для более удобной реализации (т.е. внутри тела класса).

Заметим, что не всегда при сравнениях разнотипных объектов требуется писать именно operator==(X, int); они могут также подразумевать случаи, когда int может неявно приводиться к X.

Подведём итоги по правилам до стандарта C++20:

  • Все операторы обрабатываются одинаково.
  • Мы используем идиомы для облегчения реализации. Операторы == и < мы принимаем за базовые идиомы и выражаем остальные операторы отношения через них.
  • Вот только оператор < не очень подходит на роль базового.
  • Важно (и рекомендовано) писать сравнения разнотипных объектов как свободные функции.

Новый базовый оператор упорядочения: <=>


Самое значительное и заметное изменение в работе сравнений в C++20 — это добавление нового оператора — operator<=>, оператора трёхстороннего сравнения.

С трёхсторонними сравнениями мы уже знакомы по функциям memcmp/strcmp в C и basic_string::compare() в C++. Все они возвращают значение типа int, которое представлено произвольным положительным числом, если первый аргумент больше второго, 0 — если они равны, и произвольным отрицательным числом в противном случае.

Оператор «космический корабль» возвращает не значение типа int, а объект, принадлежащий к одной из категорий сравнения, чьё значение отражает вид отношения между сравниваемыми объектами. Существует три основных категории:

  • strong_ordering: отношение линейного порядка, при котором равенство подразумевает взаимозаменяемость элементов (т.е. (a <=> b) == strong_ordering::equal подразумевает, что для всех подходящих функций f имеет место f(a) == f(b). Термину «подходящая функция» намеренно не даётся чёткого определения, но к таковым не относятся функции, которые возвращают адреса своих аргументов или capacity() вектора и т.п. Нас интересуют только «существенные» свойства, что тоже очень расплывчато, но можно условно считать, что речь идёт о значении типа. Значение вектора — это содержащиеся в нём элементы, но не его адрес и т.п.). Эта категория включает в себя следующие значения: strong_ordering::greater, strong_ordering::equal и strong_ordering::less.
  • weak_ordering: отношение линейного порядка, при котором равенство определяет лишь некоторый класс эквивалентности. Классический пример — нечувствительное к регистру сравнение строк, когда два объекта могут быть weak_ordering::equivalent, но не равны в строгом смысле (этим объясняется замена слова equal на equivalent в имени значения).
  • partial_ordering: отношение частичного порядка. В этой категории к значениям greater, equivalent и less (как в weak_ordering) добавляется ещё одно — unordered («неупорядоченно»). С его помощью можно выражать отношения частичного порядка в системе типов: 1.f <=> NaN даёт значение partial_ordering::unordered.

В основном вы будете работать с категорией strong_ordering; это также оптимальная категория для использования по умолчанию. Например, 2 <=> 4 возвращает strong_ordering::less, а 3 <=> -1 strong_ordering::greater.

Категории более сильного порядка могут неявно приводиться к категориям более слабого порядка (т.е. strong_ordering приводимо к weak_ordering). При этом текущий вид отношения сохраняется (т.е. strong_ordering::equal превращается в weak_ordering::equivalent).

Значения категорий сравнения можно сравнивать с литералом 0 (не с любым int и не с int, равным 0, а просто с литералом 0) с помощью одного из шести операторов сравнения:

strong_ordering::less < 0     // true
strong_ordering::less == 0    // false
strong_ordering::less != 0    // true
strong_ordering::greater >= 0 // true

partial_ordering::less < 0    // true
partial_ordering::greater > 0 // true

// unordered - особое значение, которое невозможно
// сравнить ни с каким другим значением
partial_ordering::unordered < 0  // false
partial_ordering::unordered == 0 // false
partial_ordering::unordered > 0  // false

Именно благодаря сравнению с литералом 0 мы можем реализовывать операторы отношения: a @ b эквивалентно (a <=> b) @ 0 для каждого из таких операторов.

Например, 2 < 4 можно вычислить как (2 <=> 4) < 0, что превращается в strong_ordering::less < 0 и даёт значение true.

На роль базового элемента оператор <=> подходит намного лучше, чем оператор <, поскольку он избавлен от обеих проблем последнего.

Во-первых, выражение a <= b гарантированно эквивалентно (a <=> b) <= 0 даже при частичном порядке. Для двух неупорядоченных значений a <=> b даст значение partial_ordered::unordered, а partial_ordered::unordered <= 0 даст false, что нам и требуется. Это возможно потому, что <=> может вернуть больше разновидностей значений: так, категория partial_ordering содержит четыре возможных значения. Значение типа bool может быть только true или false, поэтому раньше мы не могли различать сравнения упорядоченных и неупорядоченных значений.

Для большей ясности рассмотрим пример отношения частичного порядка, не связанный с числами с плавающей запятой. Допустим, мы хотим добавить типу int состояние NaN, где NaN — это просто значение, которое не образует упорядоченной пары ни с одним задействованным значением. Сделать это можно, используя для его хранения std::optional:

struct IntNan {
  std::optional<int> val = std::nullopt;
  
  bool operator==(IntNan const& rhs) const {
    if (!val || !rhs.val) {
      return false;
    }
    return *val == *rhs.val;
  }
  
  partial_ordering operator<=>(IntNan const& rhs) const {
    if (!val || !rhs.val) {
      // состояние unordered можно выразить
      // как значение первого класса
      return partial_ordering::unordered;
    }
    
    // <=> возвращает значение strong_ordering для int,
    // но оно может быть неявно приведено к partial_ordering
    return *val <=> *rhs.val;
  }
};

IntNan{2} <=> IntNan{4}; // partial_ordering::less
IntNan{2} <=> IntNan{};  // partial_ordering::unordered

// принцип работы этих операций см. в следующем разделе
IntNan{2} < IntNan{4};   // true
IntNan{2} < IntNan{};    // false
IntNan{2} == IntNan{};   // false
IntNan{2} <= IntNan{};   // false

Оператор <= возвращает правильное значение потому, что теперь мы можем выразить больше информации на уровне самого языка.

Во-вторых, чтобы получить всю необходимую информацию, достаточно один раз применить <=>, что облегчает реализацию лексикографического сравнения:
struct A {
  T t;
  U u;
  
  bool operator==(A const& rhs) const {
    return t == rhs.t &&
      u == rhs.u;
  }
  
  strong_ordering operator<=>(A const& rhs) const {
    // выполняем трёхстороннее сравнение 
    // элементов t. Если результат != 0 (т.е. элементы t
    // различаются), это будет результат
    // всего сравнения
    if (auto c = t <=> rhs.t; c != 0) return c;
    
    // в противном случае сравниваем
    // следующую пару элементов
    return u <=> rhs.u;
};

Более подробный разбор см. в P0515 — исходном предложении по добавлению operator<=>.

Новые возможности операторов


Мы не просто получаем в своё распоряжение новый оператор. В конце концов, если бы показанный выше пример с объявлением структуры A говорил лишь о том, что вместо x < y теперь придётся всякий раз писать (x <=> y) < 0, это никому бы не понравилось.

Механизм разрешения сравнений в C++20 заметно отличается от старого подхода, но это изменение напрямую связано с новой концепцией двух базовых операторов сравнения: == и <=>. Если раньше это была идиома (запись через == и <), которой пользовались мы, но о которой не знал компилятор, то теперь и он будет понимать это различие.

Ещё раз приведу таблицу, которую вы уже видели в начале статьи:
Равенство
Упорядочение
Базовые
==
<=>
Производные
!=
<, >, <=, >=

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

Обращение базовых операторов


В качестве примера возьмём тип, который может сравниваться только с int:

struct A {
  int i;
  explicit A(int i) : i(i) { }
  
  bool operator==(int j) const { 
    return i == j;
  }
};

С точки зрения старых правил, нет ничего удивительного в том, что выражение a == 10 работает и вычисляется как a.operator==(10).

Но как насчёт 10 == a? В C++17 это выражение считалось бы явной синтаксической ошибкой. Не существует такого оператора. Чтобы такой код заработал, пришлось бы писать симметричный operator==, который бы сначала брал значение int, а затем A… а реализовывать это пришлось бы в виде свободной функции.

В C++20 базовые операторы могут быть обращены. Для 10 == a компилятор найдёт кандидат operator==(A, int) (на самом деле это функция-член, но для наглядности я пишу её здесь как свободную функцию), а затем дополнительно — вариант с обратным порядком параметров, т.е. operator==(int, A). Этот второй кандидат совпадает с нашим выражением (причём идеально), так что его мы и выберем. Выражение 10 == a в C++20 вычисляется как a.operator==(10). Компилятор понимает, что равенство симметрично.

Теперь расширим наш тип так, чтобы его можно было сравнивать с int не только через оператор равенства, но и через оператор упорядочения:

struct A {
  int i;
  explicit A(int i) : i(i) { }
  
  bool operator==(int j) const { 
    return i == j;
  }
  
  strong_ordering operator<=>(int j) const {
    return i <=> j;
  }
};

Опять же, выражение a <=> 42 работает прекрасно и вычисляется по старым правилам как a.operator<=>(42), но вот 42<=> a было бы неправильно с точки зрения C++17, даже если бы оператор <=> уже существовал в языке. Но в C++20 operator<=>, как и operator==, симметричен: он распознаёт обращённые кандидаты. Для 42 <=> a будет найдена функция-член operator<=>(A, int) (опять же, я пишу её здесь как свободную функцию просто для большей наглядности), а также синтетический кандидат operator<=>(int, A). Этот обращённый вариант точно соответствует нашему выражению — его и выбираем.

Однако 42 <=> a вычисляется НЕ как a.operator<=>(42). Так было бы неправильно. Это выражение вычисляется как 0 <=> a.operator<=>(42). Попробуйте сами догадаться, почему эта запись — правильная.

Важно отметить, что никаких новых функций компилятор не создаёт. При вычислении 10 == a не появился новый оператор operator==(int, A), а при вычислении 42 <=> a не появился operator<=>(int, A). Просто два выражения переписаны через обращённые кандидаты. Повторю: никаких новых функций не создаётся.

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

struct B {
   bool operator!=(int) const;
};

b != 42; // ok и в C++17, и в C++20
42 != b; // ошибка и в C++17, и в C++20

Переписывание производных операторов


Вернёмся к нашему примеру со структурой A:

struct A {
  int i;
  explicit A(int i) : i(i) { }
  
  bool operator==(int j) const { 
    return i == j;
  }
  
  strong_ordering operator<=>(int j) const {
    return i <=> j;
  }
};

Возьмём выражение a != 17. В C++17 это синтаксическая ошибка, потому что не существует оператора operator!=. Однако в C++20 для выражений, содержащих производные операторы сравнения, компилятор будет также искать соответствующие им базовые операторы и выражать через них производные сравнения.

Мы знаем, что в математике операция != по сути означает НЕ ==. Теперь это известно и компилятору. Для выражения a!= 17 он будет искать не только операторы operator!=, но и operator== (а также, как в предыдущих примерах, обращённые operator==). Для данного примера мы нашли оператор равенства, который нам почти подходит, — нужно только переписать его в соответствии с желаемой семантикой: a != 17 будет вычисляться как !(a == 17).

Аналогично, 17 != a вычисляется как !a.operator==(17), что является одновременно и переписанным, и обращённым вариантом.

Похожие преобразования проводятся и для операторов упорядочения. Если бы мы написали a < 9, то попытались бы (безуспешно) найти operator<, а также рассмотрели бы базовые кандидаты: operator<=>. Соответствующая замена для операторов отношения выглядит так: a @ b (где @ — один из операторов отношения) вычисляется как (a <=> b) @ 0. В нашем случае — a.operator<=>(9) < 0. Аналогично, 9 <= a вычисляется как 0 <= a.operator<=>(9).

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

Вышесказанное приводит меня к следующему совету:

ТОЛЬКО БАЗОВЫЕ ОПЕРАТОРЫ: В своём типе определяйте только базовые операторы (== и <=>).

Поскольку базовые операторы дают весь набор сравнений, то и определять достаточно только их. Это значит, что вам понадобится только 2 оператора для сравнения однотипных объектов (вместо 6, как сейчас) и только 2 оператора для сравнения разнотипных объектов (вместо 12). Если вам нужна только операция равенства, то достаточно написать 1 функцию для сравнения однотипных объектов (вместо 2) и 1 функцию для сравнения разнотипных объектов (вместо 4). Класс std::sub_match представляет собой крайний случай: в C++17 в нём используется 42 оператора сравнения, а в C++20 — только 8, при этом функциональность никак не страдает.

Так как компилятор рассматривает также обращённые кандидаты, все эти операторы можно будет реализовывать как функции-члены. Больше не придётся писать свободные функции только ради сравнения разнотипных объектов.

Особые правила поиска кандидатов


Как я уже упоминал, поиск кандидатов для a @ b в C++17 происходил по следующему принципу: находим все операторы operator@ и выбираем из них наиболее подходящий.

В C++20 используется расширенный набор кандидатов. Теперь мы будем искать все operator@. Пусть @@ — это базовый оператор для @ (это может быть один и тот же оператор). Мы также находим все operator@@ и для каждого из них добавляем его обращённую версию. Из всех этих найденных кандидатов выбираем наиболее подходящий.

Заметьте, что перегрузка оператора разрешается за один-единственный проход. Мы не пытаемся подставлять разные кандидаты. Сначала мы собираем их все, а затем выбираем из них наилучший. Если такого не существует, поиск, как и раньше, заканчивается неудачей.

Теперь у нас гораздо больше потенциальных кандидатов, а значит и больше неопределённости. Рассмотрим следующий пример:

struct C {
  bool operator==(C const&) const;
  bool operator!=(C const&) const;
};

bool check(C x, C y) {
  return x != y;
}

В C++17 у нас был только один кандидат для x != y, а теперь их три: x.operator!=(y), !x.operator==(y) и !y.operator==(x). Что же выбрать? Они все равнозначны! (Примечание: кандидата y.operator!=(x) не существует, так как обращать можно только базовые операторы.)

Для снятия этой неопределённости введены два дополнительных правила. Необращённые кандидаты предпочтительнее обращённых; непереписанные кандидаты предпочтительнее переписанных. Тогда получается, что x.operator!=(y) «главнее» !x.operator==(y), а тот «главнее» !y.operator==(x). Этот принцип согласуется со стандартными правилами, по которым «побеждает» наиболее точный вариант.

Ещё одно замечание: на этапе поиска нас не интересует тип возвращаемого значения кандидатов operator@@. Мы просто находим их. Нас интересует только, являются ли они наилучшим выбором или нет.

Неудачный исход при поиске теперь тоже выглядит по-другому. Если наилучший кандидат — переписанный или обращённый (например, мы написали x < y, а наилучший кандидат — это (x <=> y) < 0), но корректно переписать или обратить сравнение невозможно (например, x <=> y возвращает void или какой-то иной тип, потому что мы вообще пишем на DSL), то программа считается некорректной. Возвращаться и искать другой подходящий вариант мы уже не будем. В случае с операцией равенства мы принимаем, что никакой тип возвращаемого значения кроме bool не совместим с переписанными кандидатами (логика здесь такая: если operator== не возвращает bool, можем ли мы считать такую операцию операцией равенства?)

Например:

struct Base { 
  friend bool operator<(const Base&, const Base&);  // #1
  friend bool operator==(const Base&, const Base&); 
}; 
struct Derived : Base { 
  friend void operator<=>(const Derived&, const Derived&); // #2
}; 
bool f(Derived d1, Derived d2) {
  return d1 < d2;
} 

Для выражения d1 < d2 будут найдены два кандидата: #1 и #2. Наилучший вариант — #2, так как он является точным совпадением, значит, его и выбираем. Поскольку это переписанный кандидат, то d1 < d2 вычисляется как (d1 <=> d2) < 0. Но это некорректное выражение, ведь нельзя сравнивать void с 0 — значит, и всё сравнение некорректно. Заметьте, что после этой неудачи мы уже не будем совершать какие-либо действия, чтобы выбрать кандидат #1.

Краткий обзор правил


Очевидно, что эти правила сложнее тех, что были в C++17, но я привожу их полностью в этом небольшом разделе. Здесь не будет сносок, посвящённых каким-то особым случаям или исключениям. Просто запомните самые главные принципы:

  • Обращение доступно только для базовых операторов
  • Переписываться могут только производные операторы (через соответствующие базовые)
  • При поиске кандидатов за один проход ищутся все операторы с данным именем, а также все их обращённые и переписанные версии
  • Если наилучший кандидат является переписанной или обращённой версией и при этом такая замена является недопустимой, программа считается некорректной.

Если вы будете следовать этому совету и определять ТОЛЬКО БАЗОВЫЕ ОПЕРАТОРЫ, вам и не придётся беспокоиться обо всём этом. Все ваши сравнения будут работать.

Для ясности я привожу таблицу со всеми возможными преобразованиями на уровне исходного кода. В каждом случае выражение в первом столбце имеет больший приоритет, чем выражение во втором, а то, в свою очередь, имеет больший приоритет, чем выражение в третьем столбце (при прочих равных условиях). Обратите внимание, что второй и третий столбцы содержат только базовые операторы:
Исходная операция
Вариант 1
Вариант 2
a == b
b == a

a != b
!(a == b)
!(b == a)
a <=> b
0 <=> (b <=> a)

a < b
(a <=> b) < 0
(b <=> a) > 0
a <= b
(a <=> b) <= 0
(b <=> a) >= 0
a > b
(a <=> b) > 0
(b <=> a) < 0
a >= b
(a <=> b) >= 0
(b <=> a) <= 0

Варианты с «космическим кораблём» в правом столбце обычно пишутся с тем же оператором, что и в исходной версии, т.е. a < b пишется как 0 < (b <=> a), но я написал их с противоположными знаками, чтобы нагляднее показать, как меняется знак в переписанной версии.

Определение сравнений для использования по умолчанию


Среди прочего в C++17 раздражает необходимость подробно расписывать поэлементные лексикографические сравнения. Это занятие утомительно и чревато ошибками. Напишем полный набор операторов для линейно упорядоченного типа с тремя членами:

struct A {
  T t;
  U u;
  V v;
  
  bool operator==(A const& rhs) const {
    return t == rhs.t &&
      u == rhs.u &&
      v == rhs.v;
  }
  
  bool operator!=(A const& rhs) const {
    return !(*this == rhs);
  }
  
  bool operator< (A const& rhs) const {
    // я предпочитаю этот стиль, потому что так сложнее ошибиться,
    // чем если использовать вложенные ?: или &&/||
    if (t < rhs.t) return true;
    if (rhs.t < t) return false;
    if (u < rhs.u) return true;
    if (rhs.u < u) return false;
    return v < rhs.v;
  }

  bool operator> (A const& rhs) const {
    return rhs < *this;
  }
  
  bool operator<=(A const& rhs) const {
    return !(rhs < *this);
  }
  
  bool operator>=(A const& rhs) const {
    return !(*this < rhs);
  }
};

Ещё лучше было бы использовать какой-нибудь std::tie(), но это всё равно утомительно.

Теперь давайте попробуем написать ту же структуру, следуя моему совету: определять только базовые операторы:

struct A {
  T t;
  U u;
  V v;
  
  bool operator==(A const& rhs) const {
    return t == rhs.t &&
      u == rhs.u &&
      v == rhs.v;
  }
  
  strong_ordering operator<=>(A const& rhs) const {
    // сравниваем элементы T
    if (auto c = t <=> rhs.t; c != 0) return c;
    // ... теперь U
    if (auto c = u <=> rhs.u; c != 0) return c;
    // ... теперь V
    return v <=> rhs.v;
  }
};

Тут не просто меньше кода. Сама реализация <=> гораздо проще для понимания по сравнению с реализацией <. Она очевидней, поскольку полное сравнение можно выполнить за один проход. Проверки c != 0 не дадут нам продолжить, если мы обнаружим пару неравных значений, и каким бы отношением ни было выражено это неравенство (меньше или больше), это будет окончательный результат сравнения.

В итоге получается обычное поэлементное лексикографическое сравнение по умолчанию. А в C++20 достаточно просто сказать компилятору, что мы хотим:

struct A {
  T t;
  U u;
  V v;
  
  bool operator==(A const& rhs) const = default;
  strong_ordering operator<=>(A const& rhs) const = default;
};

Нужно явно указать, какие операторы сравнения должен сгенерировать компилятор по умолчанию. Наш код можно ещё упростить, если категорию сравнения определять автоматически:

struct A {
  T t;
  U u;
  V v;
  
  bool operator==(A const& rhs) const = default;
  auto operator<=>(A const& rhs) const = default;
};

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

struct A {
  T t;
  U u;
  V v;
  
  auto operator<=>(A const& rhs) const = default;
};

Это единственный случай, когда компилятор сгенерирует оператор сравнения, который вы сами не писали. Последние два варианта абсолютно идентичны: у нас есть и заданный по умолчанию operator==, и заданный по умолчанию operator<=>.

Темы будущих статей


В этой статье мы рассмотрели основы сравнений в C++20: как работают синтетические кандидаты и как они находятся. Мы также коротко рассмотрели трёхстороннее сравнение и особенности его реализации. У меня в запасе есть ещё несколько интересных тем, которые тоже стоит осветить, но я стараюсь писать не слишком длинные статьи, так что ждите новых постов.

Примечание переводчика


Команда PVS-Studio с интересом познакомилась с этой статьей, так как нам в ближайшее время предстоит реализовать поддержку нового оператора <=> в анализаторе. А поскольку статья очень полезная и хорошо всё объясняет, мы решили сделать её перевод для хабра-сообщества. На наш взгляд, это очень нужное нововведение языка, так как по нашему опыту операторы сравнения очень часто содержат ошибки (см. статью "Зло живёт в функциях сравнения"). Теперь С++ программистам жить станет проще и ошибок данного типа будет меньше.

Заодно возникла идея создать в PVS-Studio новую диагностику для поиска некорректно написанных операторов <, которые были описаны в статье:

bool operator< (A const& rhs) const {
  return t < rhs.t && u < rhs.u;
}

Подобный код может присутствовать в старых больших проектах. Возможно, и ещё какие-то диагностики сделаем. Надо подумать.

Первоисточник: Comparisons in C++20.
PVS-Studio
500,40
Static Code Analysis for C, C++, C# and Java
Поделиться публикацией

Комментарии 54

    +3
    Выражение a == b никогда не будет вычисляться как operator<=>(a, b) == 0 неявно

    имо зря убрали
      +2

      Вероятно это было сделано для исключения возможной путаницы при использовании strong_ordering::equal и weak_ordering::equivalent.

        +3
        для strong_ordering то в чем проблема генерировать ==? Это же для других из эквивалентности может не следовать равенство.
        +1
        На самом деле не убрали: eel.is/c++draft/class#compare.default-3
        В начале статьи неточность, но ниже говорится что на самом деле будет использоваться operator<=> «Это единственный случай, когда компилятор сгенерирует оператор сравнения, который вы сами не писали.»
          0

          При чём здесь operator<=>? По вашей ссылке говорится — так же как и в статье — что при указанных условиях компилятор сгенерирует operator==, но последний будет определён как =default, а не через operator<=>.

        –2
        ЕСЛИ (меньше-больше-или-равно )

        Идея полезная, но синтаксис не просто режет глаз, это скорее штопор, в этот самый глаз вкручиваемый.
        –5
        struct A {
        T t;
        U u;
        V v;

        T, U и V — это где-то в другом месте определенные типы данных? Очень уж давно учил, но подобный код встречал для идеи функции с жуткой рекурсией для определения «очень большого числа».
          +2
          очень похоже на урезанное заимстование из Хаскеля класс-типов Равенства Eq и Порядка Ord
          class Eq a where  
              (==) :: a -> a -> Bool  
              (/=) :: a -> a -> Bool  
              x == y = not (x /= y)  
              x /= y = not (x == y) 

          Где достаточно определить либо равенство, либо неравенство, и второе будет вычислено как не-первое.
          Операции сравнения:
          class  (Eq a) => Ord a  where
            compare, (<), (<=), (>=), (>)  :: a -> a -> Bool
            max, min              :: a -> a -> a

          Где минимально и достаточно определить лишь функции compare и (<=)
            +1

            В известном смысле оно не урезанное, а улучшенное (и на самом деле не из Хаскелла, а из математики). Улучшенное потому, что как раз в Хаскелле (в стандартном Prelude) нет аналога partial_ordering.

              0
              Почему же нет, есть. Надо просто определить обе функции, а не минимальный набор
                +1

                Нельзя. Ord — это класс линейно упорядоченных типов и реализация обязана быть консистентной и не нарушать соответствующих свойств, в частности forall a b. (Ord a, Ord b) => a <= b || b <= a. Для NaN соответствующее свойство нарушается, и из-за этого, например, алгоритм сортировки списка выдаёт непредсказуемый результат на списке, содержащем NaN.

                  –2
                  Не очень понятно зачем держать в списке NaN, код построеный на таких допущениях кривой уже на уровне архитектуры. Это надо фиксить не на уровне языка. А есть другие примеры кроме NaN? Иначе это может трактоваться как новый способ отстрела ног, то есть теперь вместо сортировки нога отстрелится на попытке деления или чего подобного.
              +1

              Да почему же только из Хаскелля. В том же Rust, насколько я помню, чуть ли не с самого начала есть трейты PartialEq/Eq и PartialOrd/Ord… Правда, никакого аналога weak_ordering я там не помню (если вернул Ordering::Equal, значит, значения равны), это да.

                0

                (комментарий был удален)

              0
              Наш код можно ещё упростить, если категорию сравнения определять автоматически:

              И какая же категория будет выведена автоматически?

                0
                в зависимости от возвращаемого значения operator <=> для полей структуры/класса
                +5

                Невероятно, но это тот самый случай, когда я начинал читать статью с мыслями "не надо трогать мой любимый С++, и без космических кораблей жилось хорошо", а закончил с мыслями "как я раньше без этого жил" :)


                Интересно, что про spaceship говорили еще после С++14 вроде, но тогда по прочтении я еще не пробовал функциональные языки вроде Haskell или даже Rust. Теперь понять смысл почему это так удобно намного проще.


                Кажется и правда функциональщина мозги вправляет) Или просто шишек себе уже набил за эти годы обо все эти операторы)

                  0
                  А в чом проблема, господа?
                  Кто писал операторы <, >, = так и дальше смогут их писать, для них ничего не изменилось.
                  А единый оператор <=> позволяет компилятору вывести все остальные автоматически.
                    –1
                    — Я никогда не писал "<=>"
                    — Ладно, не заливай! Ни разу не писал оператор трехстороннего сравнения?!
                    — Не довелось как-то, не вышло…
                    — Ну ты даешь! Не знал, что на конференциях и даже на хабре никуда без этого?! Пойми. Там только и говорят что про оператор "<=>". Как он бесконечно прекрасен. О коде, который они видели. О том, как код, словно по волшебству, становится короче, делая то же самое, что стало легче сравнивать вещественные числа и строки, без учёта регистра. А ты? Что ты им скажешь? Там тебя окрестят лохом!..
                      0
                      большинство операторов сравнения в стандартной библиотеке заменили на <=>
                  –2
                  Классический пример — числа с плавающей запятой, для которых любая из операций 1.f < NaN, 1.f == NaN и 1.f > NaN даёт ложь. Поэтому 1.f <= NaN также даёт ложь, но при этом !(NaN < 1.f) — правда.

                  Мы ж на Хабре, и вроде как не для 1С-ников пишем, зачем true и false переводить-то?..

                    0
                    Итак, у нас есть строка.
                    Раньше я реализовывал оператор скажем < следующим образом:
                    if (a.length()<b.length())
                    return true;
                    … а здесь более сложная логика, когда все таки длины у них одинаковые и надо уже идти проверять что там внутри.

                    Таким образом оператор < в подавляющем количестве вызовов был очень быстрым, т.к. тупо сводился к проверке длины.

                    Теперь мне говорят — для упрощения кода, ты можешь определить spaceship и
                    ВСЕГДА будет вызываться условный compare при сравнении.
                    То есть оператор < автоматически сегенерируется как:
                    return a.compare(b) < 0;

                    Эффективный код? Забудьте. compare(spaceship) сделает все возможные проверки, чтобы точно рассказать о том, какие отношения у двух переменных. Даже если вам это не надо.
                    Но ведь никто не запрещает определить оператор < и не оставлять его генератору!!!
                    Ага. Поэтому люди которые рассказывают какой классный spaceship — почему-то приводят в пример как раз строки и другие сложные структуры.
                    Как плюс выставляя тот факт, что теперь не надо писать сложные проверки а можно все делать через один оператор. То есть даже сами эксперты умалчивают о проблеме избыточности оператора, даже там где это актуально.
                    Второй момент — для кого нужен этот оператор?
                    Для тех, кто пишет много не типичных классов с переопределенными операторами. то есть 99% пользователей этой фичи — писатели библиотек. И уж они то будут пользоваться по полной, чтобы оптимизировать время написания кода.
                    Поздравляю, с внедрением spaceship библиотеки которыми вы пользуетесь станут еще медленней.

                    UPD: для минусующих карму.
                    Каждый раз, когда я высказываюсь с критикой изменений в С++ мне приходят минусовать карму.
                    Господа минусующие — вы идиоты. Чтобы указать на неверность критики — надо минусовать комментарий и комментировать контраргументами. Это видно и это показывает ваше отношение к конкретному высказыванию. Минусуя карму вы просто затыкаете критика.
                    Критика(даже глупая) не вредит стандарту, потому что специалист видит несостоятельность утверждения и игонрирует критику. А полезная критика заставляет задуматься и изменить что-то если надо.
                    Минусуя карму в такой ситуации вы просто увеличиваете вероятность, что проблема не будет замечена, потому что тот кто ей видит(или считает что видит) — предпочтет промолчать, зная что придут фантики которые его будут сливать.
                      +3

                      Так и в spaceship можно точно так же сразу первой строчкой проверить length и сразу тут же и вернуть XXX_ordering::less, почему обязательно "все возможные проверки" — то?

                        0
                        Вы цепляетесь к деталям, игнорируя общий посыл.
                        Давайте чуть более абстрактно.
                        Есть две дорогих проверки первая проверка
                        A > B
                        вторая проверка
                        A < B
                        Если я делаю отдельные операции > и <, то каждая из них будет содержать только одну дорогую проверку, нужную в конкретном случае.
                        Если же я буду делать через spaceship — не получится для обеих операторов сделать дешево.
                        Либо при сравнении A > B будет сначала идти ненужное
                        if (A< B) return XXX_ordering::less;
                        а только потом сработающее
                        if (A > B) return XXX_ordering::greater;
                        либо наоборот.

                        Суть в том, что spaceship не знает и не может знать, какие проверки нам нужно делать в конкретном случае, а какие нет. Это общая большая функция вычисляющая отношение между переменные в деталях, даже если нам эти детали не нужны.
                          +3
                          Разговоры «в общем» — это, конечно, здорово, но малоконструктивно :) Обычно пишут что-нибудь вроде «вот конкретный код с operator <, а вот эквивалентный с operator <=>, я считаю, что он будет работать медленнее в таких-то и таких-то случаях потому-то и потому-то». Желательно еще сделать тесты, что это замедление действительно заметно на реальных задачах, скажем, при сортировке, поиске и так далее. Вот на КОНКРЕТНЫЙ пример с предварительным сравнением length я и ответил, а лить воду «в общем» — увольте.

                          P.S. в общем-то и до spaceship'а обычно реализовывали всего два оператора — "==" и "<", а все остальные выражали через них путем вызова этих двух.

                          P.P.S.

                          if (A< B) return XXX_ordering::less;
                          if (A > B) return XXX_ordering::greater;

                          Почему не return A <=> B?
                            +1
                            Это код внутри A<=>B
                              +3

                              Внутри operator <=> тоже можно и нужно сравнивать члены структуры или класса в свою очередь через их operator <=>. Ну, это так, детали.

                                +1
                                Для сравнения часто недостаточно просто взять переменные и их сравнить.
                                Сначала нужно провести определенные вычисления.
                                Ок, я пока помолчу и сделаю пример, раз вы так настойчиво не воспринимаете идею на абстрактных примерах.
                                  +1

                                  Да, это было бы хорошо, чтобы, так сказать, в цифрах вы подкрепили как-то свои опасения. Я думаю, что если бы в std из-за этой замены будет реальная регрессия в плане производительности, это будет замечено на тестах.

                                    +1
                                    В std не будет регрессии, там уже все операторы друг через друга выведены.
                                    Ну и в std простые типы, там не требуется делать никаких вычислений для того чтобы провести сравнение.
                                      +1

                                      Ну да, и я к тому же. У вас же были опасения что вот мол писатели библиотек будут это использовать и будет медленно, std — это библиотека, и вряд ли там будет какая-то регрессия из-за применения этого оператора. А в сложных ситуациях можно написать каждый оператор отдельно, это уже up to автор библиотеки. Если у автора затруднения с написанием эффективного кода, то operator <=> — не единственное место, где это проявится :) В общем, я думаю, что проблема несколько надуманна.

                            +1
                            Либо при сравнении A > B будет сначала идти ненужное
                            if (A< B) return XXX_ordering::less;
                            а только потом сработающее
                            if (A > B) return XXX_ordering::greater;
                            либо наоборот.

                            А вот это заведомо плохой код. Вам нужно вызывать оператор A <=> B.
                            Суть оператора spaceship — не в оптимизации скорости выполнения, а в значительном сокращении количества кода.

                              +1
                              А код A<=>B у вас как работать будет? Что у вас внутри реализации самого spaceship?
                                +1

                                Точно так же. Предполагается, что этот оператор существует для всех типов.

                                  0
                                  Сравнение сложных типов далеко не всегда сводится к сравнению их полей.
                                  Часто нужно делать доп вычисления, например.
                                    +1

                                    Ну так ничто не мешает использовать новый оператор в дополнительных вычислениях. Мне сложно представить пример, где этот оператор приводил бы к проблемам.


                                    Приводимый вами пример для строчек — плохой, потому что он прекрасно решается новым оператором без каких-либо проблем.

                          –2

                          C++ уже давно стал языком, который не особо жизнеспособен без оптимизирующего компилятора. Так что никаких проблем с производительностью не будет.

                            +1
                            Крутая оптимизация С++ это спорная штука, рассчитывать на неё не самое правильное решение.
                            Ну и в целом подход «пишу как хочу, компилятор сам всё сделает» не работает на практике.
                              0

                              Если не рассчитываете на оптимизацию, то пишите на C, а не на C++.

                                +1
                                А в С завезли ООП разве?
                                  –2
                                  А разве нет? Правда, бойлерплейта больше, а так да, завезли)
                            0
                            P.S. Кстати, я как-то сначала пропустил начальную фразу «итак, у нас есть строка». То есть вы при сравнении строк сразу считали, что одна строка «меньше» другой, если ее длина меньше? То есть по вашему алгоритму сравнения, скажем, строка «B» должна идти впереди строки «AA»? Но почему? Ведь должно быть ровно наоборот. Или я что-то не понял в сути вашего алгоритма?
                              +1
                              Семантика сравнения срок контекстозависимая.
                              Например, стандартное сравнение считает что «15» < «2». В зависимости от задачи это может быть как приемлемо, так и не приемлемо. Поэтому обсуждать абстрактное сравнение срок в отрыве от конкретной задачи достаточно бессмысленное дело.
                                0
                                Ну так-то обычно все-таки считается, что идет сначала «AA», а потом «B». Впрочем, я не спорю, что если нет задачи представления отсортированного списка человеку в, так сказать, «привычном виде», то алгоритм может быть какой угодно, лишь бы работал по понятным и однозначным правилам.
                            0

                            Удобней же структуры сравнивать по другому, по очереди для всех полей проверяешь что они не равны, и если это так возвращаешь первый меньше второго, ну и с последним так же. Получается n сравнений в худшем случае, вместо 2*n-1, более того они могут быть легковеснее, так как сравнение на неравенство может быть реализовано эффективнее сравнения на меньше.

                              0

                              Можете пояснить мысль? Идея оператора <=> возникла не на пустом месте. Процессору нужна всего одна инструкция, чтобы вычислить все 6 операций сравнения для целых чисел.

                                0
                                Всё так, моя идея относится к коду до С++20, а более оптимальный код может получиться в дебажной сборке или например лексографическом компараторе.
                                Вместо:
                                bool operator< (A const& rhs) const {
                                if (t < rhs.t) return true;
                                if (rhs.t < t) return false;
                                return u < rhs.u;
                                }

                                Использую:
                                bool operator< (A const& rhs) const {
                                if (t != rhs.t) return t < rhs.t;
                                return u < rhs.u;
                                }

                                Мой вариант может быстрее если t и rhs.t лексикографические строки разной длины, тогда если для сравнения их на меньше нужно пробежать до первого расхождения, а в сравнении на неравенство — вначале стоит проверка на длину.
                                Чисто теоретически компилятор может все понять и соптимизировать до эквивалентного кода — но на практике это не работает: код.
                                Спейсшип должен решить эту проблему.
                                  0
                                  Мой вариант может быстрее если t и rhs.t лексикографические строки разной длины

                                  но медленнее при равной длине. Собственно, для обхода этой несуразицы и был придуман std::string::compare
                                  0
                                  На удивление у clang-а при использовании spaceship-а сейчас ассемблер выглядит значительно хуже — 8 сравнений, лишние сдвиги и арифметика.
                                    0

                                    Он вообще какую-то дичь выдал, вроде:


                                      cmp edx, ecx
                                      setae al
                                      cmp edx, ecx

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое