C++: Oddzielne klasy dla węzłów gałęzi i liści?

Question

Tworzę drzewo (zasadniczo drzewo prefiksów, ale dla liczb, a nie ciągów), które składa się z posortowanej listy krotek liczb ((1,1,2), (1,2,5), (2, 1,0) itp.), Z których każdy jest powiązany z jedną wartością skalarną (najprawdopodobniej int lub double). Ponieważ jest on budowany tylko raz, a następnie iterowany nad/przeszukiwany kilka razy, zamierzam użyć std :: vectors do przechowywania dzieci każdego węzła. Aby przeszukać drzewo, wystarczy wywołać std :: lower_bound, aby wykonać przeszukiwanie binarne na wektorze _children każdego węzła, który będzie zawierał std :: pairs każdego węzła i ich odpowiedni klucz. Jednak dolne węzły muszą zawierać wektor z parami składającymi się z ostatniego wpisu w każdej krotce i ich odpowiednich wartości, a zatem muszą być innego typu niż BranchNode. Kod wygląda następująco:

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

Jednak jest to naprawdę brzydki, ponieważ obie klasy musi dziedziczyć z klasy GenNode bezużyteczną tak, że dzieci z każdej BranchNode mogą być inne BranchNodes lub LeafNodes ... jest tam lepszy sposób na zrobienie tego?

Answer 1

Jeśli chcesz przechowywać oba typy w tym samym wektorze, potrzebujesz klas, które mają być powiązane (jeden odziedziczył inny lub oba odziedziczył po wspólnym przodku).

Posiadanie pustego wspólnego przodka może wydawać się brzydkie. Ale możesz uzyskać bardziej elegancki wygląd, jeśli umieścisz akcję wyszukiwania (a także inne iteracje/przetwarzanie) w klasie bazowej jako metodę wirtualną i zaimplementujesz ją w BranchNode i LeafNode (implementacje będą inne).

W tym przypadku klasa podstawowa powinna być również szablonem. Co to znaczy jest o klasę bazową jak:

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

Answer 2

Tak, potrzebne są dwa różne typy. W rzeczywistości coś takiego (Leaf OR Node) nazywa się discriminated union.

Istnieje kilka sposobów jego implementacji, ale w C++ o wspólnej klasie bazowej z dwiema pochodnymi klasami jest prawdopodobnie najczęstsza.

Ciekawą alternatywą dla posiadania wspólnej podstawy jest użycie boost::variant z recursive wrapper. Jest to szczególnie interesujące, ponieważ unika stosowania wskaźników (i tym samym zajmuje się zarządzaniem pamięcią).