56

std::mapx 座標と y 座標の値を格納するために使用している があります。私のデータは非常にまばらなので、メモリを大量に浪費する配列やベクトルを使用したくありません。私のデータ範囲は -250000 から 250000 ですが、多くても数千ポイントしかありません。

現在std::string、2 つの座標 (つまり"12x45") を使用して を作成し、それをキーとして使用しています。これは最善の方法とは思えません。

私の他の考えは、int64 を使用し、それに 2 つの int32 を押し込んで、それをキーとして使用することでした。

または、2 つの座標を持つクラスを使用します。キーとして使用されるクラスの要件は何ですか?

これを行う最善の方法は何ですか？地図の地図は使いたくない。

4

10 に答える 10

139

キーに std::pair<int32,int32> を使用します。

std::map<std::pair<int,int>, int> myMap;

myMap[std::make_pair(10,20)] = 25;
std::cout << myMap[std::make_pair(10,20)] << std::endl;
于 2009-07-11T00:15:58.730 に答える
33

私は通常、この種の問題を次のように解決します。

struct Point {
    int x;
    int y;
};

inline bool operator<(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}
于 2009-07-11T00:25:47.407 に答える
7

Boost には、1 つ以上のインデックスを使用するマップ コンテナーがあります。

マルチ インデックス マップ

于 2009-07-11T00:18:39.463 に答える
5

キーとして使用されるクラスの要件は何ですか?

マップは、あるキーの値が別のキーの値よりも小さいかどうかを判断できる必要があります。デフォルトでは、これは (key1 < key2) が有効なブール式でなければならないこと、つまり、キーの型が「より小さい」演算子を実装する必要があることを意味します。

マップ テンプレートは、比較演算子を実装できる key_compare 型の関数オブジェクトへの参照を渡すことができるオーバーロードされたコンストラクターも実装します。キーのタイプに合わせて焼き付ける必要があります。

于 2009-07-11T00:31:25.910 に答える
1

これにより、複数の整数キーが大きな整数 (この場合は _int64) に詰め込まれます。これは _int64、別名 long long (これまでで最も醜い型宣言です。short short short short は、わずかにエレガントではありません。10 年前には vlong と呼ばれていました。はるかに優れています。「進歩」についてはこれで終わりです)、比較対象外です。機能が必要です。

#define ULNG  unsigned long
#define BYTE  unsigned char
#define LLNG  long long 
#define ULLNG unsigned long long

// --------------------------------------------------------------------------
ULLNG PackGUID(ULNG SN,  ULNG PID, BYTE NodeId) {
    ULLNG CompKey=0;

    PID = (PID << 8) + NodeId;
    CompKey = ((ULLNG)CallSN << 32) + PID;

    return CompKey;
}

この回答を提供したので、X と Y の 2 つの次元でナビゲートするには 2 つの別個の異なるキーが必要なので、これがうまくいくとは思えません。

一方、既に XY 座標があり、値をそのキーに関連付けたいだけの場合、Intel X86 チップでは _int64 比較に他の整数比較と同じ時間 (1 クロック) かかるため、これは見事に機能します。

この場合、この合成キーの比較は、トリプル複合キーと比べて 3 倍高速です。

これを使用してデータがまばらなスプレッドシートを作成する場合、2 つの異なるツリーを使用して RX を実行し、一方が他方の内部にネストされます。Y 次元を「ボス」にし、X 次元に進む前に、最初に Y 空間を検索して解決します。スプレッドシートは幅よりも高さが大きいため、複合キーの 1 番目の次元には常に最大数の一意の値が必要です。

この配置により、データとして X 次元のマップを持つ Y 次元のマップが作成されます。Y 次元のリーフに到達すると、スプレッドシートの列の X 次元の検索を開始します。

非常に強力なスプレッドシート システムを作成する場合は、同じ方法で Z 軸を追加し、例として組織単位に使用します。これは、非常に強力な予算編成/予測/会計システムの基礎であり、管理ユニットが管理費などを追跡するための多くの詳細なアカウントを持つことを可能にし、それらのアカウントが独自の種類を持つライン ユニットのスペースを占有しないようにするものです。追跡する詳細の。

于 2013-09-09T06:13:55.067 に答える
0

std::pair を使用します。QHash<QPair<int,int>,int>そのようなマッピングが多数ある場合は、使用することをお勧めします。

于 2009-07-11T13:48:15.367 に答える
-1

役に立つことを願っています：

map<int, map<int, int>> troyka = { {4, {{5,6}} } };
troyka[4][5] = 7;
于 2017-03-06T01:41:58.303 に答える
-1

パフォーマンスはわずかに低下しますが、インデックス作成が容易になる上位の結果の代替手段

std::map<int, std::map<int,int>> myMap;

myMap[10][20] = 25;
std::cout << myMap[10][20] << std::endl;
于 2021-03-15T09:50:58.607 に答える
-2

何よりもまず、文字列を捨てて 2 つの int を使用します。木がスパース行列を実装する最良の方法であることを理解してくれてありがとう。通常、悪い実装の磁石のようです。

参考までに、トリプル複合キーも機能します。ペアのペアも想定しています。

ただし、見苦しい添え字が作成されるため、マクロのちょっとした魔法で作業が楽になります。これは一般的な目的の 1 つとして残しましたが、特定のマップ用のマクロを作成する場合は、マクロ内の引数を型キャストすることをお勧めします。はTresKey12テスト済みで、正常に動作しています。QuadKeysも動作するはずです。

注: キー パーツが基本的なデータ型である限り、それ以上記述する必要はありません。別名、比較関数について心配する必要はありません。STL で対応できます。コーディングしてリッピングするだけです。

using namespace std;    // save some typing
#define DosKeys(x,y)      std::make_pair(std::make_pair(x,y))
#define TresKeys12(x,y,z) std::make_pair(x,std::make_pair(y,z))
#define TresKeys21(x,y,z) std::make_pair(std::make_pair(x,y),z))

#define QuadKeys(w,x,y,z) std::make_pair(std::make_pair(w,x),std::make_pair(y,z))


map<pair<INT, pair<ULLNG, ULLNG>>, pIC_MESSAGE> MapMe;
MapMe[TresKey12(Part1, Part2, Part3)] = new fooObject;

誰かが私に感銘を与えたい場合はTresKeys、入れ子のペアに依存しないための比較演算子を作成する方法を教えてください。これstructにより、3つのメンバーを持つ単一を使用し、比較関数を使用できます。

PS: TresKey12 は、x,pair を作成するため、pair,z として宣言されたマップで問題を引き起こしました。DosKeys や QuadKeys では問題ありません。暑い夏の金曜日の場合、DosEquis を入力すると予期しない副作用が発生する可能性があります...うーん. DosKeys を何度も入力すると、メキシコのビールが渇きます。買い手責任負担。シェルドン・クーパーが言うように、「気まぐれのない人生とは?」

于 2013-07-10T16:23:56.103 に答える