1

我对严格的弱排序以及在定义 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<在这种情况下，我如何开始考虑定义？

如果可能的话，一个带有解释的例子会很棒！

4

3 回答 3

5

Airport如果一个人出现在另一个人之前“没有意义”，Airport那么使用std::set<Airport>也没有意义。此容器利用订单金额元素来定位操作中的对象（容器的大小在O(log(n))哪里）。n如果您只能通过身份识别对象，那么您可以实现的最佳复杂度是O(n). 您可以使用std::find()orstd::find_if()和其中一个序列容器的组合，例如std::vector<Airport>或std::deque<Airport>。

由于您不需要根据 定义顺序，因此将s 放入某种顺序operator<()可能是合理的，以便将它们定位在 a中，这是通过使用与 . 不同的比较函数对象来完成的。但是，您当前在对象中拥有的属性看起来并不像合适的键。事实上，它们看起来都好像是可变的，也就是说，你可能不想要 a ，因为你不能修改 an 中的元素（好吧，至少，你不应该；是的，我意识到你可以耍花招，但这势必会破坏元素的顺序）。Airportstd::set<Airport>std::less<Airport>Airportstd::set<Airport>std::set<T>mutable

基于此，我建议使用 a std::map<std:string, Airport>: thestd::string来识别机场，例如，使用"JFK"纽约肯尼迪机场或"LHR"伦敦希思罗机场等机场代码。方便的是，已经在字符串上定义了严格的弱顺序。

也就是说，要在一组 objects 上定义严格的弱顺序O，您需要一个二元关系r(x, y)，使得以下条件适用于 elements x、y和zfrom 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) == falseand r(y, x) == falseand and r(y, z) == falseandr(z, y) == false暗示r(x, z) == falseandr(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（但是，由于不对称，不是两个）。

于 2012-11-27T00:42:06.557 回答
1

在musingstudio 博客上找到了一个不错的解决方案，并认为我在这里分享它以供下一个需要的人使用（即使 Dietmar 可能是正确的，地图不合适）：

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;
}
于 2017-06-19T19:04:01.000 回答
0

<如果每个成员都定义了，您可以执行类似于字典顺序的操作：

   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));
        }
    };
于 2012-11-27T00:23:17.343 回答