如何扁平化嵌套容器的迭代器？

Question

這是（還）跟隨詹姆斯對這個問題的回答：Flattening iterator

如何修改flattenig_iterator以便遞歸地工作？假設我有更多級別的嵌套容器，我不想限制給定的嵌套深度。即flattening_iterator應

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

工作，以及與

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

在我實際的代碼我有可能或沒有包含這樣的陣列本身對象的數組。

編輯：

訪問與執行嵌套循環容器中的元素：

通過不同類型的嵌套容器我學到了一些東西，可能是有趣的，其他人也進行迭代不同的方式玩耍後比迭代器解決方案快5到6倍。

優點：

• 元件可以是複雜的對象，例如（就像我的情況）包含容器的類。
• 更快的執行速度

缺點：

• 每個容器結構需要一個新的循環執行
• 標準庫算法不可用

其他利弊？

Answer 1

好的，所以這不是一個完整的解決方案 - 但我用完了時間。所以這當前不是一個完整的迭代器，而是一個類似於這個接口的類似於迭代器的類，它需要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; 

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

並與下面的測試情況下，它確實你所期望的：

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 

注意，它不尚未與set一起使用，因爲需要處理set迭代器返回const引用的事實。爲讀者練習... :-)

Answer 2

我會很快勾勒出一個解決方案：

1. 寫is_container性狀檢測begin()和end()成員，或可能還有一些更復雜的規則;
2. 編寫一個all_flattening_iterator<T>模板，它只是一個flattening_iterator<all_flattening_iterator<typename T::value_type>>;
3. 當T不是一個容器（使用默認模板bool參數）時，寫一個all_flattening_iterator<T>的專業化版本，它只是一個常規迭代器。

Answer 3

我在這裏稍微晚點到達，但我剛剛發佈了a library (multidim)來處理這樣的問題。詳情請查看my answer to the related question。

我的解決方案從使用「可伸縮嵌套」迭代器的Alex Wilson's idea獲得靈感。它雖然增加了一些功能（例如支持只讀容器，例如set，向後迭代，隨機訪問），並提供更愉快的界面，因爲它可以自動檢測「葉子」元素的類型。