Fusionar dos vectores STL con un patrón de alternancia

Question

Tengo dos vectores STL A y B y necesito fusionarlos en un tercero, donde los elementos deben ordenarse de forma tal que cada enésimo elemento en el vector de salida debe ser vector B. Mi código actual es como la siguiente:

std::vector<int> a(10, 4); 
std::vector<int> b(10, 8); 
std::vector<int> c; 
static const std::size_t STEP(3); 

std::vector<int>::const_iterator bIt = b.begin(); 
for(std::vector<int>::const_iterator aIt = a.begin(); 
    aIt != a.end(); ++aIt) 
{ 
    c.push_back(*aIt); 
    if((c.size() + 1) % STEP == 0) 
    { 
     c.push_back(*bIt); 
     ++bIt; //assume b is large enough 
    } 
} 

El vector c ahora queda como: 4 4 8 4 4 8 ...

esto funciona bien, pero tengo curiosidad si hay no es una solución más elegante. ¿Hay alguna manera de usar un algoritmo STL en lugar de mis loops escritos a mano?

Answer 1

Esto es demasiado especializado para ser cubierto directamente por <algorithm>. Evitar el bucle requerirá un iterador personalizado.

template< typename I1, typename I2 > 
struct interleave_iterator 
    : std::iterator< forward_iterator_tag, typename I1::value_type > { 
    using typename I1::value_type; 

    I1 i1; 
    I2 i2; 
    size_t cnt, stride; 

    interleave_iterator(I1 in1, I2 in2, size_t in_stride=0, size_t in_off=0) 
     : i1(in1), i2(in2), cnt(in_off), stride(in_stride) {} 

    value_type &operator*() const { return cnt? * i1 : * i2; } 
    interleave_iterator &operator++() { 
     if (++ cnt == stride) { 
      cnt = 0; 
      ++ i2; 
     } else ++ i1; 
     return *this; 
    } 
    value_type *operator->() const 
     { return cnt? i1.operator->() : i2.operator->(); } 

    interleave_iterator &operator++(int) 
     { interleave_iterator r = *this; ++ *this; return r; } 

    friend bool operator== 
     (interleave_iterator const &lhs, interleave_iterator const &rhs) 
     { return lhs.i1 == rhs.i1 && lhs.i2 == rhs.i2; } 
    friend bool operator!= 
     (interleave_iterator const &lhs, interleave_iterator const &rhs) 
     { return ! (lhs == rhs); } 
}; 

Un poco excesivo, creo.

Answer 2

Debo admitir que me gusta bastante la solución de Potatoswatter ... bastante.

Como demostró, esto no es un problema de algoritmo, sino de iteración. Sin embargo, su solución no encaja del todo porque la prueba para el end de la iteración es muy difícil: requiere mucho cuidado en la preparación de los contenedores y la creación de los iteradores para evitar un comportamiento indefinido.

Creo que el problema podría expresarse mucho mejor utilizando un concepto que es bastante similar a iterators: views.

Una vista es una interfaz de adaptador en uno o varios contenedores. En realidad, no contiene nada en sí (esa es la parte importante). Sin embargo, expone una interfaz similar a la de un contenedor para que pueda codificar con los modismos habituales.

Lo bueno de las vistas es que a menudo las puedes componer.

Por ejemplo, una visión muy simple:

/// Only allow to see a range of the container: 
/// std::vector<int> v(40, 3); // { 3, 3, 3, ... } 
/// auto rv = make_range_view(v, 4, 5); 
/// rv exposes the elements in the range [4,9) 
/// in debug mode, asserts that the range is sufficiently large 
template <typename Container> 
class range_view 
{ 
}; 

Por su pregunta, usted prefiere crear una interleave_view:

/// Allow to interleave elements of 2 containers each at its own pace 
/// std::vector<int> v(40, 3); 
/// std::set<int> s = /**/; 
/// 
/// auto iv = make_interleave_view(v, 3, s, 1); 
/// Takes 3 elements from v, then 1 from s, then 3 from v, etc... 
template <typename C1, typename C2> 
class interleave_view 
{ 
}; 

Aquí el problema del iterador final es de alguna manera aliviado porque sabemos ambos contenedores y así podemos crear los iteradores nosotros mismos, asegurando que pasemos los parámetros apropiados.

Por supuesto, puede ser un poco más tedioso si los contenedores no ofrecen un miembro de "tamaño" eficiente (list no, es O (n)).

Sin embargo, el principio general es que una vista le da más control (y permite más comprobaciones), y es más seguro de usar porque controla precisamente la creación de los iteradores.

Tenga en cuenta que en C++ 0x el interleave_view normalmente acomodaría un número ilimitado de secuencias.