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

Question

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

Answer 1

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

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

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

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

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 2

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 3

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

C ++ 11 решение

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

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

Answer 5

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

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