È una cattiva pratica creare un iteratore consapevole della propria fine

5

Per qualche background del perché sto facendo questa domanda ecco un esempio. In python il metodo chain concatena un numero arbitrario di intervalli insieme e li rende in uno senza fare copie. Ecco un collegamento nel caso in cui non lo capisci. Ho deciso di implementare la catena in c ++ usando modelli variadic. Per quanto ne so, l'unico modo per fare un iteratore per catena che andrà al contenitore successivo è che ogni iteratore sappia della fine del contenitore (ho pensato a una sorta di hack in cui != è chiamato contro la fine saprà di andare al prossimo contenitore, ma il primo modo sembrava più facile e più sicuro e più versatile).

La mia domanda è se c'è qualcosa di intrinsecamente sbagliato in un iteratore che conosce la propria fine, il mio codice è in c ++ ma questo può essere indipendente dal linguaggio poiché molte lingue hanno iteratori.

#ifndef CHAIN_HPP
#define CHAIN_HPP

#include "iterator_range.hpp"

namespace iter {
   template <typename ... Containers>
       struct chain_iter;
   template <typename Container>
       struct chain_iter<Container> {

        private:
           using Iterator = decltype(((Container*)nullptr)->begin());
           Iterator begin;
           const Iterator end;//never really used but kept it for consistency

        public:
           chain_iter(Container & container, bool is_end=false) :
               begin(container.begin()),end(container.end()) {
                   if(is_end) begin = container.end();
           }
           chain_iter & operator++()
           {
               ++begin;
               return *this;
           }
           auto operator*()->decltype(*begin)
           {
               return *begin;
           }
           bool operator!=(const chain_iter & rhs) const{
               return this->begin != rhs.begin;
           }
       };
   template <typename Container, typename ... Containers>
       struct chain_iter<Container,Containers...>
       {

        private:
           using Iterator = decltype(((Container*)nullptr)->begin());
           Iterator begin;
           const Iterator end;
           bool end_reached = false;
           chain_iter<Containers...> next_iter;

        public:
           chain_iter(Container & container, Containers& ... rest, bool is_end=false) :
               begin(container.begin()),
               end(container.end()),
               next_iter(rest...,is_end) {
                   if(is_end)
                       begin = container.end();
               }
           chain_iter & operator++()
           {
               if (begin == end) {
                   ++next_iter;
               }
               else {
                   ++begin;
               }
               return *this;               
           }
           auto operator*()->decltype(*begin)
           {
               if (begin == end) {
                   return *next_iter;
               }
               else {
                   return *begin;
               }
           }   
           bool operator !=(const chain_iter & rhs) const {
               if (begin == end) {
                   return this->next_iter != rhs.next_iter;
               }
               else
                   return this->begin != rhs.begin;
           }
        };
   template <typename ... Containers>
       iterator_range<chain_iter<Containers...>> chain(Containers& ... containers)
       {
           auto begin = 
               chain_iter<Containers...>(containers...);
           auto end =
               chain_iter<Containers...>(containers...,true);
           return 
               iterator_range<chain_iter<Containers...>>(begin,end);
       }
}

#endif //CHAIN_HPP
    
posta aaronman 24.09.2013 - 03:53
fonte

3 risposte

5

Ci sono stato, bruciato. Creare cose che assomigliano a un iteratore ma che hanno requisiti diversi o aggiuntivi porteranno a un pasticcio. Fondamentalmente molti intervalli non sono copiabili o almeno non a buon mercato, ma è quello che normalmente si aspetta da un iteratore (è un requisito del concetto di iteratore).

