0

X、Y、距離の組み合わせをデータ構造に格納したい。ここで、X と Y は整数です。距離は、X と Y の間の距離です。

組み合わせがリストに存在するかどうかを後で確認できるように、C ++で使用するのに最適なデータ構造はどれですか?

4

4 に答える 4

2

std::set収納に使いたい方も多いのではないでしょうか。座標を考慮した比較関数が必要です (距離は座標から直接導出されるため、実際に比較する必要はありません)。

編集：多数のポイントが関係しているというコメントに基づいてstd::unordered_set、より良い選択かもしれません。おそらくより多くの作業が必要になりますが、通常は一定であると予想される複雑さで挿入と検索の両方を行うことができます。

于 2013-02-28T23:18:22.173 に答える
2

std::unordered_set適切なハッシュでそれを作成します。

于 2013-02-28T23:19:17.570 に答える
1

編集：質問が変更され、緯度/経度がなくなり、いくつかのことが明確になりました。私は最初からやり直しています：

あなたの質問は、距離計算が単純な std::abs(XY) ではないことを暗示しているようです。結果を保存して速度を上げることはまったく意味がありません。それを計算する高価な関数があると仮定します。

int distance( int X, int Y ) { /* heavy stuff */ }

ここで、それを呼び出すかどうか、または既に呼び出しており、結果を再利用できるかどうかを決定する必要があります。結果を格納するコンテナとそれを使用する関数が必要です。

typedef std::pair< int, int > key;
std::map< key, int > values;

int quick_distance( int X, int Y )
{
  const auto k = key(X,Y);
  const auto it = values.find(k);
  if( it != values.end() ) return it->second;
  const auto d = distance(X,Y);
  values[k] = d;
  return d;
}
于 2013-02-28T23:25:28.107 に答える
0

std::pair を見てください。これらはこの目的のために作成されたものであり、この種のデータ構造に関連付けられたコンテナーの改善を使用できます。

標準ペアとは

少し前に、マイクロコントローラーからのグラフィックシリアルデータにデータペアを使用して何かを書きました。 https://github.com/jpcordovae/GLRealTimeGraphics/blob/master/DataPair.hppで確認してください。

よろしく！

JP コルドバ E.

于 2013-03-01T13:54:32.553 に答える