Come appiattire gli iteratori dei contenitori nidificati?

Question

questo è (ancora) un (altro) follow-up alla risposta James' a questa domanda: Flattening iterator

Come si toglie flattenig_iterator tale che funziona in modo ricorsivo? Supponiamo che io abbia più livelli di contenitori annidati e non voglio essere limitato a una determinata profondità di annidamento. Cioè flattening_iterator dovrebbe funzionare con

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

così come con

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

Nel mio codice vero e ho un array di oggetti che potrebbero o meno contenere una tale varietà se stessi.

modificare:

Dopo aver suonato in giro con diversi modi di iterazione attraverso diversi tipi di contenitori nidificati che ho imparato qualcosa che potrebbe essere interessante per gli altri così:

Accesso ai elementi contenitori con cicli annidati eseguiti Da 5 a 6 volte più veloce rispetto alla soluzione iteratore.

Pro:

• elementi possono essere oggetti complessi, ad esempio (come nel mio caso) le classi che contengono contenitori.
• più veloce l'esecuzione

Contro:

• Ogni struttura contenitore richiede una nuova implementazione del ciclo
• algoritmi della libreria standard non sono disponibili

Altri pro ei contro?

Answer 1

Ok, quindi questa non è una soluzione completa, ma ho esaurito il tempo. Quindi questo attualmente non implementa un iteratore completo ma una classe simile a un iteratore che definisce qualcosa come questa interfaccia e richiede C++ 11. Ho provato su g ++ 4.7:

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

Dove NestedContainerType è il tipo di contenitore nidificato (sorprendentemente), e Terminator è il tipo di cosa più intima che hai intenzione di uscire dalla appiattire.

Il codice seguente funziona, ma questo non è certamente ampiamente testato. Avvolgerlo completamente (supponendo che tu sia soddisfatto solo in anticipo) non dovrebbe essere troppo impegnativo, in particolare se usi 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; 
}; 

E con i seguenti casi di test, si fa quello che ci si aspetta:

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

Così stampa il seguente per ognuno dei tipi di contenitori:

1 
2 
3 
4 

Nota che doesn funziona ancora con set s perché ci sono alcuni foo richiesti per affrontare il fatto che gli iteratori set restituiscono riferimenti const. Esercizio per il lettore ... :-)

Answer 2

sarò delineare in fretta una soluzione:

1. Scrivi un tratto is_container che rileva begin() e end() membri, o, eventualmente, alcune regole più complesse;
2. Scrivere un modello all_flattening_iterator<T> che è solo un flattening_iterator<all_flattening_iterator<typename T::value_type>>;
3. Scrivere una specializzazione di all_flattening_iterator<T> per quando T non è un contenitore (utilizzare un parametro di modello predefinito bool) che è solo un normale iteratore.

Answer 3

Sono arrivato un po 'in ritardo qui, ma ho appena pubblicato a library (multidim) per affrontare tale problema. Controlla my answer to the related question per i dettagli.

La mia soluzione si ispira allo Alex Wilson's idea dell'utilizzo di iteratori "telescopicamente annidati". Aggiunge alcune funzionalità in più (ad esempio supporto per contenitori di sola lettura come set s, iterazione all'indietro, accesso casuale) e offre un'interfaccia più piacevole, poiché rileva automaticamente il tipo di elementi "foglia".