Iterador personalizado en C++

Question

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

Necesito crear un iterador para atravesar los elementos en todas las colecciones de mi clase TContainer, abstrayendo el 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.

I.E, Si esto es mi contenedor:

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

¿Cuál sería una buena 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 ahora), heredé de std :: iterator y especifiqué el tipo como el primer parámetro de plantilla. Espero que ayude.

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

Esta clase fue tomada originalmente de la clase istream_iterator (y modificada 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); 
} 

Comprobar esta documentación en las etiquetas de iterador:
http://www.sgi.com/tech/stl/iterator_tags.html

Habiendo acaba de volver a leer la información de iteradores:
http://www.sgi.com/tech/stl/iterator_traits.html

Esta es la vieja manera de hacer las cosas (iterator_tags) del un enfoque más moderno es configurar iterator_traits <> para que su iterador lo haga totalmente compatible con el STL.

Answer 2

Un iterador es solo una clase que admite una determinada interfaz. Como mínimo, tendrá que ser capaz de:

• incremento y/o disminuirlo
• eliminar la referencia para obtener el objeto se "puntos" a
• prueba para la igualdad y la desigualdad
• copia y asígnelo

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

• un begin() función que devuelve una instancia de su nuevo tipo de iterador de posición en el primer elemento
• una función end() que devuelve un iterador que es (posiblemente en teoría) colocada en uno más allá del final de los artículos en su contenedor

Answer 3

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

Answer 4

Compruebe el Views Template Library.

especialmente revisa

1. Union View presentar dos contenedores concatenada.
2. Concatenation View presentando una colección de contenedores concatenados.

Answer 5

primer lugar 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 exteriores contienen punteros a los rangos internos, lo cual era un requisito en tu pregunta. Esto se refleja en el miembro 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.

He dejado los siguientes miembros de la caldera de placa como "ejercicios para el lector:"!

• incremento de sufijo iterador
• operador =
• constructor por defecto
• del 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 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 imprime:

Answer 6

Este es el código más simple que era capaz de producir (por iteradores personalizados). Tenga en cuenta que solo estoy comenzando a explorar esta área. Esto 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 es así como la salida será similar a:

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