3

質問が言うように、私はそのような方法でstd::mapを使用する必要があります。

std::map<std::pair<int, int>, int*> m;

int* a_ptr = new int;
*a_ptr = 15;
m[std::make_pair(1, 2)] = a_ptr;
std::cout << *m[std::make_pair(2, 1)] << std::endl; //should output 15

さて、私の実際の実装では、すべてのキーと値は実際にはポインターです。この問題にどのように取り組むべきですか？

2つのアイデアが思い浮かびます。

  1. m[]1つは、マップにアクセスしたり、マップに書き込んだりするたびにm.find()、他のペアの組み合わせもチェックして、それに応じて動作する関数を作成する必要があることです。

  2. もう1つは、カスタムハッシャーでstd :: unordered_mapを使用しているため、 要素の位置を切り替えても何とか違いはありません。pair（これを行う方法がわかりません。2つのポインターを乗算または加算すると、結果は等しくなりません。これが方法である場合は、助けが必要です。）

あなたがより良い方法を考えることができれば私はそれを聞いてうれしいです、さもなければ私は2番目の節で私が助けを必要としていることを述べました。（これはより効率的だと思いますが、最初のものは見栄えがよくありません）

ありがとう。

4

4 に答える 4

7

ペアが常に同じ順序であることを簡単に確認できますか？次のようなヘルパー関数を使用します。

std::pair<int,int> my_make_pair(int a, int b) 
{
    if ( a < b ) return std::pair<int,int>(a,b);
    else return std::pair<int,int>(b,a);
}

そして常にそれを使って地図にアクセスします：

m[my_make_pair(1,2)] = a_ptr;
std::cout << m[my_make_pair(2, 1)] << std::endl;
于 2013-03-14T21:05:10.833 に答える
3 
template<typename T, typename PairCmp = std::less<std::pair<T,T>> >
struct symmetric_pair_sort {
  bool operator()( std::pair<T,T> const& left, std::pair<T,T> const& right ) const {
    if (left.second<left.first) {
      return (*this)(std::make_pair( left.second, left.first ), right );
    }
    if (right.second<right.first) {
      return (*this)(left, std::make_pair( right.second, right.first ) );
    }
    return PairCmp()(left, right);
  }
};

// or, the far bulkier yet more efficient:
template<typename T, typename PairCmp = std::less<std::pair<T&, T&>> >
struct symmetric_pair_sort {
  template<bool left_reversed, bool right_reversed>
  bool Helper( std::pair<T,T> const& left, std::pair<T,T> const& right ) const {
    std::pair<T&, T&> left_ordered( left_reversed?left.first:left.second, left_reversed?left.second:left.first );
    std::pair<T&, T&> right_ordered( right_reversed?right.first:right.second, right_reversed?right.second:right.first );
    return PairCmp()( left_ordered, right_ordered );
  }
  bool operator()( std::pair<T,T> const& left, std::pair<T,T> const& right ) const {
    if (left.second<left.first) {
      if (right.second<right.first) {
        return Helper<true, true>(left, right);
      } else {
        return Helper<true, false>(left, right);
      }
    } else {
      if (right.second<right.first) {
        return Helper<false, true>(left, right);
      } else {
        return Helper<false, false>(left, right);
      }
  }
};

std::map<std::pair<int, int>, int*, symmetric_pair_sort<int> > m;
于 2013-03-14T21:09:39.937 に答える
3

カスタムコンパレータを使用するだけです

[](std::pair<int, int> const& lhs, std::pair<int, int> const& rhs) {
   int lhs_min = std::min(lhs.first, lhs.second);
   int lhs_max = std::max(lhs.first, lhs.second);
   int rhs_min = std::min(rhs.first, rhs.second);
   int rhs_max = std::max(rhs.first, rhs.second);

   return lhs_min < rhs_min || (!(rhs_min < lhs_min) && lhs_max < rhs_max)
}

これはどのように作動しますか？

最初の数行は、ペアの2つの要素を決定論的に順序付けます。つまり、どちらの順序でも指定でき、lhs_min＆lhs_maxは同じになります。次に、結果に標準の等価手法を使用します。すべての整数コピーはコンパイラによって最適化され、min/maxはインライン化されます。

入力の便宜のためにC++11のラムダを使用しましたが、それ以降、C ++ 11のラムダをのコンパレータとして使用する良い方法がないことを発見したため、std::map適切なファンクタを作成する必要があります。

于 2013-03-14T21:09:59.843 に答える
1

std::set<int>別の解決策は、の代わりにを使用することですstd::pair<int,int>。セットは注文されたデータを保存するため、ペアを注文する必要がないため、要件を正確に満たすことができます。

一方、ペアを明示的に順序付けるペアの比較ラッパーを使用する他の回答は、より実用的である可能性があります。

于 2013-03-14T21:10:13.650 に答える