C++ auf der Suche nach der richtigen Datenstruktur

[Fireball89]

Hallo,

ich versuche mich zur Zeit etwas an MS Visual C++ und komme nicht weiter.
Ich brauche eine Datenstruktur, die man schnell durchlaufen kann und in einer Schleife jedes Element "anfassen" kann, ohne die Datenstruktur zu ändern.
Und zwar möchte ich Objekte meiner eigenen Klasse in dieser DS unterbringen. Jedes Objekt hat eine einzigartige Bitmaske (32bit WORD) als Attribut, anhand der ich das Objekt in der DS finden möchte.
Erste Idee: HashMap (std::map). Problem: Suche ich nach einer Bitmaske zu der kein Objekt abgelegt wurde, laufe ich in undefinierte Speicherbereiche.

return myMap[bitmask];

Also müsste ich ja quasi für jeden möglichen Schlüssel, einmal das passende Null-Objekt ablegen, um den Fall abzufangen. Das möchte ich bei 2^32 verschiedenen Schlüsseln (Bitmasken) gerne verhindern!

Zwei Idee: Ein simpler Binärbaum. Leider hab ich mich dumm und dämlich gesucht, aber es scheint dafür kein Template in der STL zu geben. Hab jetzt auch keine List für sowas banales ne eigene Klasse zu schreiben.

Was soll ich tun?

 

[amokkx]

Gibt es in C++ nicht auch sone Art ObjectList?
Ansonsten machs einfach wie bei den verketteten Listen, dürfte, denke ich, das einfachste sein.

 

[mercsen]

ich glaube sein Ziel ist es bei der suche nicht jedes Objekt zu durchlaufen sonder direkt über den has drauf zugreifen zu können.

Was ist denn so schlimm wenn man in eine undefinierten bereich kommt? Kann man den Fehler nicht einfach abfangen? Ist zwar nicht die shcönste methode, aber in Java könnntest das einfach in einem try / catch block unterbringen.

sost natürlich einfach eine liste undper foreach drüber iterieren, ob das aber so schnell ist...

man kann natürlich auch einen Baum basteln in der Strucktur
A ----- > A1 ----> A1.1
----> A1.2
A2 ----> A2.1

etc. um schnell kleinere listen zu bekommen

 

[Holt]

amokkx, die verkette List ist zwar einfach, aber beim Suchen eines beliebigen Objects, auch sehr langsam.

Fireball89, nimm einen Binärbaum, der ist beim Suchen am schnellsten, vor allem wenn es ein balancierter ist. Leider sind Microsofts-Programmierer offenbar keine Fans von schnellen Routinen und haben den nicht implementiert, Du wirst also im Netz selbst nach einem suchen müssen.

 

[Vibrationz79]

Kein schöner Ansatz, aber wie wäre sowas als Quick&Dirty-Lösung?

try
{
    MyObject result = (MyObject)myMap[bitmask];
    return result;
}
catch (...)
{
    return null;
}

Keine Ahnung ob das so auch klappt, ist nur aus dem Kopf und ich bin eher in C# beheimatet... Asche auf mein Haupt falls der Ansatz so nicht klappen kann...

 

[Fireball89]

ich glaube sein Ziel ist es bei der suche nicht jedes Objekt zu durchlaufen sonder direkt über den has drauf zugreifen zu können.

Wäre natürlich elegant, aber muss nicht sein. Wäre beim Baum ja auch nicht der Fall.

Kann man den Fehler nicht einfach abfangen?

Ich wüsste nicht wie.
Kleines Bsp mit Strings:
myMap[0] = "bla";
myMap[1] = "blubb";

D.h. myMap[2] zeigt irgendwo hin (undefiniert). Wie soll ich nun abfangen ob an diesem Ort etwas sinnvolles steht oder nur Müll? Bei Java kann man immer schön mit ==null abfragen, das geht nun mal hier nicht.

Die Liste hab ich ganz vergessen. Damit gehts natürlich schon mal. Das probier ich gleich.
Jemand noch ne Idee wie ich es mit Baum oder besser mit HashMap hinbekomme?

 

[Holt]

