programacion - Un adaptador de iterador C++ que envuelve y oculta un iterador interno y convierte el tipo iterado

que es un iterador c++

Question

Después de haber jugado con esto, sospecho que no es remotamente posible, pero pensé que podría preguntar a los expertos. Tengo el siguiente código C ++:

class IInterface { virtual void SomeMethod() = 0; }; class Object { IInterface* GetInterface() { ... } }; class Container { private: struct Item { Object* pObject; [... other members ...] }; std::list<Item> m_items; };

Quiero agregar estos métodos a Container:

MagicIterator<IInterface*> Begin(); MagicIterator<IInterface*> End();

Para que las personas que llaman puedan escribir:

Container c = [...] for (MagicIterator<IInterface*> i = c.Begin(); i != c.End(); i++) { IInterface* pItf = *i; [...] }

Así que, esencialmente, quiero proporcionar una clase que parece iterar sobre una colección (que no se permite ver a la persona que llama de Begin () y End ()) de los punteros de IInterface, pero que en realidad está iterando sobre una colección de punteros a otra objetos (privados a la clase Container) que se pueden convertir en punteros IInterface.

Algunos puntos clave:

• MagicIterator debe definirse fuera de Container .
• Container::Item debe permanecer privado.

• MagicIterator tiene que iterar sobre los punteros de IInterface , a pesar del hecho de que Container contiene una std::list<Container::Item> . Container::Item contiene un Object* y Object se puede usar para buscar IInterface* .

• MagicIterator tiene que ser reutilizable con varias clases que se parecen a Container, pero internamente puede tener diferentes implementaciones de listas que contienen diferentes objetos ( std::vector<SomeOtherItem> , mylist<YetAnotherItem> ) y con IInterface* obtenidos de manera diferente cada vez.

• MagicIterator no debe contener código específico del contenedor, aunque puede delegar en clases que sí lo hagan, siempre que dicha delegación no esté codificada de forma MagicIterator en contenedores particulares dentro de MagicIterator (por lo que el compilador lo resuelve de alguna manera, por ejemplo).

• La solución debe compilarse en Visual C ++ sin el uso de otras bibliotecas (como boost) que requerirían un acuerdo de licencia de sus autores.

• Además, la iteración no puede asignar ninguna memoria del montón (por lo que no new() o malloc() en cualquier etapa), y no memcpy() .

Gracias por su tiempo, incluso si solo está leyendo; ¡Este me ha estado molestando!

Actualización: Si bien he tenido algunas respuestas muy interesantes, ninguna ha cumplido con todos los requisitos anteriores. En particular, las áreas difíciles son i) desacoplar MagicIterator de Contenedor de alguna manera (los argumentos de plantilla predeterminados no lo cortan), y ii) evitar la asignación de pila; pero realmente estoy buscando una solución que cubra todas las balas anteriores.

Answer 1

Crear una clase abstracta IteratorImplementation :

template<typename T>
class IteratorImplementation
{
    public:
        virtual ~IteratorImplementation() = 0;

        virtual T &operator*() = 0;
        virtual const T &operator*() const = 0;

        virtual Iterator<T> &operator++() = 0;
        virtual Iterator<T> &operator--() = 0;
};

Y una clase Iterator para envolverlo:

template<typename T>
class Iterator
{
    public:
        Iterator(IteratorImplementation<T> * = 0);
        ~Iterator();

        T &operator*();
        const T &operator*() const;

        Iterator<T> &operator++();
        Iterator<T> &operator--();

    private:
        IteratorImplementation<T> *i;
}

Iterator::Iterator(IteratorImplementation<T> *impl) :
    i(impl)
{
}

Iterator::~Iterator()
{
    delete i;
}

T &Iterator::operator*()
{
    if(!impl)
    {
        // Throw exception if you please.
        return;
    }

    return (*impl)();
}

// etc.

(Puede hacer que IteratorImplementation una clase "dentro" de Iterator para mantener las cosas ordenadas).

En su clase Container , devuelva una instancia de Iterator con una subclase personalizada de IteratorImplementation en el ctor :

class ObjectContainer
{
    public:
        void insert(Object *o);
        // ...

        Iterator<Object *> begin();
        Iterator<Object *> end();