Dovresti non avere iteratori che sappiano della propria fine. Ma il concatenamento funziona con intervalli . Esistono due modi per definire gli intervalli:

  • Come "contenitori" iterabili, che puoi fare di semplici coppie di iteratori. Questo è un modo C ++ (e Boost.Range 1 ha alcune utilità utili per questi), ma a volte è un bel po 'di lavoro extra per creare vari oggetti che forniscano sequenze adatte all'interfaccia.

  • Definisci la tua interfaccia per "generatori". Probabilmente sarà simile a quello di Python, ma poiché le eccezioni sono meno convenienti in C ++ rispetto a Python, probabilmente avrà un metodo diverso per rilevare la fine. Ho optato per la seguente interfaccia per i miei propri bisogni 2 :

    template <typename T> concept Generator {
        bool valid();
        void next();
        T get();
    };
    

    dove appare l'iterazione:

    while(g.valid()) {
        auto item = g.get();
        do_anything_with(item);
        g.next();
    }
    

    il generatore inizia concettualmente sul primo elemento della sequenza, ma è possibile accedervi solo dopo aver chiamato valid . Ho trovato che questo permette di distribuire il duro lavoro tra costruttore, valid e next come è adatto per ogni caso e può essere facilmente incapsulato in iteratore in modo simile a come istream_iterator è fatto. Sono possibili altre varianti dell'interfaccia incluso il seguente istream (ma ha lo svantaggio di restituire l'elemento predefinito quando l'iterazione fallisce).

Fondamentalmente probabilmente dovresti combinare gli approcci. Se si utilizza il concetto successivo, è possibile adattare qualsiasi implementazione di questo tipo al concetto di intervallo (abbastanza complesso) da Boost.Range es utilizzando "mixin" e Modello di template curiosamente ricorrente . Qualcosa come:

template <typename GeneratorT, typename ValueT>
class GeneratorIterator :
    boost::iterator_facade<GeneratorT, ValueT, boost::single_pass_traversal_tag> {
    GeneratorT *g;
    GeneratorIterator() : g() {}
    GeneratorIterator(GeneratorT *g) g(g) {}
    ValueT &dereference() {
        if(!g || !g.valid())
            throw std::runtime_error("...");
        return g->get();
    }
    bool equal(GeneratorIterator const &l) {
        return g == l.g || ((!g || !g.valid()) && (!l.g || !l.g.valid()));
    }
    void increment() {
        if(g)
            g.next();
    }
}

template <typename GeneratorT, typename ValueT>
class GeneratorFacade {
  public:
    typedef GeneratorIterator<GeneratorT, ValueT> iterator;
    typedef GeneratorIterator<GeneratorT, ValueT> const_iterator;
    const_iterator begin() const {
        return const_iterator(this);
    }
    const_iterator end() const {
        return const_iterator();
    }
}

Il vantaggio dell'adozione indiretta è che gli intervalli ora non devono essere copiabili affatto o non a buon mercato mentre l'iteratore è solo un puntatore e, pertanto, può essere facilmente copiato a seconda delle esigenze. E la definizione dei generatori è semplice e facile da capire mentre finiscono sempre per conformarsi alla pelosa interfaccia standard del C ++.

(Disclaimer: l'ho scritto sopra la testa, non testato)

1 Boost.Range include la concatenazione di intervalli. Non reinventare la ruota e riutilizzare o almeno ispirare te stesso.

2 I Iterators Must Go parlano collegati nella risposta di Ylisar arriva con la stessa interfaccia , solo nomi diversi. Nota che molte lingue combinano il next / popFront e il valid / empty con un next che restituisce un valore booleano, ma quell'approccio è molto più difficile da racchiudere in iteratori e concettualmente un po 'più complesso, perché allora gli iteratori iniziano in uno stato speciale "non inizializzato".

    
risposta data 24.09.2013 - 15:43
fonte
1

Quindi, dopo alcuni consigli di @jozefg e della ricerca, ho appreso che altri linguaggi (ovviamente non c ++) hanno iteratori con un concetto dei propri fini, incluso python. Quindi ho deciso che è ok avere gli iteratori che si fermano da soli e lo sto tenendo nel mio codice.

    
risposta data 24.09.2013 - 05:24
fonte
0

In realtà, gli Iterator sono considerati più o meno una mancanza di progettazione che è ancora in gran parte dovuta al legacy e alla lentezza nell'adozione degli intervalli, che è un concetto molto più potente (che è il tuo caso più o meno). Dai un'occhiata a link e amplia la libreria di intervalli .

    
risposta data 24.09.2013 - 15:08
fonte

Leggi altre domande sui tag