Как правильно написать operator < в C++

Если вы захотите использовать свой класс в качестве ключа в std::map/std::multimap или хранить объекты в std::set/std::multiset, с компаратором заданным по-умолчанию, то вам понадобится перегрузить оператор <.
Для него должны выполняться условия:

1. (x < x) == false
2. Если (a < b && b < c) то (a < c)
3. Если (a < b) == true то (b < a) == false

Например, таким условиям удовлетворяет следущая реализация:

struct Test
{
  int a, b;
  std::string s;
  
  bool operator < (const Test &other) const
  {
    if (a < other.a)
      return true;
    
    if (other.a < a)
      return false;
    
    if (b < other.b)
      return true;
    
    if (other.b < b)
      return false;
    
    return s < other.s;
  }
};

Можно также заметить, что потребовались только операторы < для составных частей класса, что в принципе правильно, ведь другие операторы могут отсутствовать, и это не должно нам мешать.
Если оператор будет реализован неправильно, то возможны ошибки и/или срабатывания assert'ов при работе с контейнерами. К примеру реализация

struct Test
{
  int a, b;
  
  // Неправильный оператор
  bool operator < (const Test &other) const
  {
    if (a < other.a)
      return true;
    
    if (b < other.b)
      return true;
    
    return false;
  }
};

неверна, так как если test1.a < test2.a и test1.b > test2.b то test1 < test2 и test2 < test1 оба вернут true, что не удовлетворяет третьему условию.

Если ваш компилятор поддерживает стандарт C++11, то можно записать короче:

struct Test
{
  int a, b;
  std::string s;
  
  bool operator < (const Test &other) const
  {
    return std::tie(a, b, s) < std::tie(other.a, other.b, other.s);
  }
};

или использовать аналогичный функционал из boost. В примере используется tie а не make_tuple, чтобы избежать ненужного копирования, tie() создаёт tuple хранящий ссылки на объекты. Сравнение двух std::tuple идет в лексикографическом порядке по их содержимому, так что результирующий код должен получится эквивалентным приведенному выше.

Объекты a и b считаются эквивалентными если !(a < b) && !(b < a), при этом они могут считаться не равными при использовании оператора ==. При использовании ассоциативных контейнеров используется именно понятие эквивалентности а не равенства. К примеру, результатом выполнения программы:

#include <iostream>
#include <set>
#include <tuple>

struct Test
{
  int a;
  
  Test() : a(0) {}
  Test(int a) : a(a) {}
  
  bool operator == (const Test &other) const
  {
    return a == other.a;
  }
  
  bool operator < (const Test &other) const
  {
    return false; // Все объекты считаются эквивалентными
  }
};

int main()
{
  std::set<Test> s;
  
  // В эти две переменные будем сохранять результат операции вставки
  std::set<Test>::iterator it;
  bool is_inserted;
  
  tie(it, is_inserted) = s.insert(Test(5));
  std::cout << "Test(5) " << is_inserted << std::endl;
  
  tie(it, is_inserted) = s.insert(Test(1));
  std::cout << "Test(1) " << is_inserted << std::endl;
  
  tie(it, is_inserted) = s.insert(Test(7));
  std::cout << "Test(7) " << is_inserted << std::endl;
  
  return 0;
}

будет:

Test(5) 1
Test(1) 0
Test(7) 0

т.е. успешно добавится в контейнер только первый объект, остальные будут считаться эквивалентными с первым и добавлены не будут. Оператор == не используется совсем.

Также при написании оператора < можно озаботится производительностью, например в начале сравнивать переменные, которые более вероятно будут отличаться друг от друга, сравнивать сначала объекты, для которых эта операция наименее дорогая (сначала int потом string), использовать string::compare() взамен двух возможных вызовов operator < и т.д.

#C++, #operator <

12 декабря 2011

Комментарии [112]