Оператор< и строгий слабый порядок

Question

Как определить operator< на n-кортеже (например, на 3-кортеже) так, чтобы он удовлетворял строгий слабый порядок концепция ?Я знаю, что в библиотеке boost есть класс tuple с правильно определенным operator< но по некоторым причинам я не могу им воспользоваться.

Answer 1

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

Это упорядочивает элементы так, чтобы a1 был наиболее значимым, а a3 - наименее значимым.

Это можно продолжать до бесконечности, вы также могли бы, напримерпримените его к вектору T, повторяя сравнения a[i] < a[i+1] / a[i+1] < a[я].Альтернативным выражением алгоритма было бы "пропустить при равенстве, затем сравнить".:

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

Конечно, если сравнение является дорогостоящим, вы можете захотеть кэшировать результат сравнения.

---

[правка] удален неправильный код

---

[редактировать] если больше, чем просто operator< доступно, я склонен использовать шаблон

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

Answer 2

строгий слабый порядок

Это математический термин для определения взаимосвязи между двумя объектами.
Его определение таково:

Два объекта x и y эквивалентны, если оба f(x, y) и f(y, x) равны false.Обратите внимание, что объект всегда (по инварианту иррефлексивности) эквивалентен самому себе.

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

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

То, как вы определяете эквивалентный / меньший, полностью зависит от типа вашего объекта.

Формальное Определение:
Строгий слабый порядок

Информатика:
Строгий Слабый Порядок

Как это связано с операторами:
Компаратор

Answer 3

...новый ответ на очень старый вопрос, но в существующем ответе отсутствует простое решение из C ++ 11...

Решение на C++ 11

C ++ 11 и более поздних версий обеспечивает std::tuple<T...>, который вы можете использовать для хранения ваших данных. tupleу s есть совпадающий operator< сначала он сравнивает самый левый элемент, затем работает по кортежу до тех пор, пока результат не станет ясен.Это подходит для обеспечения строгий слабый порядок ожидаемый, например, std::set и std::map.

Если у вас есть данные в некоторых других переменных (напримерполя в struct), вы даже можете использовать std::tie() для создания кортежа количество ссылок, который затем можно сравнить с другим таким кортежем.Это облегчает написание operator< для конкретных полей данных участника в определяемом пользователем class/struct Тип:

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

Answer 4

Вы могли бы просто использовать трехэлементные векторы, которые уже будут иметь operator<() соответствующим образом определено.Преимущество этого в том, что оно распространяется на N-элементы без необходимости что-либо делать.

Answer 5

Основной поток должен быть по линиям: если K-й элемент отличается, верните тот, который меньше, иначе перейдите к следующему элементу.Приведенный ниже код предполагает, что вы не надо имейте кортеж boost, иначе вы бы использовали get<N>(tuple) и не иметь проблемы с самого начала.

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

Answer 6

Даже если вы не можете использовать версию boost, вы должны иметь возможность удалить код.Я стащил это из std::pair - думаю, кортеж из 3 будет похож.

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

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