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

Question

这是詹姆斯回答这个问题的一个(另一个)跟进： Flattening iterator

如何更改flattenig_iterator以使其递归工作？假设我有更多级别的嵌套容器,我不希望被限制在给定的嵌套深度.即flattening_iterator应该使用

std::vector< std::vector < std::vector < int > > >@H_404_5@ 
 以及
 
  
 std::vector< std::vector < std::vector < std::vector < int > > > >@H_404_5@ 
 在我的实际代码中,我有一个对象数组,它们本身可能包含或不包含这样的数组.
 
 编辑：
 
 在使用不同方式迭代不同类型的嵌套容器之后,我学到了一些可能对其他人感兴趣的东西：
 
 使用嵌套循环访问容器元素的速度比使用迭代器解决方案快5到6倍.
 
 优点：
 
 >元素可以是复杂的对象,例如(就像我的情况一样)包含容器的类.
>执行速度更快
 
 缺点：
 
 >每个容器结构都需要一个新的循环实现
>标准库算法不可用
 
 其他利弊？

Answer 1

好的,所以这不是一个完整的解决方案 – 但我没时间了.所以这当前实现的不是一个完整的迭代器,而是一个类似迭代器的类,它定义了类似这个接口的东西,并且需要C 11.我在g 4.7上测试过它：

template<typename NestedContainerType,typename Terminator>
class flatten_iterator
{
    bool complete();
    void advance();
    Terminator& current();
};@H_404_5@ 
 其中NestedContainerType是嵌套的容器类型(令人惊讶),而Terminator是你想要从flatten中走出来的最里面的东西的类型.
 
 下面的代码有效,但这肯定没有经过广泛测试.完全包装它(假设你对前进只是满意)不应该太多工作,特别是如果你使用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;
};@H_404_5@ 
 通过以下测试用例,它可以满足您的期望：
 
  
 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();
    }
}@H_404_5@ 
 因此,为每种容器类型打印以下内容：
 
  
 1
2
3
4@H_404_5@ 
 请注意,它还没有使用集合,因为需要一些foo来处理set迭代器返回const引用这一事实.为读者练习…

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

解决方法

猜你在找的C&C++相关文章