impulso :: iterador

Question

me escribió una clase de vectores escasa (ver #1, #2.)

me gustaría ofrecer dos tipos de iteradores:

el primer set, los iteradores regulares, puede apuntar cualquier elemento, ya sea establecido o no. Si se leen desde, devuelven el valor establecido o value_type(), si se escriben en ellos, crean el elemento y devuelven la referencia lvalue. Por lo tanto, ellos son:

de acceso aleatorio Transversal iterador y legible y grabable iterador

El segundo juego, los iteradores dispersos, iterar sobre sólo los elementos de ajuste. Dado que no es necesario para crear perezosamente elementos que se escriben, son:

de acceso aleatorio Transversal iterador y legible y grabable y lValue iterador

También necesito versiones const de ambos, que no son modificables.

Puedo completar los espacios en blanco, pero no estoy seguro de cómo usar boost :: iterator_adaptor para comenzar.

Esto es lo que tengo hasta ahora:

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 
      > { 
    }; 
}; 

también, ¿es esto ilegal?

typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator; 

Answer 1

No estoy seguro de que usted realmente desea utilizar iterator_adaptor en su caso - es posible que desee utilizar iterator_facade lugar.

Explicación más detallada: iterator_adaptors se usan cuando tiene un iterador existente (digamos std::list<int>::iterator) y desea reutilizar su comportamiento para su iterador, por ejemplo. su iterador devolverá el doble del valor de lo que está en la lista, pero reutilizará el código transversal del iterador original. O al revés: es posible que desee un iterador que omita algunos de los elementos en la lista original, pero devuelva los valores sin cambios. No estoy seguro de si desea basar su iterador (como en el código de reutilización de) sobre los iteradores de sus estructuras subyacentes, pero hablando en mi caso, no lo haría especialmente en el caso de un iterador no disperso, ya que probablemente quiera crear algunos proxy para la referencia, lo que significa que no puede usar ningún código de iterador subyacente dereference(), y el recorrido es probablemente fácil. Sin embargo, puede basar su sparse_iterator en algún iterador que itere sobre los elementos realmente existentes de la matriz si lo desea.

Existen problemas con el enfoque de proxy, por lo que no espere que funcionen sin problemas sin pasar por muchos aros. Por un lado, la versión const del iterador nonsparse debería devolver value_type(), lo que significa que expresiones como iter->foo() deberían traducirse a value_type().foo() si la entrada correspondiente no existe. Pero esto plantea una dificultad, que pointer_proxy::operator->() debería devolver algo con operator->, preferiblemente un puntero (definitivamente no es value_type()). Lo que lleva a la pregunta crucial: ¿un puntero a qué?Hay posibilidades de resolver esto (por ejemplo, si tiene sus objetos administrados por boost::shared_pointer, puede simplemente devolver un shared_pointer a una instancia new 'd).

Para el iterador nonsparse, es necesario poner en práctica:

• class reference_proxy con
• reference_proxy::operator& (que probablemente volverá un proxy puntero)
• reference_proxy::operator value_type&() para const utiliza
• reference_proxy::operator const value_type&() para no constante utiliza

• reference_proxy::foo() para cualquier foo() miembro función de valu e_type (de lo contrario expresiones como (*it).foo() yo sepa no funcionarán)

• class pointer_proxy con

• pointer_proxy::operator* (devolver un reference_proxy)
• pointer_proxy::operator-> (hacer algo con sentido, véase más arriba)

Los parámetros a la plantilla de fachada del iterador debe ser:

• Reference: la reference_proxy
• Pointer: la pointer_proxy

La versión escaso es más simple: si el iterador subyacente es sensible (es decir. coincide con el comportamiento que desea) y correctamente implementado, puede omitir los parámetros en el iterator_adaptor (excepto los dos primeros) y tomar toda la implementación.

Problema "no compila": inserte typename.