Unisci due vettori STL con un modello di alternanza

Question

Ho due vettori STL A e B e ho bisogno di unirli in un terzo, dove gli elementi devono essere ordinati in un modo, che ogni ennesimo elemento nel vettore di output deve essere vettore B. Il mio codice corrente simile a questa:

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 
    } 
} 

Il vettore c ora assomiglia: 4 4 8 4 4 8 ...

questo funziona bene, ma io sono curioso di sapere se ci non è una soluzione più elegante. C'è qualche modo di utilizzare un algoritmo STL invece dei miei loop scritti a mano?

Answer 1

Questo è troppo specializzato per essere coperto direttamente da <algorithm>. Evitare il ciclo richiederà un iteratore personalizzato.

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 po 'eccessivo, penso.

Answer 2

Devo ammettere che mi piace molto la soluzione Potatoswatter ... abbastanza.

Come ha dimostrato, questo non è un problema di algoritmo, ma di iterazione. Tuttavia la sua soluzione non si adatta perfettamente alla fattura perché il test per l'end dell'iterazione è molto difficile: richiede molta cura nella preparazione dei contenitori e nella creazione degli iteratori per evitare comportamenti indefiniti.

Penso che il problema potrebbe essere espresso molto meglio utilizzando un concetto che è abbastanza simile agli iteratori: viste.

Una vista è un'interfaccia dell'adattatore su uno o più contenitori. In realtà non contiene nulla (questa è la parte importante). Tuttavia espone un'interfaccia simile a quella di un contenitore in modo da poter codificare con i soliti idiomi.

Le cose belle dei panorami, è che puoi comporle spesso.

Per esempio, uno molto semplice vista:

/// 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 
{ 
}; 

Per la vostra domanda, si preferisce creare un 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 
{ 
}; 

Qui la questione del iteratore finale è in qualche modo alleviato perché sappiamo entrambi i contenitori e quindi siamo in grado di creare noi stessi gli iteratori, assicurandoci di passare i parametri corretti.

Naturalmente può diventare un po 'più noioso se i contenitori non offrono un membro efficiente "dimensione" (list no, è O (n)).

Il principio generale, tuttavia, è che una vista offre maggiore controllo (e consente un numero maggiore di controlli) ed è più sicuro da utilizzare perché si controlla con precisione la creazione degli iteratori.

Si noti che in C++ 0x lo interleave_view generalmente corrisponde a un numero illimitato di sequenze.