6

ポインターの代わりに反復子を使用する C++ でツリー データ構造を作成するにはどうすればよいですか? これを行うことができるSTLには何も見つかりませんでした。私がやりたいことは、次のようなツリーを作成および操作できるようにすることです。

#include <iostream>
#include <tree>
using namespace std;

int main()
{
    tree<int> myTree;

    tree<int>::iterator i = myTree.root();
    *i = 42;

    tree<int>::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";

    return 0;
}

ありがとう、tree.hh はまさに私が探していたもののようです。

これが、任意のインデックス タイプを保持し、検索用に最適化され、挿入が得意なデータ構造の利点を得る場合は、マップの使用を検討してください。

マップは、対数検索、対数挿入、対数削除、線形空間など、ツリーと同じパフォーマンス保証を持つ連想コンテナーです。内部的には、赤黒木として実装されることがよくありますが、それは保証ではありません。それでも、STL ユーザーとして気にする必要があるのは、STL アルゴリズムとデータ構造のパフォーマンス保証だけです。それらがツリーとして実装されているか、小さな緑の男性として実装されているかは問題ではありません。

地図が必要かどうかわかりませんが、情報をありがとうございます。ツリーを実装する代わりに、可能な限りマップを使用することを忘れないでください。

4

2 に答える 2

5

これは、少し異なりますが、やりたいことに少し近いtree.hhです。

これは、その Web サイトから抽出されたコードの一部です。

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i) 
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

今何が違うの？ノードをツリーに追加することになると、実装はより簡単になります。あなたのバージョンは明らかにシンプルですが、このライブラリの開発者はおそらく、ツリーのサイズなど、ツリーを参照せずにアクセスできる情報を望んでいました。

また、パフォーマンス上の理由から、すべてのノードにルートを保存したくなかったと思います。したがって、自分のやり方で実装したい場合は、ほとんどのロジックを保持し、親ツリーへのリンクをイテレータに追加して、append を少し書き直すことをお勧めします。

于 2008-08-21T02:57:14.663 に答える
3

なぜそれをしたいのですか？これが学習目的である場合は、独自のツリー データ構造を作成できます。これが、任意のインデックス タイプを保持し、検索用に最適化され、挿入が得意なデータ構造の利点を得る場合は、マップの使用を検討してください。

マップは、対数検索、対数挿入、対数削除、線形空間など、ツリーと同じパフォーマンス保証を持つ連想コンテナーです。内部的には、赤黒木として実装されることがよくありますが、それは保証ではありません。それでも、STL ユーザーとして気にする必要があるのは、STL アルゴリズムとデータ構造のパフォーマンス保証だけです。それらがツリーとして実装されているか、小さな緑の男性として実装されているかは問題ではありません。

ちなみに、root() 関数のようなものはありません。すべての STL コンテナーには、コンテナーの概念的な開始を実装する begin() 関数があります。その関数によって返される反復子の種類は、コンテナーの特性によって異なります。

于 2008-08-21T01:47:02.350 に答える