c++ - 如何展平嵌套容器的迭代器？

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 倍。

优点：

元素可以是复杂的对象，例如（在我的例子中）包含容器的类。
更快的执行

缺点：

每个容器结构都需要新的循环实现
标准库算法不可用

其他优点和缺点？

score 7 · Accepted Answer

我将快速概述一个解决方案：

编写一个is_container检测begin()和end()成员的特征，或者可能是一些更复杂的规则；
编写一个all_flattening_iterator<T>模板，它只是一个flattening_iterator<all_flattening_iterator<typename T::value_type>>;
编写all_flattening_iterator<T>for when的特化T不是容器（使用默认模板bool参数），它只是一个常规迭代器。

score 4 · Accepted Answer

好的，所以这不是一个完整的解决方案 - 但我没时间了。所以这目前实现的不是一个完整的迭代器，而是一个简化的迭代器类，它定义了类似这个接口的东西，并且需要 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();
    }
}

因此为每种容器类型打印以下内容：

请注意，它还不能与s 一起使用，因为需要一些 foo 来处理迭代器返回 const 引用set的事实。set为读者练习... :-)

score 2 · Accepted Answer

我到这里有点晚了，但我刚刚发布了一个库（multidim）来处理这样的问题。查看我对相关问题的回答以了解详细信息。

我的解决方案从Alex Wilson 的使用“伸缩嵌套”迭代器的想法中获得灵感。不过，它增加了一些功能（例如，支持只读容器，如sets、向后迭代、随机访问）并提供更令人愉悦的界面，因为它自动检测“叶”元素的类型。

c++ - 如何展平嵌套容器的迭代器？

3 回答 3

Related

Reference