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

Question

Как определить operator< на n-кортеже (например, на 3-кортеже), чтобы он удовлетворял строгой концепции слабого упорядочения? Я знаю, что библиотека Boost имеет класс кортежа с правильно определенным 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]

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) являются ложными. Обратите внимание, что объект всегда (по инварианту нерефлексивности) эквивалентен самому себе.

В терминах 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 с соответствием operator< который сначала сравнивает самый левый элемент, затем работает вдоль кортежа, пока результат не станет ясным. Это подходит для обеспечения строгого слабого порядка, ожидаемого, например, std::set а также std::map,

Если у вас есть данные в некоторых других переменных (например, поля в struct), вы даже можете использовать std::tie() to создает кортеж ссылок, который затем можно сравнить с другим таким кортежем. Это облегчает написание 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

Основной поток должен быть таким: если элементы Kth отличаются, возвращаемое значение меньше, а переход к следующему элементу. Следующий код предполагает, что у вас нет буст-кортежа, иначе вы бы использовали 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 5

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

Answer 6

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

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

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

Answer 7

Обратите внимание, что интересно,operator <который всегда возвращаетсяfalseотвечает требованиям строгой слабой упорядоченности .