    private:
        class CustomIteratorImplementation :
            public IteratorImplementation<Object *>
        {
            public:
                // Re-implement stuff here.
        }
};

Iterator<Object *> ObjectContainer::begin()
{
    CustomIteratorImplementation *impl = new CustomIteratorImplementation();  // Wish we had C++0x''s "var" here.  ;P

    return Iterator<Object *>(impl);
}

Answer 2

No suena demasiado complicado. Puede definir el iterador afuera. También puedes usar typedefs. Algo como esto cabría, creo. Tenga en cuenta que sería mucho más claro si MagicIterator no fuera una plantilla gratuita, sino un miembro de Item, typedefed en Container. Como está ahora, hay una referencia cíclica, lo que hace que sea necesario escribir un código de solución feo.

namespace detail {
    template<typename T, typename U>
    struct constify;

    template<typename T, typename U>
    struct constify<T*, U*> {
        typedef T * type;
    };

    template<typename T, typename U>
    struct constify<T*, U const*> {
        typedef T const * type;
    };
}

template<typename DstType, 
         typename Container,
         typename InputIterator>
struct MagicIterator;

class Container
{
private:
    struct Item
    {
        Object* pObject;
    };

    std::list<Item> m_items;

public:

    // required by every Container for the iterator
    typedef std::list<Item> iterator;
    typedef std::list<Item> const_iterator;

    // convenience declarations
    typedef MagicIterator< IInterface*, Container, iterator > 
        item_iterator;
    typedef MagicIterator< IInterface*, Container, const_iterator > 
        const_item_iterator;

    item_iterator Begin();
    item_iterator End();
};

template<typename DstType, 
         typename Container = Container,
         typename InputIterator = typename Container::iterator>
struct MagicIterator : 
    // pick either const T or T, depending on whether it''s a const_iterator.
    std::iterator<std::input_iterator_tag, 
                  typename detail::constify<
                           DstType, 
                           typename InputIterator::value_type*>::type> {
    typedef std::iterator<std::input_iterator_tag, 
                 typename detail::constify<
                          DstType, 
                          typename InputIterator::value_type*>::type> base;
    MagicIterator():wrapped() { }
    explicit MagicIterator(InputIterator const& it):wrapped(it) { }
    MagicIterator(MagicIterator const& that):wrapped(that.wrapped) { }

    typename base::value_type operator*() {
        return (*wrapped).pObject->GetInterface();
    }

    MagicIterator& operator++() {
        ++wrapped;
        return *this;
    }

    MagicIterator operator++(int) {
        MagicIterator it(*this);
        wrapped++;
        return it;
    }

    bool operator==(MagicIterator const& it) const {
        return it.wrapped == wrapped;
    }

    bool operator!=(MagicIterator const& it) const {
        return !(*this == it);
    }

    InputIterator wrapped;
};

// now that the iterator adepter is defined, we can define Begin and End
inline Container::item_iterator Container::Begin() {
    return item_iterator(m_items.begin());
}

inline Container::item_iterator Container::End() {
    return item_iterator(m_items.end());
}

Ahora, comienza a usarlo:

for(MagicIterator<IInterface*> it = c.Begin(); it != c.End(); ++it) {
    // ...
}

También puede usar un iterador de mezcla proporcionado por boost, que funciona como la versión de entrada de boost :: function_output_iterator. Llama al operator() su iterador operator() que luego devuelve el valor apropiado, haciendo lo que hacemos arriba en nuestro operator* en principio. Lo encuentras en random/detail/iterator_mixin.hpp . Eso probablemente resultaría en menos código. Pero también requiere que levantemos el cuello para garantizar el material de amistad porque el Artículo es privado y el iterador no está definido dentro del Artículo. En fin, buena suerte :)

Answer 3

No veo ninguna razón por la que no puedas implementar esto exactamente como lo has establecido ... ¿Me estoy perdiendo algo?

