Usando o boost::iterador

Question

Eu escrevi um esparso classe vector (ver #1, #2.)

Eu gostaria de fornecer dois tipos de iteradores:

O primeiro conjunto, o regular os iteradores, pode apontar qualquer elemento, seja definido ou indefinido.Se eles são lidos a partir, eles retornam o valor definido ou value_type(), se eles são escritos, eles criam o elemento e devolver o lvalue de referência.Assim, são eles:

Acesso Aleatório Transversal Iterador e Legível e Gravável Iterador

O segundo conjunto, esparsos iteradores, itere apenas o conjunto de elementos.Desde que eles não precisam preguiçosamente criar elementos que são escritos, eles são:

Acesso Aleatório Transversal Iterador e Legível e Gravável e Lvalue Iterador

Eu também preciso de const versões de ambos, que não são graváveis.

Que eu possa preencher os espaços em branco, mas não tem a certeza de como usar o boost::iterator_adaptor para começar.

Aqui está o que eu tenho até agora:

template<typename T>
class sparse_vector {
public:
    typedef size_t size_type;
    typedef T value_type;

private:
    typedef T& true_reference;
    typedef const T* const_pointer;
    typedef sparse_vector<T> self_type;
    struct ElementType {
        ElementType(size_type i, T const& t): index(i), value(t) {}
        ElementType(size_type i, T&& t): index(i), value(t) {}
        ElementType(size_type i): index(i) {}
        ElementType(ElementType const&) = default;
        size_type index;
        value_type value;
    };
    typedef vector<ElementType> array_type;

public:
    typedef T* pointer;
    typedef T& reference;
    typedef const T& const_reference;

private:
    size_type                                   size_;
    mutable typename array_type::size_type      sorted_filled_; 
    mutable array_type                          data_;

// lots of code for various algorithms...

public:    
    class sparse_iterator
        : public boost::iterator_adaptor<
          sparse_iterator                   // Derived
          , typename array_type::iterator            // Base (the internal array)
          , value_type              // Value
          , boost::random_access_traversal_tag    // CategoryOrTraversal
          > {...}

    class iterator_proxy {
          ???
    };

    class iterator
        : public boost::iterator_facade<
          iterator                          // Derived
          , ?????                           // Base
          , ?????              // Value
          , boost::??????    // CategoryOrTraversal
          > {
    };
};

também, isso é ilegal?

typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;

Answer 1

Eu não tenho certeza do que você realmente quer usar iterator_adaptor no seu caso, você pode querer usar iterator_facade em vez disso.

Explicação mais completa: iterator_adaptors são utilizados quando tem um iterador (vamos dizer que std::list<int>::iterator) e deseja reutilizar o seu comportamento para a sua iterador, por exemplo.o iterador irá devolver o dobro do valor do que está na lista, mas reutilizar transversal código do original iterador.Ou outra maneira:você pode querer um iterador que vai ignorar alguns dos elementos da lista original, mas o retorno a valores inalterados.Eu não tenho certeza se você deseja basear o seu iterador (como na reutilização de código) sobre os iteradores de suas estruturas subjacentes, mas, falando por mim, eu não iria, especialmente no caso de não esparsa iterador como você provavelmente quer criar algum proxy para a referência, o que significa que você não pode usar qualquer subjacentes iterador dereference() código, e a passagem é, provavelmente, fácil.Você pode, no entanto, a base da sua sparse_iterator em alguns iterador que itera sobre realmente existente elementos da matriz, se você desejar.

Há problemas com o proxy abordagem, portanto, não espere que ele funcione perfeitamente, sem passar por muitos aros.Para uma coisa, a const versão não esparsa iterador ainda deve retornar value_type(), o que significa que expressões como iter->foo() deve traduzir a value_type().foo() se a entrada correspondente não existe.Mas isso representa uma dificuldade, que pointer_proxy::operator->() deve retornar algo com operator->, de preferência um ponteiro (definitivamente não value_type()).O que leva à questão crucial:Um ponteiro para o que?Há possibilidades de resolver isso (para um, se tiver os objetos gerenciados pelo boost::shared_pointer, você pode simplesmente retornar uma shared_pointer para um new'd instância).

Para o não esparsa iterador, você precisa implementar:

• class reference_proxy com
• reference_proxy::operator& (que provavelmente vai retornar um ponteiro de proxy)
• reference_proxy::operator value_type&() para const usa
• reference_proxy::operator const value_type&() para não-const usa

• reference_proxy::foo() para qualquer foo() a função de membro do value_type (caso contrário, expressões como (*it).foo() AFAIK não funciona)

• class pointer_proxy com

• pointer_proxy::operator* (retornar um reference_proxy)
• pointer_proxy::operator-> (fazer algo sensato, veja acima)

Os parâmetros para o iterador fachada modelo deve ser:

• Reference:o reference_proxy
• Pointer:o pointer_proxy

O esparsos versão é mais simples:Tratando-se de um iterador é sensível (ie.coincide com o comportamento que você quer), e implementado corretamente, você pode simplesmente omitir os parâmetros para a iterator_adaptor (excepto para os dois primeiros), e tomar tudo de implementação.

O "não compile" problema:inserir typename.