C++：分岐ノードと葉ノードのクラスを分ける？

Question

私は、数（（1,1,2）、（1,2,5）、（2、...）のタプルのソートされたリストから構築されたツリー（基本的にプレフィックスツリーですが、 1,0）など）、それぞれが単一のスカラー値（intまたはdoubleの可能性が高い）に関連付けられています。一度だけ構築されてから何度も繰り返し/検索されるので、各ノードの子を保持するためにstd :: vectorsを使用する予定です。ツリーを検索するには、std :: lower_boundを呼び出すだけで、各ノードの_childrenベクトルでバイナリ検索を行う必要があります。各ベクトルには、各ノードとそれぞれのキーのstd :: pairsが含まれています。ただし、下位ノードには、各タプルの最後のエントリとそれぞれの値からなるペアを持つベクトルが含まれている必要があります。したがって、BranchNodeとは異なる型である必要があります。コードは次のようになります。しかし

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

、各BranchNodeの子供が他のBranchNodesまたはリーフノードのどちらかにすることができるように、両方のクラスには役に立たないGenNodeクラスから継承しなければならないので、これは、本当に醜いです...ですがこれを行うより良い方法は？

Answer 1

両方の型を同じベクトルに格納する場合は、関連するクラス（共通の祖先から継承したクラスまたは継承したクラスの両方）を継承する必要があります。

空の共通の祖先を持つことは醜いように見えるかもしれません。しかし、検索アクション（および他の反復/処理）を仮想メソッドとして基本クラスに入れて、BranchNodeとLeafNode（実装は異なる）に実装すれば、より洗練されたデザインを得ることができます。

この場合、ベースクラスもテンプレート化する必要があります。 私は何を意味することなどの基本クラスを持っている：

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

Answer 2

はい、次の2つの異なる種類が必要です。実際、このようなもの（Leaf OR Node）はdiscriminated unionと呼ばれます。

これを実装するにはいくつかの方法がありますが、おそらく最も一般的なのは2つの派生クラスを持つ共通基本クラスを持つC++です。

共通のベースを持つ興味深い選択肢はboost::variantにrecursive wrapperを使用しています。これは、ポインタの使用を避けるため（そしてあなたのためにメモリ管理を行うため）、特に興味深いものです。