C++: classi separate per nodi di ramo e foglia?

Question

Sto facendo un albero (essenzialmente un albero prefisso, ma per i numeri non stringhe), che è costruito dalla lista ordinata di tuple di numeri ((1,1,2), (1,2,5), (2, 1,0) ecc ...), ciascuno associato a un singolo valore scalare (int o doppio molto probabilmente). Dato che è costruito solo una volta e poi ripetuto/cercato più volte, ho intenzione di usare std :: vectors per contenere i figli di ogni nodo. Per cercare l'albero, ho solo bisogno di chiamare std :: lower_bound per fare una ricerca binaria sul vettore _children di ogni nodo, che conterrà std :: pairs di ciascun nodo e la rispettiva chiave. Tuttavia, i nodi inferiori devono contenere un vettore con coppie costituite dall'ultima voce in ciascuna tupla e i rispettivi valori e, pertanto, devono essere di un tipo diverso rispetto a BranchNode. Il codice è simile al seguente:

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

Tuttavia, questo è davvero brutta, perché entrambe le classi devono ereditano dalla classe GenNode inutile in modo che i figli di ogni BranchNode possono essere sia altri BranchNodes o LeafNodes ... c'è un modo migliore per farlo?

Answer 1

Se si desidera memorizzare entrambi i tipi nello stesso vettore, è necessario associare le classi (una ereditata da altro o entrambe ereditate dall'antenato comune).

Avere un antenato comune vuoto può sembrare brutto. Ma puoi ottenere un design più elegante se inserisci la tua azione di ricerca (così come altre iterazioni/elaborazioni) nella classe base come metodo virtuale e la implementa in BranchNode e LeafNode (le implementazioni sarebbero diverse).

In questo caso, anche la classe di base deve essere basata su modelli. Quello che voglio dire è avere una classe di base come:

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

Answer 2

Sì, avete bisogno di due tipi diversi. In effetti, qualcosa del genere (Leaf OR Node) è chiamato discriminated union.

Ci sono diversi modi per implementarlo, ma in C++ avere una classe base comune con due classi derivate è probabilmente la più comune.

Un'alternativa interessante all'utilizzo di una base comune è l'utilizzo di boost::variant con un recursive wrapper. Questo è particolarmente interessante perché evita l'uso di puntatori (e quindi si occupa della gestione della memoria per te).