严格的弱序排列混乱

Question

我对严格的弱排序以及如何在定义operator <时使用它感到困惑.我有几个结构:

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机场.我需要定义operator <,它使用严格的弱排序,但我不确切地知道这意味着什么和/或如何做.

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

std::set<Airport, cmpless> airportSet;

一个机场"小于"另一个机场没有意义.只有机场根据他们的统计数据相等才有意义.

我如何确定我对operator <的定义将遵循严格的弱排序？我如何开始考虑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<(),因此将Airports定位到某个顺序以便将它们定位在一个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(但由于不对称而不是两者).