3

std :: mapに必要なoperator<（）メソッドに問題があります。次のような複合キーとして構造体を使用しています。

struct MyKey {
  std::string string1;
  std::string string2;
  std::string string3;
  unsigned int uint1;

  friend bool operator<(const MyKey& mk1, const MyKey& mk2)
  {
    return mk1.string1 < mk2.string1 && mk1.string2 < mk2.string2 &&
           mk1.string3 < mk2.string3 && mk1.uint1 < mk2.uint1;
  }
}

紹介したように、4つの値を持つ複合キーを使用したいのですが、 operator<メソッドでこれを実現する方法がわかりません。一度に1つの値しか保存されないことを確認しました。

誰かが正しい状態がどのように見えるか教えてもらえますか？

前もって感謝します！

4

3 に答える 3

9

、、、などの標準ライブラリの連想コンテナでは、要素の順序がに続く必要があります。つまり、の実装は厳密な弱い順序に従う必要があります。したがって、1つの実装は次のようになります。std::mapstd::setstd::multisetstd::multimapstd::bitsetStrict Weak Orderingoperator<

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
  if (mk1.string1 != mk2.string1 )
       return mk1.string1 < mk2.string1;

  else if ( mk1.string2 != mk2.string2)
       return mk1.string2 < mk2.string2;

  else if (mk1.string3 != mk2.string3)
       return  mk1.string3 < mk2.string3;

  else
       return mk1.uint1 < mk2.uint1;
}

または、次のように実装できます。

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
  auto const & t1 = std::tie(mk1.string1, mk1.string2, mk1.string3, mk1.uint1);
  auto const & t2 = std::tie(mk2.string1, mk2.string2, mk2.string3, mk2.uint1);
  return t1 < t2;
}

このソリューションでは、std::tie関数は2つのタプルt1とt1、それに渡された引数の参照を作成し、代わりにオーバーロードを比較t1してt2 使用します。タプルのoperator<は、要素を辞書式順序で比較します—厳密な弱順序が実現されます。operator<std::tuple

于 2012-04-23T07:25:32.167 に答える
2

演算子<が必ずしも厳密な弱順序を実装しているとは限らないという問題があると思います。A<Bfalseとfalseの組み合わせが多すぎます。B<Aここで、AとBはMyKeyオブジェクトです。Aこれは、に等しいと解釈されBます。

于 2012-04-23T07:28:58.443 に答える
2

実装の問題は、安定していないことです。検討してください...

return mk1.string1 < mk2.string1 && mk1.string2 < mk2.string2 &&
       mk1.string3 < mk2.string3 && mk1.uint1 < mk2.uint1;

...評価{ "a", "a", "a", 1 } < { "a", "b", "a", 1 }=== a<a && ..._false && ...false

...しかし{ "a", "b", "a", 1 } < { "a", "a", "a", 1 }=== a<a && ..._false && ...false

したがって、のキーが等しいわけではないにもかかわらず、どちらも他よりも少ないと報告されますmap。

実用的な解決策：必要な文字列の比較を1回だけ行うのは簡潔で効率的です...

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
    int x;
    return (x = mk1.string1.compare(mk2.string1)) ? x < 0 :
           (x = mk1.string2.compare(mk2.string2)) ? x < 0 :
           (x = mk1.string3.compare(mk2.string3)) ? x < 0 :
           mk1.uint1 < mk2.uint1;
}
于 2012-04-23T07:46:17.200 に答える