programacion - libreria para listas c++

Iterador personalizado en C++

Question

Tengo un TContainer de clase que es un agregado de varios indicadores de colecciones stl para la clase TItems.

Necesito crear un iterador para atravesar los elementos en todas las colecciones de mi clase TContainer, abstrayendo al cliente del funcionamiento interno.

¿Cuál sería una buena manera de hacer esto? ¿Debería crear una clase que extienda un iterador (si es así, qué clase de iterador debería extender), debería crear una clase de iterador que sea un agregado de iteradores?

Solo necesito un repetidor FORWARD_ONLY.

IE, si este es mi contenedor:

typedef std::vector <TItem*> ItemVector;
class TContainer {
   std::vector <ItemVector *> m_Items;
};

Lo que sería un buen iterador para recorrer todos los elementos contenidos en los vectores de la variable miembro m_Items.

Answer 1

Cuando hice mi propio iterador (hace un tiempo) heredé de std :: iterator y especifiqué el tipo como el primer parámetro de plantilla. Espero que ayude.

Para los iteradores directos, el usuario forward_iterator_tag en lugar de input_iterator_tag en el siguiente código.

Esta clase se tomó originalmente de la clase istream_iterator (y se modificó para mi propio uso, por lo que puede que ya no se parezca al istram_iterator).

template<typename T>
class <PLOP>_iterator
         :public std::iterator<std::input_iterator_tag,       // type of iterator
                               T,ptrdiff_t,const T*,const T&> // Info about iterator
{
    public:
        const T& operator*() const;
        const T* operator->() const;
        <PLOP>__iterator& operator++();
        <PLOP>__iterator operator++(int);
        bool equal(<PLOP>__iterator const& rhs) const;
};

template<typename T>
inline bool operator==(<PLOP>__iterator<T> const& lhs,<PLOP>__iterator<T> const& rhs)
{
    return lhs.equal(rhs);
}

Verifique esta documentación en las etiquetas de los iteradores:
http://www.sgi.com/tech/stl/iterator_tags.html

Después de volver a leer la información en los iteradores:
http://www.sgi.com/tech/stl/iterator_traits.html

Esta es la forma antigua de hacer las cosas (iterator_tags), el enfoque más moderno es configurar iterator_traits <> para su iterador para que sea totalmente compatible con el STL.

Answer 2

Este es el código más simple que pude producir (para iteradores personalizados). Tenga en cuenta que solo estoy comenzando a explorar esta área. Llama a la función incorporada upper_bound para realizar una búsqueda binaria en una función entera, x^2 como ejemplo.

#include <algorithm>
#include <iostream>

using namespace std;

class Iter
{
  public:
  int x;
  Iter() { x = -1; }
  Iter(int a) { x = a; }

  bool operator!=(Iter &i2) const { return x != i2.x; }
  void operator++() { x++; }
  void operator+=(int b) { x += b; }
  int operator-(const Iter &i2) const { return x - i2.x; }
  int operator*() const {
    cout << "calculating for x " << x << endl;
    return x*x;
  }

  typedef random_access_iterator_tag iterator_category;
  typedef int value_type;
  typedef int difference_type;
  typedef int* pointer;
  typedef int& reference;
};

main ()
{
  ios::sync_with_stdio(false);
  cout << upper_bound(Iter(0), Iter(100), 40).x << endl;
}

// :collapseFolds=1:folding=explicit:

Y así es como se ve la salida:

calculating for x 50
calculating for x 25
calculating for x 12
calculating for x 6
calculating for x 9
calculating for x 8
calculating for x 7
7

Answer 3

Primero vamos a generalizar un poco:

typedef int value_type;
typedef std::vector<value_type*> inner_range;
typedef std::vector<inner_range*> outer_range;

Ahora el iterador:

struct my_iterator : std::iterator_traits<inner_range::iterator> 
{
    typedef std::forward_iterator_tag iterator_category;

