É uma prática ruim fazer um iterador ciente de seu próprio fim

5

Para alguns antecedentes do motivo por que estou fazendo esta pergunta, aqui está um exemplo. Em python, o método chain une um número arbitrário de intervalos e os transforma em um sem fazer cópias. Aqui está um link caso você não o entenda. Eu decidi que iria implementar cadeia em c ++ usando modelos variadic. Tanto quanto eu posso dizer a única maneira de fazer um iterador de cadeia que irá com sucesso para o próximo contêiner é para cada iterador para saber sobre o fim do contêiner (eu pensei em uma espécie de hack em que quando != é chamado contra o final que ele sabe para ir para o próximo recipiente, mas o primeiro caminho parecia mais fácil e mais seguro e mais versátil).

Minha pergunta é se há algo inerentemente errado com um iterador sabendo sobre seu próprio fim, meu código está em c ++, mas isso pode ser agnóstico de idioma, já que muitos idiomas possuem iteradores.

#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
    
por aaronman 24.09.2013 / 03:53
fonte

3 respostas

5

Estive lá, me queimei. Criar coisas que pareçam com iterador, mas que tenham requisitos diferentes ou extras, levará a uma bagunça. Basicamente, muitos intervalos não são copiáveis ou, pelo menos, não são baratos, mas é o que normalmente se espera de um iterador (é uma exigência do conceito do iterador).

Você deve não ter iteradores que saibam do seu próprio fim. Mas o encadeamento funciona com intervalos . Existem duas maneiras de definir intervalos:

  • Como "contêineres" de encaminhamento, que você pode fazer de simples pares de iteradores. Esta é uma maneira de C ++ (e Boost.Range 1 tem alguns utilitários úteis para estes), mas às vezes é um pouco de trabalho extra fazer com que vários objetos que fornecem seqüências se encaixem na interface.

  • Defina sua interface para "geradores". Ele provavelmente será semelhante ao do python, mas como as exceções são menos convenientes em C ++ do que em python, ele provavelmente terá um método diferente para detectar o fim. Eu me adaptei à seguinte interface para minhas próprias necessidades 2 :

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

    onde a iteração se parece:

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

    o gerador começa conceitualmente no primeiro item da sequência, mas só pode ser acessado após valid ser chamado. Eu achei que isso permite distribuir o trabalho duro entre o construtor, valid e next como é adequado para cada caso e pode ser facilmente empacotado no iterador da mesma forma como istream_iterator é feito. Outras variações da interface são possíveis, incluindo seguir o istream one (mas tem desvantagem de retornar o elemento padrão quando a iteração falha).

Basicamente, você provavelmente deve combinar as abordagens. Se você usar o conceito mais recente, poderá adaptar qualquer implementação desse tipo ao conceito de (bastante complexo) Range de Boost.Range por exemplo usando "mixin" e Padrão de Template Curiosamente Recorrente . Algo como:

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

A vantagem da indireção é que as faixas agora não precisam ser copiáveis ou não são baratas, enquanto o iterador é apenas um ponteiro e, portanto, é de baixo custo, conforme necessário. E definir geradores é simples e fácil de entender, enquanto eles ainda estão em conformidade com a interface padrão C ++.

(Disclaimer: eu escrevi em cima da minha cabeça, não testado)

1 Boost.Range inclui intervalos de concatenação. Não reinvente a roda e reutilize ou pelo menos inspire-se.

2 A conversa de Iteradores devem ir linkada na resposta do Ylisar vem com a mesma interface apenas nomes diferentes. Observe que muitas linguagens combinam o next / popFront e valid / empty para um next que retorna um booleano, mas essa abordagem é muito mais difícil de envolver em iteradores e conceitualmente um pouco mais complexa, porque os iteradores começam em um estado "não inicializado" especial.

    
por 24.09.2013 / 15:43
fonte
1

Então, depois de alguns conselhos de @jozefg e pesquisa, aprendi que outras linguagens (obviamente, não c ++) têm iteradores com um conceito próprio, incluindo python. Então eu decidi que não há problema em ter os iteradores de auto-interrupção e estou mantendo-os no meu código.

    
por 24.09.2013 / 05:24
fonte
0

Os iteradores são, na verdade, considerados mais ou menos uma falha de projeto que ainda ocorre principalmente por causa da adoção lenta e legada de intervalos, que é um conceito muito mais poderoso (que é o seu caso mais ou menos). Dê uma olhada no link e no aumentar biblioteca de intervalos .

    
por 24.09.2013 / 15:08
fonte