0

私のアプリケーションでは、（不均衡な）ツリーデータ構造があります。このツリーは、単に「std :: list of std::lists」で構成されています。ノードはサブノードの任意の「リスト」を保持します。単一のリストの代わりにこれを使用すると、アプリケーションの残りの部分がはるかに簡単になりました。（このプログラムは、移動するノードをあるツリーから別のツリー/ツリー内の別の部分/独自のツリーに変更することを目的としています）。

ここで明らかなタスクは、「ツリー」内のサブツリーを見つけることです。非再帰的検索の場合、それは十分に単純です。

subtree_iterator find_subtree(const N& n) {         
    auto iter(subtrees.begin());
    auto e(subtrees.end());
    while (iter != e) {
        if ((*iter)->name == n) {
            return iter;
        }
        ++iter;
    }
    return e;
}

これは、イテレータをサブツリーの位置に戻します。ただし、マルチレベル検索を実装しようとすると問題が発生します。hello.world.testつまり、ドットが新しいレベルを示す場所を検索したいと思います。

検索は問題なく機能しました

subtree_iterator find_subtree(const pTree_type& otree, std::string identify) const {
    pTree_type tree(otree);
    boost::char_separator<char> sep(".");
    boost::tokenizer<boost::char_separator<char> > tokens(identify, sep);
    auto token_iter(tokens.begin());
    auto token_end(tokens.end());

    subtree_iterator subtree_iter;
    for (auto token_iter(tokens.begin()); token_iter != token_end; ++token_iter) {
        std::string subtree_string(*token_iter);
        subtree_iter = tree->find_subtree_if(subtree_string);
        if (subtree_iter == tree->subtree_end()) {
            return otree->subtree_end()
        } else {
            tree = *subtree_iter;
        }
    }
    return subtree_iter;
}

一見、「正しく」動作しているように見えましたが、使用しようとすると失敗します。それを使用すると次のようになります

auto tIn(find_subtree(ProjectTree, "hello.world.test"));
if (tIn != ProjectTree->subtree_end()) {
    //rest
}

ただし、「互換性のないイテレータをリストする」というデバッグアサーションエラーが発生します。これはそれほど奇妙なことではありません。異なるリストのイテレータを相互に比較しています。しかし、私はそのようなことを実装できますか？私の「バックアップ」オプションはstd::pair<bool,iterator>、ブール部分がツリーが実際に存在するかどうかを判断する場所を返すことです。ツリー全体を単一のリストにする以外に、別の方法はありますか？

4

2 に答える 2

1

内部でイテレータに取り組むべきではありません。代わりにノードを使用してください。

template <typename T>
struct Node {
 T item;
 Node<T>* next;
};

次に、ノードを次のようなイテレータファサードにカプセル化します。

template<typename T>
class iterator {
private:
  Node<T>* node;
public:
  ...
};

次に、end（）に到達または返されるたびに返される、一般的な無効なノード（ノードがnullptrの場合）を使用します。私が提案するのは単一のリンクリストであることに注意してください（標準の二重リンクリストではありません）。これは、無効なnullノードを指す無効な汎用end（）イテレータから戻ることができないためです。アルゴリズムでイテレータ演算子--（）を使用しない場合は、これで問題ありません。

于 2012-11-27T12:49:24.933 に答える
0

std::vector<list_iterator>トラバースするスタック？.back()スタックのが前のスタックと等しくなることが許可されている唯一のものend()であり.front()、ルートへのイテレータである場合はどうlistでしょうか。

于 2012-11-27T13:25:19.870 に答える