C++: Getrennte Klassen für Zweig- und Blattknoten?

Question

Ich mache einen Baum (im Wesentlichen ein Präfix Baum, aber für Zahlen nicht Strings), die aus sortierten Liste von Tupeln von Zahlen ((1,1,2), (1,2,5), (2, 1,0) etc ...), die jeweils einem einzelnen Skalarwert (int oder double am wahrscheinlichsten) zugeordnet sind. Da es nur einmal erstellt und dann mehrmals durchlaufen/durchsucht wird, plane ich, std :: vectors zu verwenden, um die untergeordneten Elemente jedes Knotens zu halten. Um den Baum zu durchsuchen, muss ich einfach std :: lower_bound aufrufen, um eine binäre Suche auf dem _children Vektor jedes Knotens durchzuführen, der std :: -Paare jedes Knotens und ihren jeweiligen Schlüssel enthält. Die untersten Knoten müssen jedoch einen Vektor mit Paaren enthalten, die aus dem letzten Eintrag in jedem Tupel und ihren jeweiligen Werten bestehen und daher von einem anderen Typ als der BranchNode sein müssen. Der Code sieht wie folgt aus:

class GenNode 
{ 
}; 

template<typename key_type,typename value_type> 
class BranchNode : GenNode 
{ 
    void insert(std::pair< std::vector<key_type> , value_type>); 
private: 
    std::vector< std::pair<key_type,GenNode*> > _children; 
}; 

template<typename key_type,typename value_type> 
class LeafNode : GenNode 
{ 
private: 
    std::vector< std::pair<key_type,value_type> > _children; 
}; 

Allerdings ist dies wirklich hässlich ist, da beide Klassen von der nutzlosen GenNode Klasse erben müssen, damit die Kinder jedes BranchNode entweder andere BranchNodes oder LeafNodes sein kann ... gibt es eine bessere Möglichkeit, dies zu tun?

Answer 1

Wenn Sie beide Typen in dem gleichen Vektor speichern möchten, müssen Sie die Klassen bezogen werden (eine von anderen erblichen oder beide aus dem gemeinsamen Vorfahren geerbt).

Einen leeren gemeinsamen Vorfahren zu haben, mag hässlich erscheinen. Sie können jedoch eleganteres Design erhalten, wenn Sie Ihre Suchaktion (sowie andere Iterationen/Verarbeitungen) als virtuelle Methode in die Basisklasse einfügen und sie in BranchNode und LeafNode implementieren (die Implementierungen wären anders).

Die Basisklasse sollte in diesem Fall ebenfalls templatiert werden. Was ich meine, ist mit einer Basisklasse wie:

template<typename key_type,typename value_type> 
class GenNode { 
public: 
    virtual value_type search(key_type key) = 0; 
}; 

Answer 2

Ja, Sie müssen zwei verschiedene Arten. In der Tat wird so etwas (Leaf OR Node) discriminated union genannt.

Es gibt mehrere Möglichkeiten, es zu der Umsetzung, aber in C++ eine gemeinsame Basisklasse mit zwei abgeleiteten Klassen aufweist, ist wahrscheinlich die häufigste.

Eine interessante Alternative zu einer gemeinsamen Basis ist die Verwendung von boost::variant mit einer recursive wrapper. Dies ist besonders interessant, weil es die Verwendung von Zeigern vermeidet (und somit die Speicherverwaltung für Sie übernimmt).