iterador - list iterator c++

iteradores polimórficos en C++

Question

Estoy tratando de implementar un iterador polimórfico en C ++. Básicamente, necesito esto para poder aplicar un filtro, de modo que el iterador omita algunos elementos dependiendo de la condición asociada. Así que hice un iterador GoF-like con una interfaz abstracta, esto me permite derivar un iterador filtrado a partir de él e implementar la lógica requerida. También prefiero los iteradores basados ​​en la interfaz en lugar de los de plantilla, ya que permiten ocultar la implementación sin provocar un lío de plantillas tipográficas.

Sin embargo, los iteradores polimórficos no pueden devolverse por valor (a diferencia de los iteradores STL), así que tengo que pasar los punteros, y esto puede volverse peligroso como en este caso, lo que parece lógico pero lleva a una pérdida de memoria:

Iter* Collection::GetIter() {...} // new IterImpl
DoSomething(Iter*) {...} // doesn''t do delete

DoSomething(Collection.GetIter()); // convenient, but wrong :/

La solución obvia es usar algún tipo de punteros inteligentes para controlar la vida útil de los iteradores, pero la gente suele decir que las interfaces deben ser lo más simples y generales posible, por lo que probablemente se deben evitar los punteros inteligentes.

Si ha trabajado con iteradores polimórficos en C ++, ¿cómo se resolvió este problema? ¿O son los iteradores basados ​​en plantillas la única forma "buena" de iteración en C ++? Gracias.

Answer 1

El enfoque habitual es utilizar el polimorfismo en tiempo de compilación en lugar del polimorfismo en tiempo de ejecución; Esto permite al compilador muchas más oportunidades de optimizar el código utilizando el iterador y, en general, es más idiomático en C ++ moderno.

Si necesita un comportamiento polimórfico en tiempo de ejecución, probablemente sea más fácil encapsular el polimorfismo dentro del propio iterador y no exponerlo externamente. Puede lograr esto utilizando una función polimérica de tipo envoltura, que se encuentra en Boost, C ++ TR1 y C ++ 0x. He proporcionado un ejemplo aquí basado en un filtro iterador de uno de mis proyectos de hobby:

template <typename ForwardIt>
class filter_iterator
    : public std::iterator<
          std::forward_iterator_tag, 
          typename std::iterator_traits<ForwardIt>::value_type>

{
public:

    typedef typename std::iterator_traits<ForwardIt>::value_type ValueType;
    typedef typename std::function<bool(ValueType)> FunctionType;

    filter_iterator() { }

    explicit filter_iterator(ForwardIt end)
        : it_(end), end_(end) 
    {
    }

    filter_iterator(ForwardIt it, ForwardIt end, FunctionType is_filtered) 
        : it_(it), end_(end), is_filtered_(is_filtered)
    { 
        skip_filtered_elements(); 
    }

    const ValueType& operator*()  const { return it_.operator*();  }
    const ValueType* operator->() const { return it_.operator->(); }

    filter_iterator& operator++()   
    { 
        ++it_; skip_filtered_elements(); return *this; 
    }

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


    friend bool operator==(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return lhs.it_ == rhs.it_;
    }

    friend bool operator!=(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return !(lhs == rhs);
    }

private:

    void skip_filtered_elements()
    {
        while (it_ != end_ && is_filtered_(*it_))
            std::advance(it_, 1);
    }

    ForwardIt it_;
    ForwardIt end_;

    std::function<bool(const ValueType&)> is_filtered_;
};

template <typename ForwardIt>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt end)
{
    return filter_iterator<ForwardIt>(end);
}

template <typename ForwardIt, typename Function>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt it, 
                                                ForwardIt end, 
                                                Function f)
{
    return filter_iterator<ForwardIt>(it, end, f);
}

El uso es sencillo. Este ejemplo (usando una expresión lambda de C ++ 0x como tipo de función) demuestra el filtrado de números impares de un rango:

int main()
{
    std::array<int, 4> x = { 1, 2, 3, 4 };

    std::copy(make_filter_iterator(x.begin(), x.end(), [](int i) { return i % 2; }),
              make_filter_iterator(x.end()),
              std::ostream_iterator<int>(std::cout, " "));
}

Answer 2

Estado allí. Hecho eso.

