Строго слабая путаница

Question

Меня смущает строгий слабый порядок и то, как его использовать при определении оператора<. У меня есть пара структур:

struct Plane
{
    std::string name;

    int xrudder;
    int yrudder;

    int wingwidgets;

    bool hasLegacyEngine;
};


struct Airport
{
    bool securityCheck;
    unsigned __int64 capacity;

    std::vector<Plane> planes;
};

и я хочу создать std::set аэропортов. Мне нужно определить оператор<, который использует строгий слабый порядок, но я не знаю точно, что это значит и / или как это сделать.

struct cmpless
{
bool operator()(const Airport& left, const Airport& right)
    {
        //?
    }
}; 

std::set<Airport, cmpless> airportSet;

Не имеет смысла, что один аэропорт "меньше" другого. Это имеет смысл, только если аэропорты равны, основываясь на их статистике.

Как я могу быть уверен, что мое определение оператора<будет следовать строгому слабому порядку? Как мне начать думать об определении operator< в такой ситуации?

Пример с объяснением был бы великолепен, если это возможно!

Answer 1

Если это "не имеет смысла" для одного Airport опередить другого Airport тогда использование std::set<Airport> тоже не имеет смысла. Этот контейнер использует элементы суммы заказа, чтобы найти объекты в O(log(n)) операции (где n это размер контейнера). Если вы можете идентифицировать объект только по идентичности, лучшая сложность, которую вы можете достичь, это O(n), Вы можете использовать комбинацию std::find() или же std::find_if() и один из контейнеров последовательности, например, std::vector<Airport> или же std::deque<Airport>,

Поскольку вам не нужно определять порядок с точки зрения operator<()может быть разумным просто принести Airportв некотором порядке с целью их размещения в std::set<Airport> что делается с использованием объекта функции сравнения, отличного от std::less<Airport>, Атрибут, который у вас есть в вашем Airport объект не очень похож на подходящие ключи. На самом деле все они выглядят так, как будто они изменчивы, то есть вы, вероятно, не захотите std::set<Airport> в любом случае, потому что вы не можете изменить элементы в std::set<T> (ну, по крайней мере, вы не должны; да, я понимаю, что вы можете поиграть с mutable но это обязательно нарушит порядок элементов).

Исходя из этого, я бы рекомендовал использовать std::map<std:string, Airport>: std::string используется для идентификации аэропорта, например, с использованием кодов аэропортов, таких как "JFK" для аэропорта Джона Ф. Кеннеди в Нью-Йорке или "LHR" в Лондон Хитроу. Удобно, что для строк уже существует строгий слабый порядок.

Тем не менее, чтобы определить строгий слабый порядок на множестве объектов Oнужно бинарное отношение r(x, y) так что для элементов выполняются следующие условия x, y, а также z от O:

• иррефлексивное: r(x, x) == false
• асимметрично: r(x, y) == true подразумевает r(y, x) == false
• транзитивно: r(x, y) == true а также r(y, z) == true подразумевает r(x, z) == true
• несопоставимость: r(x, y) == false а также r(y, x) == false а также r(y, z) == false а также r(z, y) == false подразумевает r(x, z) == false а также r(z, x) == false

Первые три должны быть достаточно простыми. Последнее на первый взгляд немного странно, но на самом деле это не так сложно: основная идея состоит в том, что отношение не упорядочивает элемент полностью, а группирует их в эквивалентные классы. Если вы думаете об отношении r чтобы быть "меньше, чем" это просто говорит о том, что если ни то, ни другое x меньше чем y ни y меньше чем x, затем x а также y эквивалентны. Несравненные элементы просто эквивалентны.

Стандартные контейнеры работают со строгим слабым порядком, но, например, std::set<T> а также std::map<K, V> оставьте только одну версию эквивалентных ключей. Хорошо, что этого достаточно, но часто проще просто использовать общий порядок, который является строгим слабым порядком, где для каждой пары элементов x а также y или r(x, y) == true или же r(y, x) == true (но из-за асимметрии не оба).

Answer 2

Нашел хорошее решение в блоге musingstudio и решил поделиться им здесь для следующего нуждающегося (даже если Дитмар может быть прав, что карта не подходит):

bool operator <(const T& rhs) const
{
  if (a < rhs.a)
    return true;
  else if (rhs.a < a)
    return false;

  if (b < rhs.b)
    return true;
  else if (rhs.b < b)
    return false;

  // repeat for all child elements c, d, e etc
  return false;
}

Answer 3

Вы можете сделать что-то похожее на лексикографический порядок, если у каждого участника есть < определены:

   struct cmpless
    {
    bool operator()(const Airport& left, const Airport& right)
        {
            return
              left.securityCheck < right.securityCheck
              || ((left.securityCheck == right.securityCheck
                   && left.capacity < right.capacity)
                  || (left.capacity == right.capacity
                      && left.planes < right.planes));
        }
    };