El uso de impulso :: iterador

Question

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

Me gustaría ofrecer dos tipos de iteradores:

El primer conjunto, los iteradores regulares, puede señalar cualquier elemento, ya sea conjunto o desarmado. Si se leen de, vuelven ya sea el valor ajustado o value_type(), si se escriben, crean el elemento y devuelven la referencia lvalue. Por lo tanto, ellos son:

Acceso Aleatorio Transversal Iterator y legible y grabable Iterator

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

Acceso Aleatorio Transversal Iterator y legible y grabable y lValue Iterator

también necesito versiones const tanto, que no son de escritura.

Me puede llenar los espacios en blanco, pero no está seguro de cómo utilizar impulso :: iterator_adaptor para empezar.

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 este 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 en lugar iterator_facade

explicación más detallada: iterator_adaptors se utiliza cuando tiene un iterador existente (digamos std::list<int>::iterator) y desea volver a utilizar su comportamiento para su iterador, por ejemplo. el iterador devolverá el doble del valor de lo que está en la lista, pero la reutilización de código de recorrido desde el iterador originales. O a la inversa: es posible que desee un iterador que se saltará algunos de los elementos de la lista original, pero devolver los valores sin cambios. No estoy seguro de si desea basar su iterador (como en la reutilización de código de) al iteradores de sus estructuras subyacentes, pero hablando para mí, yo no especialmente en el caso de iterador como nonsparse Es probable que desee para crear un poco proxy para la referencia que significa que no puede utilizar cualquier código subyacente iterador dereference(), y el recorrido es probablemente fácil. Puede, sin embargo, la base de su sparse_iterator en algunas iterador que itera sobre realidad elementos de la matriz existente si lo desea.

Hay problemas con el enfoque proxy, así que no esperes que funcione sin problemas sin tener que pasar a través de muchos aros. Por un lado, la versión de la const nonsparse iterador todavía debe devolver value_type(), lo que significa expresiones como iter->foo() deberían traducirse en value_type().foo() si la entrada correspondiente no existe. Pero esto plantea una dificultad, que pointer_proxy::operator->() debe devolver algo con operator->, preferiblemente un puntero (definitivamente no value_type()). Lo que lleva a la pregunta crucial: Un puntero a qué? Hay posibilidades de resolver este (para uno, si tiene sus objetos gestionados por boost::shared_pointer, sólo puede devolver un shared_pointer a una instancia new'd).

En el iterador nonsparse, es necesario implementar:

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

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

• 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 de la plantilla fachada iterador deben ser:

• Reference: la reference_proxy
• Pointer: la pointer_proxy

La versión escasa es más simple: Si el subyacente iterador es sensible (. Es decir, coincide con el comportamiento que desea) y se aplica adecuadamente, puede simplemente omitir los parámetros a la iterator_adaptor (a excepción de los dos primeros), y tomar toda la implementación .

El "no se compila" problema:. typename inserción