Lo que puede hacer es ocultar la interfaz de su iterador detrás de otro iterador. Supongamos que tiene varios tipos de iteradores que se ocultan detrás de la interfaz del IIterator.

Luego escriba otra clase similar a Iterador, por ejemplo, MyIterator, que contiene un puntero a IIterator, y que simplemente reenvía todas las llamadas a IIterator, de esta forma:

template <typename T>
class MyIterator
    {
    public:
       MyIterator() : m_iterator(nullptr) {}
       MyIterator(IIterator *it) : m_iterator(it) {}
       MyIterator &operator++()
          {
          if (m_iterator) m_iterator->operator++();
          return *this;
          }
       T &operator*() const
          {
          if (m_iterator) return m_iterator->operator*();
          else            throw an exception?
          }
    private
       IIterator *m_iterator;
    };

Este ejemplo está lejos de ser completo, pero debería tener la idea.

Answer 3

Hay dos problemas aquí:

• sintaxis: la STL supone que los iteradores proporcionan rasgos ( value_type , reference por ejemplo) que deben coincidir con el elemento real.
• Semántica: los iteradores serán copiables.

Recuerde que (en C ++) un iterador no es un rango y, por lo tanto, la operación ++ se ensucia rápidamente, ya que necesita omitir algunos elementos, pero (con una implementación tradicional) no puede saber cuántos elementos están a su disposición. ..

Por lo tanto, si quiere iteradores polimórficos que sigan la interfaz de GOF, deberá renunciar al uso de algoritmos STL.

Dicho esto, es perfectamente factible implementar iteradores polimórficos:

struct IterBase
{
  virtual void increment() = 0;
  virtual void decrement() = 0;

  // others
};

class Iter
{
public:
  Iter& operator++() { base->increment(); return *this; }
  Iter operator++(int) { Iter tmp(*this); base->increment(); return tmp; }

  // others

private:
  std::unique_ptr<IterBase> base;
};

Y luego tendrás que escribir todos los constructores de copia, operadores de asignación y destructores para hacer lo correcto ...

Sin embargo, sin el polimorfismo de la plantilla, solo vale la pena si su iterador solo debe utilizarse en el mismo tipo ...

Answer 4

La gente dice que las interfaces deben ser lo más simples y generales posible. En su caso, describe un puntero en bruto como algo que no es "posible". Por lo tanto, sugeriría que su solución obvia de usar un puntero inteligente es la técnica más simple y general posible.

Para mantener este puntero inteligente tan simple y general como sea posible, me gustaría ir con uno de los punteros inteligentes proporcionados por stl, ya que son los más omnipresentes.

Answer 5

Se puede hacer usando un iterador que contiene un puntero de alguna forma, y ​​luego pasa la funcionalidad al puntero.

Sin embargo, debes tener mucho cuidado al hacer esto, y lo he visto hacerlo mal muchas veces (incluso me decanté por una vez, luego me pregunto por qué fallaron las pruebas ...)

• ¡No uses shared_ptr!

Afortunadamente, no he visto a nadie de arriba cometer el error de utilizar shared_ptr, pero tiene la semántica equivocada, ya que cuando copia un iterador tiene 2 copias separadas. Pero si contienen un shared_ptr y avanzas uno de los iteradores, el otro se moverá con él - comportamiento inesperado ...

Por lo tanto, debe clonar cada vez que copie, pero afortunadamente con C ++ 0x puede mover la mayor parte del tiempo en lugar de clonar.

También debe saber que las operaciones llegarán a la tabla v para cada iteración, lo que puede hacer que se ejecute más lentamente que si hubiera hecho polimórficos los métodos "macro" (e implementarlo tal vez con una plantilla, por lo que no es necesario volver a escribir el código). ).

Answer 6

Una buena solución que vi vinculada a la pregunta de Oli Charlesworth que no obtuvo mucho crédito (al menos, no tanto como pensé que debería).

class Iterator
{
public:
    SmartPointer<IteratorImplementation> ItrPtr;

    //Delegate methods to ItrPtr
}

Luego puede pasar el iterador por valor y diferir los métodos al puntero inteligente contenido; Es básicamente un iterador que implementa el patrón de ''Estrategia'', y la estrategia exhibe el comportamiento polimórfico.