Schau mal lieber hier.

 

[[GP] mino]

für ein schnelles ergebnis bleibe bei den hashmaps und wirf einen blick hier rübber.

 

[Raechaer]

Was spricht denn dagegen, std::map zu verwenden? Das macht doch genau was du willst (und ist übrigens auch als Baum und nicht Hash implementiert).

Wenn du dir dann noch anschaust, was operator[] wirklich macht (er gibt entweder ein bereits vorhandenes Objekt passend zum Schlüssel zurück oder erstellt mittels Default-Konstruktor ein neues Objekt für dieses Schlüssel, du bekommst also definitiv keinen undefinierten Speicher) und dass es auch eine find() Methode gibt, dann sollte dein Problem doch gelöst sein.

 

[Fireball89]

@Holt:
Das ist genau das was ich nicht will. Ich weiß wie AVL-Bäume funktionieren, ich brauch das nicht mehr lernen. Wenn ich jetzt diese Codefragmente nehme und in mein Programm einpflanze sitz ich da locker ne Stunde dran.
Es muss doch dafür ne fertige Library geben.

@Vibrationz79:
Wusste bislang nicht, dass es try&catch auch in C++ gibt. Habs gleich mal ausprobiert, funktioniert aber absolut nicht:
Unbehandelte Ausnahme im kritischen Block, obwohl der Block im try-Bereich steht und ich catch(...) geschrieben hab. Sollte catch(...) nicht ALLE Exceptions fangen?

 

[ice-breaker]

Klingt nach einem Rot-Schwarz-Baum oder AVL-Baum, zum Bestimmen des Besten für deinen Anwendungszweck müsste man noch wissen, oder der Baum hinsichtlich Lesen oder Verändern optimiert sein soll.

Ein Trie könnte auch ein sehr guter Einsatzweck sein, da die Komplexität nicht mit der Anzahl der Einträge steigt, sondern immer nur abhängig von der Länge deines Lookup-Keys ist.

 

[Fireball89]

@[GP] mino:
Super, so geht's. Danke.

Muss mir wohl doch mal ein Buch kaufen, tippe ich.

 

[mercsen]

WIll ja nix sagen aber das mit dem try / catch habe ich weiteroben schon geschrieben....

und ich bin nicht so der c++ mensch, aber ich denke nicht das eine Catch einfach mal alle Exceptions abfängt.
in java musst du für jede Exception die behandelt werden soll einen eigen Catch block schreiben, oder aber du sagst explizit das du alle Exceptions haben willst indem man dem catch block einen Paramerter der Klasse Exception übergibt.
Ist in C++ übrigens auch so: http://www.willemer.de/informatik/cpp/exceptions.htm

 

[convexus]

alternativ kann man mittels der Methode 'find' in Maps suchen. Im Source könnte das etwa so aussehen:

// Datenstruktur Abbildung 32Bit Word -> T

typedef std::map<unsigned int, T*> TAbbildung;

bool assign_value(TAbbildung& m, unsigned int k, T* v) {
   TAbbildung::iterator iter=m.find(k);
   if(iter != m.end())  {
      // Wert zu Key k gefunden
      iter->second = v;
      return true;
   }
   return false;
}

T obj;
TAbbildung m;

..
m[obj.bit_mask()] = &obj;
..
if(!assign_value(m, 0x99393, &obj))  {
  // 0x99393 nicht vorhanden, was nun?
}

}

 

[antred]

Raechaer und convexus haben's ja bereits gesagt, std::map hat eine find-Methode, die genau das tut, was du brauchst. Suchst du nach einem Element, dessen Schlüssel in der map vorhanden ist, bekommst du einen Iterator zurück, der auf dieses Schlüssel/Wert-Paar zeigt. Andernfalls bekommst du eben einen Iterator gelierfert, der auf das Ende der map zeigt (also nameMeinerMap.end()). convexus hat das in seinem Codebeispiel sehr schön demonstriert.

P.S. Da du mit Visual Studio arbeitest, es gibt dort noch eine stdext::hash_map, die von der Performance her etwas schneller ist als die std::map. Sie unterstützt die gleichen Methoden wie std::map.