2013/12/21(土)template <class T> class TreeNode { ... }; の中身は？

はてブ数 2013/12/21 18:42 プログラミング::C++つーさ

tree を作ることを考える。

根があって、任意数の子をとれる。
子も任意数の子をとれる。

汎用的なtreeクラスの節、template class Node 中身; の中身について考える。

どうやったら引き回しやすいか。

まぁ、複数の子っても、たくさんの子を持つか、
あるいはまったく子を持たないかわからないので、
二分木で表現することにする。

思いつくまま定義を書くと、

template<class TValue>
class Node
{
  TValue value;
  Node<T> *parent, *firstChild, *nextSibling;
};

みたいになって、それを実装してみたのが
https://gist.github.com/ttsuki/95ceef4cacdc9c5e0294 なのだけど、
いざ使ってみようと思って、
使う側に回ってからTValueにあたる型を作ってて思ったんだけど、

普通、Treeで何らかの構造を表そうと思ったら、
その要素TValueはデータ構造的にツリーになる前提があるわけで
TValue自身がTValue::ナントカ() が自分の親・兄弟にアクセスできないと、
トラヴァーサルしにくいなーということに後から気づいた。

じゃあ、

class 実際に扱いたい型 : public Node<実際に扱いたい型 *>
{
  ctor()
    : Node(this)
  {
  }
  
};

なら？
にしても、parentは、Node<TValue *>の型であって、
それをTValueとして扱うにはダウンキャストがいるのでなんか気持ち悪い。
って考えてると、

class 実際に扱いたい型
{ 
  Node<実際に扱いたい型 *> link;
  ctor()
    : link(this)
  {
  }
};

になって、マジで？ってなる。

これだと、でもまぁ、これだとキャストなしに、
自分の親ノードを得るのに return link.parent.value; できるので……。

ただ、GetParent() とか、ApplyAllChildren等を
全部pImplばりに再実装しないといけなくて、

それめんどくさいなぁ。

なんか、お約束のレシピはないのかしら。

コメント（0件）