Para aclarar, tendrás que poner algún tipo de método de acceso en tu clase de contenedor. Pueden ser privados y puedes declarar a MagicIterator como amigo, si crees que es la mejor manera de encapsularlo, pero los expondré directamente. Estos métodos de acceso usarían un iterador STL normal dentro de Container y realizarían la conversión a IInterface. Por lo tanto, la iteración se realizaría en realidad con los métodos de acceso del contenedor y MagicIterator simplemente sería un tipo de objeto proxy para hacerlo más fácil. Para hacerlo reentrante, podría hacer que MagicIterator pase algún tipo de ID para buscar el iterador STL dentro de Container, o podría hacer que pase en el iterador STL como un void * .

Answer 4

Creo que tienes dos problemas separados aquí:

Primero, crea un iterador que devolverá la IInterface* de tu list<Container::Item> . Esto se hace fácilmente con boost::iterator_adaptor :

class cont_iter
  : public boost::iterator_adaptor<
        cont_iter                       // Derived
      , std::list<Container::Item>::iterator // Base
      , IInterface*                     // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
      , IInterface*                     // Reference :)
    >
{
 public:
    cont_iter()
      : cont_iter::iterator_adaptor_() {}

    explicit cont_iter(const cont_iter::iterator_adaptor_::base_type& p)
      : cont_iter::iterator_adaptor_(p) {}

 private:
    friend class boost::iterator_core_access;
    IInterface* dereference() { return this->base()->pObject->GetInterface(); }
};

Debería crear este tipo como interno en Container y regresar desde sus métodos begin() y end() .

Segundo, quieres el MagicIterator polimórfico en tiempo de ejecución. Esto es exactamente lo que hace any_iterator . el MagicIterator<IInterface*> es simplemente any_iterator<IInterface*, boost::forward_traversal_tag, IInterface*> , y cont_iter se le puede asignar.

Answer 5

Ahora he encontrado una solución que está más en forma para mi propósito original. Todavía no me gusta, sin embargo :)

La solución implica que MagicIterator se modela en IInterface * y se construye con un vacío * a un iterador, el tamaño de byte de dicho iterador y una tabla de punteros a funciones que realizan funciones de iteración estándar en dicho vacío * como incremento, decremento, desreferencia, etc. MagicIterator asume que es seguro memcpy el iterador dado en un búfer interno, e implementa sus propios miembros pasando su propio búfer como un vacío * a las funciones proporcionadas como si fuera el iterador original.

A continuación, Container debe implementar funciones de iteración estáticas que devuelven un vacío * proporcionado a un std :: list :: iterator. Container :: begin () y Container :: end () simplemente construyen un std :: list :: iterator, pasan un puntero a él en un MagicIterator junto con una tabla de sus funciones de iteración, y devuelven el MagicIterator.

Es algo repugnante, y rompe mi regla original con respecto a "no memcpy ()", y hace suposiciones sobre las partes internas de los iteradores en cuestión. Pero evita la asignación de montones, mantiene las partes internas de Colección (incluido el Ítem) en privado, hace que MagicIterator sea completamente independiente de la colección en cuestión y de IInterface *, y en teoría permite a MagicIterators trabajar con cualquier colección (siempre que sus iteradores puedan ser memcopy () re).

Answer 6

Un visitante puede ser una solución más simple (y por lo tanto más fácil de mantener).

Answer 7

Realmente depende del Container , porque los valores de retorno de c.Begin() y c.End() están definidos por la implementación.

Si MagicIterator conoce una lista de posibles Container , se podría utilizar una clase contenedora.

template<typename T>
class MagicIterator
{
    public:
        MagicIterator(std::vector<T>::const_iterator i)
        {
            vector_const_iterator = i;
        }

        // Reimplement similarly for more types.
        MagicIterator(std::vector<T>::iterator i);
        MagicIterator(std::list<T>::const_iterator i);
        MagicIterator(std::list<T>::iterator i);

        // Reimplement operators here...

    private:
        std::vector<T>::const_iterator vector_const_iterator;
        std::vector<T>::iterator       vector_iterator;
        std::list<T>::const_iterator   list_const_iterator;
        std::list<T>::iterator         list_iterator;
};

La manera más fácil sería usar una plantilla que acepte el tipo de Container :

// C++0x
template<typename T>
class Iterator :
    public T::iterator
{
    using T::iterator::iterator;
};

for(Iterator<Container> i = c.begin(); i != c.end(); ++i)
{
    // ...
}

Más información aquí.