wake-up-neo.net

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

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

Momentan erstelle ich einen std :: string mit den zwei Koordinaten (dh "12x45") und verwende ihn als Schlüssel. Dies scheint nicht der beste Weg zu sein.

Meine anderen Gedanken waren, ein int64 zu verwenden und die beiden int32s hinein zu schieben und es als Schlüssel zu verwenden.

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

Was ist der beste Weg, dies zu tun? Ich möchte lieber keine Karte verwenden.

36
Roland Rabien

Verwenden Sie 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;
107
David Norman

Normalerweise löse ich diese Art von Problem so:

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;
    }
}
28
StackedCrooked

Was sind die Anforderungen an eine Klasse, die als Schlüssel verwendet werden soll?

Die Zuordnung muss feststellen können, ob der Wert eines Schlüssels niedriger ist als der Wert eines anderen Schlüssels. Standardmäßig bedeutet dies, dass (key1 <key2) ein gültiger boolescher Ausdruck sein muss, d. H. Der Schlüsseltyp sollte den Operator 'less than' implementieren.

Die Map-Vorlage implementiert außerdem 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 auch als Methode dieses externen Funktionsobjekts anstelle von implementiert werden Sie müssen in den Typ Ihres Schlüssels eingebacken werden.

5
ChrisW

Boost verfügt über einen Kartencontainer, der einen oder mehrere Indizes verwendet.

Multi Index Map

3
DeadHead

Dadurch werden mehrere Ganzzahlschlüssel in eine große Ganzzahl gefüllt, in diesem Fall ein _int64. Es ist vergleichbar mit einem _int64, AKA long long (die hässlichste Typdeklaration aller Zeiten. Short short short, wäre nur etwas weniger elegant. Vor 10 Jahren hieß es vlong. Viel besser. So viel zum "Fortschritt"), also kein Vergleich Funktion wird benötigt. 

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

Nachdem ich diese Antwort gegeben habe, bezweifle ich, dass dies für Sie funktionieren wird, da Sie zwei separate und unterschiedliche Tasten zum Navigieren in zwei Dimensionen, X und Y, benötigen. 

Wenn Sie jedoch bereits über die XY-Koordinate verfügen und diesem Schlüssel nur einen Wert zuordnen möchten, funktioniert dies auf spektakuläre Weise, da ein _int64-Vergleich dieselbe Zeit benötigt wie jeder andere Integer-Vergleich auf Intel X86-Chips - 1 Uhr. 

In diesem Fall ist der Vergleich bei diesem synthetischen Schlüssel dreimal so schnell wie bei einem dreifachen Verbundschlüssel. 

Wenn Sie dies verwenden, um eine dünn besetzte Kalkulationstabelle zu erstellen, würde ich RX verwenden, indem Sie zwei verschiedene Bäume verwenden, die ineinander verschachtelt sind. Machen Sie die Y-Dimension "den Boss" und suchen Sie zuerst den Y-Raum nach Auflösung, bevor Sie zur X-Dimension gehen. Tabellenkalkulationen sind größer als breit, und Sie möchten, dass die 1. Dimension in einem Verbundschlüssel die größte Anzahl eindeutiger Werte hat. 

Diese Anordnung würde eine Karte für die Y-Dimension erstellen, die eine Karte für die X-Dimension als ihre Daten hätte. Wenn Sie zu einem Blatt in der Y-Dimension gelangen, beginnen Sie mit der Suche der X-Dimension nach der 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-/Prognose-/Abrechnungssystem. Dieses System ermöglicht es Admin-Einheiten, über viele blutige Detailkonten zu verfügen, um Verwaltungskosten und dergleichen nachzuverfolgen, und nicht, dass diese Konten Platz für Zeileneinheiten beanspruchen, die ihre eigenen Arten haben Details zu verfolgen. 

1
user1899861

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

0
MadH