7

これは、この質問に対する James の回答に対する (まだ) (別の) フォローアップです: Flattening iterator

再帰的に動作するように flattenig_iterator を変更するにはどうすればよいですか? 入れ子になったコンテナーのレベルが増え、特定の入れ子の深さに制限されたくないとします。つまり、 flattening_iterator で動作する必要があります

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

と同様に

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

私の実際のコードでは、そのような配列自体を含む場合と含まない場合があるオブジェクトの配列があります。

編集：

さまざまな種類のネストされたコンテナーを反復処理するさまざまな方法を試した後、他の人にとっても興味深いことを学びました。

ネストされたループを使用してコンテナー要素にアクセスすると、イテレーター ソリューションよりも 5 ～ 6 倍速く実行されます。

長所：

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

短所：

  • 各コンテナ構造には、ループの新しい実装が必要です
  • 標準ライブラリのアルゴリズムは利用できません

その他の長所と短所は？

4

3 に答える 3

7

解決策の概要を簡単に説明します。

  1. 検出してメンバーになるis_container特性、または場合によってはより複雑なルールを作成します。begin()end()
  2. ;all_flattening_iterator<T>だけのテンプレートを作成します。flattening_iterator<all_flattening_iterator<typename T::value_type>>
  3. forが通常のイテレータであるコンテナではないall_flattening_iterator<T>場合(デフォルトのテンプレート パラメータを使用)の特殊化を記述します。Tbool
于 2012-07-12T15:12:31.283 に答える
4

わかりました。これは完全な解決策ではありませんが、時間がなくなりました。したがって、これは現在、完全なイテレータではなく、このインターフェイスのようなものを定義し、C++11を必要とするカットダウンされたイテレータのようなクラスを実装しています。g++4.7でテストしました。

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

ネストされたコンテナタイプはどこにありますかNestedContainerType（驚くべきことに）、ターミネーターはフラットから抜け出したい最も内側のもののタイプです。

以下のコードは機能しますが、これは確かに広範囲にテストされていません。それを完全にまとめる（フォワードアドバンスのみに満足していると仮定して）ことは、特にを使用する場合は、それほど手間がかかることはありません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;

    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;
};

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

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();
    }
}

したがって、コンテナタイプごとに次のように出力します。

1
2
3
4

イテレータがconst参照を返すsetという事実に対処するために必要ないくつかのfooがあるため、sではまだ機能しないことに注意してください。set読者のための練習...:-)

于 2012-07-12T17:01:38.717 に答える
2

ここに到着するのが少し遅れましたが、このような問題に対処するためのライブラリ (multidim)を公開しました。詳細については、関連する質問に対する私の回答を確認してください。

私のソリューションは、「入れ子になった」イテレータを使用するという Alex Wilson のアイデアから着想を得ています。ただし、いくつかの機能が追加され (たとえば、s、後方反復、ランダム アクセスなどの読み取り専用コンテナーのサポートset)、「リーフ」要素のタイプを自動検出するため、より快適なインターフェイスが提供されます。

于 2016-01-17T21:29:49.063 に答える