入れ子のコンテナのイテレータをフラット化する方法は？

Question

これは（Notherの）この質問へのジェームズの答えにフォローアップ（まだ）です：Flattening iterator

私はそれが再帰的に動作することをflattenig_iteratorは、このような変更はどうすればよいですか？より多くのレベルのネストされたコンテナがあり、指定された入れ子の深さに制限されたくないとします。私。 flattening_iteratorは私の実際のコードでは

std::vector< std::vector < std::vector < std::vector <int> > > > 

とだけでなく、

std::vector< std::vector < std::vector <int> > > 

で動作するはずです私は、または、そのような配列自体が含まれていない可能性がありますオブジェクトの配列を持っています。

編集：実行ネストされたループを有するコンテナの要素にアクセス

：

私は他の人にも同様に面白いかもしれない何かを学んだ、ネストされたコンテナの異なる種類を反復処理のさまざまな方法で遊んでた後、イテレータソリューションよりも5〜6倍高速です。

長所：

• 要素は、例えば、複雑なオブジェクトであることができます（私の場合のように）コンテナを含むクラスです。
• 速く実行

短所：

• 各コンテナ構造ループの新しい実装を必要と
• 標準ライブラリのアルゴリズムが

その他の長所と短所は使用できませんか？

Answer 1

これは完全な解決策ではありませんが、時間がなくなりました。これは現在、完全なイテレータではなく、このインタフェースのようなものを定義するイテレータのようなクラスをカットし、C++ 11を必要とします。私がg ++ 4.7でそれをテストしてみた：NestedContainerTypeは、ネストされたコンテナタイプを（驚くほど）で、ターミネーターは、あなたがフラット化から抜け出すしたいとしている最も内側のものの一種である

template<typename NestedContainerType, typename Terminator> 
class flatten_iterator 
{ 
    bool complete(); 
    void advance(); 
    Terminator& current(); 
}; 

。

以下のコードは動作しますが、これは確かに広範囲にテストではありません。あなたが前進のみに満足していると仮定して、それを完全に包み込むことは、特にboost::iterator_facadeを使用するとあまり働かないでください。

#include <list> 
#include <deque> 
#include <vector> 

#include <iostream> 

template<typename ContainerType, typename Terminator> 
class flatten_iterator 
{ 
public: 
    typedef flatten_iterator<typename ContainerType::value_type, Terminator> inner_it_type; 
    typedef typename inner_it_type::value_type value_type; 

public: 
    flatten_iterator() {} 

    flatten_iterator(ContainerType& container) : m_it(container.begin()), m_end(container.end()) 
    { 
     skipEmpties(); 
    } 

    bool complete() 
    { 
     return m_it == m_end; 
    } 

    value_type& current() 
    { 
     return m_inner_it.current(); 
    } 

    void advance() 
    { 
     if (!m_inner_it.complete()) 
     { 
      m_inner_it.advance(); 
     } 
     if (m_inner_it.complete()) 
     { 
      ++m_it; 
      skipEmpties(); 
     } 
    } 

private: 
    void skipEmpties() 
    { 
     while (!complete()) 
     { 
      m_inner_it = inner_it_type(*m_it); 
      if (!m_inner_it.complete()) break; 
      ++m_it; 
     } 
    } 

private: 
    inner_it_type     m_inner_it; 
    typename ContainerType::iterator m_it, m_end; 
}; 


template<template<typename, typename ...> class ContainerType, typename Terminator, typename ... Args> 
class flatten_iterator<ContainerType<Terminator, Args...>, Terminator> 
{ 
public: 
    typedef typename ContainerType<Terminator, Args...>::value_type value_type; 

public: 
    flatten_iterator() {} 

    flatten_iterator(ContainerType<Terminator, Args...>& container) : 
     m_it(container.begin()), m_end(container.end()) 
    { 
    } 

    bool complete() 
    { 
     return m_it == m_end; 
    } 

    value_type& current() { return *m_it; } 
    void advance() { ++m_it; } 

private: 
    typename ContainerType<Terminator, Args...>::iterator m_it, m_end; 
}; 

そして、次のテストケースで、それはあなたが期待する何を：それはdoesnのこと

1 
2 
3 
4 

注：

int main(int argc, char* argv[]) 
{ 
    typedef std::vector<int> n1_t; 
    typedef std::vector<std::deque<short> > n2_t; 
    typedef std::list<std::vector<std::vector<std::vector<double> > > > n4_t; 
    typedef std::vector<std::deque<std::vector<std::deque<std::vector<std::list<float> > > > > > n6_t; 

    n1_t n1 = { 1, 2, 3, 4 }; 
    n2_t n2 = { {}, { 1, 2 }, {3}, {}, {4}, {}, {} }; 
    n4_t n4 = { { { {1.0}, {}, {}, {2.0}, {} }, { {}, {} }, { {3.0} } }, { { { 4.0 } } } }; 
    n6_t n6 = { { { { { {1.0f}, {}, {}, {2.0f}, {} }, { {}, {} }, { {3.0f} } }, { { { 4.0f } } } } } }; 

    flatten_iterator<n1_t, int> i1(n1); 
    while (!i1.complete()) 
    { 
     std::cout << i1.current() << std::endl; 
     i1.advance(); 
    } 

    flatten_iterator<n2_t, short> i2(n2); 
    while (!i2.complete()) 
    { 
     std::cout << i2.current() << std::endl; 
     i2.advance(); 
    } 

    flatten_iterator<n4_t, double> i4(n4); 
    while (!i4.complete()) 
    { 
     std::cout << i4.current() << std::endl; 
     i4.advance(); 
    } 

    flatten_iterator<n6_t, float> i6(n6); 
    while (!i6.complete()) 
    { 
     std::cout << i6.current() << std::endl; 
     i6.advance(); 
    } 
} 

だからコンテナタイプごとに次のように出力setイテレータがconst参照を返すという事実に対処する必要があるので、まだsetで作業しています。読者のための運動... :-)

Answer 2

私はすぐに解決策について概説します：

1. がbegin()とend()メンバー、またはおそらくいくつかのより複雑なルールを検出is_container形質を書きます。
2. ちょうどflattening_iterator<all_flattening_iterator<typename T::value_type>>のall_flattening_iterator<T>テンプレートを書きます。
3. Tが通常のイテレータであるコンテナ（デフォルトテンプレートboolパラメータを使用）でない場合は、all_flattening_iterator<T>の特殊化を作成します。

Answer 3

は私が遅れて、ここで少し到着し、私はちょうどこのような問題に対処するためにa library (multidim)を公開しています。詳細についてはmy answer to the related questionをご覧ください。

私のソリューションは、「入れ子式にネスト」イテレータを使用してのAlex Wilson's ideaからインスピレーションを取ります。これは、 "リーフ"要素のタイプを自動検出するので、いくつかの機能を追加します（例えば、setのような読み取り専用コンテナのサポート、後方反復、ランダムアクセス）。