BinarySearchTree - Vergleichsoperator für gespeichete Zeiger?

Eisflamme

Hi,

Ich implementiere zur Zeit aus Übungsgründen einen binären Suchbaum, natürlich mit Templates.

Für's Einfügen habe ich damit einen Vergleich, den ich natürlich auf zwei Variablen ausführe, die vom Templatetyp sind.

Jetzt habe ich bei solch einem Suchbaum natürlich meistens Zeiger auf Objekte drin, also vergleicht er mir z.Z. die Adressen.

Folgende Lösungsideen habe ich:

operator< für den jeweiligen Objektzeiger überladen, so was wie:
operator<(const Objekt*& obj1, const Objekt*& obj2)

Lässt sich so etwas aber überhaupt implementieren? Ein Vergleichsoperator mit dieser Deklaration scheint nicht zu funktionieren.

Eine Dummyklasse bauen, die einen Zeiger auf das entsprechende Objekt hat und operator< und operator> einfach überlädt. Damit habe ich den gleichen Speicher in der Verwendung wie mit einem direkt gespeicherten Zeiger, also minimal Overhead.
Meine Templateklasse allgemein für Zeiger-Templateobjekte spezialisieren. Aber das unterstützt der Standard auch nicht, oder?

Findet ihr Variante 2 gut? Oder habt ihr eine noch bessere Idee. Vielleicht habe ich ja auch nen Designfehler oder vergesse irgendeinen mächtigen Winkel von C++.

Danke und viele Grüße,

Nexus

Eisflamme schrieb:

Lässt sich so etwas aber überhaupt implementieren?

Nein, bei der Operatorüberladung muss mindestens ein Argument von einem benutzerdefiniertem Typ sein. Für BuiltIn-Typen wie Zeiger funktioniert das nicht.

Eisflamme schrieb:

Oder habt ihr eine noch bessere Idee. Vielleicht habe ich ja auch nen Designfehler oder vergesse irgendeinen mächtigen Winkel von C++.

Du denkst nicht daran, dass C++ bereits eingebaute Vergleichsoperatoren für Zeiger besitzt. Du musst also gar nichts tun. Praktisch, oder?

P.S. Streng genommen garantiert der Standard das korrekte Resultat von Vergleichsoperationen auf Zeiger, die nicht ins selbe Array zeigen, nicht. Allerdings kann std::less , das Standardprädikat für operator< , diese Garantie erfüllen. In der Praxis stellt das eigentlich nie ein Problem dar. Am besten schreibst du den Code für den Vergleich nicht explizit hin, sondern verwendest einen weiteren Template-Parameter für die Vergleichsfunktion, der standardmässig auf std::less<T> gesetzt ist (schau wenn nötig in die Implementierung von STL-Containern, z.B. std::set ).

DocShoe

Du könntest so etwas wie ein Funktionsobjekt als weiteren Template Parameter übergeben und den Vergleich über das Objekt machen. Damit bist du wesentlich flexibler, als den < operator zu implementiern, denn damit gibt es genau eine Implementation und du kannst Objekte gleichen Typs nur nach einem Kriterium sortieren.

template<typename T, typename Pred=std::less<T> > // Default ist std::less
class BinaryTree
{
   // Objekt zum Vergleichen von zwei Typen T
   Pred Comparator;
   ...
};

struct MyPred
{
   bool operator()( const MyType& op1, const MyType& op2 ) const
   {
      return op1.SomeAttribute < op2.SomeAttribute;
   }
};

struct MyOtherPred
{
   bool operator()( const MyType& op1, const MyType& op2 ) const
   {
      return op1.SomeOtherAttribute < op2.SomeOtherAttribute;
   }
};

int main()
{
   // zwei Bäume mit unterschiedlichen Sortierkriterien
   BinaryTree<MyType, MyPred> BT1;
   BinaryTree<MyType, MyOtherPred> BT2;
}

Eisflamme

Ah, stimmt, das ist ne top Idee. Danke!

Mir einfach paar STL-Container anzuschauen wäre natürlich schlau gewesen. Werde es jetzt so bauen, danke