5

問題は十分に単純に見えます。基本的に、次のような一連のシーケンスがあります。

typedef mpl::vector<
  mpl::vector<mpl::_1, mpl::_2>,
  mpl::vector<mpl::_1, mpl::_2, mpl::_3>,
  mpl::vector<mpl::_2, mpl::_1>,
  mpl::vector<mpl::_2, mpl::_2>,
  mpl::vector<mpl::_2, mpl::_2, mpl::_3>
> seq;

私がやりたいのは、これをトライに変換することです。最終結果は次のようになります。

mpl::map<
  mpl::pair<mpl::_1, 
    mpl::map<
      mpl::pair<mpl::_2,
        mpl::map<
          mpl::pair<TERMINAL, T>,
          mpl::pair<mpl::_3,
            mpl::map<
              mpl::pair<TERMINAL, T>
            >
          >
        >
      >
    >
  >
  mpl::pair<mpl::_2, 
    mpl::map<
      mpl::pair<mpl::_1,
        mpl::map<
          mpl::pair<TERMINAL, T>
        >
      >,
      mpl::pair<mpl::_2,
        mpl::map<
          mpl::pair<TERMINAL, T>,
          mpl::pair<mpl::_3,
            mpl::map<
              mpl::pair<TERMINAL, T>
            >
          >
        >
      >
    >
  >
>

それで、問題は、これは可能ですか（私はそうではないと思います）？可能であれば、どの暗黒の呪文を逃しましたか?

編集：シーケンスのシーケンスからトライへの上記の変換が明確でない場合、平易な英語でそれを述べることができるかどうか見てみましょう（多くの場合、より困難です）。基本的に、メインシーケンス内の各シーケンスはいくつかのタイプ（_1など_2.) 変換されたバージョンは、一般的なプレフィックスが折りたたまれた trie です。添付画像が参考になるかも・・・

結果のツリー

EDIT2：@Yakkのおかげで、うまくいけば、質問はより明確になります...

4

2 に答える 2

6

どうぞ:

struct Terminal;

template < typename Trie, typename First, typename Last,
           typename Enable = void >
struct insertInTrie_impl
{
    typedef typename
        mpl::deref<First>::type key;

    typedef typename 
        mpl::at<
            Trie,
            key
        >::type subTrieOrVoid; // would be easier if "at" supported Default

    typedef typename
        mpl::if_<
            boost::is_same< subTrieOrVoid, mpl::void_ >,
            mpl::map<>,
            subTrieOrVoid
        >::type subTrie;

    typedef typename
        mpl::insert<
            Trie,
            mpl::pair<
                key, typename
                insertInTrie_impl<
                    subTrie, typename
                    mpl::next<First>::type,
                    Last
                >::type
            >
        >::type type;
};

template < typename Trie, typename First, typename Last >
struct insertInTrie_impl< Trie, First, Last, typename 
    boost::enable_if< boost::is_same<First, Last> >::type >
    : mpl::insert<
        Trie,
        mpl::pair< Terminal, Terminal >
        // I'm not sure what you want in your terminal node
    >
{};

template < typename Trie, typename Seq >
struct insertInTrie
    : insertInTrie_impl< 
        Trie, typename 
        mpl::begin<Seq>::type, typename 
        mpl::end<Seq>::type
    >
{};


template < typename SeqOfSeq >
struct constructTrie
    : mpl::fold< 
        SeqOfSeq,
        mpl::map<>,
        insertInTrie< mpl::_1, mpl::_2 >
    >
{};

insertInTrie_implイテレータを使用して、シーケンスを既存のトライに挿入する再帰メタ関数です。insertInTrieが呼び出すシーケンスを受け入れますinsertInTrie_impl。空のトライから始まる、指定されたシーケンス内のすべてのシーケンスにconstructTrie適用されます。insertInTrie

擬似コードでは、これは次のようになります。

Trie insertInTrie_impl(trie, first, last)
{
    if (first == last)
    {
        trie.insert(Terminal, Terminal);
        return trie;
    }

    key = *first;

    subTrie = trie[key];
    if (subTrie = void) // key not found
    {
        subTrie = emptyTrie;
    }

    trie.insert(key, insertInTrie_impl(subTrie, ++first, last))

    return trie;
}

Trie insertInTrie(trie, seq)
{
    return insertInTrie_impl(trie, seq.begin(), seq.end();
}

Trie constructTrie(seqOfSeq)
{
    return fold(seqOfSeq, emptyTrie, insertInTrie);
}

最後に、使用例:

int main()
{
    typedef mpl::vector<
        mpl::vector<mpl::_1, mpl::_2>,
        mpl::vector<mpl::_1, mpl::_2, mpl::_3>,
        mpl::vector<mpl::_2, mpl::_1>,
        mpl::vector<mpl::_2, mpl::_2>,
        mpl::vector<mpl::_2, mpl::_2, mpl::_3>
    > seqOfSeq;

    typedef constructTrie< seqOfSeq >::type bigTrie;

    BOOST_MPL_ASSERT(( 
        mpl::has_key<
            mpl::at< 
                mpl::at< 
                    bigTrie, 
                    mpl::_1
                >::type, 
                mpl::_2
            >::type, 
            Terminal
        > ));
    BOOST_MPL_ASSERT(( 
        mpl::has_key<
            mpl::at< 
                mpl::at< 
                    mpl::at< 
                        bigTrie, 
                        mpl::_1
                    >::type,
                    mpl::_2
                >::type, 
                mpl::_3
            >::type, 
            Terminal
        > ));
    BOOST_MPL_ASSERT(( 
        mpl::has_key<
            mpl::at< 
                mpl::at< 
                    bigTrie, 
                    mpl::_2
                >::type,
                mpl::_2
            >::type, 
            Terminal
        > ));
}
于 2013-02-19T15:27:42.480 に答える
1

したがって、答えは「はい、可能です」です。

add_to_trie と書きます。空の可能性のあるトライと要素 (型のシーケンス) を取り、その要素が追加されたトライを返します。

空のトライといくつかのシーケンス、およびその他のいくつかの手作りのケースで add_to_trie をテストします。共通接頭辞: ("A")("A","B")、共通接頭辞なし: ("A","A")("B","A")、共通接頭辞なし: ("A") ,"B")("B")、同じものの 2 つのコピー: ("A")("A") など

累積書き込み。値とバイナリ ファンクターとシーケンスを取ります。シーケンスの各要素 s に value = functor(value, s) を適用すると、value が返されます。

1 から 5 までを合計して結果を出力することにより、累積をテストします。

2つを構成します。

これにより、テンプレートの再帰スタックが壊れる可能性があり、各ステップを正しく記述するのは簡単ではありませんが、機能します。

最初に、文字列に対する上記の操作を記述すると役立つ場合があります。次に、関数を機能させます。次に、型の操作に変換します。

すでにboost適切な金額が書かれているお金でも賭けます。accumulate

于 2013-02-19T14:10:13.993 に答える