Was ist der beste Weg, um zwei Schlüssel mit einer std :: map zu verwenden?

Question

Ich habe eine Std :: Map, die ich verwende, um Werte für x & y-Koordinaten zu speichern. Meine Daten sind sehr spärlich, daher möchte ich keine Arrays oder Vektoren verwenden, was zu einer enormen Speicherverschwendung führen würde. Meine Daten reichen von -250000 bis 250000, aber ich habe höchstens ein paar tausend Punkte.

Momentan erstelle ich eine std :: string mit den zwei Koordinaten (zB "12x45") und benutze sie als Schlüssel. Dies scheint nicht der beste Weg zu sein.

Meine anderen Gedanken waren die Verwendung eines Int64 und schieben Sie die beiden Int32s hinein und verwenden Sie es als Schlüssel.

Oder eine Klasse mit den zwei Koordinaten zu verwenden. Was sind die Anforderungen an eine Klasse, die als Schlüssel verwendet werden soll?

Was ist der beste Weg, dies zu tun? Ich würde lieber keine Karte von Karten verwenden.

Answer 1

Verwendung std :: pair < int32, int32> für den Schlüssel:

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; 

Answer 2

-Boost hat eine Karte Container, der einen oder mehrere Indizes verwendet.

Multi Index Map

Answer 3

ich diese Art von Problem, wie dies in der Regel lösen:

struct Point 
{ 
    Point() : x(), y() {} 
    Point(int x, int y) : x(x), y(y) {} 
    int x, y; 
}; 

bool operator<(const Point & lhs, const Point & rhs) // lhs = left-hand side 
                 // rhs = right-hand side 
{ 
    if (lhs.x != rhs.x) 
    { 
     return lhs.x < rhs.x; 
    } 
    else 
    { 
     return lhs.y < rhs.y; 
    } 
} 

int main() 
{ 
    Point p1(0, 1); 
    Point p2(0, 2); 
    std::map<Point, std::string> mapping; 
    mapping[p1] = "p1"; 
    mapping.insert(std::make_pair(p2, "p2")); 
} 

Answer 4

Was sind die Voraussetzungen für eine Klasse, die als Schlüssel verwendet werden soll?

Die Karte muss in der Lage zu sagen, ob ein Schlüssel des Wert kleiner als ein anderer Wert des Schlüssels: Standardmäßig bedeutet dies, dass (key1 < key2) muss eine gültige boolean Ausdruck sein, dh, dass der Schlüsseltyp das Gerät sollte "weniger als" Betreiber.

Die Map-Vorlage implementiert auch einen überladenen Konstruktor, mit dem Sie einen Verweis auf ein Funktionsobjekt vom Typ key_compare übergeben können, das den Vergleichsoperator implementieren kann: Alternativ kann der Vergleich als eine Methode dieser externen Funktion implementiert werden Objekt, statt in jedem Typ gebacken zu werden, aus dem dein Schlüssel besteht.

Answer 5

Verwenden Sie std :: pair. Verwenden Sie besser QHash<QPair<int,int>,int>, wenn Sie viele solcher Zuordnungen haben.

Answer 6

In erster Linie, ziehen Sie die Saite und verwenden Sie 2 Ints, die Sie jetzt möglicherweise getan haben. Kudos, um herauszufinden, dass ein Baum der beste Weg ist, eine spärliche Matrix zu implementieren. Normalerweise scheint es ein Magnet für schlechte Implementierungen zu sein.

FYI, ein Dreifach-Verbundschlüssel funktioniert auch, und ich nehme auch ein Paar Paare an.

Es macht für einige hässliche Sub-Scripting obwohl, so ein wenig Makro Magie wird Ihr Leben leichter machen. Ich habe diesen allgemeinen Zweck verlassen, aber die Argumente im Makro zu schreiben ist eine gute Idee, wenn Sie Makros für bestimmte Karten erstellen. Die TresKey12 ist getestet und läuft gut. QuadKeys sollte auch funktionieren.

