Меня смущает строгий слабый порядок и как его использовать при определении оператора<, У меня есть пара структур:
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<
в такой ситуации?
Пример с объяснением был бы великолепен, если это возможно!
Если это «не имеет смысла» для одного Airport
опередить другого Airport
тогда использование std::set<Airport>
тоже не имеет смысла. Этот контейнер использует элементы суммы заказа, чтобы найти объекты в O(log(n))
операции (где n
это размер контейнера). Если вы можете идентифицировать объект только по идентичности, лучшая сложность, которую вы можете достичь, это O(n)
, Вы можете использовать комбинацию std::find()
или же std::find_if()
и один из контейнеров последовательности, например, std::vector<Airport>
или же std::deque<Airport>
,
Поскольку вам не нужно определять порядок с точки зрения operator<()
может быть разумным просто принести Airport
S в некотором порядке с целью размещения их в 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
(но из-за асимметрии не оба).
Нашел хорошее решение на блог 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;
}
Вы можете сделать что-то похожее на лексикографический порядок, если у каждого участника есть <
определены:
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));
}
};