    my_iterator(outer_range::iterator const & outer_iterator, 
                outer_range::iterator const & outer_end)
    : outer_iterator(outer_iterator), outer_end(outer_end)
    { 
        update();
    }

    my_iterator & operator++()
    {
        ++inner_iterator;
        if(inner_iterator == inner_end)
        {
            ++outer_iterator;
            update();
        }
        return *this;
    }

    reference operator*() const
    {   
        return *inner_iterator;
    }

    bool operator==(my_iterator const & rhs) const
    {   
        bool lhs_end = outer_iterator == outer_end;
        bool rhs_end = rhs.outer_iterator == rhs.outer_end;
        if(lhs_end && rhs_end)
            return true;
        if(lhs_end != rhs_end)
            return false;
        return outer_iterator == rhs.outer_iterator 
            && inner_iterator == rhs.inner_iterator;
    }

private:

    outer_range::iterator outer_iterator, outer_end;
    inner_range::iterator inner_iterator, inner_end;

    void update()
    {
        while(outer_iterator != outer_end)
        {
            inner_iterator = (*outer_iterator)->begin();
            inner_end = (*outer_iterator)->end();
            if(inner_iterator == inner_end)
                ++outer_iterator;
            else
                break;
        }
    }    
};

Esta clase asume que los iteradores externos contienen punteros a los rangos internos, que era un requisito en su pregunta. Esto se refleja en el miembro de update , en las flechas antes de begin() y end() . Puede reemplazar estas flechas con puntos si desea usar esta clase en la situación más común donde el iterador externo contiene los rangos internos por valor. Note por cierto que esta clase es independiente del hecho de que el rango interno contiene punteros, solo los clientes de la clase necesitarán saberlo.

El código podría ser más corto si usamos boost::iterator_facade pero no es necesario agregar una dependencia de impulso para algo tan simple. Además, las únicas partes difíciles son las operaciones de igualdad e incremento, y tenemos que codificarlas de todos modos.

Deje los siguientes miembros de la placa de la caldera como "ejercicios para el lector":

• iterador de incremento postfix
• operador! =
• Constructor predeterminado
• operador->

Otro ejercicio interesante es convertir esto en una plantilla que funciona con contenedores arbitrarios. El código es básicamente el mismo excepto que tienes que agregar anotaciones de tipo de typename en algunos lugares.

Ejemplo de uso:

int main()
{
    outer_type outer;
    int a = 0, b = 1, c = 2;
    inner_type inner1, inner2;
    inner1.push_back(&a);
    inner1.push_back(&b);
    inner2.push_back(&c);
    outer.push_back(&inner1);
    outer.push_back(&inner2);

    my_iterator it(outer.begin(), outer.end());
                e(outer.end(), outer.end());
    for(; it != e; ++it)
        std::cout << **it << "/n";
}

Que impresiones:

0 1 2

Answer 4

Si tiene acceso a Boost, usar iterator_facade es la solución más robusta, y es bastante fácil de usar.

Answer 5

Un iterador es solo una clase que admite una cierta interfaz. Como mínimo, querrás poder:

• incrementarlo y / o disminuirlo
• desreferenciarlo para obtener el objeto al que "apunta"
• probarlo por la igualdad y la desigualdad
• copiar y asignarlo

Una vez que tenga una clase que pueda hacer eso con sensatez para su colección, tendrá que modificar la colección para tener funciones que devuelvan iteradores. Como mínimo querrás

• una función de inicio () que devuelve una instancia de su nuevo tipo de iterador ubicado en el primer elemento
• una función end () que devuelve un iterador que (posiblemente teóricamente) está posicionado al final de los artículos en su contenedor

Answer 6

Verifique la Biblioteca de plantillas de vistas .

Especialmente cheque

1. Union View presenta dos contenedores concatenados.
2. Vista de concatenación que presenta una colección de contenedores concatenados.