HINWEIS: Solange Ihre Schlüsselteile grundlegende Datentypen sind, brauchen Sie NICHT mehr zu schreiben. AKA, keine Notwendigkeit, sich über Vergleichsfunktionen zu ärgern. Die STL hat dich abgedeckt. Codiere es einfach und lass es krachen.

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; 

Wenn jemand will, um mich beeindrucken, zeigt mir, wie einen Operator vergleichen zu machen für TresKeys, die nicht auf Brutpaare angewiesen ist, damit ich ein einziger struct mit 3 Mitgliedern nutzen kann und eine Vergleichsfunktion verwenden.

PS: TresKey12 gab mir Probleme mit einer Karte als Paar deklariert, z wie es x macht, paar, und diese beiden nicht schön spielen. Kein Problem für DosKeys oder QuadKeys. Wenn es aber ein heißer Sommer Freitag ist, können Sie eine unerwartete Nebenwirkung der Eingabe in DosEquis finden ... ähm .. DosKeys ein paar Mal, ist ein Durst nach mexikanischen Bier. Vorbehalt Emptor. Wie Sheldon Cooper sagt: "Was ist das Leben ohne Laune?".

Answer 7

Dies stopft mehrere Integer-Schlüssel in eine große Ganzzahl, in diesem Fall ein _int64. Es vergleicht als _int64, AKA long long (Die hässlichste Typdeklaration überhaupt. Kurz kurz kurz kurz, wäre nur etwas weniger elegant. Vor 10 Jahren hieß es vlong. Viel besser. So viel zum "Fortschritt"), also kein Vergleich Funktion ist erforderlich.

#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; 
} 

diese Antwort gegeben hat, ich bezweifle, dass dies für Sie arbeiten wird, wie Sie zwei getrennte und unterschiedliche Schlüssel müssen mit

in 2 Dimensionen, X und Y.

Auf der anderen Seite navigieren, Wenn Sie bereits die XY-Koordinate haben und nur einen Wert mit diesem Schlüssel verknüpfen möchten, dann funktioniert dies auf spektakuläre Weise, da ein _int64-Vergleich die gleiche Zeit wie jeder andere Ganzzahlvergleich auf Intel X86-Chips benötigt - 1 Takt.

In diesem Fall ist der Vergleich 3X so schnell auf diesem synthetischen Schlüssel, verglichen mit einem Dreifachverbindungsschlüssel.

Wenn Sie dies verwenden, um ein dünn besiedeltes Arbeitsblatt zu erstellen, würde ich RX mit zwei verschiedenen Bäumen verwenden, von denen der eine ineinander verschachtelt ist. Machen Sie die Y-Dimension zum "Boss" und suchen Sie zuerst in Y-Raum nach der Auflösung, bevor Sie zur X-Dimension weitergehen. Kalkulationstabellen sind größer als breit und Sie möchten immer, dass die erste Dimension in einem zusammengesetzten Schlüssel die größte Anzahl eindeutiger Werte aufweist.

Diese Anordnung würde eine Zuordnung für die Y-Dimension erstellen, die eine Zuordnung für die X-Dimension als Daten hätte. Wenn Sie zu einem Blatt in der Y-Dimension gelangen, beginnen Sie mit der Suche nach seiner X-Dimension für die Spalte in der Kalkulationstabelle.

Wenn Sie ein sehr leistungsfähiges Tabellenkalkulationssystem erstellen möchten, fügen Sie auf dieselbe Weise eine Z-Dimension hinzu und verwenden Sie diese beispielsweise für Organisationseinheiten. Dies ist die Grundlage für ein sehr leistungsfähiges Budgetierungs-/Prognostizierungs-/Buchhaltungssystem, das es Admin-Einheiten ermöglicht, viele detaillierte Konten zu haben, um Verwaltungskosten und dergleichen zu verfolgen, und diese Konten nicht Platz für Linieneinheiten nehmen, die ihre eigenen Arten haben Details zu verfolgen.

Answer 8

Hoffe, dass Sie es nützlich finden werden:

map<int, map<int, int>> troyka = { {4, {{5,6}} } }; 
troyka[4][5] = 7;