2 - dimesionale std::map ?

Computer: Software & Programmierung C/C++
#1

Hallo,

ich arbeite gerade mit maps, die sind klassischer Weise eindimesional. Ein Key weis auf eine Element.

Nun würde das gerne 2 - dimensional machen, also die kombination aus 2 Keys auf eine Element zuweisen.

etwa
std::map verheiratet;
Map[Thorsten, Anna] = true;
Map[Anna, Thorsten] = true;
Map[Thorsten,Gabi] = false;
…

Und nun will ich wissen, ob zwei Personen verheiratet sind

if(Map.find(Thorsten,Gabi)!=Map.end())
{
irgendwas
}
Der Code geht so natürlich nicht, ich hoffe es bescheibt meine Idee.

Dieses Beispiel dient nur der Veranschaulichung, da es zu viel Aufwand ist das ganze Prinzip zu erklären, Map[Thorsten]=Anna ist also leider für mich keine Lösung :frowning:

Der Code geht so natürlich nicht, ich hoffe es bescheibt meine Idee.

In der Realität geht es mir darum die Elemente eine sehr dünn besetzten Matrix zu verwalten. Eine einfach 2-dim Matix [vector] wäre zu speicheraufwändig. Zur Zeit habe ich einen vektor aus Maps, auf den ich von einer anderen map mappe (welche ein Satz), leider dauert die Suche hier zu lange. Dabei lege ich, sobald der erste Key einmal gesetzt wird, eine „Zielmap“ in den Vector. Das Ziel der ersten Map ist ein Pointer auf die zweite Map, und in der wird dann der 2. Key gesucht.

Ist das schon der Beste weg oder wüsste noch jemand etwas?

Wie würdet ihr überhaupt Elemente eine sehr dünn besetzen Matrix speichern?

#2

Hallo,

ich arbeite gerade mit maps, die sind klassischer Weise
eindimesional. Ein Key weis auf eine Element.
Nun würde das gerne 2 - dimensional machen, also die
kombination aus 2 Keys auf eine Element zuweisen.
etwa
std::map verheiratet;
Map[Thorsten, Anna] = true;
Map[Anna, Thorsten] = true;
Map[Thorsten,Gabi] = false;
Und nun will ich wissen, ob zwei Personen verheiratet sind

if(Map.find(Thorsten,Gabi)!=Map.end())
{
irgendwas
}
Der Code geht so natürlich nicht, ich hoffe es bescheibt meine
Idee.

Meinst Du so etwas in der Art? :

 ...
 typedef map \> Map2D; // generell: jeweils 
 Map2D verheiratet;
 verheiratet["Thorsten"]["Anna"] = true;
 verheiratet["Anna"]["Thorsten"] = true;
 verheiratet["Thorsten"]["Gabi"] = false;

 if(verheiratet["Thorsten"]["Gabi"] == true) 
 cout ::const\_iterator innen;
 for(innen=aussen-\>second.begin(); innen!=aussen-\>second.end(); innen++) 
 cout first first " 
 second ? "true" : "false")


Grüße

CMБ

ps.: includes:
#include 
#include 
#include 
#include 
#include 

using namespace std;
#3

Das klingt gut. Vielleicht zwei Fragen dazu:

a)Wie kann ich prüfen, ob ein Element existiert?

Bei einer normalen map prüfe ich gegen .end(),
aber wenn ich das nun so mache, kann es doch sein, dass key1 nicht existiert und/oder das key2 nicht existiert. Wie prüfe ich das?

b) Gibt es optimierungen für den Zugriff auf die Rechenzeit eine 2D Matrix. vector scheidet wegen der größe ja aus, die Matrix ist nur sehr dünn besetzt. Viele Spalten und Zeilen existieren gar nicht, aber mit Maps muss man ja immer „suchen“, das dauert da leider.

Vielen Dank aber schonmal für die Anregeung

#4

Hallo

a)Wie kann ich prüfen, ob ein Element existiert?
Bei einer normalen map prüfe ich gegen .end(),
aber wenn ich das nun so mache, kann es doch sein, dass key1
nicht existiert und/oder das key2 nicht existiert. Wie prüfe
ich das?

z.B.: so:

 ...
 Map2D::const\_iterator z = verheiratet.find("Thorsten");
 if(z!=verheiratet.end() && z-\>second.find("Gabi")!=z-\>second.end())
 cout 




> b) Gibt es optimierungen für den Zugriff auf die Rechenzeit  
> eine 2D Matrix. vector scheidet wegen der größe ja  
> aus, die Matrix ist nur sehr dünn besetzt. Viele Spalten und  
> Zeilen existieren gar nicht, aber mit Maps muss man ja immer  
> "suchen", das dauert da leider.


Weisst Du vorher, a) wieviele Personen <u>maximal</u>
vorkommen können und b) um welche "Anzahlen" handelt
es sich am Ende?

Grüße

CMБ
#5

Wenn ich die Matrix erstelle, weiss ich, wieviele „Personen“ es gibt. In meinem Programm sind es IDs

Größenordnung 100.000 pro Dimmension, können auch mehr werden.

#6

Hallo

Wenn ich die Matrix erstelle, weiss ich, wieviele „Personen“
es gibt. In meinem Programm sind es IDs
Größenordnung 100.000 pro Dimmension, können auch mehr werden.

OK, wenn Du von einer std::map (Baumstruktur)
zu einer std::hash_map (hash-Funktion) übergehst,
könntest Du etwa mit einer Beschleunigung zwischen
x3 bis x5 bei derart großen Systemen rechnen.

Wie stark/dicht ist denn Dein
100,000 x 100,000-System besetzt?

Grüße

CMБ

#7

Unterschiedlich, sicher nicht über 1%.

Wie würde ich überhaupt ein komplett beliebiges Element finden, das existiert (am schnellsten). Dabei verbrate ich zZ die meiste Zeit, kommt auch sehr häufig vor.