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<このような状況で定義することをどのように考え始めるのですか？

説明付きの例は、可能であれば素晴らしいでしょう！

4

3 に答える 3

5

Airportある人が別の人の前に来ることが「意味をなさない」場合Airport、その使用も意味がありstd::set<Airport>ません。このコンテナは、注文金額要素を利用して、O(log(n))操作中のオブジェクトを検索します（ここnで、はコンテナのサイズです）。IDのみでオブジェクトを識別できる場合、達成できる最も複雑なのはですO(n)。またはとシーケンスコンテナの1つ、たとえば、std::find()またはの組み合わせを使用できます。std::find_if()std::vector<Airport>std::deque<Airport>

の観点から順序を定義する必要がないので、とは異なる比較関数オブジェクトを使用して行われる、でそれらを見つけるためにoperator<()、sをある順序にするのが合理的かもしれません。ただし、現在オブジェクトにある属性は、実際には適切なキーのようには見えません。実際、それらはすべて変更可能であるかのように見えます。つまり、（少なくとも、そうすべきではありません。そう、私はあなたがでトリックをプレイできますが、これは要素の順序を壊すことになります）。Airportstd::set<Airport>std::less<Airport>Airportstd::set<Airport>std::set<T>mutable

これに基づいて、std::map<std:string, Airport>：を使用することをお勧めします。たとえば、ニューヨークのジョンF.ケネディ空港やロンドンヒースローのstd::stringような空港コードを使用して、空港を識別します。便利なことに、文字列にはすでに厳密な弱順序が定義されています。"JFK""LHR"

とはいえ、オブジェクトのセットに厳密な弱順序を定義するには、次の条件が要素、、、およびfromに当てはまるような二項関係Oにする必要があります。r(x, y)xyzO

  • 無反射：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) == falser(z, y) == falser(x, z) == falser(z, x) == false

最初の3つは十分に単純なはずです。最後のものは最初は少し奇妙ですが、実際にはそれほど難しくはありません。基本的な考え方は、リレーションが要素を完全に順序付けするのではなく、それらを同等のクラスにグループ化することです。r関係が「よりも小さい」と考える場合、それは、より小さくもx小さくもない場合、とは同等であると言うだけです。比類のない要素はちょうど同等です。yyxxy

標準のコンテナは厳密な弱順序で動作しますが、たとえば、同等のキーの1つのバージョンのみstd::set<T>を保持します。これで十分なのは良いことですが、要素の各ペアに対して、または（ただし、非対称性のために両方ではない）std::map<K, V>の厳密な弱順序である全順序を使用する方が簡単な場合がよくあります。xyr(x, y) == truer(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 に答える