Cómo aplanar los iteradores de contenedores anidados?

Question

esto es (aún) un (tro) dar seguimiento a la respuesta de James a esta pregunta: Flattening iterator

¿Cómo se altera el flattenig_iterator tal que funciona de forma recursiva? Supongamos que tengo más niveles de contenedores anidados y no quiero limitarme a una profundidad de anidamiento determinada. Es decir. flattening_iterator debe trabajar con

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

así como con

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

En mi código real que tengo una matriz de objetos que pueden o no contener una matriz de modo a sí mismos.

edición:

Después de jugar con diferentes formas de iteración a través de diferentes tipos de contenedores anidados que aprendí algo que podría ser interesante para otros también:

Acceso a los elementos contenedores con bucles anidados ejecutados 5 a 6 veces más rápido que con la solución del iterador.

Pros:

• elementos pueden ser objetos complejos, por ejemplo (como en mi caso) clases que contienen contenedores.
• más rápida ejecución

Contras:

• Cada estructura del contenedor requiere una nueva implementación del bucle
• algoritmos biblioteca estándar no están disponibles

Otras ventajas y desventajas?

Answer 1

Ok, así que esta no es una solución completa, pero me quedé sin tiempo. Por lo tanto, actualmente no se implementa un iterador completo, sino una clase reducida de tipo iterador que define algo así como esta interfaz y requiere C++ 11. Lo he probado en g ++ 4.7:

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

Dónde NestedContainerType es el tipo de contenedor anidado (sorprendentemente), y Terminator es el tipo de lo más interno que está queriendo salir de la aplanar.

El siguiente código funciona, pero ciertamente no se ha probado exhaustivamente. Envolverlo por completo (suponiendo que esté satisfecho con el avance adelantado solamente) no debería ser demasiado trabajo, en particular si usa 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; 
}; 

Y con los siguientes casos de prueba, se hace lo que se puede esperar:

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

Así que imprime la siguiente para cada uno de los tipos de contenedores:

1 
2 
3 
4 

Tenga en cuenta que doesn Todavía no funciona con set s porque se necesita algo de tiempo para lidiar con el hecho de que los iteradores set devuelven las referencias const. Ejercicio para el lector ... :-)

Answer 2

Voy a esbozar rápidamente una solución:

1. Escribir un rasgo is_container que detecta begin() y end() miembros, o, posiblemente, algunas reglas más complejas;
2. Escriba una plantilla all_flattening_iterator<T> que es solo flattening_iterator<all_flattening_iterator<typename T::value_type>>;
3. Escriba una especialización de all_flattening_iterator<T> para cuando T no es un contenedor (use un parámetro predeterminado de plantilla bool) que es simplemente un iterador regular.

Answer 3

Llego un poco tarde aquí, pero acabo de publicar a library (multidim) para tratar ese problema. Consulte my answer to the related question para más detalles.

Mi solución se inspira en el Alex Wilson's idea del uso de iteradores "anidados telescópicamente". Sin embargo, agrega algunas funciones más (por ejemplo, soporte para contenedores de solo lectura como set s, iteración hacia atrás, acceso aleatorio) y ofrece una interfaz más agradable, ya que detecta automáticamente el tipo de elementos "hoja".