2011-07-19 12 views
14

consideremos el siguiente ejemplo simplificado y salida deseada:Escribir un iterador que hace que varios contenedores se ven como uno

class A 
{ 
    class combined_iterator 
    { 
     ???? 
    } 
    typedef ??? t_combined_it; 

    t_combined_it begin(); 
    t_combined_it end(); 

    std::vector<int> m_Vec1, m_Vect2; 
} 

A a; 
a.m_Vec1.push_back(1); 
a.m_Vec2.push_back(2); 
for (A::t_combined_it it = a.begin() ; it != a.end() ; it++) { 
    std::cout << *it << " "; 
} 

Salida:

1 2 

Creo que la pregunta se desprende de esto: ¿cómo hacer yo escribe un iterador que hace que parezca que dos o más iteradores son en realidad una sola secuencia. De modo que, en el ejemplo, en lugar de la iteración sobre m_Vec1 y m_Vec2, puedo usar un iterador que repite primero los elementos de m_Vec1 y luego m_Vec2, de forma transparente.

Encontré la siguiente pregunta que creo que pregunta lo mismo: Make a c++ iterator that traverses 2 containers. No hubo buenas respuestas a esta pregunta; la solución presentada por el asker original parece intrincada, y es (relativamente) intensiva en memoria.

Intenté un enfoque ingenuo manteniendo un std :: vector :: iterator como miembro de mi iterador personalizado, y comparándolo con los iteradores .end() de cada una de las secuencias que se están iterando; sin embargo, parece que es ilegal comparar iteradores de diferentes contenedores (donde hubiera preferido que simplemente regresaran "no iguales", tal vez esa sea una dirección para encontrar la solución a este problema). No puedo pensar cómo para implementarlo, sin embargo).

Siempre que sea posible, me gustaría utilizar boost :: iterators como los uso en otro lugar y me gusta la homogeneidad que proporciona a las implementaciones de mi iterador; pero, por supuesto, si alguien tiene una idea sin usarla, puedo trabajarla en mí mismo, por lo que no se requiere en ese sentido.

Respuesta

16

boost::join es lo que estás buscando. También puede estudiar la implementación, especialmente cómo derivar el mínimo común denominador para los tipos de cruce de contenedores, referencia y valor de retorno. Para citar:

La intención de la función de unión es unir dos rangos en un rango más largo.

El rango resultante tendrá el recorrido común mínimo de los dos rangos suministrados como parámetros.

Tenga en cuenta que el rango unido implica un costo de rendimiento debido a la necesidad de verificar si se ha alcanzado el final de un rango> internamente durante el recorrido.

+0

Gracias, exactamente lo que estaba buscando. Nunca se me ocurrió que esto sería en boost :: range, aunque en retrospectiva tiene sentido. – Roel

7

Creo que su enfoque de "ingenua" debería funcionar, con la siguiente modificación: en lugar de comparar el iterador a la end() de cada contenedor, mantener un puntero a la actual contenedor y comparar el iterador sólo el contenedor actual de end() . Cuando se haya alcanzado el final, avance al siguiente contenedor. De esta forma, nunca compararás el iterador con otro contenedor distinto al que apunta. Esto también se generalizará fácilmente a una colección de colecciones de tamaño arbitrario.

+0

Y en operator == y tal prueba primero el contenedor actual de cada iterador. –

+1

Cuando probé esto, en lugar de mantener referencias a los contenedores, guardé el iterador de inicio y final de los dos rangos. La única ventaja es que es un poco más flexible (es decir, podría enlazar subsecuencias desde cada contenedor) –

+0

@Martin: lo que David quiso decir es mantener los iteradores de inicio/final en el iterador de combinación, lo que no afectaría el uso del iterador - tal vez estoy malinterpretando su comentario. – Roel

2

zip_iterator funciona si desea iterar dos iteradores en paralelo. Si necesita iterar sobre contenedores en secuencia, probablemente pueda implementar uno usando iterator_adaptor.

+0

zip_iterator solo funciona al pasar por ambos en paralelo, que no es lo que quiero hacer. Supongo que hay una manera de hacerlo con iterator_adaptor, mi pregunta era * how * :) – Roel

0

Aasmund tiene razón. Su enfoque, aunque simple debería funcionar. Pero hay mucho espacio para optimizar.

Colección Objetos son a menudo grandes, y como tal tómense un tiempo para ser repetidos. Especialmente listas y matrices.

Debe considerar el multihilo para que cada colección se pueda repetir en paralelo.

Adicionalmente. Usted debe tomar el consejo del post relacionados con el consumo y el uso de

Boost.MultiIndex

3

ya he implementado algo similar para una pregunta diferente. La implementación es here. La idea básica es a la que se acercó: almacenar los dos rangos de iteradores, cuando se le pide que realice una operación, compruebe si ha completado la iteración en el primer rango y use cualquiera de los rangos.

Esto no es hilo de seguridad por cualquier medio, y nunca he utilizado esa implementación en código real, lo que puede haber problemas y errores y ...

+0

Gracias, creo que esto funcionaría, parece lo que llamé mi solución "ingenua" pero con el cambio que propuso Aasmund. boost :: range :: join utiliza un enfoque ligeramente diferente con una bandera, no estoy muy seguro de por qué. – Roel

1

Las respuestas a otras personas dieron sólo funcionan para la unión de dos rangos, pero no un número arbitrario de gama.

PStade Oven has a concatenated adaptor para unir cualquiera cantidad de rangos; también tiene un adaptador jointed para unir 2 rangos, específicamente.

Por supuesto, puede convertir los rangos en iteradores con begin() y end() si es necesario; solo asegúrate de que los rangos perduren más que los iteradores.

Cuestiones relacionadas